The Parsing Problem
Determine if a string of tokens can be generated by a grammar.
A grammar is expressed using rules named productions.
Productions are built from terminal and nonterminal symbols.
The terminal symbols are the tokens returned by the lexical analyser.
Every nonterminal symbol has a production that defines it in terms of other terminal and nonterminal symbols.
The Parsing Problem:
- Using the grammar rules, construct a parse tree that connects the root nonterminal with a tokenized input sentence.
- May start at the root (Top-Down parsing), or at the leaves (Bottom-Up parsing).
- Sentence is syntactically correct if the tree can be constructed.