#parsing #context-free-grammar #computation-theory #context-free-language
#синтаксический анализ #контекстно-свободная грамматика #теория вычислений #контекстно-свободный язык
Вопрос:
Я пытаюсь реализовать контекстно-свободную грамматику для языка логических операторов со скобками, включая приоритет оператора.
Например, следующее:
{1} or {2}
{1} and {2} or {3}
({1} or {2}) and {3}
not {1} and ({2} or {3})
...
Я начал со следующей грамматики:
expr := control | expr and expr | expr or expr | not expr | (expr)
control := {d }
Чтобы реализовать приоритет оператора и исключить левую рекурсию, я изменил его следующим образом:
S ::= expr
expr ::= control or expr1 | expr1
expr1 ::= control and expr2 | expr2
expr2 ::= not expr3 | expr3
expr3 ::= (expr) | expr | control
control := {d }
Но такая грамматика не поддерживает такие примеры, как: ({1} или {2}) и {3}, которые содержат ‘и’ / ‘или’ после круглых скобок.
На данный момент у меня есть следующая грамматика:
S ::= expr
expr ::= control or expr1 | expr1
expr1 ::= control and expr2 | expr2
expr2 ::= not expr3 | expr3
expr3 ::= (expr) | (expr) expr4 | expr | control
expr4 :: = and expr | or expr
control := {d }
Правильна ли эта грамматика?
Можно ли это как-то упростить?
Спасибо!
Комментарии:
1. Как вывести ваш второй пример из этой грамматики? Я не думаю, что это возможно, и в этом случае грамматика неверна. Алгебраический язык с двумя двоичными и одним унарным оператором может быть написан в общей сложности с семью производствами (считая альтернативы как производства). У вашего их 15 или около того, так что да, это можно упростить. Начнем с того, что нет необходимости сшивать Франкенштейна из двух разных стилей написания грамматики. Я бы начал с отказа от expr5, 6 и 7.
2. Допустим, я удаляю выражения 5, 6 и 7. В этом случае такие примеры, как «({1} или {2}) и {3}», не работают.
3. Вам нужно производство
expr3 -> ( expr ), чтобы заставить круглые скобки работать, но, похоже, у вас это есть. Проблема в том, что вы используете «control» в первых двух производствах. Вместо этого они должны быть леворекурсивными (хотя ассоциативность не имеет большого значения для булевых операторов) и каскадными, как стандартная алгебраическая грамматика, которую вы найдете по всему Интернету (например, здесь . Я выбрал это, потому что это не PDF, в отличие от остальных первых двух десятков результатов, которые мне дал Google. )4. Спасибо @rici, я проверю пример, который вы мне прислали. Кроме того, я отредактировал свой вопрос, чтобы получить более подробную информацию.
Ответ №1:
Чтобы реализовать приоритет вашего оператора, вам нужно просто:
S ::= expr
expr ::= expr or expr1 | expr1
expr1 ::= expr1 and expr2 | expr2
expr2 ::= not expr2 | expr3
expr3 ::= (expr) | control
control := {d }
Это лево-рекурсивно, чтобы быть левоассоциативным, поскольку это обычно то, что вы хотите (как для корректности, так и для большинства генераторов синтаксического анализа), но если вам по какой-то причине нужно избежать левой рекурсии, вы можете использовать праворекурсивную, правоассоциативную грамматику:
S ::= expr
expr ::= expr1 or expr | expr1
expr1 ::= expr2 and expr1 | expr2
expr2 ::= not expr2 | expr3
expr3 ::= (expr) | control
control := {d }
поскольку оба and и or являются ассоциативными операторами, поэтому left-vs-right не имеет значения.
В обоих случаях вы можете «упростить» его, свернув expr3 и control в expr2:
expr2 ::= not expr2 | ( expr ) | {d }