LL(1) table generator

Abstract

Predictive parsers, that is, recursive-descent parsers needing no backtracking, can be constructed for a class of grammars called LL(1). The first "L" in LL(1) stands for scanning the input from left to rigth, the second "L" for producing a leftmost derivation, and the "1" for using one input symbol of lookahead at each step to make parsing action decisions[1].

The class of LL(1) grammars is rich enough to cover most programming constructs, although care is needed in writing a suitable grammar for the source language. For example, no left-recursive or ambiguous grammar can be LL(1)[1].

How to use it

Execute linux commands in the following order:

• g++ generador_tablas_LL1_linux.cpp : compiles .cpp file
• ./a.out : runs the compiled file
• paste input and hit enter
• Open report.html (if generated) in preferred browser

NOTE: If the given grammar is not LL(1) report.html won't be generated, and console will display a warning message

LL(1) Table Generator

Input

5 4
goal -> A
A -> ( A )
A -> two
two -> a
two -> b
( ( a ) )
( a ) )
( ( ( ( ( b ) ) ) ) )
( ( ( ( ( a b ) ) ) ) )

Result

Image 1. Input grammar is LL(1)

Image 2. Input grammar is no LL(1)

Firsts and Follows Generator

In order to get the exact output uncomment lines 1348 and 1349 from generador_tablas_LL1_linux.cpp.

Input

5 4
goal -> A
A -> ( A )
A -> two
two -> a
two -> b
( ( a ) )
( a ) )
( ( ( ( ( b ) ) ) ) )
( ( ( ( ( a b ) ) ) ) )

Result

Image 3. Input grammar Firsts and Follows

Terminals and Nonterminals Generator

In order to get the exact output uncomment lines 1345, 1346 and 1347 from generador_tablas_LL1_linux.cpp.

Input

5 4
goal -> A
A -> ( A )
A -> two
two -> a
two -> b
( ( a ) )
( a ) )
( ( ( ( ( b ) ) ) ) )
( ( ( ( ( a b ) ) ) ) )

Result

Image 4. Input grammar Terminals and Nonterminals

References

[1]Aho, A., 2007. Compilers. 2nd ed. Boston: Pearson/Addison Wesley.