Можно ли написать рекурсивный спуск парсер для этой грамматики?

Question

От this question, грамматика для выражений, включающих бинарные операторы (+ - * /), который запрещает внешние скобки:

top_level : expression PLUS term 
      | expression MINUS term 
      | term TIMES factor 
      | term DIVIDE factor 
      | NUMBER 
expression : expression PLUS term 
      | expression MINUS term 
      | term 
term  : term TIMES factor 
      | term DIVIDE factor 
      | factor 
factor  : NUMBER 
      | LPAREN expression RPAREN 

Эта грамматика LALR (1). Поэтому я смог использовать PLY (реализация на Python yacc) для создания анализатора восходящего потока для грамматики.

Для сравнения, теперь я хотел бы попытаться создать парсер для рекурсивного спуска сверху вниз для одного и того же языка. Я преобразовал грамматику, удаляя левую рекурсию и применяя влево-факторинг:

top_level : expression top_level1 
      | term top_level2 
      | NUMBER 
top_level1 : PLUS term 
      | MINUS term 
top_level2 : TIMES factor 
      | DIVIDE factor 
expression : term expression1 
expression1 : PLUS term expression1 
      | MINUS term expression1 
      | empty 
term  : factor term1 
term1  : TIMES factor term1 
      | DIVIDE factor term1 
      | empty 
factor  : NUMBER 
      | LPAREN expression RPAREN 

Без top_level правила эта грамматика LL (1), так что написание рекурсивным спуском анализатор может быть довольно простым. К сожалению, в том числе top_level, грамматика не LL (1).

1. Существует ли классификация «LL» для этой грамматики (например, LL (k), LL (*))?
2. Можно ли написать парсер для рекурсивного спуска для этой грамматики? Как это будет сделано? (Требуется ли откат?)
3. Возможно ли упростить эту грамматику, чтобы облегчить подход рекурсивного спуска?

Answer 1

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

1. Есть ли "LL" классификации для этой грамматики (например, LL (к), LL (*))?

Если α является вывод expression, β из term и γ из factor, то top_level можно получить как предложение ( α )+ β и предложение ( α )* γ (но он не может получить предложение ( α ).) Тем не менее, ( α ) возможный вывод как expression и term, так что невозможно решить, производство top_level не использовать до тех пор, символ, следующий за ). Поскольку α может быть произвольной длины, нет k, для которого достаточно взглянуть на k, чтобы отличить эти два произведения. Некоторые люди могут назвать это LL(), но это не кажется мне очень полезной грамматической категорией. (LL (*) является, afaik, именем стратегии синтаксического анализа, изобретенной Теренсом Парром, а не принятым именем для класса грамматик.) Я бы просто сказал, что грамматика не LL (k) для любого k.

2. Можно ли написать рекурсивный спуск парсер для этой грамматики? Как это будет сделано? (Требуется ли откат?)

Конечно. Это даже не так сложно.

Первый символ должен быть либо NUMBER или (. Если это NUMBER, мы предсказываем (вызов) expression. Если (, мы уничтожаем его, называют expression, потребляют следующие ) (или объявить ошибку, если следующий символ не является близкой скобкой), а затем либо вызывать expression1, либо term1, а затем expression1, в зависимости от того, что следующий символ. Опять же, если следующий символ не соответствует FIRST-набору либо expression1, либо term1, мы объявляем синтаксическую ошибку. Обратите внимание, что указанная выше стратегия не требует e top_level* производства вообще.

Поскольку это явно работает без возврата, это может послужить основой для написания грамматики LL (1).

3. Возможно ли упростить эту грамматику, чтобы облегчить подход рекурсивного спуска?

Я не уверен, если следующая грамматика проще, а это не соответствует методу рекурсивного спуска, описанному выше.

top_level : NUMBER optional_expression_or_term_1 
      | LPAREN expression RPAREN expression_or_term_1 
optional_expression_or_term_1: empty 
      | expression_or_term_1 
expression_or_term_1 
      : PLUS term expression1 
      | MINUS term expression1 
      | TIMES factor term1 expression1 
      | DIVIDE factor term1 expression1 
expression : term expression1 
expression1 : PLUS term expression1 
      | MINUS term expression1 
      | empty 
term  : factor term1 
term1  : TIMES factor term1 
      | DIVIDE factor term1 
      | empty 
factor  : NUMBER 
      | LPAREN expression RPAREN 

---

Я осталась с двумя наблюдениями, оба из которых вы полностью свободны проигнорировать (в частности, второй, который 100% мнение).

Во-первых, мне кажется странным запретить (1+2), но разрешить (((1)))+2, или ((1+2))+3. Но, без сомнения, у вас есть свои причины. (Конечно, вы могли бы легко запретить лишние двойные круглые скобки, заменив expression с top_level во втором производстве для factor.

Во-вторых, мне кажется, что Обруч-джампинг участвует в LL (1) грамматикой в ​​третьем раздел является еще одной причиной, чтобы спросить, почему существует какая-либо причина использовать грамматики LL.Глава LR (1) легче читать, и ее соответствие синтаксической структуре языка более ясное. Логика сгенерированного парсера рекурсивного спуска может легче понять, но для меня это кажется второстепенным.

Answer 2

Чтобы сделать грамматику LL (1), вам необходимо закончить левый факторинг top_level. Вы остановились на:

top_level : expression top_level1 
      | term top_level2 
      | NUMBER 

expression и term оба имеют NUMBER в своих первых наборов, поэтому они сначала должны быть заменены на лево-фактор:

top_level : NUMBER term1 expression1 top_level1 
      | NUMBER term1 top_level2 
      | NUMBER 
      | LPAREN expression RPAREN term1 expression1 top_level1 
      | LPAREN expression RPAREN term1 top_level2 

который вы можете слева-фактор для

top_level : NUMBER term1 top_level3 
      | LPAREN expression RPAREN term1 top_level4 

top_level3 : expression1 top_level1 
      | top_level2 
      | empty 

top_level4 : expression1 top_level1 
      | top_level2 

Обратите внимание, что это все еще не LL (1), поскольку существуют правила epsilon (term1, expression1) с перекрытием FIRST и FOLLOW. Поэтому вам нужно также учитывать их, чтобы сделать LL (1)