left context in parser states

Jim Roskind raised a question about what you can have for left context
in an LR parser state. I believe there is a "tail" property for
these left contexts (it may have a real name as well). That is, you could
have a state with items that look like


sym1 : Z . x
sym2 : Y Z . x
sym3 : X Y Z . x


but not one with items that look like


sym1 : Y Z . x
sym2 : X Z . x


You can see by an induction argument that the standard construction of
LR(0) sets maintains this property. It is true for the start state, where
the left context is empty for all items. You get from one state to the
next during the construction by moving the carrot across a given symbol.
You could get the first set of items above from a state with items


sym1 : . Z x
sym2 : Y . Z x
sym3 : X Y . Z x


If the tail property is true for one state, all you do is tack Z on to
the end of the left contexts, so it is true for the next state as well.


More complex variations in the left context during a parse are recorded
by different state stacks, not by different states.


Of course, in practice a parser generator might merge states as part of
an optimization step, so this may not hold in real life.


Peter Garst
Bloomsbury Software Group
--

Return to the comp.compilers page.
Search the comp.compilers archives again.