Value : INT_CONST | IDENTIFIER ; Products : Products '*' Value | Value ; Sums : Sums '+' Products | Products ; start : Sums ;
and an input of "A*2 + 1".
The parser will read in the file, construct a table of the non-terminals, and their alternatives within, and then attempt to shift incoming tokens on to the token stack, and then reduce them when the topmost tokens match any alternative of a non-terminal, which sounds good in theory.
However, the bug come in ambiguities in handling the integers and the identifier. The parser will push the A, see that the IDENTIFIER matches Value, and reduce it and push a Value on the stack. Then, it sees that Value matches Products, since it can be made from a single Value. Then it reduces and pushes a Products on to the stack. Then it sees that Products matches Sums, since it can be made from a single Products. Then it reduces and pushes a Sums on to the stack. Then it sees that Sums matches start, since it can be made from a single Sums. Then it reduces and pushes a start on to the stack.
Then it pushes the asterisk, and after that, the 2. The parser then sees the INT_CONST matches Value, and reduce it and push a Value on the stack. Then, it sees that Value matches Products, since it can be made from a single Value... all the way up to start, and adds another start.
I suppose I could modify the grammar to avoid this, but I'd like to support this kind of grammar. This leads me to believe that I need a special table that has information on where to go next, rather than check everything to see if it matches. The problem that must be accomodated, is that its behavior could be correct in some instances, such as if the input is simply "A". The parse can't fail by requiring the ignored parts of grammar to be present and used. I could read a token of look-ahead, but I can't figure out how to use it with this situation; looking ahead one token might help me guess what's next, but if the ambiguitiy occurs one more token out in the alternatives, than one token of look-ahead won't resolve the issue with such naivety. So, surely there's another method than looking ahead to the entire input to know for absolute sure. If anyone could point me in the right direction, I'd appreciate it. Online references are extremely confusing, making huge assumptions about what the reader knows, without first telling the reader what they should know beforehand.