Проблема, создающая грамматику LL (1)

Question

Я изучаю, как работают парсеры, создавая простой рекурсивный анализатор спуска. Однако у меня проблема с определением моей грамматики как LL (1). Я хочу, чтобы иметь возможность проанализировать следующие два утверждения:

a = 1 
a + 1 

Чтобы сделать это, я создал следующие правила грамматики:

statement: assignent | expression 
assignment: NAME EQUALS expression 
expression: term [(PLUS|MINUS) term] 
term:  NAME | NUMBER 

Однако это приводит к неоднозначности при использовании LL (1), как если токен NAME встречается в правиле statement, он не знает, является ли он assignment или expression без ожидания.

Python грамматика LL (1), поэтому я знаю, что это возможно, но я не могу понять, как это сделать. Я рассмотрел правила грамматики Python, найденные здесь (https://docs.python.org/3/reference/grammar.html), но я все еще не уверен, как они это реализуют.

Любая помощь будет принята с благодарностью :)

Answer 1

Просто лечить = как оператор с очень низким приоритетом. Однако (если вам не нужен такой язык, как C, где = действительно является оператором с очень низким приоритетом), вам нужно исключить его из внутренних (например, скотистых) выражений.

Если вы имели только умножение и сложение, вы можете использовать:

expression: factor ['+' factor] 
factor:  term ['*' term] 
term:  ID | NUMBER | '(' expression ')' 

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

statement: expression ['=' expression] 

К сожалению, это позволило бы, например:

(a + 1) = b 

что нежелательно. Поэтому его нужно устранить, но его можно устранить, когда производство принято (путем проверки формы первого expression), а не самой грамматики. Насколько я понимаю, это то, что делает парсер Python; см. длинный комментарий о test и ключевых словах.

Если вы использовали парсер LR (1) вместо этого, у вас не было бы этой проблемы.