В информатике парсер приоритета операторов — это парсер снизу вверх , который интерпретирует грамматику приоритета операторов . Например, большинство калькуляторов используют парсеры приоритета операторов для преобразования из понятной человеку инфиксной нотации , основанной на порядке операций , в формат, оптимизированный для оценки, такой как обратная польская нотация (RPN).
Алгоритм сортировочной станции Эдсгера Дейкстры обычно используется для реализации синтаксических анализаторов приоритета операторов.
Парсер приоритета операторов — это простой парсер сдвига-свертки , который способен анализировать подмножество грамматик LR(1) . Точнее, парсер приоритета операторов может анализировать все грамматики LR(1), где два последовательных нетерминала и эпсилон никогда не появляются в правой части любого правила.
Парсеры приоритета операторов нечасто используются на практике; однако у них есть некоторые свойства, которые делают их полезными в более крупном проекте. Во-первых, их достаточно просто писать вручную, что обычно не относится к более сложным парсерам сдвига вправо-свертки. Во-вторых, их можно написать так, чтобы они обращались к таблице операторов во время выполнения , что делает их подходящими для языков, которые могут добавлять или изменять свои операторы во время разбора. (Примером является Haskell , который допускает определяемые пользователем инфиксные операторы с настраиваемой ассоциативностью и приоритетом; следовательно, парсер приоритета операторов должен быть запущен в программе после разбора всех указанных модулей.)
Raku помещает парсер приоритета операторов между двумя парсерами рекурсивного спуска , чтобы достичь баланса скорости и динамичности. Парсеры C и C++ GCC , которые являются вручную закодированными парсерами рекурсивного спуска, оба ускоряются парсером приоритета операторов, который может быстро проверять арифметические выражения. Парсеры приоритета операторов также встроены в парсеры, сгенерированные компилятором-компилятором , чтобы заметно ускорить подход рекурсивного спуска к разбору выражений. [1]
Метод повышения приоритета — это компактный, эффективный и гибкий алгоритм для анализа выражений, впервые описанный Мартином Ричардсом и Колином Уитби-Стревенсом. [2]
Грамматика выражений с инфиксной нотацией в формате EBNF обычно выглядит следующим образом:
выражение :: = выражение-равенства выражение-равенства :: = аддитивное-выражение ( ( ' == ' | '! = ' ) аддитивное-выражение ) * аддитивное-выражение :: = мультипликативное-выражение ( ( '+' | '-' ) мультипликативное-выражение ) * мультипликативное-выражение :: = первичный ( ( ' * ' | ' / ' ) первичный ) * первичный :: = ' ( ' выражение ' ) ' | ЧИСЛО | ПЕРЕМЕННАЯ | '-' первичный При наличии многих уровней приоритета реализация этой грамматики с помощью предиктивного рекурсивно-спускового анализатора может стать неэффективной. Например, для анализа числа может потребоваться пять вызовов функций: по одному для каждого нетерминала в грамматике до достижения первичного .
Анализатор приоритета операторов может делать то же самое более эффективно. [1] Идея заключается в том, что мы можем слева ассоциировать арифметические операции, пока мы находим операторы с тем же приоритетом, но мы должны сохранить временный результат для оценки операторов с более высоким приоритетом. Алгоритм, представленный здесь, не нуждается в явном стеке; вместо этого он использует рекурсивные вызовы для реализации стека.
Алгоритм не является чистым парсером приоритета операторов, как алгоритм сортировочной станции Дейкстры. Он предполагает, что первичный нетерминал анализируется в отдельной подпрограмме, как в парсере рекурсивного спуска.
Псевдокод алгоритма выглядит следующим образом. Анализатор начинается с функции parse_expression . Уровни приоритета больше или равны 0.
parse_expression() возвращает parse_expression_1(parse_primary(), 0)
parse_expression_1(lhs, min_precedence) lookahead := peek next token , в то время как lookahead — это бинарный оператор, приоритет которого >= min_precedence op := lookahead перейти к следующему токену rhs := parse_primary () lookahead := peek next token , в то время как lookahead — это бинарный оператор, приоритет которого выше чем op 's, или правоассоциативный оператор приоритет которого равен приоритету op' s rhs := parse_expression_1 ( rhs , приоритет op + (1, если приоритет опережающего просмотра больше, иначе 0)) lookahead := peek next token lhs := результат применения op с операндами lhs и rhs return lhs
Обратите внимание, что в случае такого правила производства (где оператор может появляться только один раз):
выражение-равенства :: = аддитивное-выражение ( ' == ' | '! = ' ) аддитивное-выражение алгоритм необходимо модифицировать так, чтобы он принимал только бинарные операторы, приоритет которых > min_precedence .
Ниже приведен пример выполнения выражения 2 + 3 * 4 + 5 == 19. Мы даем приоритет 0 выражениям равенства, 1 — аддитивным выражениям, 2 — мультипликативным выражениям.
parse_expression_1 ( lhs = 2, min_precedence = 0)
Возвращается 1.
Другой синтаксический анализатор приоритетов, известный как синтаксический анализ Пратта, был впервые описан Воганом Праттом в статье 1973 года "Top Down Operator Precedence", [3] на основе рекурсивного спуска . Хотя он предшествовал восхождению приоритетов, его можно рассматривать как обобщение восхождения приоритетов. [4]
Первоначально Пратт разработал синтаксический анализатор для реализации языка программирования CGOL , и он был гораздо более подробно рассмотрен в магистерской диссертации под его руководством. [5]
Учебники и реализации:
Существуют и другие способы применения правил приоритета операторов. Один из них — построить дерево исходного выражения, а затем применить к нему правила перезаписи дерева.
Такие деревья не обязательно должны быть реализованы с использованием структур данных, традиционно используемых для деревьев. Вместо этого токены могут храниться в плоских структурах, таких как таблицы, одновременно создавая список приоритетов, который указывает, какие элементы обрабатывать в каком порядке.
Другой подход заключается в том, чтобы сначала полностью заключить выражение в скобки, вставив несколько скобок вокруг каждого оператора, так что они приведут к правильному приоритету даже при разборе линейным анализатором слева направо. Этот алгоритм использовался в раннем компиляторе FORTRAN I : [7]
Компилятор Fortran I расширил бы каждый оператор последовательностью скобок. В упрощенной форме алгоритма это было бы
- замените
+и–на))+((и))-((, соответственно;- замените
*и/на)*(и)/(, соответственно;- добавить
((в начале каждого выражения и после каждой левой скобки в исходном выражении; и- добавьте
))в конце выражения и перед каждой правой скобкой в исходном выражении.Хотя алгоритм не был очевиден, он был верным, и, по словам Кнута , «полученная формула правильно заключена в скобки, хотите верьте, хотите нет». [8]
Пример кода простого приложения на языке C, которое обрабатывает скобки основных математических операторов ( +, -, *, /, ^, (и )):
#include <stdio.h> #include <string.h> // Граница аргумента командной строки — это наш лексер. 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 '+' : // унарная проверка: либо первая, либо имелась операция, ожидающая вторичный аргумент 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 " ); возврат 0 ; }Сначала вам нужно скомпилировать вашу программу. Предполагая, что ваша программа написана на языке C, а исходный код находится в файле с именем program.c, вы можете использовать следующую команду:
программа gcc.c -o программа
Приведенная выше команда указывает gcc скомпилировать program.c и создать исполняемый файл с именем program.
Команда для запуска программы с параметрами, например; a * b + c ^ d / e
./программа а '*' б + в '^' г / е
он производит
((((а))*((б)))+(((с)^(г))/((д))))
как вывод на консоль.
Ограничением этой стратегии является то, что унарные операторы должны иметь более высокий приоритет, чем инфиксные операторы. "Отрицательный" оператор в приведенном выше коде имеет более высокий приоритет, чем возведение в степень. Запуск программы с этим вводом
- а ^ 2
производит этот вывод
((((-а)^(2))))
что, вероятно, не совсем то, что имелось в виду.
Цель этой статьи — [... начать] с восхождения по приоритету и переработать его для использования шаблона команды, пока мы не придем к синтаксическому анализатору Пратта. [Это автор, который придумал термин "восхождение по приоритету".]