Парсер приоритета операторов - Operator-precedence parser
В информатике , оператор старшинства анализатор представляет собой снизу вверх анализатор , который интерпретирует оператор-старшинство грамматики . Например, большинство калькуляторов используют синтаксические анализаторы приоритета операторов для преобразования из удобочитаемой инфиксной нотации, основанной на порядке операций, в формат, оптимизированный для оценки, такой как обратная польская нотация (RPN).
Эдсгер Дейкстр «s алгоритм сортировочной станции обычно используются для реализации оператора предшествования парсеров.
Отношение к другим парсерам
Синтаксический анализатор приоритета операторов - это простой синтаксический анализатор с уменьшением сдвига, который способен анализировать подмножество грамматик LR (1) . Точнее, синтаксический анализатор приоритета операторов может анализировать все грамматики LR (1), в которых два последовательных нетерминала и эпсилон никогда не появляются в правой части любого правила.
Парсеры приоритета операторов на практике используются нечасто; однако у них есть некоторые свойства, которые делают их полезными в более крупном дизайне. Во-первых, они достаточно просты для написания вручную, чего обычно не происходит с более сложными синтаксическими анализаторами с правым сдвигом и уменьшением. Во-вторых, они могут быть написаны так, чтобы обращаться к таблице операторов во время выполнения , что делает их пригодными для языков, которые могут добавлять или изменять свои операторы во время синтаксического анализа. (Примером является Haskell , который допускает определяемые пользователем инфиксные операторы с настраиваемой ассоциативностью и приоритетом; следовательно, синтаксический анализатор приоритета операторов должен запускаться в программе после анализа всех модулей, на которые есть ссылки.)
Raku помещает синтаксический анализатор приоритета операторов между двумя синтаксическими анализаторами рекурсивного спуска , чтобы достичь баланса скорости и динамизма. Синтаксические анализаторы C и C ++ GCC , которые представляют собой ручные синтаксические анализаторы рекурсивного спуска, ускоряются синтаксическим анализатором приоритета операторов, который может быстро проверять арифметические выражения. Парсеры приоритета операторов также встроены в парсеры, генерируемые компилятором-компилятором, чтобы заметно ускорить подход рекурсивного спуска к синтаксическому анализу выражений.
Метод восхождения по приоритету
Метод восхождения по приоритету - это компактный, эффективный и гибкий алгоритм синтаксического анализа выражений, который впервые был описан Мартином Ричардсом и Колином Уитби-Стревенсом.
Грамматика выражения инфиксной нотации в формате EBNF обычно выглядит следующим образом:
expression ::= equality-expression
equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) *
additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) *
multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary
При многих уровнях приоритета реализация этой грамматики с помощью синтаксического анализатора с прогнозирующим рекурсивным спуском может стать неэффективной. Например, для синтаксического анализа числа может потребоваться пять вызовов функций: по одному для каждого нетерминала в грамматике до достижения первичного .
Синтаксический анализатор приоритета операторов может сделать то же самое более эффективно. Идея состоит в том, что мы можем оставить ассоциировать арифметические операции, пока мы находим операторы с таким же приоритетом, но мы должны сохранить временный результат для оценки операторов с более высоким приоритетом. Представленный здесь алгоритм не требует явного стека; вместо этого он использует рекурсивные вызовы для реализации стека.
Алгоритм не является чистым синтаксическим анализатором приоритета операторов, как алгоритм маневровой станции Дейкстры. Предполагается, что первичный нетерминал анализируется в отдельной подпрограмме, как в парсере рекурсивного спуска.
Псевдокод
Псевдокод алгоритма следующий. Парсер запускается с функции parse_expression . Уровни приоритета больше или равны 0.
parse_expression() return parse_expression_1(parse_primary(), 0)
parse_expression_1(lhs, min_precedence) lookahead := peek next token while lookahead is a binary operator whose precedence is >= min_precedence op := lookahead advance to next token rhs := parse_primary () lookahead := peek next token while lookahead is a binary operator whose precedence is greater than op's, or a right-associative operator whose precedence is equal to op's rhs := parse_expression_1 (rhs, precedence of op + 1) lookahead := peek next token lhs := the result of applying op with operands lhs and rhs return lhs
Обратите внимание, что в случае такого производственного правила (где оператор может появляться только один раз):
equality-expression ::= additive-expression ( '==' | '!=' ) additive-expression
алгоритм должен быть изменен, чтобы принимать только бинарные операторы с приоритетом> min_precedence .
Пример выполнения алгоритма
Пример выполнения выражения 2 + 3 * 4 + 5 == 19 выглядит следующим образом. Мы отдаем приоритет 0 выражениям равенства, 1 - аддитивным выражениям, 2 - мультипликативным выражениям.
parse_expression_1 ( LHS = 2, min_precedence = 0)
- лексема опережающего просмотра - +, с приоритетом 1. вводится внешний цикл while.
- op равен + (приоритет 1), а ввод расширен
- правая равняется 3
- маркер просмотра вперед - *, с приоритетом 2. вводится внутренний цикл while.
parse_expression_1 ( LHS = 3, min_precedence = 2)
-
- лексема просмотра вперед - *, с приоритетом 2. вводится внешний цикл while.
- op равен * (приоритет 2), а ввод расширен
- правая равняется 4
- следующая лексема - +, с приоритетом 1. внутренний цикл while не вводится.
- lhs присвоено 3 * 4 = 12
- следующая лексема - + с приоритетом 1. внешний цикл while остается.
- 12 возвращается.
- лексема опережающего просмотра - +, с приоритетом 1. внутренний цикл while не вводится.
- lhs присвоено 2 + 12 = 14
- лексема опережающего просмотра - +, с приоритетом 1. внешний цикл while не остается.
- op равен + (приоритет 1), а ввод расширен
- правая сторона 5
- следующий токен == с приоритетом 0. внутренний цикл while не вводится.
- lhs присвоено 14 + 5 = 19
- следующий токен == с приоритетом 0. внешний цикл while не остается.
- op == (приоритет 0), а ввод расширен
- правый - 19
- следующий токен - это конец строки , который не является оператором. внутренний цикл while не вводится.
- lhs присваивается результат вычисления 19 == 19, например 1 (как в стандарте C).
- следующий токен - это конец строки , который не является оператором. внешний цикл while остается.
1 возвращается.
Разбор Пратта
Другой синтаксический анализатор приоритета, известный как синтаксический анализ Пратта, был впервые описан Воаном Праттом в статье 1973 г. «Приоритет операций сверху вниз», основанной на рекурсивном спуске . Хотя это восхождение предшествует старшинству, его можно рассматривать как обобщение предшествующего скалолазания.
Первоначально Пратт разработал синтаксический анализатор для реализации языка программирования CGOL , и под его руководством он был рассмотрен более подробно в магистерской диссертации.
Учебники и реализации:
- Дуглас Крокфорд основал синтаксический анализатор JavaScript в JSLint на синтаксическом анализе Пратта.
- Сравнение реализаций Python для восхождения на приоритет и синтаксического анализа Пратта: «Анализ Пратта и восхождение на приоритет - это один и тот же алгоритм» (2016) Энди Чу
- Учебник с использованием Rust : «Простой, но мощный анализ Pratt» (2020) от Алексея Кладова
- Учебное пособие с использованием Python : «Простой анализ сверху вниз в Python» (2008 г.), автор Фредрик Лунд.
- Учебное пособие по Java : «Парсеры Pratt: упрощенный анализ выражений» (2011 г.) Боба Нистрома, автора книги Crafting Interpreters
Альтернативные методы
Есть и другие способы применения правил приоритета операторов. Один из них - построить дерево исходного выражения, а затем применить к нему правила перезаписи дерева.
Такие деревья не обязательно должны быть реализованы с использованием структур данных, обычно используемых для деревьев. Вместо этого токены можно хранить в плоских структурах, таких как таблицы, путем одновременного создания списка приоритетов, в котором указывается, какие элементы в каком порядке обрабатывать.
Другой подход состоит в том, чтобы сначала полностью заключить выражение в круглые скобки, вставив ряд круглых скобок вокруг каждого оператора, чтобы они приводили к правильному приоритету даже при анализе с помощью линейного синтаксического анализатора слева направо. Этот алгоритм использовался в раннем компиляторе FORTRAN I.
Компилятор Fortran I расширил бы каждый оператор последовательностью круглых скобок. В упрощенной форме алгоритма это было бы
- заменить
+
и–
на))+((
и))-((
соответственно;- заменить
*
и/
на)*(
и)/(
соответственно;- добавить
((
в начале каждого выражения и после каждой левой круглой скобки в исходном выражении; а также- добавить
))
в конце выражения и перед каждой правой круглой скобкой в исходном выражении.Хотя это и не очевидно, алгоритм был правильным, и, по словам Кнута , «полученная формула правильно заключена в круглые скобки, хотите верьте, хотите нет».
Пример кода простого приложения C , который обрабатывает parenthesisation базовых математических операторов ( +
, -
, *
, /
, ^
, (
и )
):
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[]) {
int i;
printf("((((");
for (i=1;i!=argc;i++) {
if (argv[i] && !argv[i][1]) {
switch (*argv[i]) {
case '(': printf("(((("); continue;
case ')': printf("))))"); continue;
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+':
if (i == 1 || strchr("(^*/+-", *argv[i-1]))
printf("+");
else
printf(")))+(((");
continue;
case '-':
if (i == 1 || strchr("(^*/+-", *argv[i-1]))
printf("-");
else
printf(")))-(((");
continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
Например, при компиляции и вызове из командной строки с параметрами
a * b + c ^ d / e
он производит
((((a))*((b)))+(((c)^(d))/((e))))
как вывод на консоль.
Ограничением этой стратегии является то, что все унарные операторы должны иметь более высокий приоритет, чем инфиксные. «Отрицательный» оператор в приведенном выше коде имеет более высокий приоритет, чем возведение в степень. Запуск программы с этим входом
- a ^ 2
производит этот вывод
((((-a)^(2))))
что, вероятно, не то, что задумано.
использованная литература
внешние ссылки
- Кларк, Кит (1992-05-26). «Re: компактный синтаксический анализ выражений с рекурсивным спуском» . Проверено 24 января 2012 .
- Пример кода C ++ Кейта Кларка для синтаксического анализа инфиксных выражений с использованием метода восхождения по приоритету
- Самельсон, Клаус ; Фридрих Л. Бауэр (февраль 1960 г.). «Последовательный перевод формул». Коммуникации ACM . 3 (2): 76–83. DOI : 10.1145 / 366959.366968 .
- Синтаксический анализатор выражения с инфиксной нотацией с использованием списков приоритета