Content deleted Content added
→Example: Removed original research warning, since the challenge was answered and never rebutted on the talk page |
avoid unnec redirect, link scope |
||
| (29 intermediate revisions by 26 users not shown) | |||
Line 1:
Recursive ascent was first described by Thomas
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.<ref>{{cite web|title=ScalaBison
== Summary ==
Intuitively, recursive ascent is a literal implementation of the [[LR parser|LR parsing]] concept. Each function in the parser represents a single LR [[Finite
* '''Shift''' - Encoded as a function call, effectively jumping to a new automaton state.
* '''Reduce''' - Encoded differently according to the [[semantic action routine]] for the relevant [[Formal grammar#The syntax of grammars|production]]. The result of this routine is wrapped in an [[Algebraic data type|ADT]] which is returned to the caller. The reduce action must also record the number of tokens which were shifted ''prior'' to the reduce, passing this value back to the caller along with the reduce value. This shift counter determines at which point up the call stack the reduce should be handled.
There is also a third LR automaton action which may be taken in a given state, but only after a reduce where the shift counter has decremented to zero (indicating that the current state should handle the result). This is the '''goto''' action, which is essentially a special case of '''shift''' designed to handle non-terminals in a production. This action must be handled ''after'' the multi-branch statement, since this is where any reduction results will "resurface" from farther down the call stack.
Line 31:
;</pre>
This grammar is [[LR
The following is a [[Scala (programming language)|Scala]] implementation of a recursive ascent parser based on the above grammar:
<syntaxhighlight lang="scala">
object ExprParser {
private type Result = (NonTerminal, Int)
Line 50 ⟶ 51:
def this(c: Char) = this(c.toString)
}
Line 307 ⟶ 301:
(res, goto - 1)
}
}
</syntaxhighlight>
The following is a [[Prolog]] implementation of a recursive ascent parser based on the above grammar:
<syntaxhighlight lang="prolog">
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).
</syntaxhighlight>
==See also==
* [[Recursive descent parser]]
== References ==
{{reflist}}
{{Parsers}}
[[Category:Parsing algorithms]]
| |||