В информатике , оператор старшинства анализатор представляет собой снизу вверх анализатор , который интерпретирует оператор-старшинство грамматики . Например, большинство калькуляторов используют синтаксические анализаторы приоритета операторов для преобразования из удобочитаемой инфиксной нотации в зависимости от порядка операций в формат, оптимизированный для оценки, такой как обратная польская нотация (RPN).
Эдсгер Дейкстр «s алгоритм сортировочной станции обычно используются для реализации оператора предшествования парсеров.
Отношение к другим парсерам
Синтаксический анализатор приоритета операторов - это простой синтаксический анализатор с уменьшением сдвига, который способен анализировать подмножество грамматик 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) опережения : = PEEK следующий маркер в то время опережения является бинарным оператором которого является приоритет> = min_precedence оп : = опережения перейти к следующему токену RHS : = parse_primary () опережения : = PEEK следующий маркер в то время опережения представляет собой бинарный оператор, приоритет больше , чем op , или правоассоциативный оператор чей приоритет равен ор» ы RHS : = parse_expression_1 ( шк , min_precedence + 1) опережения : = PEEK следующая лексема LHS : = результат применения оп с операндами LHS и RHS вернуть LHS
Обратите внимание, что в случае такого производственного правила (где оператор может появляться только один раз):
выражение-равенство :: = аддитивное-выражение ('==' | '! =') аддитивное-выражение
алгоритм должен быть изменен, чтобы принимать только бинарные операторы с приоритетом> 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 г. «Приоритет операций сверху вниз» [3] на основе рекурсивного спуска . Хотя это восхождение предшествует старшинству, его можно рассматривать как обобщение предшествующего лазания [4]
Первоначально Пратт разработал синтаксический анализатор для реализации языка программирования CGOL , и под его руководством он был рассмотрен более подробно в магистерской диссертации. [5]
Учебники и реализации:
- Дуглас Крокфорд основал синтаксический анализатор JavaScript в JSLint на синтаксическом анализе Пратта. [6]
- Сравнение реализаций Python для восхождения на приоритет и синтаксического анализа Пратта: «Анализ Пратта и восхождение на приоритет - это один и тот же алгоритм» (2016) Энди Чу
- Учебник с использованием Rust : «Простой, но мощный анализ Pratt» (2020) от Алексея Кладова
- Учебное пособие с использованием Python : «Простой анализ сверху вниз в Python» (2008 г.) Фредрика Лунда
- Учебное пособие по Java : «Парсеры Pratt: упрощенный анализ выражений» (2011 г.) Боба Нистрома, автора книги Crafting Interpreters
Альтернативные методы
Есть и другие способы применения правил приоритета операторов. Один из них - построить дерево исходного выражения, а затем применить к нему правила перезаписи дерева.
Такие деревья не обязательно должны быть реализованы с использованием структур данных, обычно используемых для деревьев. Вместо этого токены можно хранить в плоских структурах, таких как таблицы, путем одновременного создания списка приоритетов, в котором указывается, какие элементы в каком порядке обрабатывать.
Другой подход состоит в том, чтобы сначала полностью заключить выражение в круглые скобки, вставив ряд круглых скобок вокруг каждого оператора, чтобы они приводили к правильному приоритету даже при анализе с помощью линейного синтаксического анализатора слева направо. Этот алгоритм использовался в раннем компиляторе FORTRAN I. [7]
Компилятор Fortran I расширил бы каждый оператор последовательностью круглых скобок. В упрощенной форме алгоритма это было бы
- заменить
+
и–
на))+((
и))-((
соответственно;- заменить
*
и/
на)*(
и)/(
соответственно;- добавить
((
в начале каждого выражения и после каждой левой круглой скобки в исходном выражении; а также- добавить
))
в конце выражения и перед каждой правой круглой скобкой в исходном выражении.Хотя это и не очевидно, алгоритм был правильным, и, по словам Кнута , «полученная формула правильно заключена в круглые скобки, хотите верьте, хотите нет». [8]
Пример кода простого приложения C , который обрабатывает parenthesisation базовых математических операторов ( +
, -
, *
, /
, ^
, (
и )
):
#include #include int main ( int argc , char * argv []) { int я ; printf ( "((((" ); for ( i = 1 ; i ! = argc ; i ++ ) { if ( argv [ i ] && ! argv [ i ] [ 1 ]) { switch ( * argv [ i ] ) { case '(' : printf ( "((((" ); продолжить ; case ')' : printf ( "))))" ); продолжить ; case '^' : printf ( ") ^ (" ); continue ; case '*' : printf ( ")) * ((" ); continue ; case '/' : printf ( ")) / ((" ); continue ; case '+' : if ( i == 1 | | strchr ( "(^ * / + -" , * argv [ i -1 ])) printf ( "+" ); else printf ( "))) + (((" ); продолжить ; case '-' : если ( i == 1 || strchr ( "(^ * / + -" , * argv [ i -1 ])) printf ( "-" ); else printf ( "))) - (((" ); продолжить ; } } printf ( "% s" , argv [ i ]); } printf ( ")))) \ n " ); return 0 ; }
Например, при компиляции и вызове из командной строки с параметрами
а * б + с ^ г / д
он производит
((((a)) * ((b))) + (((c) ^ (d)) / ((e))))
как вывод на консоль.
Ограничением этой стратегии является то, что унарные операторы должны иметь более высокий приоритет, чем инфиксные. «Отрицательный» оператор в приведенном выше коде имеет более высокий приоритет, чем возведение в степень. Запуск программы с этим входом
- а ^ 2
производит этот вывод
((((-a) ^ (2))))
что, вероятно, не то, что задумано.
Рекомендации
- ^ а б Харвелл, Сэм (2008-08-29). «Парсер приоритета операторов» . ANTLR3 Вики . Проверено 25 октября 2017 .
- ^ Ричардс, Мартин; Уитби-Стревенс, Колин (1979). BCPL - язык и его компилятор . Издательство Кембриджского университета. ISBN 9780521219655.
- ^ Пратт, Воган. « Приоритет оператора сверху вниз ». Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (1973).
- ^ Норвелл, Теодор. «Анализ выражений с помощью рекурсивного спуска» . www.engr.mun.ca .
Цель этого поста - [... начать] восхождение по приоритетам и его рефакторинг для использования шаблона команд, пока мы не дойдем до синтаксического анализатора Pratt. [Это автор, который ввел термин «восхождение по старшинству».]
- ^ Ван Де Вантер, Майкл Л. « Формализация и доказательство правильности языковой системы CGOL ». (Дипломная работа). Технический отчет лаборатории компьютерных наук Массачусетского технологического института MIT-LCS-TR-147 (Кембридж, Массачусетс). 1975 г.
- ^ Крокфорд, Д. (21 февраля 2007 г.). «Приоритет оператора сверху вниз» .
- ^ Падуя, Дэвид (2000). "Компилятор Fortran I" (PDF) . Вычислительная техника в науке и технике . 2 (1): 70–75. Bibcode : 2000CSE ..... 2a..70P . DOI : 10.1109 / 5992.814661 .
- ^ Кнут, Дональд Э. (1962). «ИСТОРИЯ ПИСАТЕЛЕЙ КОМПИЛЯТОРОВ» . Компьютеры и автоматика . Эдмунд С. Беркли. 11 (12): 8–14.
Внешние ссылки
- Кларк, Кит (1992-05-26). "Re: компактный синтаксический анализ выражений с рекурсивным спуском" . Проверено 24 января 2012 .
- Пример кода C ++ Кейта Кларка для синтаксического анализа инфиксных выражений с использованием метода восхождения по приоритету
- Самельсон, Клаус ; Фридрих Л. Бауэр (февраль 1960 г.). «Последовательный перевод формул». Коммуникации ACM . 3 (2): 76–83. DOI : 10.1145 / 366959.366968 .
- Синтаксический анализатор выражения с инфиксной нотацией с использованием списков приоритета