Грамматика выражений Python

Текст и язык

Грамматику, которую будет распознавать наш парсер, можно описать так:

[variable]

[(]

tokens: (, ), num, var, -, +, /, *, set, end

Это довольно типичная грамматика простого языка выражений, допускающая произвольную вложенность выражений (некоторые примеры выражений можно найти в конце листинга модуля testparser, представленного в примере 19.15). Анализируемые строки представляют собой выражение или присваивание значения переменной (set). В выражениях участвуют числа, переменные и операторы +, -, * и /. Поскольку в грамматике factor вложен в expr, то * и / имеют более высокий приоритет (то есть связывают сильнее), чем + и -. Выражения могут заключаться в круглые скобки, чтобы переопределять старшинство операций, и все операторы являются левоассоциативными (например, выражение 1-2-3 интерпретируется как (1-2)-3).

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

term -> <number> term -> <variable> term -> '(' <expr> ')'

[number, variable, ( ]

[END, ) ]

[+]

[-]

[number, variable, ( ]

[set]

подпись: tokens: (, ), num, var, -, +, /, *, set, end
это довольно типичная грамматика простого языка выражений, допус¬кающая произвольную вложенность выражений (некоторые примеры выражений можно найти в конце листинга модуля testparser, представ¬ленного в примере 19.15). анализируемые строки представляют собой выражение или присваивание значения переменной (set). в выражени¬ях участвуют числа, переменные и операторы +, -, * и /. поскольку в грамматике factor вложен в expr, то * и / имеют более высокий приори¬тет (то есть связывают сильнее), чем + и -. выражения могут заключать¬ся в круглые скобки, чтобы переопределять старшинство операций, и все операторы являются левоассоциативными (например, выражение 1-2-3 интерпретируется как (1-2)-3).
лек се мы представляют собой наиболее элементарные компоненты язы¬ка выражений. за каждым грамматическим правилом, приведенным выше, в квадратных скобках следует список лексем, по которым оно выбирается. при анализе методом рекурсивного спуска мы определяем набор лексем, которые могут начинать подстроку правила, и с помо¬щью этой информации заранее предсказываем правило, которое будет работать. для повторяющихся правил (правил -tail) используется на-

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

Использованная литература:

Марк Лутц — Программирование на Python, 4-е издание, II том, 2011

Каталог сайтов Всего.ру