Синтаксический анализатор if-else конструкции на основе контекстно свободной грамматики в БНФ?

Question

[Денис Яковенко]

Приветствую!

Мне нужно построить синтаксический анализатор, который бы создавал дерево разбора выражения следующего вида:

if ( arr[i, j+5, j*j+1] >= 5 + a )
      a = a * b + 1;
else a = 2 * b;

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

Для начала, нужно построить грамматику в форме Бэкуса-Наура (БНФ). Ниже то, что у меня получилось:

Id        = {Letter}{AlphaNumeric}*
Integer   = {Digit}+
          
<Condition> ::= <Condition IF> <Condition ELSE>             

<IF> ::= 'if'

<ELSE> ::= 'else'

<Condition IF>   ::= <IF> '(' <Boolean Exp> ')' <Expression> '=' <Expression> ';'

<Condition ELSE> ::= <ELSE> <Expression> '=' <Expression> ';'


<Expression>   ::= <Expression> '+' <Mult Exp> 
                 | <Expression> '-' <Mult Exp> 
                 | <Mult Exp>
                 
<Array Expression> ::= <Expression>
                    | <Array Expression> ',' <Expression>

<Mult Exp>    ::= <Mult Exp> '*' <Negate Exp> 
                | <Mult Exp> '/' <Negate Exp> 
                | <Negate Exp> 

<Negate Exp>  ::= '-' <Value> 
                | <Value> 

<Value>       ::= ID 
                | Integer
                | '(' <Expression> ')'
                
<BoolOperator> ::= '>'|'<'|'>='|'<='|'=='

<Boolean Exp> ::= <Expression> | ID'['<Array Expression>']' <BoolOperator> <Expression> | ID'['<Array Expression>']'

Собственно, вопросы:
1) Правильно ли построена БНФ? Если нет, прошу помочь с построением.
2) Как грамотнее перенести такое задание грамматики в C#?
3) Как вообще строить дерево разбора? (есть регулярное выражение, которое разбирает все строки нужного вида на массив лексем).

PS: Сторонние парсеры/лексеры использовать нельзя

Answer 1

[so-olitary]

1) Да, ты правильно построил БНФ - там нет ничего сверхъестественного.
Только вот это Expression := Expression;, в общем говоря, всё-таки неверно, т.к. нельзя присвоить: a + b = 5.
И на мой вкус:

Expression := Expression | ID=Expression
Block := Expression; | Expression; Block
ArrayExpression := { Block }
BoolExp, как и в С, можно отдельно не выделять, 0 - false, !0 - true

2) Можно использовать готовый синтаксический анализатор, который разбивает на токены сам по сгенерированным тобой правилам (yacc, bison), можно писать вручную.
3) Как вручную:

Я писал в своё время интерпретатор языка программирования.
БНФ - есть алгоритм - собственно как ты будешь парсить файл. Можешь смотреть на свою структуру, она описывает всевозможные варианты того, что ты можешь увидеть в файле с программой. Читаешь по файлу и проверяешь, что ты оказался прав.

Сначала регулярными выражениями выдели "токены", что у тебя есть "слово языка":

1. (\d)+ - Integer
2. \w (\w | \d )* - identificator
3. + | - | * | / | % | := | < | > | <= | >= | != | == | ( | )  | ... - arithmetic sign
4. ; | [ | ] | { | } | ... - separators

Приступай к разбору:
Введи понятие функционального оператора, а также понятие ID, которое включает в себя имя переменной или обращание к массиву, как единый "токен" с числовым значением (или Expression) внутри [...].
Рассматривай файл, как подряд идущие инструкции языка.
Сначала ты должен понять в какой из них ты находишься - это (1) объявление переменной, (2) арифметическое выражение, (3) условный оператор. Как это понять? Просто читай подряд по словам. например:
1. если это if - то за ним
(а) идёт ( Expression ) - это какое-то арифметическое выражение:
Первое, что с ним нужно делать - это избавиться от скобок и пересобрать в последовательность операций для выполнения, имея в виду приоритеты операций. Проще всего это сделать переведя в польскую аннотацию, делается это при помощи стека - можешь в википедии посмотреть алгоритм. Смысл: (a + b) * c + d = +*+abcd.

Хотя тебе не надо выполнять программу, я всё-таки рекомендую переводить в польскую нотацию - так ты сможешь проверить корректность арифм.выражения и понять, где оно завершилось.
Либо можно придумать какие-то правила чтобы это понять, непример: не может быть 2 знака подряд (кроме унарного оператора), ... но так ИМХО сложнее.

(b) затем за ним идёт Expression | ArrayExpressions, их тоже парсишь.
(в) может быть Else или следующая инструкция
И так далее.

Comments

[Денис Яковенко]

Хорошее объяснение, спасибо!