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.

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

Concept of First and Follow

The construction of a top-down parser is aided by FIRST and FOLLOW functions, that are associated with a grammar G. During top-down parsing, FIRST and FOLLOW allow us to choose which production to apply, based on the next input symbol.

Rules for First computation:

1) If x is terminal, then FIRST(x)={x}

2) If X→ ε is production, then add ε to FIRST(X)

3) If X is a non-terminal and X → PQR then FIRST(X)=FIRST(P)

   If FIRST(P) contains ε, then  

        FIRST(X) = (FIRST(P) – {ε}) U FIRST(QR)

Rules for Follow computation:

Note: Epsilon (ε) can never be present in FOLLOW of any non-terminal symbol.

1) For Start symbol, place $ in FOLLOW(S)

2) If A→ α B, then FOLLOW(B) = FOLLOW(A)

3) If A→ α B β, then

  If ε not in FIRST(β),

       FOLLOW(B) = FIRST(β)

  else do,

       FOLLOW(B) = (FIRST(β)-{ε}) U FOLLOW(A)

Parsing table

After the construction of the parsing table, if for any non-terminal symbol in the table we have more than one production rule for any terminal symbol in the table column the grammar is not LL(1). Otherwise, then grammar is considered as LL(1).  

Rules for construction of parsing table:

Step 1: For each production A → α , of the given grammar perform Step 2 and Step 3.  

Step 2: For each terminal symbol ‘a’ in FIRST(α), ADD A → α in table T[A,a], where ‘A’ determines row & ‘a’ determines column.

Step 3:  If ε is present in FIRST(α) then find FOLLOW(A), ADD A → ε, at all columns ‘b’, where ‘b’ is FOLLOW(A).  (T[A,b])

Step 4: If ε is in FIRST(α) and $ is the FOLLOW(A), ADD A → α to T[A,$].

The assumption made in code:  

a) LHS symbol of First rule is considered as start symbol.

b) ‘#’ represents epsilon symbol.

Approach

• There are seven functions and the driver code, they together execute the calculations. Code takes grammar rules as input. The user is required to determine which symbols are terminals (list: term_userdef) and which are non-terminals (list: nonterm_userdef).
• Code is executed on the sample set 5 for demo purpose as shown in code, this grammar has left recursion, function computeAllFirsts() is called. This function is responsible for calling functions removeLeftRecursion() and LeftFactoring(). These functions work on the above-mentioned rules respectively. Now, first() function is called for every non-terminal. The recursive logic implemented is purely based on mentioned rules of FIRST computation only.
• Base condition of first() is whether an epsilon or terminal symbol is present, for every non-terminal code enters a recursive logic and if the FIRST has multiple symbols, a list is returned else a string is returned. Therefore, in between lines of code are just making the program type-safe.
• FIRST computation is the prerequisite for FOLLOW computation as follow() function has multiple calls to first() function. A start_symbol is the LHS symbol of First rule given in the ‘rules’ list. (This can be modified), For FOLLOW computation computeAllFollows() function is called. This leads to the calling of follow() function on all non-terminals. follow() function has recursive logic with a base condition being, the function called on start_symbol which will return $ symbol.
• Rest all conditions are handled as per the above-mentioned rules in FOLLOW computation. For the target non-terminal all rules are traversed and required firsts and circular follows are calculated. All of the intermediate results are accumulated during traversal and the final list of computed follow is returned at the traversal end. Here also, the base case returns a string, but if there are multiple symbols in the result, a list is returned. Therefore, in between extra lines of code are added for type safety.
• After FIRSTs and FOLLOWs are calculated, createPaseTable() function is called. Here firsts and follow are outputted in a formatted way. Then for parse table 2D list named ‘mat’ is prepared, non-terminals form rows and terminals form columns, with ‘$’ as an extra column. Above mentioned rules for the construction of the parsing table forms the foundation for logic implemented.

Approach for String Validation

• After the parsing table is generated, we must validate the input string for the given grammar. We make use of the stack and buffer for this purpose. If grammar is not LL(1) String validation cannot be performed. Enter the follow of START SYMBOL, ‘$’ in both stack and buffer. Firstly, enter the input string in reverse order into the buffer. Then add the START SYMBOL to the top of the stack.
• Then we iteratively traverse over the current state of stack and buffer and match the entries of Table[x][y], where ‘x’ is a symbol at top of the stack and ‘y’ is a symbol at the rear of the buffer. We take the corresponding rule from the table and expand Non-terminal at TOS in the following iteration.
• If x and y both symbols are the same terminals, then we pop them from both stack and buffer and continue computation. If the stack and buffer remain with only ‘$’ symbol, this shows that all input string symbols have been matched and the string belongs to the given grammar. If Rule is not present in the parsing table or x and y are unequal terminal symbols, then string does not belong to the given grammar.

Below is the complete implementation:

Rules: 

S->[['A', 'k', 'O']]
A->[['A', 'd'], ['a', 'B'], ['a', 'C']]
C->[['c']]
B->[['b', 'B', 'C'], ['r']]

After elimination of left recursion:

S->[['A', 'k', 'O']]
A->[['a', 'B', "A'"], ['a', 'C', "A'"]]
C->[['c']]
B->[['b', 'B', 'C'], ['r']]
A'->[['d', "A'"], ['#']]

After left factoring:

S->[['A', 'k', 'O']]
A->[['a', "A''"]]
A''->[['B', "A'"], ['C', "A'"]]
C->[['c']]
B->[['b', 'B', 'C'], ['r']]
A'->[['d', "A'"], ['#']]

Calculated firsts: 
first(S) => {'a'}
first(A) => {'a'}
first(A'') => {'c', 'r', 'b'}
first(C) => {'c'}
first(B) => {'r', 'b'}
first(A') => {'d', '#'}

Calculated follows: 
follow(S) => {'$'}
follow(A) => {'k'}
follow(A'') => {'k'}
follow(C) => {'d', 'c', 'k'}
follow(B) => {'d', 'c', 'k'}
follow(A') => {'k'}

Firsts and Follow Result table

Non-T      FIRST                FOLLOW              
S          {'a'}                {'$'}               
A          {'a'}                {'k'}               
A''        {'c', 'r', 'b'}      {'k'}               
C          {'c'}                {'d', 'c', 'k'}     
B          {'r', 'b'}           {'d', 'c', 'k'}     
A'         {'d', '#'}           {'k'}               

Generated parsing table:

           k           O           d           a           c           b           r           $
S                                         S->A k O                                                
A                                         A->a A''                                                
A''                                                    A''->C A'   A''->B A'   A''->B A'            
C                                                         C->c                                    
B                                                                 B->b B C        B->r            
A'        A'->#                A'->d A'                                                            

Validate String => a r k O

              Buffer                Stack               Action
           $ O k r a                  S $        T[S][a] = S->A k O
           $ O k r a              A k O $        T[A][a] = A->a A''
           $ O k r a          a A'' k O $            Matched:a
             $ O k r            A'' k O $     T[A''][r] = A''->B A'
             $ O k r           B A' k O $            T[B][r] = B->r
             $ O k r           r A' k O $            Matched:r
               $ O k             A' k O $          T[A'][k] = A'->#
               $ O k                k O $            Matched:k
                 $ O                  O $            Matched:O
                   $                    $                Valid

Valid String!

Inference

Sample set 7 is used to represent code output, it covers all the aspects of LL(1) parsing. Grammar after left recursion removal and after left factoring is printed. After that, we also have first and follow computation results. Then we generate the parsing table, if there are no multiple entries at any position (Table[NT][T]) in the table, we say grammar is LL(1). Finally, the sample input string is validated using stack buffer validation.