Vineet Kaushik February 2016

LL(1) parsing : end of input reached with null valued variables in stack

I am trying to understand stack operation during LL(1) parsing of an input.

In an example, the input has reached the end ie. $ . Although there are some variables in my stack, they have null production rules under the $ column in my parse table.

A-> epsilon
B-> epsilon
C-> epsilon
D-> epsilon

Is it legal to simple pop ABCD from the stack to reach $ or must the stack be empty regardless of available production rules when we reach end of input $?


templatetypedef March 2016

The way an LL(1) parser works in this case will cause is to predict the A → ε productions while the stack is nonempty because that's what the parsing table says to do here. The net effect is that it will eventually pop everything off the parsing stack before accepting, so in principle you could just look at the stack and say that you're done, but if you were actually coding this up I think this would actually be harder to implement than just following the standard algorithm.

Post Status

Asked in February 2016
Viewed 1,385 times
Voted 14
Answered 1 times


Leave an answer