Разбор + и * в логических выражениях рекурсивным спуском

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

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

Где 1 — «Истина», 0 — «Ложь», + — «или», * — «и», ~ — «не», а «с» — просто имя переменной (это может быть любая буква алфавита). Я планирую использовать круглые скобки, а не реализовывать какой-то порядок операций.

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

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

Но я не уверен, как бы я реализовал + и * поверх этого. Я вполне уверен из того, что я прочитал об очевидной реализации

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

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


parsing recursion left-recursion recursive-descent
person K810    schedule 13.04.2016    source источник
comment
См. мой ответ SO о том, как написать анализатор рекурсивного спуска: on-8-bit-embedded-systems/2336769#2336769" title="Есть ли альтернатива гибкому бизону, которую можно использовать в 8-битных встроенных системах"> stackoverflow.com/questions/2245962/   -  person Ira Baxter    schedule 13.04.2016

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

Expression ::= 1
             | 0
             | Character
             | ParExpr

ParExpr ::= ( Expression ParOp  Expression )

ParOp ::= +
        | *
person 500 - Internal Server Error    schedule 13.04.2016

arrow_upward
0
arrow_downward

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

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

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

ЛогОп ::= + | *

Пометьте похожие операнды, чтобы разрешить расширение:

UnaryOp ::= ~

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

person Prune    schedule 13.04.2016