Again Freestudy9 comes with the new post related to LL(1) Parsing. Additionally, we had described it to point to point Information.
- This top-down parsing is non-recursive. LL (1) – the first L indicates input is scanned from down left to right. The second L means it uses leftmost derivation for input string and 1 means it uses only input symbol to predict the parsing process.
- The block diagram for LL(1) parser is given below,
- The data structure used by LL(1) parser are input buffer, stack and parsing table.
- The parser works as follows,
- The parsing program reads the top of the stack and a current input symbol. With the help of these two symbols parsing action can be determined.
- The parser consults the table M[A, a] each time while taking the parsing actions hence this the type of parsing method is also called the table-driven parsing method.
- The input is successfully parsed if the parser reaches the halting configuration. When the stack is empty and next token is $ then it corresponds to successful parsing.
Steps to Construct LL(1) Parser
1. Remove left recursion / Perform left factoring.
2. Compute FIRST and FOLLOW of nonterminals.
3. Construct the predictive parsing table.
4. Parse the input string with the help of the parsing table.
Example LL(1) Parser
Step1: Remove left recursion
E’→+TE’ | ϵ
T’→*FT’ | ϵ
F→(E) | id
Step2: Compute FIRST & FOLLOWStep3: Predictive Parsing Table: LL(1) ParsingStep4: Parse the string: LL(1) Parsing
Shift-reduce Parsing: LL(1) Parsing
- The shift-reduce parser performs the following the basic operation,
- Shift: Moving of the symbols from the input buffer onto the stack, this action called shift-shift.
- Reduce: If handle appears on the top of the stack then reduction of it by appropriate rule done. This action called reduce action.
- Accept: If the stack contains the start symbol only an input buffer is empty at the same time then that action called to accept.
- Error: A situation in which parser cannot either shift or reduce the symbols, it can not reduce
even perform accept action then it called error action.
Example: Consider the following grammar,onsider
E→E + T | T
T→T * F | F
Perform shift reduce parsing for string id + id * id.ft
$E+ id*id$Reduce F->id
$E+T*id $Reduce F->id
$E+T*F $Reduce T->T*F