Рекурсивный парсер восхождения

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

Рекурсивное восхождение было впервые описано Томасом Пеннелло в его статье. Пеннелло, Томас Дж. (1986). «Очень быстрый анализ LR» . Материалы симпозиума SIGPLAN 1986 года по построению компилятора - SIGPLAN '86 . стр. 145–151. дои : 10.1145/12276.13326 . ISBN 0897911970 . S2CID 17214407 . в 1986 году. Он намеревался создать не редактируемую вручную реализацию парсера LR, а скорее удобный в сопровождении и эффективный парсер, реализованный на языке ассемблера . Позднее эта техника была объяснена Г.Х. Робертсом. ^[2] в 1988 году, а также в статье Леермейкеров, Огюстайна, Круземана Ареца. ^[3] в 1992 году в журнале Theoretical Computer Science . Чрезвычайно читабельное описание техники написали Морелл и Миддлтон. ^[4] в 2003 году. Хорошее изложение можно также найти в статье Спербера и Тимана в TOPLAS. ^[5]

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

Краткое содержание

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

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

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

Пример

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

expr : expr '+' term   { $$ = $1 + $3; }
     | expr '-' term   { $$ = $1 - $3; }
     | term            { $$ = $1; }
     ;

term : '(' expr ')'    { $$ = $2; }
     | num             { $$ = $1; }
     ;

num : '0'              { $$ = 0; }
    | '1'              { $$ = 1; }
    ;

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

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

object ExprParser {
  private type Result = (NonTerminal, Int)
  
  private sealed trait NonTerminal {
    val v: Int
  }
  
  private case class NTexpr(v: Int, in: Stream[Char]) extends NonTerminal
  private case class NTterm(v: Int, in: Stream[Char]) extends NonTerminal
  private case class NTnum(v: Int, in: Stream[Char]) extends NonTerminal
  
  class 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, and go to state 1
   * '0'  shift, and go to state 2
   * '1'  shift, and go to state 3
   *
   * expr  go to state 4
   * term  go to state 5
   * num   go to state 6
   */
  private def state0(in: Stream[Char]) = in match {
    case cur #:: tail => {
      def loop(tuple: Result): Result = {
        val (res, goto) = tuple
        
        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)
      }
      
      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 term: '(' . expr ')'
   *
   * '('  shift, and go to state 1
   * '0'  shift, and go to state 2
   * '1'  shift, and go to state 3
   *
   * expr  go to state 7
   * term  go to state 5
   * num   go to state 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)
      }
      
      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
  }
  
  /*
   * 6 num: '0' .
   *
   * $default  reduce using rule 6 (num)
   */
  private def state2(in: Stream[Char]) = (NTnum(0, in), 0)
  
  /*
   * 7 num: '1' .
   *
   * $default  reduce using rule 7 (num)
   */
  private def state3(in: Stream[Char]) = (NTnum(1, in), 0)
  
  /*
   * 0 $accept: expr . $end
   * 1 expr: expr . '+' term
   * 2     | expr . '-' term
   *
   * $end  shift, and go to state 8
   * '+'   shift, and go to state 9
   * '-'   shift, and go to state 10
   */
  private def state4(in: Stream[Char], arg1: Int): Result = in match {
    case cur #:: tail => {
      decrement(cur match {
        case '+' => state9(tail, arg1)
        case '-' => state10(tail, arg1)
        case c => throw new ParseException(c)
      })
    }
    
    case Stream() => state8(arg1)
  }
  
  /*
   * 3 expr: term .
   *
   * $default  reduce using rule 3 (expr)
   */
  private def state5(in: Stream[Char], arg1: Int) = (NTexpr(arg1, in), 0)
  
  /*
   * 5 term: num .
   *
   * $default  reduce using rule 5 (term)
   */
  private def state6(in: Stream[Char], arg1: Int) = (NTterm(arg1, in), 0)
  
  /*
   * 1 expr: expr . '+' term
   * 2     | expr . '-' term
   * 4 term: '(' expr . ')'
   *
   * '+'  shift, and go to state 9
   * '-'  shift, and go to state 10
   * ')'  shift, and go to state 11
   */
  private def state7(in: Stream[Char], arg1: Int): Result = in match {
    case cur #:: tail => {
      decrement(cur match {
        case '+' => state9(tail, arg1)
        case '-' => state10(tail, arg1)
        case ')' => state11(tail, arg1)
        case c => throw new ParseException(c)
      })
    }
    
    case Stream() => throw new ParseException
  }
  
  /*
   * 0 $accept: expr $end .
   *
   * $default  accept
   */
  private def state8(arg1: Int) = (NTexpr(arg1, Stream()), 1)
  
  /*
   * 1 expr: expr '+' . term
   *
   * '('  shift, and go to state 1
   * '0'  shift, and go to state 2
   * '1'  shift, and go to state 3
   *
   * term  go to state 12
   * num   go to state 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)
      }
      
      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
  }
  
  /*
   * 2 expr: expr '-' . term
   *
   * '('  shift, and go to state 1
   * '0'  shift, and go to state 2
   * '1'  shift, and go to state 3
   *
   * term  go to state 13
   * num   go to state 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 term: '(' expr ')' .
   *
   * $default  reduce using rule 4 (term)
   */
  private def state11(in: Stream[Char], arg1: Int) = (NTterm(arg1, in), 2)
  
  /*
   * 1 expr: expr '+' term .
   *
   * $default  reduce using rule 1 (expr)
   */
  private def state12(in: Stream[Char], arg1: Int, arg2: Int) = (NTexpr(arg1 + arg2, in), 2)
  
  /*
   * 2 expr: expr '-' term .
   *
   * $default  reduce using rule 2 (expr)
   */
  private def state13(in: Stream[Char], arg1: Int, arg2: Int) = (NTexpr(arg1 - arg2, in), 2)
  
  private def decrement(tuple: Result) = {
    val (res, goto) = tuple
    assert(goto != 0)
    (res, goto - 1)
  }
}

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

state(S), [S] --> [S].
state(S0, S), [S] --> [S0].


/*
    0. S --> E$
    1. E --> E + T
    2. E --> E - T
    3. E --> T
    4. T --> (E)
    5. T --> N
    6. N --> 0
    7. N --> 1
*/
accept --> state(s([], [e(_)])).
r(1) --> state(s(Ts, [t(A1), '+', e(A0)|Ss]), s(Ts, [e(A0+A1)|Ss])).
r(2) --> state(s(Ts, [t(A1), '-', e(A0)|Ss]), s(Ts, [e(A0-A1)|Ss])).
r(3) --> state(s(Ts, [t(A)|Ss]), s(Ts, [e(A)|Ss])).
r(4) --> state(s(Ts, [')', e(A), '('|Ss]), s(Ts, [t(A)|Ss])).
r(5) --> state(s(Ts, [n(A)|Ss]), s(Ts, [t(A)|Ss])).
r(6) --> state(s(Ts, ['0'|Ss]), s(Ts, [n(0)|Ss])).
r(7) --> state(s(Ts, ['1'|Ss]), s(Ts, [n(1)|Ss])).
t(T) --> state(s([T|Ts], Ss), s(Ts, [T|Ss])).


/*
    S --> .E$
    E --> .E + T
    E --> .E - T
    E --> .T
    T --> .(E)
    T --> .N
    N --> .0
    N --> .1
*/
s0 --> t('('), s3, s2, s1.
s0 --> t('0'), s11, s10, s2, s1.
s0 --> t('1'), s12, s10, s2, s1.

/*
    S --> E.$
    E --> E. + T
    E --> E. - T
*/
s1 --> accept.
s1 --> t('+'), s7, s1.
s1 --> t('-'), s8, s1.

/*
    E --> T.
*/
s2 --> r(3).

/*
    T --> (.E)
    E --> .E + T
    E --> .E - T
    E --> .T
    T --> .(E)
    T --> .N
    N --> .0
    N --> .1
*/
s3 --> t('('), s3, s2, s4.
s3 --> t('0'), s11, s10, s2, s4.
s3 --> t('1'), s12, s10, s2, s4.

/*
    T --> (E.)
    E --> E .+ T
    E --> E .- T
*/
s4 --> t(')'), s9.
s4 --> t('+'), s7, s4.
s4 --> t('-'), s8, s4.

/*
    E --> E + T.
*/
s5 --> r(1).

/*
    E --> E - T.
*/
s6 --> r(2).

/*
    E --> E + .T
    T --> .(E)
    T --> .N
    N --> .0
    N --> .1
*/
s7 --> t('('), s3, s5.
s7 --> t('0'), s11, s10, s5.
s7 --> t('1'), s12, s10, s5.

/*
    E --> E - .T
    T --> .(E)
    T --> .N
    N --> .0
    N --> .1
*/
s8 --> t('('), s3, s6.
s8 --> t('0'), s11, s10, s6.
s8 --> t('1'), s12, s10, s6.

/*
    T --> (E).
*/
s9 --> r(4).

/*
    T --> N.
*/
s10 --> r(5).

/*
    N --> '0'.
*/
s11 --> r(6).

/*
    N --> '1'.
*/
s12 --> r(7).

parser(Cs, T) :-
    length(Cs, _),
    phrase(s0, [s(Cs, [])], [s([], [e(T)])]).

% state(S0, S), [S] --> [S0, S].
%?- S0 = [s("(1+1)", [])|_], phrase(s0, S0, [S]), maplist(portray_clause, S0).

См. также

Парсер рекурсивного спуска

Ссылки

^ Томас Дж. Пенелло (1986). «Очень быстрый анализ LR» . Уведомления ACM SIGPLAN . 21 (7): 145–151. дои : 10.1145/13310.13326 .
^ Г.Х. Робертс (1988). «Рекурсивный подъем: LR-аналог рекурсивного спуска» . Уведомления ACM SIGPLAN . 23 (8): 23–29. дои : 10.1145/47907.47909 . S2CID 12740771 .
^ Леермейкерс, Огюстейн, Круземан Арец (1992). «Функциональный парсер LR» . Теоретическая информатика . 104 (2): 313–323. дои : 10.1016/0304-3975(92)90128-3 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Ларри Морелл и Дэвид Миддлтон (2003). «Рекурсивно-восходящий синтаксический анализ» . Журнал компьютерных наук в колледжах . Том. 18, нет. 6. С. 186–201.
^ Спербер и Тиманн (2000). «Генерация парсеров LR путем частичной оценки» . Транзакции ACM в языках и системах программирования . 22 (2): 224–264. дои : 10.1145/349214.349219 . S2CID 14955687 .
^ Джон Бойланд и Дэниел Спивак (2009). «Генератор рекурсивного анализатора восходящего-спуска ScalaBison» (PDF) . Архивировано из оригинала (PDF) 18 июля 2009 г.

[1] Томас Дж. Пенелло (1986). «Очень быстрый анализ LR» . Уведомления ACM SIGPLAN . 21 (7): 145–151. дои : 10.1145/13310.13326 .

[2] Г.Х. Робертс (1988). «Рекурсивный подъем: LR-аналог рекурсивного спуска» . Уведомления ACM SIGPLAN . 23 (8): 23–29. дои : 10.1145/47907.47909 . S2CID 12740771 .

[3] Леермейкерс, Огюстейн, Круземан Арец (1992). «Функциональный парсер LR» . Теоретическая информатика . 104 (2): 313–323. дои : 10.1016/0304-3975(92)90128-3 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[4] Ларри Морелл и Дэвид Миддлтон (2003). «Рекурсивно-восходящий синтаксический анализ» . Журнал компьютерных наук в колледжах . Том. 18, нет. 6. С. 186–201.

[5] Спербер и Тиманн (2000). «Генерация парсеров LR путем частичной оценки» . Транзакции ACM в языках и системах программирования . 22 (2): 224–264. дои : 10.1145/349214.349219 . S2CID 14955687 .

[6] Джон Бойланд и Дэниел Спивак (2009). «Генератор рекурсивного анализатора восходящего-спуска ScalaBison» (PDF) . Архивировано из оригинала (PDF) 18 июля 2009 г.

[1]

[2]

[3]

[4]

[5]

[6]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов