Парсинг грамматики в РБНФ?

Question

[cheetahfm]

Не могу никак понять, каким образом можно считать грамматику в расширенной форме Бэкуса-Наура. Гугл вроде ничего не выдаёт. У меня имеется грамматика "C-light":

<program>: <type>   ’main’   ‘(‘   ‘)’   ‘{‘   <statement>   ‘}’
<type>: ‘int’
 | ‘bool’
 | ‘void’
<statement>: 
  | <declaration> ‘;’
  | ‘{‘ <statement> ‘}’
  | <for>   <statement>
  | <if>      <statement>
  | <return>
<declaration>: <type>   <identifier>   <assign>
<identifier>: <character><id_end>
<character>: ‘a’ | ‘b’ | ‘c’ | ‘d’ | ‘e’ | ‘f’ | ‘g’ | ‘h’ | ‘i' | ‘j’ | ‘k’ | ‘l’ | ‘m’ | ‘n’ | ‘o’ | ‘p’ | ‘q’ | ‘r’ | ‘s’ | ‘t’ | ‘u’ | ‘v’ | ‘w’ | ‘x’ | ‘y’ | ‘z’ | ‘A’ | ‘B’ | ‘C’ | ‘D’ | ‘E’ | ‘F’ | ‘G’ | ‘H’ | ‘I’ | ‘J’ | ‘K’ | ‘L’ | ‘M’ | ‘N’ | ‘O’ | ‘P’ | ‘Q’ | ‘R’ | ‘S’ | ‘T’ | ‘U’ | ‘V’ | ‘W’ | ‘X’ | ‘Y’ | ‘Z’ | ‘_’
<id_end>:
| <character><id_end>
<assign>:
  | ‘=’ <assign_end>
<assign_end>: <identifier>
  | <number>
<number>: <digit><number_end>
<digit>: ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ |  ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
<number_end>:
  | <digit><number_end>
<for>: ‘for’ ‘(‘ <declaration> ‘;’ <bool_expression> ‘;’ ‘)’
<bool_expression>: <identifier>   <relop>    <identifier>
  | <number>      <relop>    <identifier>
<relop>:  ‘<’ | ‘>’ | ‘==’ | ‘!=’
<if>: ‘if’ ‘(‘ <bool_expression> ‘)’
<return>: ‘return’ <number> ‘;’

Делаю это всё на С++, но с грехом пополам попытаюсь понять и на других языках. Лучше, конечно, в виде алгоритма. Можно ссылки на книги.
Мне нужно как-нибудь её считать и дальше использовать (всё задание - это синтаксический анализатор с восстановлением в режиме паники, но дальше ещё будет интерпретатор, так что пригодится и потом).
Да, генераторы и парсеры использовать нельзя. Так что ANTLR и прочие не предлагать. :)
Всем заранее спасибо!)
UPDATE: судя по всему, это даже не расширенная, а обычная форма. В любом случае, по предложенному примеру.

Comments

[Rsa97]

Так Вам надо просто по этой грамматике построить анализатор или написать универсальный анализатор, считывающий любую грамматику?

[cheetahfm]

Rsa97: вполне вероятно, "hardcoded" вариант не оценят. Также возможно изменение грамматики. Поэтому желательно такой, чтоб смог считать вот такую из файла и любые схожие (но не сильно сложнее).

Answer 1

[tsarevfs]

Мне кажется, что так или иначе, для построения парсера придется сконвертировать РБНФ в БНФ. Плюсом БНФ является то, что нет необходимости писать сложный парсер, чтобы считывать саму грамматику.
Поэтому для начала реализуйте генератор парсера по БНФ грамматике.
В приведенной вами статье есть РБНФ описание РБНФ грамматики. Вы можете вручную преобразовать его в БНФ и построить парсер для нее.
Преобразование из РБНФ в БНФ будет заключатся в последовательной замене конструкций из РБНФ на несколько эквивалентных из БНФ. Я не уверен, что в результате получится сразу получить "хорошую" грамматику (в зависимости от выбранного алгоритма на грамматику могут накладываться различные ограничения, например отсутствие левой рекурсии, эпсилон-правил и.т.д). В таком случае придется нормализовывать полученную грамматику.
Читайте dragon book, какой-то материал можно найти на вики.
RE: UPD А грамматика из примера очень похожа на LL(1) грамматику. Если нет необходимости работать с РБНФ, считывание тривиальное. Правила с '|' стоит разбить на части с одинаковой левой частью. Identifier и Number я бы вообще для простоты сделал терминалами, и предоставил лексеру разбираться с ними. Про то как разбирать LL(1) грамматики, например, рекурсивным спуском материал найти очень легко.
UPD2
И да, еще придется подумать о том как задавать действия, которые вы хотите сделать (непосредственно компиляция С кода). Я реализовывал это на python, и все равно было много возни с этим.
parser_gen.py и lexer_gen.py генерируют парсер_.py и лексер_.py по их описаниям в файлах *.txt
main используя сгенерированные файлы запускает парсинг целевого текста.

Comments

[tsarevfs]

И да, я согласен с Rsa97 для начала стоит понять как писать парсер для конкретной грамматики, и только потом, при необходимости, писать генератор парсеров.

[cheetahfm]

Компиляции не будет. :) Объём курса небольшой.

[tsarevfs]

cheetahfm: Ну в любом случае вы должны получить какой-то результат. Ну то же синтаксическое дерево построить. Или посчитать что-то. Ну а имея дерево получить код на ASM или, каком-нибудь pascal достаточно просто.

Answer 2

[Rsa97]

Универсальный анализатор написать на несколько порядков сложнее, чем реализовать конкретную грамматику. Выделить лексическую часть и написать лексический анализатор несложно, а вот синтаксический анализатор произвольной грамматики... Практически Вы хотите написать свой yacc, причём ещё и с автоматическим определением синхронизирующей лексемы для восстановления.
Ну и, как написал уже tsarevfs, если предварительно вручную привести грамматику к LL(1) или хотя бы LALR(1), то реализовать её разбор гораздо проще. Например правило для <number> переписанное в виде
<number>: <digit> | <number><digit>
обрабатывается намного проще.

Comments

[tsarevfs]

Не соглашусь что правило записанное таким образом обрабатывать проще. Оно содержит левую рекурсию, и рекурсивный парсер не сможет ее обработать.

[Rsa97]

Зато восходящий распознаватель легко обработает, у него свои достоинства.