LL(1) grammar
The first ‘L’ in LL(1) stands for scanning the input from left to right, the second ‘L’ stands for producing a leftmost derivation, and the ‘1’ for using one input symbol of lookahead at each step to make parsing action decisions. LL(1) grammar follows Top-down parsing method. For a class of grammars called LL(1) we can construct grammars predictive parser. That works on the concept of recursive-descent parser not requiring backtracking.
Elimination of Left Recursion
A grammar is left recursive if it has a nonterminal A such that there is a derivation A → A α | β. Top-down parsing methods cannot handle left-recursive grammars, so a transformation is needed to eliminate left recursion. Left recursion can be eliminated by modifying the rule as follows: (A’ is new non-terminal and ε is representing epsilon).
A → β A’ A’ → α A’ | ε
Left Factoring
It is a grammar transformation that is useful for producing grammar suitable for predictive or top-down parsing. When the choice between two alternative productions is not clear, we rewrite the productions to defer the decision to make the right choice.
For example, if we have grammar rule A → α β1 | α β2 A → α A’ A’ → β1 | β2
Compiler Design LL(1) Parser in Python
Prerequisite: Construction of LL(1) Parsing Table, Classification of top-down parsers, FIRST Set, FOLLOW Set
In this article, we are going to see how to design LL(1) Parser compiler using Python.
Contact Us