Синтаксические + и * в логических выражениях с помощью рекурсивного спуска

Question

Я пишу метод рекурсивного спуска для булевых выражений, например:

(1 * 0) 
(0 + ~1) 
(0 * (1 + c) 

Где-«True», 0 «False», + есть " или ', * is' и ', ~ is' not 'и' c '- это просто имя переменной (это может быть любая отдельная буквенная буква). Я планирую использовать скобки, а не выполнять какой-то порядок операций.

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

Expression ::= 1 
      | 0 
      | Character 
      | ~ Expression 

Но я не уверен в том, как я бы реализовать + и * на вершине этого. Я совершенно уверен, от того, что я прочитал очевидное выполнение

Expression ::= 1 
      | 0 
      | Character 
      | (Expression + Expression) 
      | (Expression * Expression) 

вызывают бы бесконечный цикл, как это "лево-рекурсивным. Я не уверен, как изменить это, чтобы удалить такую ​​бесконечную рекурсию.

Answer 1

С скобкой на месте, то, что у вас там, не осталось рекурсивным. Левая рекурсия - это когда продукция может достигать себя (прямо или косвенно) без использования токенов между ними. Такие грамматики действительно вызывают бесконечную рекурсию в паркурсах рекурсивного спуска, но это не может случиться с вашими.

У вас есть вопрос о том, что грамматика, как она стоит неоднозначна: После того, как скобок, не известен ли + или * формы разбираемая, пока все выражение левого не было разобрано.

Один из способов обойти этот вопрос является подтягивание общих частей в общем производстве префикс/суффикс:

Expression ::= 1 
      | 0 
      | Character 
      | ParExpr 

ParExpr ::= (Expression ParOp Expression) 

ParOp ::= + 
     | * 

Answer 2

Позвольте мне найти, что для вас ... https://en.wikipedia.org/wiki/Recursive_descent_parser

Ведущее LPAREN заставляет это быть леворекурсивным. Если вы хотите обобщить выражения и иметь некоторый приоритет оператора, следуйте части выражения BNF в статье в Википедии.

Однако у вас есть синтаксическая неоднозначность в выбранной вами грамматике. Когда у вас есть операторы с одинаковым приоритетом, объедините их в нетерминал, например

LogOp :: = + | *

этикетки подобные операнды, чтобы учесть расширение:

UnaryOp :: = ~

Теперь вы можете ... не важно, @ 500 только отправил хороший ответ, который покрывает мою конечную точку.