Canonical LR parser
Encyclopedia
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 lookahead, 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 lookahead, which results in so-called LALR parsers.
[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).
The core of an LR(1) item [S → a A • B e, c] is the LR(0) item S → a A • B e. Different LR(1) items may share the same core.
For example, if we have two LR(1) items of the form
we 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
.)
An item [A → β1 • β2, a] is valid for a viable prefix
α β1 if there is a rightmost derivation that yields α A a w which in one step yields α β1β2 a w
Here $ is a special character denoting the end of the string.
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 b in FIRST(β a).
A state containing [A → α • X β, a] will move to a state containing [A → α X • β, a] with label X.
Every state has transitions according to Goto.
for all
If [A → α • b β, a] is in state Ik and Ik moves to state Im with label b, then we add the action
If [A→α •, a] is in state Ik, then we add the action:
"Reduce A → α" to action[Ik, a].
Observe that we don’t use information from FOLLOW(A) anymore.
The goto part of the table is as before.
LR parser
In computer science, an LR parser is a parser that reads input from Left to right and produces a Rightmost derivation. The term LR parser is also used; where the k refers to the number of unconsumed "look ahead" input symbols that are used in making parsing decisions...
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 lookahead, 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
- 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 lookahead, 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).
The core of an LR(1) item [S → a A • B e, c] is the LR(0) item S → a A • B e. Different LR(1) items may share the same core.
For example, if we have two LR(1) items of the form
- [A → α •, a] and
- [B → α •, b],
we 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
Simple LR parser
An SLR parser will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool....
.)
Validity
The notion of validity changes.An item [A → β1 • β2, a] is valid for a viable prefix
Viable prefix
The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. An equivalent definition of a viable prefix is that it is a prefix of right sentential form that does not continue past the right end of the rightmost handle of that...
α β1 if there is a rightmost derivation that yields α A a w which in one step yields α β1β2 a w
Initial item
To get the parsing started, we begin with the initial item of- [S’ → • S, $].
Here $ is a special character denoting the end of the string.
Closure
Closure is 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 b in FIRST(β a).
Goto
Goto is the same.A state containing [A → α • X β, a] will move to a state containing [A → α X • β, a] with label X.
Every state has transitions according to Goto.
for all
Shift actions
The shift actions are the same.If [A → α • b β, a] is in state Ik and Ik moves to state Im with label b, then we add the action
- action[k, b] = "shift m"
Reduce actions
The reduce actions are more refined than SLR .If [A→α •, a] is in state Ik, then we add the action:
"Reduce A → α" to action[Ik, a].
Observe that we don’t use information from FOLLOW(A) anymore.
The goto part of the table is as before.
External links
- LR parsing MS/Powerpoint presentation, Aggelos Kiayias, University of ConnecticutUniversity of ConnecticutThe admission rate to the University of Connecticut is about 50% and has been steadily decreasing, with about 28,000 prospective students applying for admission to the freshman class in recent years. Approximately 40,000 prospective students tour the main campus in Storrs annually...