Recursive ascent parser

In computer science, recursive ascent parsing is a technique for implementing an LR parser which uses mutually-recursive functions rather than tables. Thus, the parser is directly encoded in the host language similar to recursive descent. Direct encoding usually yields a parser which is faster than its table-driven equivalent for the same reason that compilation is faster than interpretation. It is also (nominally) possible to hand edit a recursive ascent parser, whereas a tabular implementation is nigh unreadable to the average human. Recursive ascent was first described by Thomas Pennello in his article in 1986. He was not intending to create a hand-editable implementation of an LR parser, but rather a maintainable and efficient parser implemented in assembly language. The technique was later expounded upon by G.H. Roberts in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz in 1992 in the journal Theoretical Computer Science. An extremely readable description of the technique was written by Morell and Middleton in 2003. A good exposition can also be found in a TOPLAS article by Sperber and Thiemann. Recursive ascent has also been merged with recursive descent, yielding a technique known as recursive ascent/descent.…

In computer science, recursive ascent parsing is a technique for implementing an LR parser which uses mutually-recursive functions rather than tables. Thus, the parser is directly encoded in the host language similar to recursive descent. Direct encoding usually yields a parser which is faster than its table-driven equivalent for the same reason that compilation is faster than interpretation. It is also (nominally) possible to hand edit a recursive ascent parser, whereas a tabular implementation is nigh unreadable to the average human. Recursive ascent was first described by Thomas Pennello in his article in 1986. He was not intending to create a hand-editable implementation of an LR parser, but rather a maintainable and efficient parser implemented in assembly language. The technique was later expounded upon by G.H. Roberts in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz in 1992 in the journal Theoretical Computer Science. An extremely readable description of the technique was written by Morell and Middleton in 2003. A good exposition can also be found in a TOPLAS article by Sperber and Thiemann. Recursive ascent has also been merged with recursive descent, yielding a technique known as recursive ascent/descent. This implementation technique is arguably easier to hand-edit due to the reduction in states and fact that some of these states are more intuitively top-down rather than bottom up. It can also yield some minimal performance improvements over conventional recursive ascent. expr : expr '+' term { $$ = $1 + $3; } | expr '-' term { $$ = $1 - $3; } | term { $$ = $1; } ; term : '(' expr ')' { $$ = $2; } | num { $$ = $1; } ; num : '0' { $$ = 0; } | '1' { $$ = 1; } ; This grammar is LR(0) in that it is left-recursive (in the expr non-terminal) but does not require any lookahead. Recursive ascent is also capable of handling grammars which are LALR(1) in much the same way that table-driven parsers handle such cases (by pre-computing conflict resolutions based on possible lookahead). The following is a Scala implementation of a recursive ascent parser based on the above grammar: 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) } } The following is a Prolog implementation of a recursive ascent parser based on the above grammar: 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).

See also

Recursive descent parser

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354867431 under CC BY-SA 4.0; modifications have been made.