3 ms·

I was referring specifically to an LR(1) bottom-up parser, but I was confused how the stack looks like (all this was some time ago). The parser might indeed en

by moring 4y ago

I was referring specifically to an LR(1) bottom-up parser, but I was confused how the stack looks like (all this was some time ago). The parser might indeed encounter an identifier without knowing whether it is part of an expression. However, it does know whether an expression is valid at that point. This isn't encoded buried in the stack but it is encoded in the top-of-stack state (this is the part that I was confused about). For example, suppose that the input is now at a point where a statement starts in a Java-like language. An identifier may be part of many different kinds of statements, and the parser will not know which of them an identifier starts, nor whether that identifier is part of an expression. It does, however, know that a statement is valid at this point, because this information can be found in the transition table used after reduction. It will also know which high-level constructs are valid from that table, including statement and expression, and from the token transition table it will know which tokens are valid. What you might be referring to is that while the transition table will show that an expression is allowed, it does not easily show whether such an expression must be part of a statement or can indicate another high-level construct. My experience with using such a parser in the context of an IDE is that it is okay to show them both, because most syntax errors made by a user are far more trivial (such as the wrong number of closing parentheses). Note that an LL(1) top-down (recursive descent) parser would not know either if the first identifier is part of an expression because that information cannot be derived from the left-side context. Only a larger lookahead will fix that. Or backtracking, which is kind of similar to a larger lookahead.

HarHarVeryFunny 4y ago
> The parser might indeed encounter an identifier without knowing whether it is part of an expression. However, it does know whether an expression is valid at that point. This isn't encoded buried in the stack but it is encoded in the top-of-stack state (this is the part that I was confused about). No, it really isn't! Table driven parsers basically have two actions encoded in their tables - for any (state, current input symbol) pair (i.e. table indices) they can either SHIFT or REDUCE. A SHIFT action means to push the symbol onto the stack since it doesn't yet know what it's part of. A REDUCE action means to pull the top N symbols (terminals and non-terminals) off the stack and replace them with the RHS of the grammar rule they represent that it has now recognized. e.g. If there was only one grammar rule: A -> x y z Then when the parser saw "x" it would SHIFT, then "y" => SHIFT, then "z" => SHIFT, then (with next symbol end-of-file) REDUCE - popping (x, y, x) off the stack and replacing them with A. This REDUCE action is the first time it knew that those x, y, z were part of A. In a real grammar with more than one rule there may be multiple REDUCE actions (with different RHS) depending on what followed x [y [z]]. In a top-down (recursive descent) parser you know what you're parsing at any point, and then go looking for what you hope to be there. e.g. if you see "if" then you will call ParseIfStatement which will call ParseExpression etc. In a bottom-up parser you're discovering what you're parsing by SHIFTING these bottom level (then progressively higher) symbols until finally you've seen enough to recognize what the constuct is and can do a REDUCE action using that rule. So, using the above example, if after "x" and "y" you see something unexpected like "w" rather than "z" you can't generate a top-down error like "Invalid A", because you don't yet know this is part of an "A" (and indeed in a more complex grammar there may be multiple things that "x y" could be part of). So, in the bottom up parser all you can generate as an error is something like "z expected" given that you know "z" would be a valid next symbol (leading to a SHIFT action in this case).
- moring 4y ago
  The stack contains states, not symbols. A shifted state encodes the shifted terminal PLUS the information what nonterminals that terminal can be part of (in LR(1), each of those nonterminals is augmented with its accepted follow-set). Really the only place where the above breaks down is when in the middle of a rule, after shifting a terminal (or "shifting" a nonterminal after reduction; this is called differently in literature but it really behaves like shifting nonterminals) all that context information is dropped under the assumption that it is not needed for the current rule, but is still available deeper on the stack and will resurface after reducing the current rule. At that point, an error would be missing this information.

by moring 4y ago

HarHarVeryFunny 4y ago

> The parser might indeed encounter an identifier without knowing whether it is part of an expression. However, it does know whether an expression is valid at that point. This isn't encoded buried in the stack but it is encoded in the top-of-stack state (this is the part that I was confused about). No, it really isn't! Table driven parsers basically have two actions encoded in their tables - for any (state, current input symbol) pair (i.e. table indices) they can either SHIFT or REDUCE. A SHIFT action means to push the symbol onto the stack since it doesn't yet know what it's part of. A REDUCE action means to pull the top N symbols (terminals and non-terminals) off the stack and replace them with the RHS of the grammar rule they represent that it has now recognized. e.g. If there was only one grammar rule: A -> x y z Then when the parser saw "x" it would SHIFT, then "y" => SHIFT, then "z" => SHIFT, then (with next symbol end-of-file) REDUCE - popping (x, y, x) off the stack and replacing them with A. This REDUCE action is the first time it knew that those x, y, z were part of A. In a real grammar with more than one rule there may be multiple REDUCE actions (with different RHS) depending on what followed x [y [z]]. In a top-down (recursive descent) parser you know what you're parsing at any point, and then go looking for what you hope to be there. e.g. if you see "if" then you will call ParseIfStatement which will call ParseExpression etc. In a bottom-up parser you're discovering what you're parsing by SHIFTING these bottom level (then progressively higher) symbols until finally you've seen enough to recognize what the constuct is and can do a REDUCE action using that rule. So, using the above example, if after "x" and "y" you see something unexpected like "w" rather than "z" you can't generate a top-down error like "Invalid A", because you don't yet know this is part of an "A" (and indeed in a more complex grammar there may be multiple things that "x y" could be part of). So, in the bottom up parser all you can generate as an error is something like "z expected" given that you know "z" would be a valid next symbol (leading to a SHIFT action in this case).

moring 4y ago
The stack contains states, not symbols. A shifted state encodes the shifted terminal PLUS the information what nonterminals that terminal can be part of (in LR(1), each of those nonterminals is augmented with its accepted follow-set). Really the only place where the above breaks down is when in the middle of a rule, after shifting a terminal (or "shifting" a nonterminal after reduction; this is called differently in literature but it really behaves like shifting nonterminals) all that context information is dropped under the assumption that it is not needed for the current rule, but is still available deeper on the stack and will resurface after reducing the current rule. At that point, an error would be missing this information.