Canonical LR parser: Difference between revisions

Revision as of 03:27, 21 October 2012

Latest revision as of 17:57, 9 August 2025

(104 intermediate revisions by 63 users not shown)

Line 1:

{{Short description|Algorithm used to analyze and process programming languages}}

In [[computer science]], a '''canonical LR parser''' or '''LR(1) parser''' is an [[LR(k)]] parser for ''k=1'', i.e. with a single [[Parsing#Lookahead|lookahead]] [[terminal symbol|terminal]]. The special attribute of this parser is that all LR(k) parsers with ''k>1'' can be transformed into a LR(1) parser.<ref name="Knuth 1965">{{cite journal | last=Knuth | first=Donald | title=On the Translation of Languages from Left to Right | work=Information and Control | volume=8 | pages=707 - 639 | year=1965 | month=July | url=http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | accessdate=29 May 2011 }}</ref> It can handle all [[deterministic context-free language]]s <ref name="Knuth 1965"/> but is mostly avoided because of its high memory requirements in favor of less powerful but more efficient alternatives such as the [[LALR]] and the [[LL(k)]] parser.

A '''canonical LR parser''' (also called a '''LR(1) parser''') is a type of [[bottom-up parsing]] algorithm used in [[computer science]] to analyze and process [[programming language]]s. It is based on the [[LR parsing]] technique, which stands for "left-to-right, rightmost derivation in reverse."

In [[computer science]]Formally, a '''canonical LR parser''' or '''LR(1) parser''' is an [[LR(k)]] parser for ''k=1'', i.e. with a single [[Parsing#Lookahead|lookahead]] [[terminal symbol|terminal]]. The special attribute of this parser is that allany LR(k) parsersgrammar with ''k>1'' can be transformed into aan LR(1) parsergrammar.<ref name="Knuth 1965">{{citeCite journal | lastlast1 = Knuth | firstfirst1 = D. E. | author-link = Donald Knuth | title = On the Translationtranslation of Languageslanguages from Leftleft to Rightright | workdoi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | pagesissue =707 - 6396 | yearpages =1965 607–639 | monthdate = July | url=http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf1965 | accessdatedoi-access =29 May 2011 }}</ref> ItHowever, back-substitutions are required to reduce k and as back-substitutions increase, the grammar can quickly become large, repetitive and hard to understand. LR(k) can handle all [[deterministic context-free language]]s .<ref name="Knuth 1965"/> but isIn the past this LR(k) parser has mostlybeen avoided because of its highhuge memory requirements in favor of less powerful but more efficient alternatives such as the [[LALR]] and the [[LL(k1)]] parser. Recently, however, a "minimal LR(1) parser" whose space requirements are close to LALR parsers{{citation needed|date=October 2020}}, is being offered by several parser generators.

Like most parsers, this parser is automatically generated by [[compiler compiler]]s like [[GNU Bison]] and Menhir.<ref>{{cite web|title=What is Menhir?|url=http://cristal.inria.fr/~fpottier/menhir/|publisher=INRIA, CRISTAL project|accessdate=29 June 2012}}</ref>

Like most parsers, thisthe LR(1) parser is automatically generated by [[compiler -compiler]]s like [[GNU Bison]], andMSTA, Menhir.,<ref>{{cite web|title=What is Menhir?|url=httphttps://cristal.inria.fr/~fpottier/menhir/|publisher=INRIA, CRISTAL project|accessdateaccess-date=29 June 2012}}</ref> HYACC,<ref>{{cite web|title=HYACC, minimal LR(1) parser generator|url=http://hyacc.sourceforge.net/}}</ref> and LRSTAR.<ref>{{cite web|title=LRSTAR parser generator | url=http://lrstar.cc/}}</ref>

== History ==

In 1965 [[Donald Knuth]] invented the [[LR parser|LR(k) parser]] ('''L'''eft to right, [[Rightmost_derivationRightmost derivation#Derivations_and_syntax_treesDerivations and syntax trees|'''R'''ightmost derivation]] parser) a type of [[shift-reduce parser]], as a generalization of existing [[precendenceprecedence parser (disambiguation)|precedence parser]]s. This parser has the potential of recognizing all deterministic context-free languages and can produce both left and right derivations of grammarstatements rulesencountered in the input file. Knuth proved that it reaches its maximum language recognition power for k=1 and provided a method for transforming LR(k), k > 1 grammars into a LR(1) grammargrammars. <ref name="Knuth 1965"/>

Canonical LR(1) parsers have the practical disadvantage of having enormous memory requirements for their internal parser-table representation. In 1969, Frank DeRemer suggested two simplified versions of the LR parser called [[LALR parser|LALR]] and [[Simple LR parser|SLR]]. These parsers require much less memory than Canonical LR(1) parsers, but have slightly less language-recognition power.<ref name="DeRemer 1969">{{cite web|title=Practical Translators for LR(k) languages |url=http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf |author=Franklin L. DeRemer |publisher=MIT, PhD Dissertation |year=1969 |url-status=dead |archive-url=https://web.archive.org/web/20120405124425/http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf |archive-date=April 5, 2012 }}</ref> LALR(1) parsers have been the most common implementations of the LR Parser.

In 1965 [[Donald Knuth]] invented the [[LR parser|LR(k) parser]] ('''L'''eft to right, [[Rightmost_derivation#Derivations_and_syntax_trees|'''R'''ightmost derivation]] parser) a type of [[shift-reduce parser]], as a generalization of existing [[precendence parser]]s. This parser has the potential of recognizing all deterministic context-free languages and can produce both left and right derivations of grammar rules. Knuth proved that it reaches its maximum language recognition power for k=1 and provided a method for transforming LR(k), k > 1 grammars into a LR(1) grammar. <ref name="Knuth 1965"/>

UnfortunatelyHowever, thea new type of LR(1) parser, hassome thepeople practicalcall disadvantagea of"Minimal havingLR(1) enormous memory requirements for its interal [[formal grammar|grammar]] representation. The first attempt to solve this problem were the memoryparser" optimizationswas introduced in 1977 by D.David Pager<ref name="Pager 1977">{{citation|title=A Practical General Method for Constructing LR(k) Parsers|author=Pager, D.|work=Acta Informatica 7|pages=249–268|year=1977}}</ref> butwho stillshowed thethat LR(1) parserparsers requiredcan significantlybe morecreated whose memory thanrequirements otherrival parsingthose methods.of Earlier,LALR(1) inparsers. 1969Recently{{when|date=November 2019}}, Franksome DeRemerparser hadgenerators are suggestedoffering two simplified version of theMinimal LR(1) Parser called [[LALR]] and [[Simple LR parser|SLR]]parsers, which greatlynot reducedonly memory requirements atsolve the costmemory ofrequirement lessproblem, languagebut recognitionalso power.<refthe name="DeRemermysterious-conflict-problem 1969">{{citeinherent web|title=Practicalin Translators for LRLALR(k1) languages|url=http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf|author=Franklinparser Lgenerators.{{citation DeRemerneeded|publisherdate=MIT,November PhD Dissertation|year=19692019}}</ref> TheseIn twoaddition, parsersMinimal LR(especially LALR1) haveparsers sincecan beenuse andshift-reduce stillactions, arewhich bymakes farthem thefaster mostthan common implementations of theCanonical LR(1) Parserparsers.

== Overview ==

The LR(1) parser is a [[deterministic automaton]] and as such its operation is based on static [[state transition table]]s. These codify the grammar of the language it recognizes and are typically called "parsing tables".

The parsing tables of the LR(1) parser are parameterized with a lookahead terminal. Simple parsing tables, like those used by the [[LR(0)]] parser represent grammar rules of the form

: A1 → A, B

which means that if we go fromhave stateinput ''A'' tofollowed stateby ''B'' then we will goreduce tothe statepair to ''A1'' regardless of what follows. After parameterizing such a rule with a lookahead we have:

: A1 → A, B, a

which means that the transitionreduction will now be performed only if the lookahead terminal is ''a''. This allows for richer languages where a simple rule can have different meanings depending on the lookahead context. For example, in a LR(1) grammar, all of the following rules transition toperform a different statereduction in spite of being based on the same state sequence.

: A1 → A, B, a

: A2 → A, B, b

: A3 → A, B, c

: A4 → A, B, d

The same would not be true if a lookahead terminal was not being taken into account. Parsing errors can be identified without the parser having to read the whole input by declaring some rules as errors. For example,

: E1 → B, C, d

can be declared an error, causing the parser to stop. This means that the lookahead information can also be used to catch errors, as in the following example:

: A1 → A, B, a

: A1 → A, B, b

: A1 → A, B, c

: E1 → A, B, d

In this case A, B will be reduced to A1 when the lookahead is a, b or c and an error will be reported when the lookahead is d.

The lookahead can also be helpful in deciding when to reduce a rule. The lookahead can help avoid reducing a specific rule if the lookahead is not valid, which would probably mean that the current state should be combined with the following instead of the previous state. That means that in the following example

* StateInput sequence: A, B, C

* Rules:

:: A1 → A, B

:: A2 → B, C

the state sequence can be reduced to

: A, A2

instead of

: A1, C

if the lookahead after the parser went to state B wasn't acceptable, i.e. no transition rule existed. It should be noted here that statesReductions can be produced directly from a terminal as in

: X → y

which allows for statemultiple sequences to appear.

LR(1) parsers have the requirement that each rule should be expressed in a complete LR(1) manner, i.e. a sequence of two states with a specific lookahead. That makes simple rules such as

: X → y

requiring a great many artificial rules that essentially enumerate the combinations of all the possible states and lookahead terminals that can follow. A similar problem appears for implementing non-lookahead rules such as

: A1 → A, B

where all the possible lookaheads must be enumerated. That is the reason why LR(1) parsers cannot be practically implemented without significant memory optimizations.<ref name="Pager 1977"/>

== Constructing LR(1) parsing tables ==

LR(1) parsing tables are constructed in the same way as [[LR_parserLR parser#Constructing_LR.280.29_parsing_tablesConstructing LR(0) parsing tables|LR(0) parsing tables]] with the modification that each [[LR_parserLR parser#Items|Item]] contains a lookahead [[Terminal symbol|terminal]]. This means, contrary to LR(0) parsers, a different action may be executed, if the item to process is followed by a different terminal.

=== Parser items ===

Starting from the [[Formal_grammarFormal grammar#The_syntax_of_grammarsThe syntax of grammars|production rules]] of a language, at first the item sets for this language have to be determined. In plain words, an item set is the list of production rules, which the currently processed symbol might be part of. An item set has a one-to-one correspondence to a parser state, while the items within the set, together with the next symbol, are used to decide which state transitions and parser action are to be applied. Each item contains a marker, to note at which point the currently processed symbol appears in the rule the item represents. For LR(1) parsers, each item is specific to a lookahead terminal, thus the lookahead terminal has also bebeen noted inside each item.

For example, assume a language consisting of the terminal symbols 'n', '+', '(', ')', the nonterminals 'E', 'T', the starting rule 'S' and the following production rules:

: S → E

: E → T

: E → ( E )

: T → n

: T → + T

: T → T + n

Items sets will be generated by analog to the procedure for LR(0) parsers. The item set 0 which represents the initial state will be created from the starting rule:

: [S → • E, $]

The dot '•' denotes the marker of the current parsing position within this rule. The expected lookahead terminal to apply this rule is noted after the comma. The '$' sign is used to denote 'end of input' is expected, as is the case for the starting rule.

This is not the complete item set 0, though. Each item set must be 'closed', which means all production rules for each nonterminal following a '•' have to be recursively included into the item set until all of those nonterminals are dealt with. The resulting item set is called the closure of the item set we began with.

For LR(1) for each production rule an item has to be included for each possible lookahead terminal following the rule. For more complex languages this usually results in very large item sets, which is the reason for the large memory requirements of LR(1) parsers.

In our example, the starting symbol requires the nonterminal 'TE' which in turn requires 'T', thus all production rules will appear in item set 0. ArAt first, we ignore the problem of finding the lookaheads and just look at the case of an LR(0), whose items do not contain lookahead terminals. So the item set 0 (without lookaheads) will look like this:

: [S → • E]

: [E → • T]

: [E → • ( E )]

: [T → • n]

: [T → • + T]

: [T → • T + n]

=== FIRST and FOLLOW sets ===

To determine lookheadlookahead terminals, so-called FIRST and FOLLOW sets are used.

FIRST(A) is the set of terminals which can appear as the first element of any chain of rules matching nonterminal A. FOLLOW(I) of an Item I [A → α • B β, x] is the set of terminals that can appear immediately after [[nonterminal]] B, where α, β are arbitrary symbol strings, and x is an arbitrary lookahead terminal. FOLLOW(k,B) of an item set k and ana nonterminal B is the union of the follow sets of all items in Kk where '•' is followed by B. The FIRST sets can be determined directly from the closures of all nonterminals in the language, while the FOLLOW sets are determined from the items under usage of the FIRST sets.

In our example, as one can verify from the full list of item sets below, the first sets are:

: FIRST(ES) = { n, '+', '(' }

: FIRST(TE) = { n, '+', '(' }

: FIRST(T) = { n, '+' }

=== Determining lookahead terminals ===

Within item set 0 the follow sets can be found to be:

: FOLLOW(0,S) = { $ }

: FOLLOW(0,E) = { $, ')'}

: FOLLOW(0,T) = { $, '+', ')' }

From this the full item set 0 for an LR(1) parser can be created, by creating for each item in the LR(0) item set one copy for each terminal in the follow set of the LHS nonterminal. Each element of the follow set may be a valid lookahead terminal:

: [S → • E, $]

: [E → • T, $]

: [E → • ( ET, ), $]

: [TE → • n( E ), $]

: [TE → • n( E ), +)]

: [T → • + Tn, $]

: [T → • + Tn, +]

: [T → • T + n, $)]

: [T → • T + nT, +$]

: [T → • + T, +]

: [T → • + T, )]

: [T → • T + n, $]

: [T → • T + n, +]

: [T → • T + n, )]

=== Creating new item sets ===

The rest of the item sets can be created by the following algorithm

: 1. For each terminal and nonterminal symbol A appearing after a '•' in each already existing item set k, create a new item set m by adding to m all the rules of k where '•' is followed by A, but only if m will not be the same as an already existing item set after step 3.

: 2. shift all the '•'s for each rule in the new item set one symbol to the right

: 3. create the closure of the new item set

: 4. Repeat from step 1 for all newly created item sets, until no more new sets appear

In the example we get 5 more sets from item set 0, item set 1 for nonterminal E, item set 2 for nonterminal T, item set 3 for terminal n, item set 4 for terminal '+' and item set 5 for '('.

Line 136 ⟶ 145:

Item set 1 (E):

: [S → E •, $]

Item set 2 (T):

: [E → T •, $]

: [T → T • + n, $]

: [T → T • + n, +]

: ·

: ·

: ·

Item set 3 (n):

: [T → n •, $]

: [T → n •, +]

: [T → n •, )]

Item set 4 ('+'):

: [T → + • T, $]

: [T → + • T, +]

: [T → • n, $]

: [T → • n, +]

: [T → • + T, $]

: [T → • + T, +]

: [T → • T + n, $]

: [T → • T + n, +]

: ·

: ·

: ·

Item set 5 ('('):

: [E → ( • E ), $]

: [E → • T, )]

: [E → • ( E ), )]

: [T → • n, )]

: [T → • n, +]

: [T → • + T, )]

: [T → • + T, +]

: [T → • T + n, )]

: [T → • T + n, +]

: ·

: ·

: ·

From item sets 2, 4 and 5 several more more item sets will be produced. The complete list is quite long and thus will not be stated here. Detailed LR(k) treatment of this grammar can e.g. be found in [http://david.tribble.com/text/lrk_parsing.html].

=== Goto ===

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, in item set 2

: [E → T •, $]

: [T → T • + n, $]

: [T → T • + n, +]

the parser is required to perform the reduction [E → T] if the next symbol is '$', but to do a shift if the next symbol is '+'. Note that a LR(0) parser would not be able to make this decision, as it only considers the core of the items, and would thus report a shift/reduce conflict.

A state containing [A → α • X β, a] will move to a state containing [A → α X • β, a] with label X.

Line 192 ⟶ 211:

=== Shift actions ===

If [A → α • b β, a] is in state I_k and I_k moves to state I_m with label b, then we add the action

: action[I_k, b] = "shift m"

=== Reduce actions ===

If [A→α •, a] is in state I_k, then we add the action

If: action[A→α •, a] is in state I_k, thena] we= add"reduce theA action:→ α"

"Reduce A → α" to action[I_k, a].

== References ==

{{Reflist}}

== External links ==

{{Reflist}}

* [http://www.cse.uconn.edu/~akiayias/cse244fa04/N244-4.ppt Syntax Analysis] MS/Powerpoint presentation, Aggelos Kiayias, [[University of Connecticut]]

* [http://www.cse.uconn.edu/~akiayias/cse244fa04/N244-4-LR-more.ppt LR parsing] MS/Powerpoint presentation, Aggelos Kiayias, [[University of Connecticut]]

* [http://david.tribble.com/text/lrk_parsing.html Practical LR(k) Parser Construction] HTML page, David Tribble

* [https://code.activestate.com/recipes/579140-follow-sets-construction/?in=user-4174427 First & Follow Sets Construction in Python (Narayana Chikkam)]

{{Parsers}}

[[Category:Parsing algorithms]]

[[Category:Article Feedback 5]]

[[sr:Kanonski LR analizator]]