Рассматривайте разделители как входные токены

Я хотел бы знать, как это сделать как на С++, так и на Java (EDIT: я не имею в виду одновременно. Я задаю два похожих вопроса: «Как мне это сделать на С++?» и «Как мне это сделать на Яве?").

Я хочу проанализировать ввод из файла и обработать '(' и ')' как разделители в дополнение к пробелам. Но я также хочу, чтобы каждая встреча '(' или ')' распознавалась как отдельный токен. Так, например, при разборе

Это contians (вложенные (круглые скобки))

Я хотел бы, чтобы последовательные вызовы next() (или >>) давали (по одному в строке)

This
contains
(
nested
(
parentheses
)
)
<end of input>

Существуют ли встроенные парсеры/сканеры с такой функциональностью? Я знаю, что Java Scanner является мощным, но, насколько я могу судить, нет никакого способа определить, какой разделитель совпадал каждый раз, когда вы сталкиваетесь со следующим токеном.


c++ java parsing delimiter parentheses
person dspyz    schedule 13.08.2013    source источник
comment
Было бы более уместно разделить это на два вопроса? Один для C++ и один для Java?   -  person dspyz    schedule 13.08.2013
comment
Вы можете прочитать о компиляторах-компиляторах. Например, ANTLR может создавать код синтаксического анализатора как для Java, так и для C (что, конечно, может использоваться в С++).   -  person Some programmer dude    schedule 13.08.2013
comment
Извините, я не имел в виду одновременно. Я пытаюсь объединить два похожих вопроса в один: как это сделать на С++? и как мне это сделать в Java? Я уточню это   -  person dspyz    schedule 13.08.2013
comment
Если бы это был python, правильным инструментом был бы shlex. Он делает именно это   -  person dspyz    schedule 02.02.2014

Ответы (2)


arrow_upward
1
arrow_downward

Помимо обсуждения компилятор-компилятор, такой синтаксический анализатор может быть наивно реализован с использованием двух индексов, что-то вроде как это:

for(int i = 0; i < str.size(); ) {
  int j = i;
  for(; j < str.size(); ++j) {
    // check for spaces
    if(str[j] == ' ') {
      // capture substring index i to j-1 as a token
      i = j+1;
      break;
    }

    // check for brackets
    if(str[j] == '(' || str[j] == ')') {
      // str[j] is a token
      i = j+1;
      break;
    }

  }

  // no more characters to check
  if(j >= str.size()) break;
}

По сути, i — это маркер, указывающий начало токена, а j используется для поиска того, где заканчивается токен.

Отказ от ответственности: приведенный выше код не тестировался, может содержать синтаксическую ошибку и ошибку, особенно с пустым вводом, пробелами и т. д., и, вероятно, будет плохо работать с большими данными. Прежде чем изобретать велосипед, рассмотрите возможность использования сторонней библиотеки.

Или для решения с минимальным количеством кода вы можете просто заменить каждое вхождение "(" на " ( " (аналогично с ")") и выполнить токенизацию пробелов:

str.replaceAll("(", " ( ").split("\s+");
person gerrytan    schedule 13.08.2013
comment
Да, мой вопрос касался существования такого устройства в STL, но я бы с радостью принял стороннюю библиотеку, которая делает то же самое. Я не могу найти ни для C++, ни для Java, что странно, потому что мне кажется, что это довольно типичный вариант использования. - person dspyz; 13.08.2013
comment
Параметр replaceAll не работает, если я извлекаю данные из потока, а не из строки. Я хочу что-то, что можно сделать за один проход (конечно, я мог бы вытащить слова по отдельности, а затем вернуть разделитель и все, что следует за ним, или же поддерживать очередь токенов для чтения, которые уже были разделены, но оба эти варианты все еще кажутся большими неприятными хаками для решения того, что должно быть очень простой проблемой) - person dspyz; 13.08.2013
comment
Ваш код не может захватить токен строки, за которым сразу же следует открытая/закрытая скобка (без пробела). Он переходит прямо к скобке. Итак, для моего примера ваш код вернет This, содержит, (, вложенные, (, ), ) и пропускает круглые скобки слова. Не могли бы вы исправить это, чтобы справиться с этим случаем? Мне кажется, вам понадобится какой-то метод возврата или вам нужно отслеживать текущий размер или что-то в этом роде. - person dspyz; 13.08.2013
comment
@dspyz Я быстро написал код, чтобы дать вам основную идею, а не окончательное решение. Поэтому, как «мотивированный» программист, я считаю, что вы должны быть в состоянии исправить это самостоятельно. - person gerrytan; 14.08.2013
comment
Я понимаю это, но исправление иллюстрирует основную проблему вашего кода, заключающуюся в том, что он предполагает, что я перечисляю результаты, а не создаю итератор. В C++ нет ключевого слова yield, так что на самом деле это не решение моей проблемы. - person dspyz; 14.08.2013

arrow_upward
0
arrow_downward

Это должно быть легко обработано регулярным выражением. Что-то вроде `"\\s*(?:(\\w+)|([()]))" должно помочь в C++11 (для более ранних версий C++ вам понадобится обычный Boost выражения). В Java также есть поддержка регулярных выражений, поэтому вы сможете сделать то же самое.

В обоих случаях приведенное выше выражение пропускает пробелы, а затем «захватывает» символ в группе 1 или скобки в группе 2.

person James Kanze    schedule 13.08.2013
comment
Что делать с регулярным выражением? Есть ли в С++ какой-то сканер, который соответствует экземплярам? - person dspyz; 13.08.2013
comment
@dspyz Регулярные выражения являются частью как Java, так и современного C++. Если у вас есть современный компилятор с C++11, вы можете просто использовать std::regex и std::regex_search; в противном случае вам понадобятся регулярные выражения Boost (и замените std:: на boost::). В Java это java.util.regex. - person James Kanze; 13.08.2013
comment
Я искал std::regex и std::regex_search. Это решение страдает от той же проблемы, что и другое. Он работает со строками, а не с потоками. Я ищу итератор, построенный поверх потока или метода потока. Смысл в том, чтобы читать эти токены из файла или стандартного ввода один за другим, а не создавать список элементов из существующей строки. - person dspyz; 13.08.2013
comment
@dspyz std::regex не требует строки. Однако для этого требуется двунаправленный итератор, исключающий потоки. На практике это будет иметь место практически для любого токенизатора, потому что он должен иметь возможность копировать токен от начала до конца, как только он найдет конец. Мой собственный класс RE будет работать с итераторами ввода, но он не выполняет захват, и он не очень полезен с итератором ввода, если вы не спроектируете специальный итератор, который сохраняет копию того, что он видел. В глобальном масштабе обычно предпочтительнее считывать фрагменты ввода в строку. - person James Kanze; 14.08.2013