31-10-2012, 05:10 PM
Canonical LR parser
CLR.doc (Size: 31 KB / Downloads: 23)
A canonical LR parser or LR(1) parser is an LR parser whose parsing tables are constructed in a similar way as with LR(0) parsers except that the items in the item sets also contain a follow, i.e., a terminal that is expected by the parser after the right-hand side of the rule. For example, such an item for a rule A → B C might be
which would mean that the parser has read a string corresponding to B and expects next a string corresponding to C followed by the terminal 'a'. LR(1) parsers can deal with a very large class of grammars but their parsing tables are often very big. This can often be solved by merging item sets if they are identical except for the follows, which results in so-called LALR parsers.
Constructing LR(1) parsing tables
An LR(1) item is a production with a marker together with a terminal, e.g., [S → a A • B e, c]. Intuitively, such an item indicates how much of a certain production we have seen already (a A), what we could expect next (B e), and a lookahead that agrees with what should follow in the input if we ever reduce by the production S → a A B e. By incorporating such lookahead information into the item concept, we can make wiser reduce decisions. The lookahead of an LR(1) item is used directly only when considering reduce actions (i.e., when the • marker is at the right end).