| << Prev | - Up - | Next >> |
The primary job of a parser/recognizer is to determine whether a sequence of terminal categories can be generated by the rules of the grammar. Bottom-up parsing is based on the idea of applying rules in reverse: i. e. given a rule C -> C1 ... Cn, we can replace by C any sequence of categories matching C1 ... Cn. This is a non-deterministic process (choice of rule, choice of subsequence) which we can iterate. If by repeated applications of rules in reverse, we can arrive at a sequence of length 1 containing a single category C, we have recognized C.
Let's illustrate the process on the sequence john sees the man. Given (lexical) rules recognizing the terminals:
PN -> john
VT -> sees
DET -> the
N -> man the sequence can be rewriten PN VT DET N. Then we can recognize the two noun phrases:
NP -> DET N
NP -> PN obtaining NP VT NP. Then the verb phrase:
VP -> VT NP obtaining NP VP. And finally a whole sentence:
S -> NP VP Arriving at the singleton sequence S. Thus, we have recognized S.
| << Prev | - Up - | Next >> |