Анализатор приоритета операторов
В информатике анализатор приоритета операторов — это восходящий анализатор , который интерпретирует грамматику приоритета операторов . Например, большинство калькуляторов используют анализаторы приоритета операторов для преобразования удобочитаемой инфиксной нотации , основанной на порядке операций , в формат, оптимизированный для вычислений, такой как обратная польская нотация (RPN).
Эдсгера Дейкстры обычно Алгоритм сортировочной станции используется для реализации анализаторов приоритета операторов.
Отношения с другими парсерами
[ редактировать ]Анализатор с приоритетом операторов — это простой анализатор с сокращением сдвига , который способен анализировать подмножество LR(1) грамматик. Точнее, анализатор приоритета операторов может анализировать все грамматики LR(1), в которых два последовательных нетерминала и эпсилон никогда не появляются в правой части любого правила.
Анализаторы приоритета операторов на практике используются нечасто; однако у них есть некоторые свойства, которые делают их полезными в более крупном проекте. Во-первых, их достаточно просто написать вручную, чего обычно не происходит с более сложными парсерами со сдвигом вправо. Во-вторых, их можно написать так, чтобы они обращались к таблице операторов во время выполнения , что делает их подходящими для языков, которые могут добавлять или изменять свои операторы во время синтаксического анализа. (Примером является Haskell , который позволяет определять пользовательские инфиксные операторы с настраиваемой ассоциативностью и приоритетом; следовательно, анализатор приоритета операторов должен быть запущен в программе после анализа всех ссылочных модулей.)
Raku помещает анализатор приоритета операторов между двумя анализаторами рекурсивного спуска , чтобы достичь баланса скорости и динамизма. Синтаксические анализаторы C и C++ в GCC , которые представляют собой написанные вручную анализаторы рекурсивного спуска, ускоряются благодаря анализатору с приоритетом операторов, который может быстро проверять арифметические выражения. Анализаторы приоритета операторов также встроены в анализаторы , генерируемые компилятором, чтобы заметно ускорить подход рекурсивного спуска к анализу выражений. [1]
Метод восхождения по приоритету
[ редактировать ]Метод восхождения по приоритету — это компактный, эффективный и гибкий алгоритм анализа выражений, который впервые был описан Мартином Ричардсом и Колином Уитби-Стривенсом. [2]
Грамматика выражений с инфиксной записью в формате 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
При многих уровнях приоритета реализация этой грамматики с помощью анализатора с прогнозирующим рекурсивным спуском может стать неэффективной. Например, для анализа числа может потребоваться пять вызовов функций: по одному для каждого нетерминала в грамматике до достижения первичного .
Анализатор приоритета операторов может сделать то же самое более эффективно. [1] Идея состоит в том, что мы можем оставить ассоциированные арифметические операции, пока находим операторы с одинаковым приоритетом, но нам нужно сохранить временный результат для оценки операторов с более высоким приоритетом. Представленный здесь алгоритм не требует явного стека; вместо этого он использует рекурсивные вызовы для реализации стека.
Алгоритм не является чисто анализатором приоритета операторов, как алгоритм сортировочной станции Дейкстры. Предполагается, что основной нетерминал анализируется в отдельной подпрограмме, как в анализаторе рекурсивного спуска.
Псевдокод
[ редактировать ]Псевдокод алгоритма следующий. Анализатор начинается с функции 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 if lookahead precedence is greater, else 0))
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 не вводится.
- левой стороне присвоено 3*4 = 12
- следующий токен — +, с приоритетом 1. Внешний цикл while остается.
- 12 возвращается.
- токен просмотра - +, с приоритетом 1. внутренний цикл while не вводится.
- левой стороне присвоено 2+12 = 14
- токен просмотра - +, с приоритетом 1. Внешний цикл while не остается.
- op равен + (приоритет 1), а ввод продвигается вперед
- резус равен 5
- следующий токен == с приоритетом 0. внутренний цикл while не вводится.
- левой стороне присвоено 14+5 = 19
- следующий токен == с приоритетом 0. Внешний цикл while не остается.
- op == (приоритет 0), а ввод расширен
- резус 19
- следующий токен — конец строки , который не является оператором. внутренний цикл while не вводится.
- lhs присваивается результат вычисления 19 == 19, например 1 (как в стандарте C).
- следующий токен — конец строки , который не является оператором. внешний цикл while остается.
1 возвращается.
Парсинг Пратта
[ редактировать ] | в этом разделе Использование внешних ссылок может не соответствовать политике и рекомендациям Википедии . ( Август 2023 г. ) |
Другой анализатор приоритета, известный как анализ Пратта, был впервые описан Воаном Праттом в статье 1973 года «Приоритет операторов сверху вниз». [3] на основе рекурсивного спуска . Хотя оно предшествовало повышению приоритета, его можно рассматривать как обобщение повышения приоритета. [4]
Пратт изначально разработал синтаксический анализатор для реализации языка программирования CGOL , и под его руководством он был рассмотрен гораздо более подробно в магистерской диссертации. [5]
Учебники и реализации:
- Дуглас Крокфорд основал парсер JavaScript в JSLint на анализе Пратта. [6]
- Сравнение реализаций восхождения по приоритету и синтаксического анализа Пратта на языке Python: Энди Чу «Разбор Пратта и восхождение по приоритету — один и тот же алгоритм» (2016).
- Учебное пособие по Rust : «Простой, но мощный парсинг Пратта» (2020), Алексей Кладов
- Учебное пособие по использованию Rust : «Техника анализа Пратта» (2024), Уильям Рогстад
- Учебное пособие по использованию Python : «Простой нисходящий анализ в Python» (2008), Фредрик Лунд. Архивировано 28 февраля 2015 г. на Wayback Machine.
- Учебное пособие по использованию Java : «Парсеры Пратта: анализ выражений стал проще» (2011), Боб Нистром, автор книги Crafting Interpreters.
- Реализация на C# : «Gratt: универсальный нисходящий анализатор приоритета операторов Вона Пратта для .NET Standard» ( универсальная версия, вдохновленная реализацией Java, представленной Бобом Нистромом в «Парсеры Пратта: анализ выражений стал проще» ).
Альтернативные методы
[ редактировать ]Существуют и другие способы применения правил приоритета операторов. Один из них — построить дерево исходного выражения и затем применить к нему правила перезаписи дерева.
Такие деревья не обязательно должны быть реализованы с использованием структур данных, обычно используемых для деревьев. Вместо этого токены можно хранить в плоских структурах, таких как таблицы, путем одновременного создания списка приоритетов, в котором указано, какие элементы и в каком порядке обрабатывать.
Полные скобки
[ редактировать ]Другой подход состоит в том, чтобы сначала полностью заключить выражение в круглые скобки, вставив несколько круглых скобок вокруг каждого оператора, чтобы они приводили к правильному приоритету даже при анализе с помощью линейного синтаксического анализатора слева направо. Этот алгоритм использовался в раннем компиляторе FORTRAN I : [7]
Компилятор Fortran I расширял каждый оператор последовательностью круглых скобок. В упрощенной форме алгоритма это будет
- заменять
+и–с))+((и))-((, соответственно;- заменять
*и/с)*(и)/(, соответственно;- добавлять
((в начале каждого выражения и после каждой левой скобки в исходном выражении; и- добавлять
))в конце выражения и перед каждой правой круглой скобкой в исходном выражении.Хотя это и не очевидно, алгоритм был правильным, и, по словам Кнута , «полученная формула правильно заключена в круглые скобки, хотите верьте, хотите нет». [8]
 | В этом разделе отсутствует информация о том, почему скобки работают. ( май 2023 г. ) |
Пример кода простого приложения C, которое обрабатывает скобки основных математических операторов ( +, -, *, /, ^, ( и )):
#include <stdio.h>
#include <string.h>
// The command-line argument boundary is our lexer.
int main(int argc, char *argv[]) {
int i;
printf("((((");
for (i=1; i!=argc; i++) {
// strlen(argv[i]) == 2
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 '+':
// unary check: either first or had an operator expecting secondary argument
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;
}
Во-первых, вам нужно скомпилировать вашу программу. Предполагая, что ваша программа написана на C, а исходный код находится в файле с именем program.c, вы должны использовать следующую команду:
gcc program.c -o program
Приведенная выше команда сообщает gcc скомпилировать файл program.c и создать исполняемый файл с именем program.
Команда запуска программы с параметрами, Например; а*б+с^д/е
./program a '*' b + c '^' d / e
он производит
((((a))*((b)))+(((c)^(d))/((e))))
как вывод на консоли.
Ограничением этой стратегии является то, что все унарные операторы должны иметь более высокий приоритет, чем инфиксные операторы. «Отрицательный» оператор в приведенном выше коде имеет более высокий приоритет, чем возведение в степень. Запуск программы с этим вводом
- a ^ 2
производит этот вывод
((((-a)^(2))))
что, вероятно, не то, что задумано.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Харвелл, Сэм (29 августа 2008 г.). «Парсер приоритета операторов» . ANTLR3 Wiki . Проверено 25 октября 2017 г.
- ^ Ричардс, Мартин; Уитби-Стривенс, Колин (1979). BCPL — язык и его компилятор . Издательство Кембриджского университета. ISBN 9780521219655 .
- ^ Пратт, Воган. « Приоритет операторов сверху вниз ». Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (1973).
- ^ Норвелл, Теодор. «Разбор выражений рекурсивным спуском» . www.engr.mun.ca.
Цель этого поста — [... начать] с повышения приоритета и его рефакторинга для использования шаблона команды, пока мы не придем к парсеру Пратта. [Это автор, который ввёл термин «восхождение по приоритету».]
- ^ Ван Де Вантер, Майкл Л. « Формализация и доказательство правильности языковой системы CGOL ». (Магистерская диссертация). Технический отчет Лаборатории компьютерных наук Массачусетского технологического института MIT-LCS-TR-147 (Кембридж, Массачусетс). 1975.
- ^ Крокфорд, Д. (21 февраля 2007 г.). «Приоритет операторов сверху вниз» .
- ^ Падуя, Дэвид (2000). «Компилятор Фортрана I» (PDF) . Вычисления в науке и технике . 2 (1): 70–75. Бибкод : 2000CSE.....2a..70P . дои : 10.1109/5992.814661 .
- ^ Кнут, Дональд Э. (1962). «ИСТОРИЯ НАПИСАНИЯ СОСТАВИТЕЛЕЙ» . Компьютеры и автоматизация . 11 (12). Эдмунд К. Беркли: 8–14.
Внешние ссылки
[ редактировать ]- Кларк, Кейт (26 мая 1992 г.). «Re: компактный анализ выражений с рекурсивным спуском» . Проверено 24 января 2012 г.
- Пример кода C++ Кейта Кларка для анализа инфиксных выражений с использованием метода восхождения по приоритету
- Самельсон, Клаус ; Фридрих Л. Бауэр (февраль 1960 г.). «Последовательный перевод формул» . Коммуникации АКМ . 3 (2): 76–83. дои : 10.1145/366959.366968 .
- Анализатор выражений с инфиксной записью с использованием списков приоритета