Грамматика LL(1) для условных операторов

Я создаю синтаксический анализатор для Паскаля, и я застрял в условных операторах.

Предположим, у меня есть этот фрагмент кода:

if ((10 mod 3) = 1) then ...

Это допустимый оператор паскаля if. Однако, когда я пытаюсь придумать грамматику LL(1) для выражения ((10 mod 3) = 1), я терплю крах и сжигаю скобки. Проблема в том, что приведенное выше условие может быть переписано как if (10 mod 3) = 1 then ... или благодаря приоритету оператора как if 10 mod 3 = 1 then ...

У меня есть типичная грамматика LL(1) для арифметических выражений:

E  -> TE'
E' -> ADD_SUB TE' | epsion
T  -> FT'
T' -> MUL_DIV FT' | epsilon
F  -> 'number' | '(' E ')'

ADD_SUB -> '+' | '-'
MUL_DIV -> '*' | 'div' | 'mod'

Однако я не могу придумать грамматику LL (1) для всего условия. Я подумал о чем-то вроде:

CE  -> CT CE'
CE' -> 'or' CT CE' | epsion
CT  -> CF CT'
CT' -> 'and' CF CT' | epsilon
CF  -> E REL-OP E | '(' E REL-OP E ')' | 'not' E REL-OP E

REL-OP -> '=' | '<' | '<=' | '>' | '>=' | '<>

Где E — это E из приведенной выше грамматики арифметических выражений.

Это не LL(1), потому что правила CF -> E REL_OP E и CF -> '(' E REL-OP E ')' содержат коллизию '(' первый-первый.

Любые идеи, как исправить первое столкновение?


parsing grammar ll context-free-grammar
person isklenar    schedule 30.05.2014    source источник
comment
Проект @MitchWheat для языков программирования и класса компиляторов :)   -  person isklenar    schedule 30.05.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

Итак, вам нужно расширить expression (или E, как вы это пишете) таким образом, чтобы (10 mod 3) = 1 было expression (и, следовательно, ((10 mod 3) = 1) было expression), а затем оператор if начинался с "if" expression "then".

Если вы действительно хотите создать отдельную синтаксическую категорию для conditional expression (CE), то вам нужно пройти весь путь до самого низа иерархии приоритетов, чтобы в итоге вы получили список, начинающийся с чего-то вроде

CE  -> CT CE'
CE' -> "or" CT CE' | epsilon

и заканчивается

CF  -> 'number' | '(' CE ')'

Последним из этих производств будут простые дубликаты существующей грамматики выражений с последовательным изменением нетерминальных имен. Но это много ненужного дублирования.

person rici    schedule 30.05.2014