pg@bsg.com (Peter Garst) (04/23/91)
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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.