Парсер приоритета операторов - Operator-precedence parser

В Информатика, парсер приоритета операторов это восходящий парсер что интерпретирует грамматика приоритета операторов. Например, большинство калькуляторы используйте парсеры приоритета операторов для преобразования из удобочитаемого инфиксная запись надеется порядок действий в формат, оптимизированный для оценки, например Обратная польская запись (РПН).

Эдсгер Дейкстра с алгоритм маневровой площадки обычно используется для реализации парсеров приоритета операторов.

Отношение к другим парсерам

Парсер приоритета операторов - это простой парсер сдвиг-уменьшение который способен анализировать подмножество LR (1) грамматики. Точнее, синтаксический анализатор приоритета операторов может анализировать все грамматики LR (1), в которых два последовательных нетерминалы и эпсилон никогда не появляются в правой части любого правила.

Парсеры приоритета операторов на практике используются нечасто; однако у них есть некоторые свойства, которые делают их полезными в более крупном дизайне. Во-первых, они достаточно просты для написания вручную, чего обычно не бывает с более сложными синтаксическими анализаторами сдвига вправо. Во-вторых, их можно написать для обращения к таблице операторов на время выполнения, что делает их подходящими для языков, которые могут добавлять или изменять свои операторы во время синтаксического анализа. (Пример: Haskell, который позволяет определять пользовательские инфиксные операторы с настраиваемой ассоциативностью и приоритетом; следовательно, в программе должен быть запущен синтаксический анализатор приоритета операторов. после анализ всех упомянутых модулей.)

Раку помещает парсер приоритета операторов между двумя парсеры рекурсивного спуска для достижения баланса скорости и динамизма. Это выражается в виртуальной машине для Раку, Попугай, как Парсер грамматики (PGE). GCC Синтаксические анализаторы C и C ++, которые представляют собой кодируемые вручную анализаторы рекурсивного спуска, ускоряются анализатором приоритета операторов, который может быстро проверять арифметические выражения. Парсеры приоритета операторов также встроены в компилятор компилятор -сгенерированные парсеры для заметного ускорения подхода рекурсивного спуска к синтаксическому анализу выражений.[1]

Метод восхождения по приоритету

Метод восхождения по приоритету - это компактный, эффективный и гибкий алгоритм синтаксического анализа выражений, который впервые был описан Мартином Ричардсом и Колином Уитби-Стревенсом.[2]

Грамматика выражения инфиксной записи в EBNF формат обычно выглядит так:

выражение ::= выражение-равенствовыражение-равенство ::= аддитивное выражение ( ( '==' | '!=' ) аддитивное выражение ) *аддитивное выражение ::= мультипликативное выражение ( ( '+' | '-' ) мультипликативное выражение ) *мультипликативное выражение ::= первичный ( ( '*' | '/' ) первичный ) *первичный ::= '(' выражение ')' | КОЛИЧЕСТВО | ПЕРЕМЕННАЯ | '-' первичный

При многих уровнях приоритета реализация этой грамматики с помощью синтаксического анализатора с прогнозирующим рекурсивным спуском может стать неэффективной. Например, для анализа числа может потребоваться пять вызовов функций: по одному для каждого нетерминального элемента в грамматике до достижения первичный.

Парсер приоритета операторов может сделать то же самое более эффективно.[1] Идея состоит в том, что мы можем оставить ассоциировать арифметические операции, пока мы находим операторы с таким же приоритетом, но мы должны сохранить временный результат для оценки операторов с более высоким приоритетом. Представленный здесь алгоритм не требует явного стека; вместо этого он использует рекурсивные вызовы для реализации стека.

Алгоритм не является чистым синтаксическим анализатором приоритета операторов, как алгоритм маневровой станции Дейкстры. Предполагается, что первичный нетерминал анализируется в отдельной подпрограмме, как в парсере рекурсивного спуска.

Псевдокод

Псевдокод для алгоритма следующий. Парсер начинается с функции parse_expression. Уровни приоритета больше или равны 0.

parse_expression () вернуть parse_expression_1 (parse_primary (), 0)
parse_expression_1 (lhs, min_precedence) смотреть вперед : = посмотреть следующий токен в то время как смотреть вперед бинарный оператор с приоритетом> = min_precedence        op := смотреть вперед        перейти к следующему токену rhs := parse_primary ()        смотреть вперед : = посмотреть следующий токен в то время как смотреть вперед бинарный оператор, приоритет которого больше, чем op's, или правоассоциативный оператор, приоритет которого равен op 's rhs := parse_expression_1 (rhs, приоритет просмотра вперед) смотреть вперед : = посмотреть следующий токен lhs : = результат применения op с операндами 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) и ввод расширен
  • rhs 3 года
  • лексема просмотра вперед - *, с приоритетом 2. вход во внутренний цикл while.
    parse_expression_1 (lhs = 3, min_precedence = 2)
  • лексема просмотра вперед - *, с приоритетом 2. вводится внешний цикл while.
  • op равно * (приоритет 2) и ввод расширен
  • rhs это 4
  • следующий токен - +, с приоритетом 1. внутренний цикл while не вводится.
  • lhs присваивается 3 * 4 = 12
  • следующий токен + с приоритетом 1. внешний цикл while остается.
  • 12 возвращается.
  • лексема просмотра вперед - +, с приоритетом 1. внутренний цикл while не вводится.
  • lhs присваивается 2 + 12 = 14
  • маркер просмотра вперед равен + с приоритетом 1. внешний цикл while не остается.
  • op равно + (приоритет 1) и ввод расширен
  • rhs 5 лет
  • следующий токен == с приоритетом 0. внутренний цикл while не вводится.
  • lhs присваивается 14 + 5 = 19
  • следующий токен ==, с приоритетом 0. Внешний цикл while не остается.
  • op == (приоритет 0) и ввод расширен
  • rhs 19 лет
  • следующий токен конец линии, который не является оператором. внутренний цикл while не вводится.
  • lhs присваивается результат оценки 19 == 19, например 1 (как в стандарте C).
  • следующий токен конец линии, который не является оператором. внешний цикл while остается.

1 возвращается.

Анализ Пратта

Другой синтаксический анализатор приоритета, известный как синтаксический анализ Пратта, был впервые описан Воном Праттом в статье 1973 г. «Приоритет операторов сверху вниз».[3], на основе рекурсивный спуск. Хотя это восхождение предшествует старшинству, его можно рассматривать как обобщение предшествующего лазания. [4]

Первоначально Пратт разработал парсер для реализации CGOL язык программирования, и он был рассмотрен более подробно в магистерской диссертации под его руководством.[5]

Учебники и реализации:

Альтернативные методы

Есть и другие способы применения правил приоритета операторов. Один из них - построить дерево исходного выражения, а затем применить к нему правила перезаписи дерева.

Такие деревья не обязательно должны быть реализованы с использованием структур данных, обычно используемых для деревьев. Вместо этого токены можно хранить в плоских структурах, таких как таблицы, путем одновременного создания списка приоритетов, в котором указывается, какие элементы в каком порядке обрабатывать.

Другой подход состоит в том, чтобы сначала полностью заключить выражение в круглые скобки, вставив ряд круглых скобок вокруг каждого оператора, чтобы они приводили к правильному приоритету даже при анализе с помощью линейного синтаксического анализатора слева направо. Этот алгоритм использовался в раннем FORTRAN I компилятор:[7]

Компилятор Fortran I расширил бы каждый оператор последовательностью круглых скобок. В упрощенной форме алгоритма это было бы

  • заменять + и – с ))+(( и ))-((соответственно;
  • заменять * и / с )*( и )/(соответственно;
  • Добавить (( в начале каждого выражения и после каждой левой круглой скобки в исходном выражении; и
  • Добавить )) в конце выражения и перед каждой правой круглой скобкой в ​​исходном выражении.

Хотя это и не очевидно, алгоритм был правильным, и, по словам Knuth, «Полученная формула правильно заключена в круглые скобки, хотите верьте, хотите нет».[8]

Пример кода простого приложения на C, которое обрабатывает скобки для основных математических операторов (+, -, *, /, ^, ( и )):

#включают <stdio.h>#включают <string.h>int основной(int argc, char *argv[]) {  int я;  printf("((((");  за (я=1;я!=argc;я++) {    если (argv[я] && !argv[я][1]) {      переключатель (*argv[я]) {          кейс '(': printf("(((("); Продолжать;          кейс ')': printf("))))"); Продолжать;          кейс '^': printf(")^("); Продолжать;          кейс '*': printf("))*(("); Продолжать;          кейс '/': printf("))/(("); Продолжать;          кейс '+':            если (я == 1 || strchr("(^*/+-", *argv[я-1]))              printf("+");            еще              printf(")))+(((");            Продолжать;          кейс '-':            если (я == 1 || strchr("(^*/+-", *argv[я-1]))              printf("-");            еще              printf(")))-(((");            Продолжать;      }    }    printf("% s", argv[я]);  }  printf(")))) п");  вернуть 0;}

Например, при компиляции и вызове из командной строки с параметрами

а * б + с ^ г / д

он производит

((((a)) * ((b))) + (((c) ^ (d)) / ((e))))

как вывод на консоль.

Ограничением этой стратегии является то, что унарные операторы должны иметь более высокий приоритет, чем инфиксные. «Отрицательный» оператор в приведенном выше коде имеет более высокий приоритет, чем возведение в степень. Запуск программы с этим входом

- а ^ 2

производит этот вывод

((((-a) ^ (2))))

что, вероятно, не то, что задумано.

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

  1. ^ а б Харвелл, Сэм (29 августа 2008 г.). "Парсер приоритета операторов". ANTLR3 Вики. Получено 2017-10-25.
  2. ^ Ричардс, Мартин; Уитби-Стревенс, Колин (1979). BCPL - язык и его компилятор. Издательство Кембриджского университета. ISBN  9780521219655.
  3. ^ Пратт, Воган. "Приоритет оператора сверху вниз." Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (1973).
  4. ^ Норвелл, Теодор. «Анализ выражений методом рекурсивного спуска». www.engr.mun.ca. Цель этого поста - [... начать] восхождение по приоритетам и его рефакторинг для использования шаблона команд, пока мы не дойдем до синтаксического анализатора Pratt. [Это автор, который ввел термин «восхождение по старшинству».]
  5. ^ Ван Де Вантер, Майкл Л. "Формализация и подтверждение правильности языковой системы CGOL. »(Магистерская диссертация). Технический отчет лаборатории компьютерных наук Массачусетского технологического института MIT-LCS-TR-147 (Кембридж, Массачусетс). 1975.
  6. ^ Крокфорд, Д. (21 февраля 2007 г.). «Приоритет оператора сверху вниз».
  7. ^ Падуя, Дэвид (2000). "Компилятор Fortran I" (PDF). Вычислительная техника в науке и технике. 2 (1): 70–75. Bibcode:2000CSE ..... 2a..70P. Дои:10.1109/5992.814661.
  8. ^ Кнут, Дональд Э. (1962). "ИСТОРИЯ ПИСАТЕЛЕЙ КОМПИЛЯТОРОВ". Компьютеры и автоматика. Эдмунд С. Беркли. 11 (12): 8–14.

внешняя ссылка