Parsing table

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....

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....

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)....

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....

Inference

...