Canonical LR parser
|
|
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. Such an item for a rule A -> BC is for example of the form
- A -> B · C, a
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
DEF. A LR(1) item is a production with a marker together with a terminal:E.g. [S → aA.Be, c]intuition: it indicates how much of a certain production we have seen already (aA) + what we could expect next (Be) + a lookahead that agrees with what should follow in the input if we ever do Reduce by the production S → aABe. By incorporating such lookahead information into the item concept we will make more wise reduce decisions. Direct use of lookahead in an LR(1) item is only performed in considering reduce actions. (I.e. when marker is in the rightmost).
Core of an LR(1) item [S → aA.Be, c] is the LR(0) item S → aA.Be Different LR(1) items may share the same core. E.g. if we have two LR(1) items of the form [ A → α., a ] [ B → α., b ] we will take advantage of the lookahead to decide which reduction to use (the same setting would perhaps produce a reduce/reduce conflict in the SLR approach).
How the Notion of Validity changes: An item [ A → β1.β2, a ] is valid for a viable prefix αβ1 if we have a rightmost derivation that yields αAaw which in one step yields αβ1β2aw
Initial item: [ S’ → .S, $]
Closure. (more refined) if [A→α.Bβ, a] belongs to the set of items, and B → γ is a production of the grammar, then:we add the item [B → .γ, b] for all bFIRST(βa) Goto. (the same)A state containing [A→α.Xβ, a] will move to a state containing [A→αX.β, a] with label X Every state is closed according to Closure. Every state has transitions according to Goto. Shift actions: (same)If [A→α.bβ, a] is in state Ik and Ik moves to state Im with label b then we add the actionaction[k, b] = “shift m” Reduce actions: (more refined)If [A→α., a] is in state Ik then we add the action:“Reduce A→α”into action[A, a]Observe that we don’t use information from FOLLOW(A) anymore. Goto part of the table is as before. S’ → SS → CC C → c C | d FIRST S c d C c d S’ → SS → L = R | R L → * R | id R → L FIRST S * id L * id R * id