Predictive Parsing LL(1) Acceptance
In this class, We discuss Predictive Parsing LL(1) Acceptance.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of LL(1) Table construction. Click Here.
The below diagram shows the LL(1) input parsing.
We are using an extra stack to parse the input string.
We place an input string in a buffer with a dollar symbol added at the end of the input.
Similarly dollar symbol is added to the stack.
How did the LL(1) parsing work? The below explanation is about the parsing.
The below table shows the parsing actions in LL(1).
The First Non-Terminal symbol, E added to the stack.
1) The input is pointing to the id in the input string.
Stack Top is E, and the input is pointing to id. So check the E, id block in the parse table.
The [E, id] block has production E – TE’. So pop the E from the stack top and push TE’ onto the stack.
2) Now, The stack top is T, and the input symbol is id. So check the block [T, id].
We have the production T – FT’ in the block [T, id]. So pop the element from the stack and push FT’ onto the stack.
3) We have F on the top of the stack, and input is pointing to id.
Check the block [F, id]. We have the production F – id., so pop F from the stack and push it onto the stack.
4) The stack top has an id, and the input points to id.
Both stack top and input are matched. So id is taken to matched symbols, and input points to the next symbol ‘+’.
The stack top id is moved to matched symbols.
5) The stack top has T’, and the input points to ‘+’.
Check the production in the block [T’, +]. We have the production T’ – epsilon.
Pushing epsilon on to stack will give nothing.
Similarly, the remaining steps are followed.
The above table shows the complete actions.
If the stack top is a dollar and the input points to a dollar, we say input accepted.
Important: During these parsing steps, we check the block related to stack top and input symbol.
If the block contains a blank, there is an error in the input string. We must display an error message.