Требуется: пример (ы) грамматики PEG для глубоко вложенных булевых выражений Python

Question

Я хотел бы привести пример грамматики ПЭГ для глубоко вложенных булевых выражений Python. Грамматика PEG не может быть «очень рекурсивной», иначе это приведет к переполнению стека. Требуется поддержка '|', '&', '(' и ')'.

Пример ввода: (а = 1 | Ь = 1 | с = 1 | д = 1 & е = 2) & (е = 2 & г = 2 & ч = 2 | г = 3 | J = 3 | k = 3)

Answer 1

Чтобы разобрать типичные (особенно булевы логические) выражения, вам вряд ли нужен парсер Peg; никогда не нужно возвращаться. Выберите любой синтаксический анализатор и используйте его (включая двигатель Peg, если вы настаиваете).

Вот грамматика, которая будет работать на ваш пример:

EXPRESSION = DISJUNCTION ; 
DISJUNCTION = CONJUNCTION ('|' CONJUNCTION)*; 
CONJUNCTION = TERM ('&' TERM); 
TERM = '~' TERM | '(' EXPRESSION ')' | CONDITION ; 
CONDITION = VARIABLE '=' CONSTANT ; 

Если вы хотите реализовать эту грамматику с помощью рукописного, рекурсивного спуска парсера, который легко коды, см моего SO ответа о том, как сделайте это: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?

Что касается переполнения стека: если ваше выражение вложено в сотни уровней («круглых скобок») в большинстве окон или систем Linux, доступный стек намного больше, чем требования стека к парсеру, применяемому к выражения, которые люди пишут на практике. С огромными выражениями, многие люди не могут их прочитать, так что они не происходят. Для выражения примера OP требуется вложение всего нескольких записей в стек.

Если вы пишете грамматику для полноценного языка программирования, а кто-то пишет большую сложную программу в этом langauge, вы можете рискнуть переполнением стека. Я могу рассказать вам по опыту с компилятором, который я построил, что вложение из 256 (стековых фреймов) легко вписывается в стек стека Windows 1Mb, и этого достаточно, чтобы скомпилировать 2 миллиона линейных программ с каждой странной конструкцией и глубоко вложенным лексическим очерченным трюком, известным человечеству в этом.