Content deleted Content added
→Generating a parse tree: corrected reference style. |
|||
Line 78:
==Extensions==
===Generating a parse tree===
The above algorithm is a [[recognizer]] that will only determine if a sentence is in the language. It is simple to extend it into a [[parser]] that also construct a [[parse tree]], by storing parse tree nodes as elements of the array, instead of booleans. Since the parsing process generates also unneeded subtrees that cannot be immediately known as such, it is necessary to store a list of of potential subtree roots (at list ome for each possible non-terminal, even if one wishes to only pick only one of the possible parse trees); the end result is then a shared-forest of possible parse trees. This shared forest can conveniently be read as a grammar generating only the sentence parsed, with any of the parse-trees corresponding to the original grammar, up to a very simple renaming of non-terminals
An alternative formulation employs a second table B[n,n,r] of so-called ''backpointers''.
| |||