Download project documentation

3.8.2 Left Factoring Tool
Left Factoring Tool
Scanning
Tokens
Parsing
Building the Syntax Tree
Left Factoring
Generating Output File
Figure III-9: Left Factoring Tool
Left factoring is an algorithm required when two or more grammar rule choices
(productions) share a common prefix string. For example;
Before Left-Factoring : A → B C | B D
After Left-Factoring : A → B A1
A1 → C | D
3.8.2.1 The Input
The input of this tool is considered to be a valid LL(1) parser specification file. If the
file contains errors the tool will inform the developer that the file contains errors and
will exit.
3.8.2.2 The Output
The output is a new specification file containing the left-factored grammar, which
may be the same as the input grammar if no common prefixes exist.
Some phases (such as the scanning and the parsing phase) illustrated above have been
already explained, so we will skip these two phases and we will focus on the "Left
Factoring" and "Generating Output File" phases.