Content deleted Content added
m clean up, References after punctuation per WP:REFPUNC and WP:PAIC using AWB (8748) |
avoid unnec redirect, link scope |
||
| (19 intermediate revisions by 18 users not shown) | |||
Line 1:
In [[computer science]], '''recursive ascent parsing''' is a technique for implementing an [[
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.
Line 35:
The following is a [[Scala (programming language)|Scala]] implementation of a recursive ascent parser based on the above grammar:
<
object ExprParser {
private type Result = (NonTerminal, Int)
Line 302:
}
}
</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]]
| |||