Рекурсивный анализатор подъема

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

Рекурсивное восхождение было впервые описано Томасом Пенелло в его статье «Очень быстрый LR-анализ». в 1986 году. Он не собирался создавать редактируемую вручную реализацию анализатора LR, а скорее обслуживаемого и эффективного парсера, реализованного на языке ассемблера. Позже эта техника была изложена Г. Робертс в 1988 г., а также в статье Лермакерса, Аугустейна, Круземана Аретца в 1992 г. в журнале «Теоретическая информатика». Чрезвычайно удобочитаемое описание техники было написано Мореллом и Миддлтоном в 2003 году. Хорошее изложение можно также найти в статье Спербера и Тимана в TOPLAS.

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

• 1 Резюме
• 2 Пример
• 3 См. Также
• 4 Ссылки

Интуитивно понятно, Рекурсивное восхождение - это буквальная реализация концепции LR parsing. Каждая функция в синтаксическом анализаторе представляет отдельное состояние LR автомата. Внутри каждой функции оператор с несколькими ветвями используется для выбора соответствующего действия на основе текущего токена, извлеченного из входного стека. После идентификации токена предпринимаются действия в зависимости от кодируемого состояния. Существуют два различных основных действия, которые могут быть предприняты на основе рассматриваемого токена:

• Shift - закодировано как вызов функции, эффективно переходя в новое состояние автомата.
• Reduce - закодировано по-разному в зависимости от к подпрограмме семантического действия для соответствующего production. Результат этой процедуры упаковывается в ADT, который возвращается вызывающей стороне. Действие сокращения также должно записывать количество токенов, которые были сдвинуты до уменьшения, передавая это значение обратно вызывающей стороне вместе со значением уменьшения. Этот счетчик сдвига определяет, в какой точке стека вызовов следует обработать сокращение.

Существует также третье действие автомата LR, которое может быть предпринято в данном состоянии, но только после уменьшения, когда счетчик сдвига уменьшился до нуля. (указывая, что текущее состояние должно обрабатывать результат). Это действие goto, которое по сути является частным случаем shift, предназначенным для обработки нетерминалов в производстве. Это действие необходимо обрабатывать после оператора multi-branch, так как именно здесь любые результаты сокращения будут «всплывать» дальше вниз по стеку вызовов.

Рассмотрим следующую грамматику в синтаксисе bison :

expr: expr '+' term {$$ = $ 1 + $ 3; } | expr '-' термин {$$ = $ 1 - $ 3; } | термин {$$ = $ 1; }; термин: '(' выражение ')' {$$ = $ 2; } | число {$$ = $ 1; }; число: '0' {$$ = 0; } | '1' {$$ = 1; };

Эта грамматика LR (0) в том смысле, что она леворекурсивна (в expr нетерминальном), но не требует никакого просмотра вперед. Рекурсивное восхождение также способно обрабатывать грамматики, которые являются LALR (1), во многом таким же образом, как управляемые таблицами синтаксические анализаторы обрабатывают такие случаи (путем предварительного вычисления разрешения конфликтов на основе возможного опережающего просмотра).

Ниже приводится реализация Scala рекурсивного синтаксического анализатора восходящего движения на основе приведенной выше грамматики:

объект ExprParser {частный тип Результат = (NonTerminal, Int) частный запечатанный признак NonTerminal {val v: Int} класс частного случая NTexpr (v: Int, in: Stream [Char]) расширяет класс частного случая NonTerminal NTterm (v: Int, in: Stream [Char]) расширяет класс частного случая NonTerminal NTnum (v: Int, in : Stream [Char]) расширяет класс NonTerminal ParseException (msg: String) extends RuntimeException (msg) {def this () = this ("") def this (c: Char) = this (c.toString)} def parse (in : Stream [Char]) = state0 (in)._ 1.v / * * 0 $ accept:. expr $ end * * '(' shift и перейти в состояние 1 * '0' shift и перейти в состояние 2 * '1' shift и перейти в состояние 3 * * expr перейти в состояние 4 * term перейти в состояние 5 * num перейти в состояние 6 * / private def state0 (in: Stream [Char]) = in match {case cur # :: tail =>{def loop (tuple: Result): Result = {val (res, goto) = кортеж if (goto == 0) {loop (res match {case NTexpr (v, in) =>state4 (in, v) case NTterm (v, in) =>state5 (in, v) case NTnum (v, in)) =>state6 (in, v)})} else (res, goto - 1)} цикл (cur match {case '(' =>state1 (tail) case '0' =>state2 (tail) case '1') =>state3 (tail) case c =>throw new ParseException (c)})} case Stream () =>throw new ParseException} / * * 4 термин: '('. expr ')' * * '(' shift, и перейти в состояние 1 * '0' shift, и перейти в состояние 2 * '1' shift, и перейти в состояние 3 * * expr перейти в состояние 7 * term перейти в состояние 5 * num перейти в состояние 6 * / private def state1 (in: Stream [Char]): Result = in match {case cur # :: tail =>{def loop (tuple: Result): Result = {val (res, goto) = tuple if (goto == 0) {loop (res match {case NTexpr (v, in) =>state7 (in, v) case NTterm (v, in) =>state5 (in, v) case NTnum (v, in) =>state6 (in, v)})} else (res, goto - 1)} цикл (cur match {case '(' =>state1 (tail) case '0' =>state2 (tail) case '1' =>state3 (tail) case c =>throw new ParseException (c)})} case Stream () =>throw new ParseException} / * * 6 число: '0'. * * $ default уменьшить с использованием правила 6 (num) * / private def state2 (in: Stream [Char]) = (NTnum (0, in), 0) / * * 7 num: '1'. * * $ default уменьшить с использованием правила 7 (num) * / private def state3 (in: Stream [Char]) = (NTnum (1, in), 0) / * * 0 $ accept: expr. $ end * 1 expr: expr. '+' термин * 2 | выраж. '-' term * * $ end shift и перейти в состояние 8 * '+' shift и перейти в состояние 9 * '-' shift и перейти в состояние 10 * / private def state4 (in: Stream [Char], arg1: Int): Result = in match {case cur # :: tail =>{декремент (cur match {case '+' =>state9 (tail, arg1) case '-' =>state10 (tail, arg1) case c =>выбросить новое исключение ParseException (c)})} case Stream () =>state8 (arg1)} / * * 3 expr: term. * * $ default уменьшить с использованием правила 3 ​​(expr) * / private def state5 (in: Stream [Char], arg1: Int) = (NTexpr (arg1, in), 0) / * * 5 term: num. * * $ default уменьшить с использованием правила 5 (термин) * / private def state6 (in: Stream [Char], arg1: Int) = (NTterm (arg1, in), 0) / * * 1 expr: expr. '+' термин * 2 | выраж. '-' term * 4 term: '(' expr. ')' * * '+' shift и перейти в состояние 9 * '-' shift и перейти в состояние 10 * ')' shift и перейти в состояние 11 * / private def state7 (in: Stream [Char], arg1: Int): Result = in match {case cur # :: tail =>{декремент (cur match {case '+' =>state9 (tail, arg1) case '-' =>state10 (tail, arg1) case ')' =>state11 (tail, arg1) case c =>throw new ParseException (c)})} case Stream () =>выбросить новое исключение ParseException} / * * 0 $ accept: expr $ end. * * $ default accept * / private def state8 (arg1: Int) = (NTexpr (arg1, Stream ()), 1) / * * 1 expr: expr '+'. term * * '(' shift и перейти в состояние 1 * '0' shift и перейти в состояние 2 * '1' shift и перейти в состояние 3 * * term перейти в состояние 12 * num перейти в состояние 6 * / private def state9 (in: Stream [Char], arg1: Int) = in match {case cur # :: tail =>{def loop (tuple: Result): Result = {val (res, goto) = tuple if (goto == 0) {loop (res match {case NTterm (v, in) =>state12 (in, arg1, v) case NTnum (v, in) =>state6 (in, v) case _ =>throw new AssertionError}))} else (res, goto - 1)} цикл (cur match {case '(' =>state1 (tail) case '0' =>state2 (tail) case '1' =>state3 (tail) case c =>throw new ParseException (c)})} case Stream () =>throw new ParseException} / * * 2 expr: expr '-'. term * * '(' shift и перейти в состояние 1 * '0' shift, и перейти в состояние 2 * сдвиг '1' и перейти в состояние 3 * * срок перейти в состояние 13 * число перейти в состояние 6 * / private def state10 (in: Stream [Char], arg1: Int) = in match {case cur # :: tail =>{def loop (tuple: Result): Result = {val (res, goto) = tuple if (goto == 0) {loop (res match {case NTterm (v, in) =>state13 (in, arg1, v) case NTnum (v, in) =>state6 (in, v) case _ =>throw new AssertionError})} else (res, goto - 1)} loop (cur match {case '(' =>state1 (tail) case '0' =>state2 (tail) case '1' =>state3 (tail) case c =>throw new ParseException (c)})} case Stream () =>throw new ParseException} / * * 4 термин: '(' expr ')'. * * $ default уменьшить с использованием правила 4 (термин) * / private def state11 (in: Stream [Char], arg1: Int) = (NTterm (arg1, in), 2) / * * 1 expr: expr '+' term. * * $ default уменьшить с использованием правила 1 (expr) * / private def state12 (in: Stream [Char], arg1: Int, arg2: Int) = (NTexpr (arg1 + arg2, in), 2) / * * 2 expr : expr '-' срок. * * $ default уменьшить с использованием правила 2 (expr) * / private def state13 (in: Stream [Char], arg1: Int, arg2: Int) = (NTexpr (arg1 - arg2, in), 2) private def декремент (кортеж : Result) = {val (res, goto) = tuple assert (goto! = 0) (res, goto - 1)}}

• Анализатор рекурсивного спуска