Example
lConsider the grammar
with start symbol S:
lS ¨ V + S | V
lV ¨ a | b |
c
lThe parse begins by
trying to identify the entire input string as being in syntactic category S.
lClearly it must find
a V to start.
lTo find a V, it checks to see
whether the next symbol is one of those listed.
lHaving found a V, it
checks to see if the next symbol is +.
lIf so, it recurses, trying to
find another S.
lIf not it stops.
lAfter the top call to
S returns, it checks to see whether there are any spurious remaining characters in the input.
lIf there are, the input is
not accepted.
lIf not, the input is
accepted.