242:
2656:
with each change to see if it worked okay. (This requires backtracking to snapshots of the parse stack and input stream, normally unneeded by the parser.) Some best repair is picked. This gives a very helpful error message and resynchronizes the parse well. However, the repair is not trustworthy enough to permanently modify the input file. Repair of syntax errors is easiest to do consistently in parsers (like LR) that have parse tables and an explicit data stack.
1473:. These are names for concepts or patterns in the language. They are defined in the grammar and never occur themselves in the input stream. They are always internal nodes (above the bottom) of the parse tree. They only happen as a result of the parser applying some grammar rule. Some nonterminals are defined with two or more rules; these are alternative patterns. Rules can refer back to themselves, which are called
622:(rightmost on the stack) and the lookahead symbol. In the steps below, all the black details are exactly the same as in other non-LR shift-reduce parsers. LR parser stacks add the state information in purple, summarizing the black phrases to their left on the stack and what syntax possibilities to expect next. Users of an LR parser can usually ignore state information. These states are explained in a later section.
2631:
Unfortunately, this greatly magnifies the size of the parse tables if done for all parts of the grammar. This splitting of states can also be done manually and selectively with any SLR or LALR parser, by making two or more named copies of some nonterminals. A grammar that is conflict-free for a canonical LR generator but has conflicts in an LALR generator is called LR(1) but not LALR(1), and not SLR.
307:
2623:
generators, or it may turn out to be a subset of the SLR lookaheads. Some grammars are okay for LALR parser generators but not for SLR parser generators. This happens when the grammar has spurious shift/reduce or reduce/reduce conflicts using Follow sets, but no conflicts when using the exact sets computed by the LALR generator. The grammar is then called LALR(1) but not SLR.
1376:, and Products into one thing. State 3 itself doesn't know what the next state should be. This is found by going back to state 0, just to the left of the phrase being reduced. When state 0 sees this new completed instance of a Sums, it advances to state 1 (again). This consulting of older states is why they are kept on the stack, instead of keeping only the current state.
2082:. If the lookahead is either of those, the parser shifts them in and advances to state 8 or 9, respectively. When a Products has been found, the parser advances to state 3 to accumulate the complete list of summands and find the end of rule r0. A Products can also begin with nonterminal Value. For any other lookahead or nonterminal, the parser announces a syntax error.
25:
315:
gets reduced to Value and then to
Products in steps 1-3 as soon as lookahead * is seen, rather than waiting any later to organize those parts of the parse tree. The decisions for how to handle A are based only on what the parser and scanner have already seen, without considering things that appear much later to the right.
2751:) grammar. And that grammar could always be mechanically transformed into an equivalent (but larger) LR(1) grammar. So an LR(1) parsing method was, in theory, powerful enough to handle any reasonable language. In practice, the natural grammars for many programming languages are close to being LR(1).
2655:
Many syntactic coding errors are simple typos or omissions of a trivial symbol. Some LR parsers attempt to detect and automatically repair these common cases. The parser enumerates every possible single-symbol insertion, deletion, or substitution at the error point. The compiler does a trial parse
2598:
How can a mere FSM do this when the original unparsed language has nesting and recursion and definitely requires an analyzer with a stack? The trick is that everything to the left of the stack top has already been fully reduced. This eliminates all the loops and nesting from those phrases. The FSM
253:
incrementally, bottom up, and left to right, without guessing or backtracking. At every point in this pass, the parser has accumulated a list of subtrees or phrases of the input text that have been already parsed. Those subtrees are not yet joined together because the parser has not yet reached the
171:
LR parsers are deterministic; they produce a single correct parse without guesswork or backtracking, in linear time. This is ideal for computer languages, but LR parsers are not suited for human languages which need more flexible but inevitably slower methods. Some methods which can parse arbitrary
3881:
Starting at the begin state (S0), all of the states that can be reached from this state are now determined. The possible transitions for an item set can be found by looking at the symbols (terminals and nonterminals) found following the dots; in the case of item set 0 those symbols are the terminals
3776:
The first step of constructing the tables consists of determining the transitions between the closed item sets. These transitions will be determined as if we are considering a finite automaton that can read terminals as well as nonterminals. The begin state of this automaton is always the closure of
2664:
The LR parser generator decides what should happen for each combination of parser state and lookahead symbol. These decisions are usually turned into read-only data tables that drive a generic parser loop that is grammar- and state-independent. But there are also other ways to turn those decisions
2634:
SLR, LALR, and canonical LR parsers make exactly the same shift and reduce decisions when the input stream is the correct language. When the input has a syntax error, the LALR parser may do some additional (harmless) reductions before detecting the error than would the canonical LR parser. And the
1384:
LR parsers are constructed from a grammar that formally defines the syntax of the input language as a set of patterns. The grammar doesn't cover all language rules, such as the size of numbers, or the consistent use of names and their definitions in the context of the whole program. LR parsers use
609:
In LR parsers, the shift and reduce decisions are potentially based on the entire stack of everything that has been previously parsed, not just on a single, topmost stack symbol. If done in an unclever way, that could lead to very slow parsers that get slower and slower for longer inputs. LR parsers
3642:
B, indicates that the parser expects to parse the nonterminal B next. To ensure the item set contains all possible rules the parser may be in the midst of parsing, it must include all items describing how B itself will be parsed. This means that if there are rules such as B β 1 and B β 0 then the
3501:
The stack corresponds with a list of states of a finite automaton that has read a nonterminal E, followed by a '+' and then a nonterminal B. In state 8 the parser always performs a reduce with rule 2. The top 3 states on the stack correspond with the 3 symbols in the right-hand side of rule 2. This
2676:
variation, the explicit parse stack structure is also replaced by the implicit stack used by subroutine calls. Reductions terminate several levels of subroutine calls, which is clumsy in most languages. So recursive ascent parsers are generally slower, less obvious, and harder to hand-modify than
2643:
LR parsers can generate somewhat helpful error messages for the first syntax error in a program, by simply enumerating all the terminal symbols that could have appeared next instead of the unexpected bad lookahead symbol. But this does not help the parser work out how to parse the remainder of the
2280:
LR parser stack usually stores just the LR(0) automaton states, as the grammar symbols may be derived from them (in the automaton, all input transitions to some state are marked with the same symbol, which is the symbol associated with this state). Moreover, these symbols are almost never needed as
2132:
Individual table cells must not hold multiple, alternative actions, otherwise the parser would be nondeterministic with guesswork and backtracking. If the grammar is not LR(1), some cells will have shift/reduce conflicts between a possible shift action and reduce action, or reduce/reduce conflicts
1488:
itself, or must be augmented by tie-breaking precedence rules. This means there is only one correct way to apply the grammar to a given legal example of the language, resulting in a unique parse tree with just one meaning, and a unique sequence of shift/reduce actions for that example. LR parsing
3446:
The first symbol from the input string that the parser sees is '1'. To find the next action (shift, reduce, accept or error), the action table is indexed with the current state (the "current state" is just whatever is on the top of the stack), which in this case is 0, and the current input symbol,
596:
This matches the stack top holding the parsed phrases "... Products * Value". The reduce step replaces this instance of the rule's right hand side, "Products * Value" by the rule's left hand side symbol, here a larger
Products. If the parser builds complete parse trees, the three trees for inner
4566:
Only step 4 of the above procedure produces reduce actions, and so all reduce actions must occupy an entire table row, causing the reduction to occur regardless of the next symbol in the input stream. This is why these are LR(0) parse tables: they don't do any lookahead (that is, they look ahead
2707:
use LR bottom-up techniques for recognizing the left end of alternative grammar rules. When the alternatives have been narrowed down to a single possible rule, the parser then switches to top-down LL(1) techniques for parsing the rest of that rule. LC parsers have smaller parse tables than LALR
314:
Like other shift-reduce parsers, an LR parser lazily waits until it has scanned and parsed all parts of some construct before committing to what the combined construct is. The parser then acts immediately on the combination instead of waiting any further. In the parse tree example, the phrase A
2697:
use LR bottom-up techniques to find all possible parses of input text, not just one correct parse. This is essential for ambiguous grammar such as used for human languages. The multiple valid parse trees are computed simultaneously, without backtracking. GLR is sometimes helpful for computer
2615:
parsers, these lookahead sets are determined directly from the grammar, without considering the individual states and transitions. For each nonterminal S, the SLR generator works out
Follows(S), the set of all the terminal symbols which can immediately follow some occurrence of S. In the parse
2128:
In state 9 above, all the non-blank, non-error cells are for the same reduction r6. Some parsers save time and table space by not checking the lookahead symbol in these simple cases. Syntax errors are then detected somewhat later, after some harmless reductions, but still before the next shift
3457:
In state 2, the action table says to reduce with grammar rule 5 (regardless of what terminal the parser sees on the input stream), which means that the parser has just recognized the right-hand side of rule 5. In this case, the parser writes 5 to the output stream, pops one state from the stack
3270:
is indexed by a state of the parser and a nonterminal and simply indicates what the next state of the parser will be if it has recognized a certain nonterminal. This table is important to find out the next state after every reduction. After a reduction, the next state is found by looking up the
2651:
and bison parser generators, the parser has an ad hoc mechanism to abandon the current statement, discard some parsed phrases and lookahead tokens surrounding the error, and resynchronize the parse at some reliable statement-level delimiter like semicolons or braces. This often works well for
1579:
right half of the table has columns for nonterminal symbols. These cells show which state to advance to, after some reduction's Left Hand Side has created an expected new instance of that symbol. This is like a shift action but for nonterminals; the lookahead terminal symbol is unchanged.
257:
At step 6 in an example parse, only "A*2" has been parsed, incompletely. Only the shaded lower-left corner of the parse tree exists. None of the parse tree nodes numbered 7 and above exist yet. Nodes 3, 4, and 6 are the roots of isolated subtrees for variable A, operator *, and number 2,
2622:
parsers have the same states as SLR parsers, but use a more complicated, more precise way of working out the minimum necessary reduction lookaheads for each individual state. Depending on the details of the grammar, this may turn out to be the same as the Follow set computed by SLR parser
2590:
The parse stack shows a series of state transitions, from the start state 0, to state 4 and then on to 5 and current state 8. The symbols on the parse stack are the shift or goto symbols for those transitions. Another way to view this, is that the finite state machine can scan the stream
293:
Much of the LR parser's efficiency is from being deterministic. To avoid guessing, the LR parser often looks ahead (rightwards) at the next scanned symbol, before deciding what to do with previously scanned symbols. The lexical scanner works one or more symbols ahead of the parser. The
2630:
parsers use duplicated (or "split") states to better remember the left and right context of a nonterminal's use. Each occurrence of a symbol S in the grammar can be treated independently with its own lookahead set, to help resolve reduction conflicts. This handles a few more grammars.
326:
grows rightwards. The base or bottom of the stack is on the left and holds the leftmost, oldest parse fragment. Every reduction step acts only on the rightmost, newest parse fragments. (This accumulative parse stack is very unlike the predictive, leftward-growing parse stack used by
3509:
Finally, the parser reads a '$ ' (end of input symbol) from the input stream, which means that according to the action table (the current state is 3) the parser accepts the input string. The rule numbers that will then have been written to the output stream will be which is indeed a
3283:
The table below illustrates each step in the process. Here the state refers to the element at the top of the stack (the right-most element), and the next action is determined by referring to the action table above. A $ is appended to the input string to denote the end of the stream.
2481:
Some transitions will be to cores and states that have been enumerated already. Other transitions lead to new states. The generator starts with the grammar's goal rule. From there it keeps exploring known states and transitions until all needed states have been found.
225:. This is because the LR parser waits until it has seen an entire instance of some grammar pattern before committing to what it has found. An LL parser has to decide or guess what it is seeing much sooner, when it has only seen the leftmost input symbol of that pattern.
1553:
LR parse tables are two-dimensional. Each current LR(0) parser state has its own row. Each possible next symbol has its own column. Some combinations of state and next symbol are not possible for valid input streams. These blank cells trigger syntax error messages.
4567:
zero symbols) before deciding which reduction to perform. A grammar that needs lookahead to disambiguate reductions would require a parse table row containing different reduce actions in different columns, and the above procedure is not capable of creating such rows.
2501:(FSM). An FSM is a simple engine for parsing simple unnested languages, without using a stack. In this LR application, the FSM's modified "input language" has both terminal and nonterminal symbols, and covers any partially parsed stack snapshot of the full LR parse.
1480:
Any given computer language can be described by several different grammars. An LR(1) parser can handle many but not all common grammars. It is usually possible to manually modify a grammar so that it fits the limitations of LR(1) parsing and the generator tool.
2668:
Some LR parser generators create separate tailored program code for each state, rather than a parse table. These parsers can run several times faster than the generic parser loop in table-driven parsers. The fastest parsers use generated assembler code.
4056:
Above procedure is continued until no more new item sets are found. For the item sets 1, 2, and 4 there will be no transitions since the dot is not in front of any symbol. For item set 3 though, we have dots in front of terminals '*' and '+'. For symbol
1518:). Entries in a table show whether to shift or reduce (and by which grammar rule), for every legal combination of parser state and lookahead symbol. The parse tables also tell how to compute the next state, given just a current state and a next symbol.
3465:
However, in state 4, the action table says the parser should now reduce with rule 3. So it writes 3 to the output stream, pops one state from the stack, and finds the new state in the goto table for state 0 and E, which is state 3. The resulting stack:
2616:
table, each reduction to S uses Follow(S) as its LR(1) lookahead set. Such follow sets are also used by generators for LL top-down parsers. A grammar that has no shift/reduce or reduce/reduce conflicts when using Follow sets is called an SLR grammar.
2409:
The kernel and closure items together show all possible legal ways to proceed from the current state to future states and complete phrases. If a follower symbol appears in only one item, it leads to a next state containing only one core item with the
2397:
markers, and possibly different follower symbols. This closure process continues until all follower symbols have been expanded. The follower nonterminals for state 2 begins with
Products. Value is then added by closure. The follower terminals are
2141:
The LR parser begins with a nearly empty parse stack containing just the start state 0, and with the lookahead holding the input stream's first scanned symbol. The parser then repeats the following loop step until done, or stuck on a syntax error:
4206:
For item set 5, the terminals '0' and '1' and the nonterminal B must be considered, but the resulting closed item sets for the terminals are equal to already found item sets 1 and 2, respectively. For the nonterminal B, the transition goes to:
3447:
which is '1'. The action table specifies a shift to state 2, and so state 2 is pushed onto the stack (again, all the state information is in the stack, so "shifting to state 2" is the same as pushing 2 onto the stack). The resulting stack is
1509:
Most LR parsers are table driven. The parser's program code is a simple generic loop that is the same for all grammars and languages. The knowledge of the grammar and its syntactic implications are encoded into unchanging data tables called
2384:
marker is at the beginning of each of these added rules; the parser has not yet confirmed and parsed any part of them. These additional items are called the "closure" of the core items. For each nonterminal symbol immediately following a
2325:
marker has advanced beyond the beginning of the rule. It also shows how the parser expects to eventually complete the rule, by next finding a complete
Products. But more details are needed on how to parse all the parts of that Products.
4225:
For item set 6, the terminal '0' and '1' and the nonterminal B must be considered, but as before, the resulting item sets for the terminals are equal to the already found item sets 1 and 2. For the nonterminal B the transition goes to:
3603:
It is usually not possible to characterize the state of the parser with a single item because it may not know in advance which rule it is going to use for reduction. For example, if there is also a rule E β E * B then the items E β E
4590:
The automaton is constructed in such a way that it is guaranteed to be deterministic. However, when reduce actions are added to the action table it can happen that the same cell is filled with a reduce action and a shift action (a
614:. For each grammar and LR analysis method, there is a fixed (finite) number of such states. Besides holding the already-parsed symbols, the parse stack also remembers the state numbers reached by everything up to those points.
617:
At every parse step, the entire input text is divided into a stack of previously parsed phrases, a current look-ahead symbol, and the remaining unscanned text. The parser's next action is determined by its current LR(0)
289:
LR parsers differ from other shift-reduce parsers in how they decide when to reduce, and how to pick between rules with similar endings. But the final decisions and the sequence of shift or reduce steps are the same.
2489:=0, i.e. no lookahead. The only checking of input symbols occurs when the symbol is shifted in. Checking of lookaheads for reductions is done separately by the parse table, not by the enumerated states themselves.
2644:
input program to look for further, independent errors. If the parser recovers badly from the first error, it is very likely to mis-parse everything else and produce a cascade of unhelpful spurious error messages.
4244:
These final item sets 7 and 8 have no symbols beyond their dots so no more new item sets are added, so the item generating procedure is complete. The finite automaton, with item sets as its states is shown below.
285:
If the input has no syntax errors, the parser continues with these steps until all of the input has been consumed and all of the parse trees have been reduced to a single tree representing an entire legal input.
2607:
The states and transitions give all the needed information for the parse table's shift actions and goto actions. The generator also needs to calculate the expected lookahead sets for each reduce action.
2754:
The canonical LR parsers described by Knuth had too many states and very big parse tables that were impractically large for the limited memory of computers of that era. LR parsing became practical when
1583:
The table column "Current Rules" documents the meaning and syntax possibilities for each state, as worked out by the parser generator. It is not included in the actual tables used at parsing time. The
1466:
spellings are, nor does it care about blanks or line breaks. The grammar uses these terminal symbols but does not define them. They are always leaf nodes (at the bottom bushy end) of the parse tree.
2440:
If the same follower symbol appears in several items, the parser cannot yet tell which rule applies here. So that symbol leads to a next state that shows all remaining possibilities, again with the
3454:
where the top of the stack is 2. For the sake of explaining the symbol (e.g., '1', B) is shown that caused the transition to the next state, although strictly speaking it is not part of the stack.
2472:
In words, that means if the parser has seen a single
Products, it might be done, or it might still have even more things to multiply together. All the core items have the same symbol preceding the
2329:
The partially parsed rules for a state are called its "core LR(0) items". The parser generator adds additional rules or items for all the possible next steps in building up the expected
Products:
3484:
that has just read a nonterminal E followed by a terminal '+'. The transition table of this automaton is defined by the shift actions in the action table and the goto actions in the goto table.
3721:
is an item set. It is these closed item sets that are taken as the states of the parser, although only the ones that are actually reachable from the begin state will be included in the tables.
1477:. This grammar uses recursive rules to handle repeated math operators. Grammars for complete languages use recursive rules to handle lists, parenthesized expressions, and nested statements.
2708:
parsers and better error diagnostics. There are no widely used generators for deterministic LC parsers. Multiple-parse LC parsers are helpful with human languages with very large grammars.
3595:+ B, for example, indicates that the parser has recognized a string corresponding with E on the input stream and now expects to read a '+' followed by another string corresponding with B.
3616:* B will both apply after a string corresponding with E has been read. Therefore, it is convenient to characterize the state of the parser by a set of items, in this case the set { E β E
2635:
SLR parser may do even more. This happens because the SLR and LALR parsers are using a generous superset approximation to the true, minimal lookahead symbols for that particular state.
3705:
Thus, any set of items can be extended by recursively adding all the appropriate items until all nonterminals preceded by dots are accounted for. The minimal extension is called the
3870:" in front of an item indicates the items that were added for the closure (not to be confused with the mathematical '+' operator which is a terminal). The original items without a "
3458:(since the right-hand side of the rule has one symbol), and pushes on the stack the state from the cell in the goto table for state 0 and B, i.e., state 4. The resulting stack is:
1550:. LALR parsers handle more grammars than SLR parsers. Canonical LR parsers handle even more grammars, but use many more states and much larger tables. The example grammar is SLR.
2112:
The choice between r1 and r3 can't be decided just from looking backwards at prior phrases. The parser has to check the lookahead symbol to tell what to do. If the lookahead is
1521:
The parse tables are much larger than the grammar. LR tables are hard to accurately compute by hand for big grammars. So they are mechanically derived from the grammar by some
1596:
have been parsed, and the things to the right are expected soon. A state has several such current rules if the parser has not yet narrowed possibilities down to a single rule.
4722:
There is a reduce-reduce conflict in this item set because in the cells in the action table for this item set there will be both a reduce action for rule 3 and one for rule 4.
3502:
time we pop 3 elements off of the stack (since the right-hand side of the rule has 3 symbols) and look up the goto state for E and 0, thus pushing state 3 back onto the stack
3930:
2599:
can ignore all the older beginnings of phrases, and track just the newest phrases that might be completed next. The obscure name for this in LR theory is "viable prefix".
4158:
4085:
43:
5074:
3535:
here) which are grammar rules with a special dot added somewhere in the right-hand side. For example, the rule E β E + B has the following four corresponding items:
3228:
is indexed by a state of the parser and a terminal (including a special terminal $ that indicates the end of the input stream) and contains three types of actions:
125:
An LR parser (left-to-right, rightmost derivation in reverse) reads input text from left to right without backing up (this is true for most parsers), and produces a
1489:
is not a useful technique for human languages with ambiguous grammars that depend on the interplay of words. Human languages are better handled by parsers like
3737:
where S is a new start symbol and E the old start symbol. The parser will use this rule for reduction exactly when it has accepted the whole input string.
2626:
An SLR or LALR parser avoids having duplicate states. But this minimization is not necessary, and can sometimes create unnecessary lookahead conflicts.
318:
Reductions reorganize the most recently parsed things, immediately to the left of the lookahead symbol. So the list of already-parsed things acts like a
1340:
The states corresponding to the stacked phrases are 0, 4, and 5. The current, rightmost state on the stack is state 5. When state 5 sees the lookahead
4599:). However, it can be shown that when this happens the grammar is not an LR(0) grammar. A classic real-world example of a shift-reduce conflict is the
4582:) are capable of constructing reduce actions that do not occupy entire rows. Therefore, they are capable of parsing more grammars than LR(0) parsers.
2133:
between multiple grammar rules. LR(k) parsers resolve these conflicts (where possible) by checking additional lookahead symbols beyond the first.
2595: + 1" (without using yet another stack) and find the leftmost complete phrase that should be reduced next. And that is indeed its job!
1356:
At step 12, all of the input stream has been consumed but only partially organized. The current state is 3. When state 3 sees the lookahead
4668:
There is a shift-reduce conflict in this item set: when constructing the action table according to the rules above, the cell for contains
1561:
left half of the table has columns for lookahead terminal symbols. These cells determine whether the next parser action is shift (to state
258:
respectively. These three root nodes are temporarily held in a parse stack. The remaining unparsed portion of the input stream is "+ 1".
4926:
Compilers: Principles, Techniques, and Tools (2nd
Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.
5096:
2826:
601:
details from the inner
Products and Value are output to some later compiler pass, or are combined and saved in the new Products symbol.
87:
5091:
4866:
5133:
5043:
4991:
61:
4053:
The closure does not add new items in all cases - in the new sets above, for example, there are no nonterminals following the dot.
2724:. Knuth proved that LR parsers were the most general-purpose parsers possible that would still be efficient in the worst cases.
2860:
281:
step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol.
5351:
5056:
5356:
1590:(pink dot) marker shows where the parser is now, within some partially recognized grammar rules. The things to the left of
610:
do this with constant speed, by summarizing all the relevant left context information into a single number called the LR(0)
2273:
marker. End of parsing. If the state stack contains just the start state report success. Otherwise, report a syntax error.
2747:
In other words, if a language was reasonable enough to allow an efficient one-pass parser, it could be described by an LR(
2786:
notation of LR parsers to the task of generating all possible parses for ambiguous grammars such as for human languages.
5382:
5361:
2848:
188:) time. Other methods which backtrack or yield multiple parses may even take exponential time when they guess badly.
5086:
4948:β₯1 there, but it is required by his theorems he referred to, viz. on p.629 and p.630. Similarly, the restriction to
266:
As with other shift-reduce parsers, an LR parser works by doing some combination of Shift steps and Reduce steps.
5299:
5201:
5035:
3473:
The next terminal that the parser sees is a '+' and according to the action table it should then shift to state 6:
319:
218:
2732:) grammars can be efficiently parsed with an execution time essentially proportional to the length of the string."
2810:
160:
is 1 and is not mentioned. The name "LR" is often preceded by other qualifiers, as in "SLR" and "LALR". The "LR(
3729:
Before the transitions between the different states are determined, the grammar is augmented with an extra rule
5196:
5168:
2721:
2678:
210:
5304:
5247:
5206:
2673:
274:
step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree.
5048:
Pager, D., A Practical
General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977)
3481:
2498:
249:
An LR parser scans and parses the input text in one forward pass over the text. The parser builds up the
241:
164:)" notation for a grammar was suggested by Knuth to stand for "translatable from left to right with bound
3763:
It is for this augmented grammar that the item sets and the transitions between them will be determined.
2684:
Another variation replaces the parse table by pattern-matching rules in non-procedural languages such as
2220:
Remove the matched topmost L symbols (and parse trees and associated state numbers) from the parse stack.
5329:
5309:
5173:
5126:
4949:
2694:
2086:
In state 3, the parser has just found a Products phrase, that could be from two possible grammar rules:
1490:
137:
or ad-hoc parse. The name "LR" is often followed by a numeric qualifier, as in "LR(1)" or sometimes "LR(
107:
2743:) grammar if and only if it is deterministic , if and only if it can be generated by an LR(1) grammar."
221:). LR parsers can handle a larger range of languages and grammars than precedence parsers or top-down
5341:
4854:
3511:
1532:
Depending on how the states and parsing table are generated, the resulting parser is called either a
1386:
126:
5346:
5314:
5252:
5230:
4762:
2756:
2446:
marker advanced. Products appears in both r1 and r3. So Products leads to next state 3 with core
1547:
206:
103:
99:
3885:
5278:
4133:
4060:
3262:, which is written as "acc" and indicates that the parser accepts the string in the input stream.
2704:
1470:
4905:
Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.
3940:, of all items in the current item set where there is a dot in front of the symbol of interest,
3487:
The next terminal is now '1' and this means that the parser performs a shift and go to state 2:
3275:
entry for top of the stack (i.e. current state) and the reduced rule's LHS (i.e. non-terminal).
4490:
From this table and the found item sets, the action and goto table are constructed as follows:
5324:
5268:
5185:
5052:
5039:
4987:
4862:
1485:
130:
119:
83:
5077:
This simulator is used to generate parsing tables LR and to resolve the exercises of the book
4504:
action is added to the '$ ' column for each item set that contains an item of the form S β w
118:
defining the syntax of the language to be parsed. They are widely used for the processing of
5220:
5150:
5119:
5071:, Parsing Techniques - A Practical Guide 1st Ed. web page of book includes downloadable pdf.
4817:
4750:
4575:
4558:
The reader may verify that these steps produce the action and goto table presented earlier.
2760:
1533:
1522:
1436:
134:
111:
75:
4893:
1432:
328:
153:
1302:
The parse stack begins by holding only initial state 0. When state 0 sees the lookahead
2497:
The parse table describes all possible LR(0) states and their transitions. They form a
4961:
Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.
4844:
2161:
of the Lookahead Action table. That action is either Shift, Reduce, Accept, or Error:
115:
4822:
4805:
5376:
5242:
5158:
4981:
4858:
4848:
4600:
2834:
2777:
1498:
1494:
177:
173:
5273:
4801:
2717:
214:
142:
2289:
This section of the article can be skipped by most users of LR parser generators.
5101:
5029:
597:
Products, *, and Value are combined by a new tree root for Products. Otherwise,
5319:
5225:
5068:
4772:
4767:
4725:
Both examples above can be solved by letting the parser use the follow set (see
4579:
3882:'0' and '1' and the nonterminals E and B. To find the item set that each symbol
2867:
This example of LR parsing uses the following small grammar with goal symbol E:
2770:
For full details on LR theory and how LR parsers are derived from grammars, see
1540:
95:
4745:
for a reduction if the next symbol on the input stream is in the follow set of
306:
5336:
5235:
5080:
4840:
4777:
4497:
The columns for the terminals are copied to the action table as shift actions.
3494:
Just as the previous '1' this one is reduced to B giving the following stack:
3439:
The parser starts out with the stack containing just the initial state ('0'):
2180:
onto the parse stack and scan the next input symbol into the lookahead buffer.
250:
222:
181:
91:
5106:
4914:
Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.
2074:
The next expected phrase is Products. Products begins with terminal symbols
5163:
4726:
2698:
languages that are not easily described by a conflict-free LALR(1) grammar.
1526:
598:
213:. But by convention, the LR name stands for the form of parsing invented by
2230:
Join the L parse trees together as one parse tree with new root symbol Lhs.
1435:
are the multi-character symbols or 'tokens' found in the input stream by a
2478:
marker; all transitions into this state are always with that same symbol.
2276:
Error: Report a syntax error. The parser ends, or attempts some recovery.
1392:
The example grammar used here is a tiny subset of the Java or C language:
217:, and excludes the earlier, less powerful precedence methods (for example
4892:
Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon,
4679:
A small example of a non-LR(0) grammar with a reduce-reduce conflict is:
4500:
An extra column for '$ ' (end of input) is added to the action table. An
3863:
4606:
A small example of a non-LR(0) grammar with a shift-reduce conflict is:
3932:
leads to, the following procedure is followed for each of the symbols:
5142:
5051:"Compiler Construction: Principles and Practice" by Kenneth C. Louden.
2652:
allowing the parser and compiler to look over the rest of the program.
2485:
These states are called "LR(0)" states because they use a lookahead of
1318:
At step 4, the total input stream "A*2 + 1" is currently divided into
149:
4850:
The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.)
2859:
1501:
that can simultaneously compute all possible parse trees in one pass.
5111:
2685:
2391:, the generator adds the rules defining that symbol. This adds more
2297:
State 2 in the example parse table is for the partially parsed rule
4881:
3527:
The construction of these parsing tables is based on the notion of
2858:
1322:
the parsed section "A *" with 2 stacked phrases Products and
305:
240:
4550:
in the action table is completely filled with the reduce action r
2797:β₯1, the case of LR(0) grammars is slightly different. A language
1348:
onto the stack as its own phrase, and scan the next input symbol
3772:
Finding the reachable item sets and the transitions between them
2764:
2648:
2281:
the state is all that matters when making the parsing decision.
2124:, it is at the end of rule 1 and rule 0, so the parser is done.
5115:
3980:
and for the terminal '1' (i.e. where x = '1') this results in:
3740:
For this example, the same grammar as above is augmented thus:
2902:
The two LR(0) parsing tables for this grammar look as follows:
2052:
In state 2 above, the parser has just found and shifted-in the
298:
symbols are the 'right-hand context' for the parsing decision.
4035:
and for the nonterminal B (i.e. where x = B) this results in:
3998:
and for the nonterminal E (i.e. where x = E) this results in:
3675:
in an item set and in the grammar there is a rule of the form
1284:
At initial step 0, the input stream "A*2 + 1" is divided into
18:
4970:
Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.
4248:
The transition table for the automaton now looks as follows:
4983:
Introduction to Automata Theory, Languages, and Computation
3962:
For the terminal '0' (i.e. where x = '0') this results in:
3480:
The resulting stack can be interpreted as the history of a
2772:
The Theory of Parsing, Translation, and Compiling, Volume 1
1372:
by combining the stack's rightmost three phrases for Sums,
5092:
Shift-reduce and Reduce-reduce conflicts in an LALR parser
4944:
Knuth (1965), p.635. Knuth didn't mention the restriction
4494:
The columns for nonterminals are copied to the goto table.
1458:
for end of input file. The grammar doesn't care what the
90:
in linear time. There are several variants of LR parsers:
3636:
An item with a dot before a nonterminal, such as E β E +
2315:
This shows how the parser got here, by seeing Sums then
254:
right end of the syntax pattern that will combine them.
156:
before deciding how to parse earlier symbols. Typically
2829:
with the prefix property. As a consequence, a language
145:
or guessing, the LR parser is allowed to peek ahead at
39:
4136:
4063:
3888:
2248:
Push the symbol and tree for Lhs onto the parse stack.
5081:
Internals of an LALR(1) parser generated by GNU Bison
4806:"On the translation of languages from left to right"
2840:
has an LR(0) grammar, where "$ " is not a symbol of
2149:, and the current lookahead is some terminal symbol
5292:
5261:
5184:
5149:
4882:
Language theoretic comparison of LL and LR grammars
4737:s rules for a reduction; it will only use the rule
3632:
Extension of Item Set by expansion of non-terminals
3252:" and indicates that a reduction with grammar rule
2145:The topmost state on the parse stack is some state
588:Step 6 applies a grammar rule with multiple parts:
34:
may be too technical for most readers to understand
4152:
4079:
3924:
4696:In this case the following item set is obtained:
3655:0. In general this can be formulated as follows:
2227:that was expecting an instance of the Lhs symbol.
4922:
4920:
4835:
4833:
2258:The lookahead and input stream remain unchanged.
1389:that deals just with local patterns of symbols.
110:(GLR parsers). LR parsers can be generated by a
2793:) grammars have equal generative power for all
2116:, it is in rule 3, so the parser shifts in the
1360:, it knows to apply the completed grammar rule
1310:onto the stack, and scan the next input symbol
4980:Hopcroft, John E.; Ullman, Jeffrey D. (1979).
4562:A note about LR(0) versus SLR and LALR parsing
2255:onto the parse stack as the new current state.
2187:onto the parse stack as the new current state.
2120:and advances to state 5. If the lookahead is
5127:
5007:Hopcroft, Ullman (1979), Theorem 10.12, p.260
2833:is deterministic context-free if and only if
8:
4796:
4794:
4792:
3919:
3895:
245:Bottom-up parse tree built in numbered steps
2153:. Look up the next parser action from row
5134:
5120:
5112:
4595:) or with two different reduce actions (a
4574:(0) table construction procedure (such as
2739:β₯1, "a language can be generated by an LR(
2720:in 1965 as an efficient generalization of
2504:Recall step 5 of the Parse Steps Example:
4821:
4144:
4143:
4135:
4071:
4070:
4062:
3887:
3643:item set must also include the items B β
335:Bottom-up parse steps for example A*2 + 1
62:Learn how and when to remove this message
46:, without removing the technical details.
5016:Hopcroft, Ullman (1979), Corollary p.260
4250:
4145:
4072:
3286:
2904:
2506:
1598:
624:
338:
4952:is tacitly understood from the context.
4788:
4733:to decide if it is going to use one of
4486:Constructing the action and goto tables
3239:" and indicates that the next state is
3777:the first item of the added rule: S β
2319:while looking for a larger Sums. The
1298:the remaining unscanned text "*2 + 1".
4749:. This solution results in so-called
1484:The grammar for an LR parser must be
44:make it understandable to non-experts
7:
2821:has an LR(0) grammar if and only if
1469:The capitalized terms like Sums are
1336:the remaining unscanned text " + 1".
1288:an empty section on the parse stack,
88:deterministic context-free languages
5102:Practical LR(k) Parser Construction
4586:Conflicts in the constructed tables
2827:deterministic context-free language
1505:Parse table for the example grammar
184:) have worst-case performance of O(
3514:of the string "1 + 1" in reverse.
605:LR parse steps for example A*2 + 1
16:Type of parser in computer science
14:
4203:Now, the third iteration begins.
3958:Close the resulting set of items.
3518:Constructing LR(0) parsing tables
1329:lookahead text "2" scanned as an
1291:lookahead text "A" scanned as an
234:Bottom-up parse tree for example
5352:History of compiler construction
3659:If there is an item of the form
2767:parsers with much fewer states.
2420:leads to next state 8 with core
23:
5357:Comparison of parser generators
5031:LR Parsing: Theory and Practice
4617:One of the item sets found is:
3951:, move the dot to the right of
3696:should also be in the item set.
1410:r3: Products β Products * Value
1380:Grammar for the example A*2 + 1
4676:(reduce with grammar rule 2).
4546:> 0 then the row for state
3709:of an item set and written as
2887:to parse the following input:
1565:), or reduce (by grammar rule
1450:for any integer constant, and
172:context-free languages (e.g.,
1:
4823:10.1016/S0019-9958(65)90426-2
4517:contains an item of the form
3925:{\textstyle x\in \{0,1,E,B\}}
1454:for any identifier name, and
4153:{\textstyle x={\texttt {+}}}
4080:{\textstyle x={\texttt {*}}}
3579:β Ξ΅ have only a single item
2716:LR parsers were invented by
1912:Products β Products * Value
470:Products β Products * Value
5362:Operator-precedence grammar
5107:The Honalee LR(k) Algorithm
2583:
2452:r1: Sums β Sums + Products
2223:This exposes a prior state
2176:Shift the matched terminal
2129:action or parser decision.
2092:r1: Sums β Sums + Products
1076:
1032:
995:
965:Products β Products * Value
958:
906:
856:
812:
775:
735:
697:
592:Products β Products * Value
508:
494:
480:
466:
449:
432:
418:
404:
387:
371:
205:are actually shared by all
5399:
5087:Course notes on LR parsing
5036:Cambridge University Press
4998:Here: Exercise 5.8, p.121.
1404:r1: Sums β Sums + Products
1352:, and advance to state 8.
1314:, and advance to state 9.
310:Bottom-Up Parser at step 6
219:Operator-precedence parser
2921:
2914:
2780:apply the techniques and
2679:recursive descent parsers
1611:
1606:
1344:, it knows to shift that
1306:, it knows to shift that
4160:the transition goes to:
4087:the transition goes to:
3248:, which is written as "r
3235:, which is written as "s
2460:r3: Products β Products
2100:r3: Products β Products
262:Shift and reduce actions
191:The above properties of
5305:Definite clause grammar
5083:- Implementation issues
4810:Information and Control
2674:recursive ascent parser
2665:into an active parser.
2198:: Apply grammar rule r
1783:Sums β Sums + Products
566:Sums β Sums + Products
100:canonical LR(1) parsers
4950:context-free languages
4597:reduce-reduce conflict
4154:
4081:
3926:
3482:finite state automaton
2898:Action and goto tables
2864:
2863:Bottom-up parse of 1+1
2855:Additional example 1+1
2695:Generalized LR parsers
2660:Variants of LR parsers
2591:"Products *
2245:of the LHS Goto table.
2233:Lookup the next state
1877:Products β Products *
1544:(look-ahead LR) parser
1439:. Here these include
1366:Sums β Sums + Products
1239:Sums β Sums + Products
311:
246:
129:in reverse: it does a
108:generalized LR parsers
5310:Deterministic parsing
4593:shift-reduce conflict
4155:
4082:
3927:
2862:
2639:Syntax error recovery
2416:marker advanced. So
2285:LR generator analysis
1491:Generalized LR parser
309:
302:Bottom-up parse stack
244:
104:minimal LR(1) parsers
4855:Englewood Cliffs, NJ
4134:
4061:
3886:
3701:Closure of item sets
3512:rightmost derivation
2801:is said to have the
2499:finite state machine
2493:Finite state machine
1837:Products β Products
1790:Products β Products
1413:r4: Products β Value
1387:context-free grammar
207:shift-reduce parsers
174:CockeβYoungerβKasami
127:rightmost derivation
5347:Scannerless parsing
5315:Dynamic programming
5097:A LR parser example
5028:Chapman, Nigel P.,
4935:Knuth (1965), p.638
4763:Canonical LR parser
4729:) of a nonterminal
4672:(shift to state 1)
4570:Refinements to the
3256:should be performed
2813:of another word in
2705:Left corner parsers
1548:canonical LR parser
1471:nonterminal symbols
1407:r2: Sums β Products
5383:Parsing algorithms
5143:Parsing algorithms
4986:. Addison-Wesley.
4853:(Repr. ed.).
4845:Ullman, Jeffrey D.
4150:
4077:
3922:
3767:Table construction
3575:Rules of the form
2865:
2774:(Aho and Ullman).
2722:precedence parsers
2303:r1: Sums β Sums +
2265:Accept: Lookahead
2062:r1: Sums β Sums +
1537:(simple LR) parser
312:
247:
211:precedence parsers
120:computer languages
5370:
5369:
5169:Recursive descent
5075:Parsing Simulator
4751:Simple LR parsers
4483:
4482:
4147:
4074:
3947:For each item in
3936:Take the subset,
3878:of the item set.
3874:" are called the
3725:Augmented grammar
3589:. The item E β E
3432:
3431:
3222:
3221:
2588:
2587:
2544:
2538:
2531:
2513:
2050:
2049:
1946:Products β Value
1282:
1281:
676:
669:
663:
656:
650:
643:
631:
586:
585:
550:Products β Value
408:Products β Value
359:
354:
349:
344:
135:top-down LL parse
72:
71:
64:
5390:
5325:Parser generator
5248:Recursive ascent
5136:
5129:
5122:
5113:
5017:
5014:
5008:
5005:
4999:
4997:
4977:
4971:
4968:
4962:
4959:
4953:
4942:
4936:
4933:
4927:
4924:
4915:
4912:
4906:
4903:
4897:
4890:
4884:
4879:
4873:
4872:
4837:
4828:
4827:
4825:
4798:
4717:
4709:
4662:
4650:
4639:
4630:
4528:
4508:
4251:
4239:
4220:
4197:
4185:
4173:
4159:
4157:
4156:
4151:
4149:
4148:
4124:
4112:
4100:
4086:
4084:
4083:
4078:
4076:
4075:
4048:
4029:
4020:
4011:
3993:
3975:
3931:
3929:
3928:
3923:
3856:
3844:
3832:
3820:
3808:
3796:
3781:
3691:
3670:
3653:
3647:
3640:
3626:
3620:
3614:
3608:
3593:
3587:
3570:
3561:
3552:
3543:
3287:
2905:
2846:
2784:
2576:
2568:
2562:
2556:
2541:
2534:
2528:
2522:
2516:
2510:
2507:
2476:
2464:
2456:
2444:
2433:
2414:
2395:
2389:
2382:
2368:
2357:
2348:
2341:Products * Value
2339:
2323:
2307:
2251:Push next state
2183:Push next state
2104:
2096:
2066:
2056:of grammar rule
2024:
1987:
1950:
1916:
1881:
1841:
1834:
1830:Sums β Products
1794:
1787:
1751:
1714:
1704:
1664:
1599:
1594:
1588:
1523:parser generator
1433:terminal symbols
1398:r0: Goal β Sums
1262:
1256:
1244:
1224:
1218:
1212:
1206:
1194:
1189:Products β Value
1174:
1168:
1162:
1156:
1144:
1121:
1113:
1107:
1101:
1089:
1067:
1061:
1055:
1043:
1025:
1019:
1007:
988:
982:
970:
951:
945:
939:
933:
921:
899:
891:
885:
879:
867:
847:
841:
835:
823:
805:
799:
787:
782:Products β Value
768:
762:
750:
728:
720:
708:
688:
672:
666:
659:
653:
646:
640:
634:
628:
625:
621:
484:Sums β Products
464:Products * Value
357:
352:
347:
342:
339:
329:top-down parsers
237:
112:parser generator
84:bottom-up parser
76:computer science
67:
60:
56:
53:
47:
27:
26:
19:
5398:
5397:
5393:
5392:
5391:
5389:
5388:
5387:
5373:
5372:
5371:
5366:
5288:
5257:
5180:
5145:
5140:
5065:
5025:
5023:Further reading
5020:
5015:
5011:
5006:
5002:
4994:
4979:
4978:
4974:
4969:
4965:
4960:
4956:
4943:
4939:
4934:
4930:
4925:
4918:
4913:
4909:
4904:
4900:
4894:Morgan Kaufmann
4891:
4887:
4880:
4876:
4869:
4839:
4838:
4831:
4800:
4799:
4790:
4786:
4759:
4718:
4715:
4710:
4707:
4663:
4660:
4651:
4648:
4640:
4637:
4631:
4628:
4588:
4564:
4529:
4526:
4513:If an item set
4509:
4506:
4488:
4240:
4237:
4221:
4218:
4198:
4195:
4186:
4183:
4174:
4171:
4132:
4131:
4125:
4122:
4113:
4110:
4101:
4098:
4059:
4058:
4049:
4046:
4030:
4027:
4021:
4018:
4012:
4009:
3994:
3991:
3976:
3973:
3884:
3883:
3857:
3854:
3845:
3842:
3833:
3830:
3821:
3818:
3809:
3806:
3797:
3794:
3782:
3779:
3774:
3769:
3727:
3703:
3692:
3689:
3671:
3668:
3654:
3651:
3648:
3645:
3641:
3638:
3634:
3627:
3624:
3621:
3618:
3615:
3612:
3609:
3606:
3601:
3594:
3591:
3588:
3585:
3571:
3568:
3562:
3559:
3553:
3550:
3544:
3541:
3531:(simply called
3525:
3520:
3437:
3281:
2900:
2874:(2) E β E + B
2871:(1) E β E * B
2857:
2844:
2803:prefix property
2785:
2782:
2714:
2662:
2641:
2605:
2577:
2574:
2569:
2566:
2563:
2560:
2557:
2554:
2542:
2536:
2529:
2526:
2523:
2520:
2518:
2511:
2495:
2477:
2474:
2465:
2462:
2457:
2454:
2445:
2442:
2434:
2431:
2415:
2412:
2396:
2393:
2390:
2387:
2383:
2380:
2369:
2366:
2358:
2355:
2349:
2346:
2344:r4: Products β
2340:
2337:
2335:r3: Products β
2324:
2321:
2308:
2305:
2295:
2287:
2213:
2209:
2205:
2201:
2197:
2139:
2126:
2105:
2102:
2097:
2094:
2084:
2067:
2064:
2025:
2022:
1988:
1985:
1951:
1948:
1917:
1914:
1882:
1879:
1860:
1855:
1850:
1842:
1839:
1836:
1835:
1832:
1813:
1808:
1803:
1795:
1792:
1789:
1788:
1785:
1752:
1749:
1730:
1725:
1715:
1712:
1709:
1705:
1702:
1665:
1662:
1595:
1592:
1589:
1586:
1571:
1507:
1437:lexical scanner
1382:
1354:
1316:
1263:
1260:
1257:
1254:
1242:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1192:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1142:
1122:
1119:
1114:
1111:
1108:
1105:
1102:
1099:
1087:
1068:
1065:
1062:
1059:
1056:
1053:
1041:
1026:
1023:
1020:
1017:
1005:
1002:Sums β Products
989:
986:
983:
980:
968:
952:
949:
946:
943:
940:
937:
934:
931:
919:
900:
897:
892:
889:
886:
883:
880:
877:
865:
848:
845:
842:
839:
836:
833:
821:
806:
803:
800:
797:
785:
769:
766:
763:
760:
748:
729:
726:
721:
718:
706:
689:
686:
674:
667:
661:
654:
648:
641:
638:
636:
629:
619:
607:
558:Sums + Products
337:
304:
264:
239:
235:
231:
187:
131:bottom-up parse
68:
57:
51:
48:
40:help improve it
37:
28:
24:
17:
12:
11:
5:
5396:
5394:
5386:
5385:
5375:
5374:
5368:
5367:
5365:
5364:
5359:
5354:
5349:
5344:
5339:
5334:
5333:
5332:
5322:
5317:
5312:
5307:
5302:
5296:
5294:
5293:Related topics
5290:
5289:
5287:
5286:
5283:
5282:
5281:
5271:
5265:
5263:
5259:
5258:
5256:
5255:
5250:
5245:
5240:
5239:
5238:
5233:
5228:
5223:
5213:
5212:
5211:
5210:
5209:
5199:
5190:
5188:
5182:
5181:
5179:
5178:
5177:
5176:
5174:Tail recursive
5166:
5161:
5155:
5153:
5147:
5146:
5141:
5139:
5138:
5131:
5124:
5116:
5110:
5109:
5104:
5099:
5094:
5089:
5084:
5078:
5072:
5064:
5063:External links
5061:
5060:
5059:
5049:
5046:
5024:
5021:
5019:
5018:
5009:
5000:
4992:
4972:
4963:
4954:
4937:
4928:
4916:
4907:
4898:
4885:
4874:
4868:978-0139145568
4867:
4841:Aho, Alfred V.
4829:
4816:(6): 607β639.
4787:
4785:
4782:
4781:
4780:
4778:Generalized LR
4775:
4770:
4765:
4758:
4755:
4720:
4719:
4714:
4711:
4706:
4703:
4694:
4693:
4690:
4687:
4684:
4666:
4665:
4659:
4653:
4647:
4641:
4636:
4633:
4627:
4624:
4615:
4614:
4611:
4587:
4584:
4563:
4560:
4556:
4555:
4525:
4511:
4505:
4498:
4495:
4487:
4484:
4481:
4480:
4477:
4474:
4471:
4468:
4465:
4462:
4458:
4457:
4454:
4451:
4448:
4445:
4442:
4439:
4435:
4434:
4431:
4428:
4425:
4422:
4419:
4416:
4412:
4411:
4408:
4405:
4402:
4399:
4396:
4393:
4389:
4388:
4385:
4382:
4379:
4376:
4373:
4370:
4366:
4365:
4362:
4359:
4356:
4353:
4350:
4347:
4343:
4342:
4339:
4336:
4333:
4330:
4327:
4324:
4320:
4319:
4316:
4313:
4310:
4307:
4304:
4301:
4297:
4296:
4293:
4290:
4287:
4284:
4281:
4278:
4274:
4273:
4270:
4267:
4264:
4261:
4258:
4255:
4242:
4241:
4236:
4233:
4223:
4222:
4217:
4214:
4201:
4200:
4194:
4188:
4182:
4176:
4170:
4167:
4142:
4139:
4128:
4127:
4121:
4115:
4109:
4103:
4097:
4094:
4069:
4066:
4051:
4050:
4045:
4042:
4033:
4032:
4026:
4023:
4017:
4014:
4008:
4005:
3996:
3995:
3990:
3987:
3978:
3977:
3972:
3969:
3960:
3959:
3956:
3945:
3921:
3918:
3915:
3912:
3909:
3906:
3903:
3900:
3897:
3894:
3891:
3860:
3859:
3853:
3847:
3841:
3835:
3829:
3823:
3817:
3811:
3805:
3799:
3793:
3790:
3778:
3773:
3770:
3768:
3765:
3761:
3760:
3757:
3754:
3751:
3748:
3745:
3735:
3734:
3726:
3723:
3702:
3699:
3698:
3697:
3688:
3683:then the item
3667:
3650:
3644:
3637:
3633:
3630:
3623:
3617:
3611:
3610:+ B and E β E
3605:
3600:
3597:
3590:
3584:
3573:
3572:
3567:
3564:
3558:
3555:
3549:
3546:
3540:
3524:
3521:
3519:
3516:
3507:
3506:
3499:
3498:
3492:
3491:
3478:
3477:
3471:
3470:
3463:
3462:
3452:
3451:
3444:
3443:
3436:
3433:
3430:
3429:
3426:
3424:
3421:
3418:
3414:
3413:
3410:
3408:
3405:
3402:
3398:
3397:
3394:
3392:
3389:
3386:
3382:
3381:
3378:
3376:
3373:
3370:
3366:
3365:
3362:
3360:
3357:
3354:
3350:
3349:
3346:
3344:
3341:
3338:
3334:
3333:
3330:
3328:
3326:
3323:
3319:
3318:
3315:
3313:
3311:
3308:
3304:
3303:
3300:
3297:
3296:Output stream
3294:
3291:
3280:
3277:
3264:
3263:
3257:
3243:
3220:
3219:
3216:
3213:
3210:
3207:
3204:
3201:
3198:
3192:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3164:
3163:
3160:
3157:
3154:
3151:
3148:
3145:
3142:
3136:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3108:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3080:
3079:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3052:
3051:
3048:
3045:
3042:
3039:
3036:
3033:
3030:
3024:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2996:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2968:
2967:
2962:
2957:
2952:
2947:
2942:
2937:
2932:
2928:
2927:
2920:
2913:
2899:
2896:
2895:
2894:
2885:
2884:
2881:
2878:
2875:
2872:
2856:
2853:
2805:if no word in
2781:
2778:Earley parsers
2745:
2744:
2733:
2713:
2710:
2661:
2658:
2640:
2637:
2604:
2603:Lookahead sets
2601:
2586:
2585:
2582:
2579:
2573:
2565:
2559:
2553:
2550:
2546:
2545:
2539:
2532:
2525:
2519:
2514:
2494:
2491:
2473:
2470:
2469:
2468:
2467:
2461:
2458:
2453:
2441:
2438:
2437:
2436:
2435:
2430:
2411:
2392:
2386:
2379:
2376:
2375:
2374:
2373:
2365:
2362:
2354:
2351:
2345:
2342:
2336:
2320:
2313:
2312:
2311:
2310:
2304:
2294:
2291:
2286:
2283:
2278:
2277:
2274:
2262:
2261:
2260:
2259:
2256:
2249:
2246:
2231:
2228:
2221:
2215:
2214:
2211:
2207:
2203:
2199:
2195:
2191:
2190:
2189:
2188:
2181:
2171:
2170:
2138:
2137:LR parser loop
2135:
2110:
2109:
2108:
2107:
2101:
2098:
2093:
2072:
2071:
2070:
2069:
2063:
2048:
2047:
2045:
2043:
2041:
2039:
2036:
2033:
2030:
2028:
2026:
2021:
2015:
2011:
2010:
2008:
2006:
2004:
2002:
1999:
1996:
1993:
1991:
1989:
1984:
1978:
1974:
1973:
1971:
1969:
1967:
1965:
1962:
1959:
1956:
1954:
1952:
1947:
1944:
1940:
1939:
1937:
1935:
1933:
1931:
1928:
1925:
1922:
1920:
1918:
1913:
1910:
1906:
1905:
1902:
1900:
1898:
1896:
1894:
1892:
1890:
1887:
1884:
1878:
1875:
1871:
1870:
1868:
1866:
1864:
1862:
1857:
1852:
1848:
1846:
1844:
1838:
1831:
1828:
1824:
1823:
1821:
1819:
1817:
1815:
1810:
1805:
1801:
1799:
1797:
1791:
1784:
1781:
1777:
1776:
1773:
1770:
1768:
1766:
1764:
1762:
1760:
1757:
1754:
1748:
1747:Sums β Sums +
1745:
1741:
1740:
1738:
1736:
1734:
1732:
1727:
1723:
1721:
1719:
1717:
1711:
1701:
1698:
1694:
1693:
1690:
1687:
1684:
1682:
1680:
1678:
1676:
1673:
1670:
1661:
1658:
1654:
1653:
1650:
1647:
1644:
1642:
1637:
1634:
1631:
1626:
1621:
1618:
1614:
1613:
1610:
1608:
1605:
1603:
1591:
1585:
1569:
1516:parsing tables
1506:
1503:
1431:The grammar's
1429:
1428:
1427:
1426:
1420:
1414:
1411:
1408:
1405:
1402:
1381:
1378:
1370:
1369:
1368:
1367:
1338:
1337:
1334:
1327:
1300:
1299:
1296:
1289:
1280:
1279:
1277:
1275:
1272:
1270:
1265:
1259:
1253:
1250:
1246:
1245:
1240:
1237:
1234:
1232:
1227:
1221:
1215:
1209:
1203:
1200:
1196:
1195:
1190:
1187:
1184:
1182:
1177:
1171:
1165:
1159:
1153:
1150:
1146:
1145:
1140:
1134:
1131:
1129:
1124:
1118:
1110:
1104:
1098:
1095:
1091:
1090:
1085:
1083:
1080:
1075:
1070:
1064:
1058:
1052:
1049:
1045:
1044:
1039:
1037:
1034:
1031:
1028:
1022:
1016:
1013:
1009:
1008:
1003:
1000:
997:
994:
991:
985:
979:
976:
972:
971:
966:
963:
960:
957:
954:
948:
942:
936:
930:
927:
923:
922:
917:
911:
908:
905:
902:
896:
888:
882:
876:
873:
869:
868:
863:
861:
858:
855:
850:
844:
838:
832:
829:
825:
824:
819:
817:
814:
811:
808:
802:
796:
793:
789:
788:
783:
780:
777:
774:
771:
765:
759:
756:
752:
751:
746:
740:
737:
734:
731:
725:
717:
714:
710:
709:
704:
702:
699:
696:
691:
685:
682:
678:
677:
670:
664:
657:
651:
644:
637:
632:
606:
603:
594:
593:
584:
583:
580:
575:
572:
568:
567:
564:
559:
556:
552:
551:
548:
543:
540:
536:
535:
529:
524:
518:
514:
513:
510:
507:
504:
500:
499:
496:
493:
490:
486:
485:
482:
479:
476:
472:
471:
468:
465:
462:
458:
457:
451:
448:
442:
438:
437:
434:
431:
428:
424:
423:
420:
417:
414:
410:
409:
406:
403:
400:
396:
395:
389:
386:
381:
377:
376:
373:
370:
365:
361:
360:
355:
350:
345:
336:
333:
303:
300:
283:
282:
275:
263:
260:
238:
232:
230:
227:
185:
116:formal grammar
82:are a type of
70:
69:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
5395:
5384:
5381:
5380:
5378:
5363:
5360:
5358:
5355:
5353:
5350:
5348:
5345:
5343:
5340:
5338:
5335:
5331:
5328:
5327:
5326:
5323:
5321:
5318:
5316:
5313:
5311:
5308:
5306:
5303:
5301:
5298:
5297:
5295:
5291:
5284:
5280:
5277:
5276:
5275:
5272:
5270:
5267:
5266:
5264:
5260:
5254:
5251:
5249:
5246:
5244:
5241:
5237:
5234:
5232:
5229:
5227:
5224:
5222:
5219:
5218:
5217:
5214:
5208:
5207:Shunting-yard
5205:
5204:
5203:
5200:
5198:
5195:
5194:
5192:
5191:
5189:
5187:
5183:
5175:
5172:
5171:
5170:
5167:
5165:
5162:
5160:
5157:
5156:
5154:
5152:
5148:
5144:
5137:
5132:
5130:
5125:
5123:
5118:
5117:
5114:
5108:
5105:
5103:
5100:
5098:
5095:
5093:
5090:
5088:
5085:
5082:
5079:
5076:
5073:
5070:
5069:dickgrune.com
5067:
5066:
5062:
5058:
5054:
5050:
5047:
5045:
5044:0-521-30413-X
5041:
5037:
5033:
5032:
5027:
5026:
5022:
5013:
5010:
5004:
5001:
4995:
4993:0-201-02988-X
4989:
4985:
4984:
4976:
4973:
4967:
4964:
4958:
4955:
4951:
4947:
4941:
4938:
4932:
4929:
4923:
4921:
4917:
4911:
4908:
4902:
4899:
4895:
4889:
4886:
4883:
4878:
4875:
4870:
4864:
4860:
4859:Prentice Hall
4856:
4852:
4851:
4846:
4842:
4836:
4834:
4830:
4824:
4819:
4815:
4811:
4807:
4804:(July 1965).
4803:
4797:
4795:
4793:
4789:
4783:
4779:
4776:
4774:
4773:Look-Ahead LR
4771:
4769:
4766:
4764:
4761:
4760:
4756:
4754:
4752:
4748:
4744:
4740:
4736:
4732:
4728:
4723:
4712:
4704:
4702:
4699:
4698:
4697:
4691:
4688:
4685:
4682:
4681:
4680:
4677:
4675:
4671:
4657:
4654:
4645:
4642:
4634:
4625:
4623:
4620:
4619:
4618:
4612:
4609:
4608:
4607:
4604:
4602:
4601:dangling else
4598:
4594:
4585:
4583:
4581:
4577:
4573:
4568:
4561:
4559:
4553:
4549:
4545:
4541:
4537:
4533:
4524:
4520:
4516:
4512:
4503:
4499:
4496:
4493:
4492:
4491:
4485:
4478:
4475:
4472:
4469:
4466:
4463:
4460:
4459:
4455:
4452:
4449:
4446:
4443:
4440:
4437:
4436:
4432:
4429:
4426:
4423:
4420:
4417:
4414:
4413:
4409:
4406:
4403:
4400:
4397:
4394:
4391:
4390:
4386:
4383:
4380:
4377:
4374:
4371:
4368:
4367:
4363:
4360:
4357:
4354:
4351:
4348:
4345:
4344:
4340:
4337:
4334:
4331:
4328:
4325:
4322:
4321:
4317:
4314:
4311:
4308:
4305:
4302:
4299:
4298:
4294:
4291:
4288:
4285:
4282:
4279:
4276:
4275:
4271:
4268:
4265:
4262:
4259:
4256:
4253:
4252:
4249:
4246:
4234:
4232:
4229:
4228:
4227:
4215:
4213:
4210:
4209:
4208:
4204:
4192:
4189:
4180:
4177:
4168:
4166:
4163:
4162:
4161:
4140:
4137:
4119:
4116:
4107:
4104:
4095:
4093:
4090:
4089:
4088:
4067:
4064:
4054:
4043:
4041:
4038:
4037:
4036:
4024:
4015:
4006:
4004:
4001:
4000:
3999:
3988:
3986:
3983:
3982:
3981:
3970:
3968:
3965:
3964:
3963:
3957:
3954:
3950:
3946:
3943:
3939:
3935:
3934:
3933:
3916:
3913:
3910:
3907:
3904:
3901:
3898:
3892:
3889:
3879:
3877:
3873:
3869:
3865:
3851:
3848:
3839:
3836:
3827:
3824:
3815:
3812:
3803:
3800:
3791:
3789:
3786:
3785:
3784:
3771:
3766:
3764:
3758:
3755:
3752:
3750:(2) E β E + B
3749:
3747:(1) E β E * B
3746:
3744:(0) S β E eof
3743:
3742:
3741:
3738:
3733:(0) S β E eof
3732:
3731:
3730:
3724:
3722:
3720:
3716:
3712:
3708:
3700:
3695:
3686:
3682:
3678:
3674:
3666:
3662:
3658:
3657:
3656:
3631:
3629:
3598:
3596:
3582:
3578:
3565:
3556:
3547:
3538:
3537:
3536:
3534:
3530:
3522:
3517:
3515:
3513:
3505:
3504:
3503:
3497:
3496:
3495:
3490:
3489:
3488:
3485:
3483:
3476:
3475:
3474:
3469:
3468:
3467:
3461:
3460:
3459:
3455:
3450:
3449:
3448:
3442:
3441:
3440:
3434:
3427:
3425:
3422:
3419:
3416:
3415:
3411:
3409:
3406:
3403:
3400:
3399:
3395:
3393:
3390:
3387:
3384:
3383:
3379:
3377:
3374:
3371:
3368:
3367:
3363:
3361:
3358:
3355:
3352:
3351:
3347:
3345:
3342:
3339:
3336:
3335:
3331:
3329:
3327:
3324:
3321:
3320:
3316:
3314:
3312:
3309:
3306:
3305:
3301:
3298:
3295:
3293:Input stream
3292:
3289:
3288:
3285:
3279:Parsing steps
3278:
3276:
3274:
3269:
3261:
3258:
3255:
3251:
3247:
3244:
3242:
3238:
3234:
3231:
3230:
3229:
3227:
3217:
3214:
3211:
3208:
3205:
3202:
3199:
3197:
3194:
3193:
3189:
3186:
3183:
3180:
3177:
3174:
3171:
3169:
3166:
3165:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3141:
3138:
3137:
3133:
3130:
3127:
3124:
3121:
3118:
3115:
3113:
3110:
3109:
3105:
3102:
3099:
3096:
3093:
3090:
3087:
3085:
3082:
3081:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3057:
3054:
3053:
3049:
3046:
3043:
3040:
3037:
3034:
3031:
3029:
3026:
3025:
3021:
3018:
3015:
3012:
3009:
3006:
3003:
3001:
2998:
2997:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2973:
2970:
2969:
2966:
2963:
2961:
2958:
2956:
2953:
2951:
2948:
2946:
2943:
2941:
2938:
2936:
2933:
2930:
2929:
2926:
2925:
2919:
2918:
2912:
2911:
2907:
2906:
2903:
2897:
2893:
2890:
2889:
2888:
2882:
2879:
2876:
2873:
2870:
2869:
2868:
2861:
2854:
2852:
2850:
2843:
2839:
2837:
2832:
2828:
2824:
2820:
2817:. A language
2816:
2812:
2811:proper prefix
2808:
2804:
2800:
2796:
2792:
2787:
2779:
2775:
2773:
2768:
2766:
2762:
2758:
2757:Frank DeRemer
2752:
2750:
2742:
2738:
2734:
2731:
2727:
2726:
2725:
2723:
2719:
2711:
2709:
2706:
2703:
2699:
2696:
2693:
2689:
2687:
2682:
2680:
2675:
2670:
2666:
2659:
2657:
2653:
2650:
2645:
2638:
2636:
2632:
2629:
2624:
2621:
2617:
2614:
2609:
2602:
2600:
2596:
2594:
2580:
2578:
2572:
2551:
2548:
2547:
2540:
2533:
2515:
2509:
2508:
2505:
2502:
2500:
2492:
2490:
2488:
2483:
2479:
2459:
2451:
2450:
2449:
2448:
2447:
2429:
2425:
2424:
2423:
2422:
2421:
2419:
2407:
2405:
2401:
2372:
2363:
2361:
2352:
2343:
2334:
2333:
2332:
2331:
2330:
2327:
2318:
2302:
2301:
2300:
2299:
2298:
2292:
2290:
2284:
2282:
2275:
2272:
2268:
2264:
2263:
2257:
2254:
2250:
2247:
2244:
2240:
2236:
2232:
2229:
2226:
2222:
2219:
2218:
2217:
2216:
2193:
2192:
2186:
2182:
2179:
2175:
2174:
2173:
2172:
2168:
2164:
2163:
2162:
2160:
2156:
2152:
2148:
2143:
2136:
2134:
2130:
2125:
2123:
2119:
2115:
2099:
2091:
2090:
2089:
2088:
2087:
2083:
2081:
2077:
2061:
2060:
2059:
2058:
2057:
2055:
2046:
2044:
2042:
2040:
2037:
2034:
2031:
2029:
2027:
2020:
2016:
2013:
2012:
2009:
2007:
2005:
2003:
2000:
1997:
1994:
1992:
1990:
1983:
1979:
1976:
1975:
1972:
1970:
1968:
1966:
1963:
1960:
1957:
1955:
1953:
1945:
1942:
1941:
1938:
1936:
1934:
1932:
1929:
1926:
1923:
1921:
1919:
1911:
1908:
1907:
1903:
1901:
1899:
1897:
1895:
1893:
1891:
1888:
1885:
1876:
1873:
1872:
1869:
1867:
1865:
1863:
1858:
1853:
1849:
1847:
1845:
1829:
1826:
1825:
1822:
1820:
1818:
1816:
1811:
1806:
1802:
1800:
1798:
1782:
1779:
1778:
1774:
1771:
1769:
1767:
1765:
1763:
1761:
1758:
1755:
1746:
1743:
1742:
1739:
1737:
1735:
1733:
1728:
1724:
1722:
1720:
1718:
1708:
1699:
1696:
1695:
1691:
1688:
1685:
1683:
1681:
1679:
1677:
1674:
1671:
1669:
1659:
1656:
1655:
1651:
1648:
1645:
1643:
1641:
1638:
1635:
1632:
1630:
1627:
1625:
1622:
1620:Current Rules
1619:
1616:
1615:
1609:
1604:
1601:
1600:
1597:
1581:
1578:
1573:
1568:
1564:
1560:
1555:
1551:
1549:
1545:
1543:
1538:
1536:
1530:
1528:
1524:
1519:
1517:
1513:
1504:
1502:
1500:
1499:CYK algorithm
1496:
1495:Earley parser
1492:
1487:
1482:
1478:
1476:
1472:
1467:
1465:
1461:
1457:
1453:
1449:
1445:
1442:
1438:
1434:
1425:
1421:
1419:
1415:
1412:
1409:
1406:
1403:
1401:
1397:
1396:
1395:
1394:
1393:
1390:
1388:
1379:
1377:
1375:
1365:
1364:
1363:
1362:
1361:
1359:
1353:
1351:
1347:
1343:
1335:
1332:
1328:
1325:
1321:
1320:
1319:
1315:
1313:
1309:
1305:
1297:
1294:
1290:
1287:
1286:
1285:
1278:
1276:
1273:
1271:
1269:
1266:
1264:
1251:
1248:
1247:
1241:
1238:
1235:
1233:
1231:
1228:
1226:
1201:
1198:
1197:
1191:
1188:
1185:
1183:
1181:
1178:
1176:
1151:
1148:
1147:
1141:
1139:
1135:
1132:
1130:
1128:
1125:
1123:
1117:
1096:
1093:
1092:
1086:
1084:
1081:
1079:
1074:
1071:
1069:
1050:
1047:
1046:
1040:
1038:
1035:
1029:
1027:
1014:
1011:
1010:
1004:
1001:
998:
992:
990:
977:
974:
973:
967:
964:
961:
955:
953:
928:
925:
924:
918:
916:
912:
909:
903:
901:
895:
874:
871:
870:
864:
862:
859:
854:
851:
849:
830:
827:
826:
820:
818:
815:
809:
807:
794:
791:
790:
784:
781:
778:
772:
770:
757:
754:
753:
747:
745:
741:
738:
732:
730:
724:
715:
712:
711:
705:
703:
700:
695:
692:
690:
683:
680:
679:
671:
665:
658:
652:
645:
633:
627:
626:
623:
615:
613:
604:
602:
600:
591:
590:
589:
581:
579:
576:
573:
570:
569:
565:
563:
560:
557:
554:
553:
549:
547:
544:
541:
538:
537:
534:
530:
528:
525:
523:
519:
516:
515:
511:
505:
502:
501:
497:
491:
488:
487:
483:
477:
474:
473:
469:
463:
460:
459:
456:
452:
447:
443:
440:
439:
435:
429:
426:
425:
421:
415:
412:
411:
407:
401:
398:
397:
394:
390:
385:
382:
379:
378:
374:
369:
366:
363:
362:
356:
351:
346:
341:
340:
334:
332:
330:
325:
321:
316:
308:
301:
299:
297:
291:
287:
280:
276:
273:
269:
268:
267:
261:
259:
255:
252:
243:
233:
228:
226:
224:
220:
216:
212:
208:
204:
203:
198:
194:
189:
183:
179:
175:
169:
167:
163:
159:
155:
151:
148:
144:
141:)". To avoid
140:
136:
132:
128:
123:
121:
117:
113:
109:
105:
101:
97:
93:
89:
86:that analyse
85:
81:
77:
66:
63:
55:
52:November 2023
45:
41:
35:
32:This article
30:
21:
20:
5262:Mixed, other
5253:Shift-reduce
5215:
5057:0-534-939724
5030:
5012:
5003:
4982:
4975:
4966:
4957:
4945:
4940:
4931:
4910:
4901:
4888:
4877:
4849:
4813:
4809:
4802:Knuth, D. E.
4746:
4742:
4738:
4734:
4730:
4724:
4721:
4700:
4695:
4678:
4673:
4669:
4667:
4655:
4643:
4621:
4616:
4605:
4596:
4592:
4589:
4571:
4569:
4565:
4557:
4551:
4547:
4543:
4539:
4535:
4531:
4522:
4518:
4514:
4501:
4489:
4247:
4243:
4230:
4224:
4211:
4205:
4202:
4190:
4178:
4164:
4129:
4117:
4105:
4091:
4055:
4052:
4039:
4034:
4002:
3997:
3984:
3979:
3966:
3961:
3952:
3948:
3941:
3937:
3880:
3875:
3871:
3867:
3861:
3849:
3837:
3825:
3813:
3801:
3787:
3775:
3762:
3739:
3736:
3728:
3718:
3714:
3710:
3706:
3704:
3693:
3684:
3680:
3676:
3672:
3664:
3660:
3635:
3602:
3580:
3576:
3574:
3532:
3528:
3526:
3508:
3500:
3493:
3486:
3479:
3472:
3464:
3456:
3453:
3445:
3438:
3302:Next action
3282:
3272:
3267:
3265:
3259:
3253:
3249:
3245:
3240:
3236:
3232:
3226:action table
3225:
3223:
3195:
3167:
3139:
3111:
3083:
3055:
3027:
2999:
2971:
2964:
2959:
2954:
2949:
2944:
2939:
2934:
2923:
2922:
2916:
2915:
2909:
2908:
2901:
2891:
2886:
2866:
2841:
2835:
2830:
2822:
2818:
2814:
2806:
2802:
2798:
2794:
2790:
2788:
2776:
2771:
2769:
2753:
2748:
2746:
2740:
2736:
2729:
2718:Donald Knuth
2715:
2701:
2700:
2691:
2690:
2683:
2671:
2667:
2663:
2654:
2646:
2642:
2633:
2628:Canonical LR
2627:
2625:
2619:
2618:
2612:
2610:
2606:
2597:
2592:
2589:
2570:
2552:
2503:
2496:
2486:
2484:
2480:
2471:
2439:
2427:
2426:r5: Value β
2417:
2408:
2403:
2399:
2377:
2370:
2364:r6: Value β
2359:
2353:r5: Value β
2328:
2316:
2314:
2296:
2288:
2279:
2270:
2266:
2252:
2242:
2238:
2234:
2224:
2184:
2177:
2166:
2158:
2154:
2150:
2146:
2144:
2140:
2131:
2127:
2121:
2117:
2113:
2111:
2085:
2079:
2075:
2073:
2053:
2051:
2018:
1981:
1710:Sums β Sums
1706:
1700:Goal β Sums
1667:
1639:
1628:
1623:
1582:
1576:
1574:
1566:
1562:
1558:
1556:
1552:
1541:
1534:
1531:
1520:
1515:
1512:parse tables
1511:
1508:
1483:
1479:
1474:
1468:
1463:
1459:
1455:
1451:
1447:
1443:
1440:
1430:
1423:
1422:r6: Value β
1417:
1416:r5: Value β
1399:
1391:
1383:
1373:
1371:
1357:
1355:
1349:
1345:
1341:
1339:
1330:
1323:
1317:
1311:
1307:
1303:
1301:
1292:
1283:
1267:
1252:
1229:
1202:
1179:
1152:
1137:
1126:
1115:
1097:
1077:
1072:
1051:
1015:
978:
929:
914:
893:
875:
852:
831:
795:
758:
743:
722:
716:
693:
684:
668:Grammar Rule
620:state number
616:
612:parser state
611:
608:
595:
587:
577:
561:
545:
542:Sums + Value
532:
526:
521:
454:
445:
392:
383:
367:
358:Shift/Reduce
323:
317:
313:
295:
292:
288:
284:
278:
271:
265:
256:
248:
215:Donald Knuth
209:, including
201:
200:
196:
192:
190:
170:
165:
161:
157:
146:
143:backtracking
138:
124:
96:LALR parsers
79:
73:
58:
49:
33:
5320:Memoization
5285:Statistical
5279:Left corner
5236:Generalized
5193:Precedence
4686:(2) E β B 2
4683:(1) E β A 1
4610:(1) E β 1 E
3622:+ B, E β E
3529:LR(0) items
3435:Walkthrough
2883:(5) B β 1
2880:(4) B β 0
2877:(3) E β B
2517:Parse Stack
2241:and column
2157:and column
1486:unambiguous
1333:symbol, and
1295:symbol, and
635:Parse Stack
444:Products *
348:Parse Stack
324:parse stack
92:SLR parsers
5337:Parse tree
5269:Combinator
5226:Look-ahead
4784:References
4701:Item set 1
4622:Item set 1
4235:E β E + B
4231:Item set 8
4216:E β E * B
4212:Item set 7
4165:Item set 6
4092:Item set 5
4040:Item set 4
4003:Item set 3
3985:Item set 2
3967:Item set 1
3788:Item set 0
3649:1 and B β
3566:E β E + B
3273:goto table
3268:goto table
2735:For every
1716:+ Products
1525:tool like
1462:values or
430:Products *
251:parse tree
223:LL parsing
80:LR parsers
5231:Canonical
5186:Bottom-up
4768:Simple LR
4727:LL parser
4692:(4) B β 1
4689:(3) A β 1
4613:(2) E β 1
4603:problem.
4254:Item Set
4130:and for
3893:∈
3864:boldfaced
3759:(5) B β 1
3756:(4) B β 0
3753:(3) E β B
3599:Item sets
3412:Reduce 2
3396:Reduce 5
3348:Reduce 3
3332:Reduce 5
2789:While LR(
2759:invented
2543:Unscanned
2293:LR states
2237:from row
2202:: Lhs β S
1633:*
1612:LHS Goto
1607:Lookahead
1497:, or the
1475:recursive
655:Unscanned
296:lookahead
150:lookahead
5377:Category
5202:Operator
5151:Top-down
5038:, 1987.
4847:(1972).
4757:See also
4538:is rule
4169:E β E +
4096:E β E *
3717:) where
3557:E β E +
3423:5,3,5,2
3380:Shift 2
3364:Shift 6
3317:Shift 2
2849:alphabet
2558:Products
2309:Products
2194:Reduce r
2068:Products
2017:Value β
1980:Value β
1753:Products
1649:Products
1636:+
1220:Products
1136:Value β
984:Products
935:Products
913:Value β
881:Products
837:Products
801:Products
742:Value β
599:semantic
531:Value β
478:Products
453:Value β
416:Products
391:Value β
353:Unparsed
322:. This
236:A*2 + 1
229:Overview
133:β not a
4479:
4456:
4387:
4364:
4341:
4318:
3783:E eof:
3707:closure
3628:* B }.
3428:Accept
3218:
3190:
3106:
3078:
3050:
3022:
2931:
2672:In the
2647:In the
2524:Symbol
2466:* Value
2269:is the
2106:* Value
1843:* Value
1796:* Value
1660:Goal β
582:accept
520:Sums +
372:A*2 + 1
154:symbols
114:from a
38:Please
5221:Simple
5197:Simple
5159:Earley
5055:
5042:
4990:
4865:
4713:B β 1
4705:A β 1
4674:and r2
4635:E β 1
4626:E β 1
4476:
4473:
4470:
4467:
4464:
4453:
4450:
4447:
4444:
4441:
4430:
4421:
4418:
4407:
4398:
4395:
4384:
4381:
4378:
4375:
4372:
4361:
4358:
4355:
4338:
4335:
4332:
4329:
4326:
4315:
4312:
4309:
4306:
4303:
4283:
4280:
4044:E β B
4025:E β E
4016:E β E
4007:S β E
3989:B β 1
3971:B β 0
3876:kernel
3548:E β E
3407:5,3,5
3310:1+1$
3299:Stack
3290:State
3260:accept
3246:reduce
3215:
3187:
3159:
3156:
3147:
3144:
3131:
3128:
3119:
3116:
3103:
3075:
3069:
3066:
3047:
3019:
2988:
2979:
2976:
2917:action
2712:Theory
2686:Prolog
2165:Shift
1861:
1856:
1814:
1809:
1731:
1729:accept
1652:Value
1559:Action
1493:, the
1274:accept
1236:reduce
1186:reduce
1133:reduce
999:reduce
962:reduce
910:reduce
779:reduce
739:reduce
698:*2 + 1
662:Action
660:Parser
512:shift
506:Sums +
498:shift
436:shift
422:shift
419:*2 + 1
405:*2 + 1
388:*2 + 1
375:shift
279:Reduce
199:, and
178:Earley
152:input
106:, and
5274:Chart
4896:2011.
4542:with
3822:E + B
3810:E * B
3798:E eof
3545:E + B
3533:items
3523:Items
3356:+1$
3340:+1$
3325:+1$
3233:shift
2910:state
2892:1 + 1
2845:'
2825:is a
2809:is a
2537:Ahead
2527:state
2521:state
2350:Value
2210:... S
1883:Value
1666:Sums
1617:State
1546:, or
1527:Bison
1170:Value
1082:shift
1036:shift
947:Value
860:shift
816:shift
813:2 + 1
776:2 + 1
764:Value
736:2 + 1
701:shift
675:State
649:Ahead
639:state
433:2 + 1
402:Value
368:empty
320:stack
272:Shift
5330:LALR
5053:ISBN
5040:ISBN
4988:ISBN
4863:ISBN
4658:E β
4646:E β
4580:LALR
4578:and
4530:and
4510:eof.
4193:B β
4181:B β
4120:B β
4108:B β
3862:The
3852:B β
3840:B β
3828:E β
3816:E β
3804:E β
3792:S β
3711:clos
3539:E β
3391:5,3
3375:5,3
3372:1$
3359:5,3
3266:The
3224:The
2924:goto
2765:LALR
2763:and
2728:"LR(
2649:yacc
2620:LALR
2535:Look
2512:Step
2402:and
2378:The
1646:Sums
1602:Curr
1577:Goto
1575:The
1557:The
1542:LALR
1514:(or
1446:and
1258:Sums
1208:Sums
1158:Sums
1103:Sums
1057:Sums
1021:Sums
673:Next
647:Look
630:Step
574:Sums
492:Sums
343:Step
5342:AST
5300:PEG
5243:CYK
4818:doi
4652:1 E
4576:SLR
4502:acc
4031:+ B
4022:* B
4013:eof
3694:w'
3681:w'
3554:+ B
3420:$
3404:$
3388:$
3072:acc
2761:SLR
2692:GLR
2613:SLR
2611:In
2593:int
2571:int
2530:...
2428:int
2418:int
2400:int
2360:int
2271:eof
2243:Lhs
2122:eof
2078:or
2076:int
1982:int
1859:r2
1854:r2
1812:r1
1807:r1
1707:eof
1668:eof
1640:eof
1624:int
1572:).
1535:SLR
1460:int
1456:eof
1448:int
1418:int
1400:eof
1358:eof
1346:int
1342:int
1331:int
1268:eof
1230:eof
1180:eof
1138:int
1127:eof
1116:int
1078:eof
1073:int
915:int
894:int
857:+ 1
853:int
578:eof
562:eof
546:eof
533:int
527:eof
522:int
495:+ 1
481:+ 1
467:+ 1
455:int
450:+ 1
446:int
331:.)
182:GLR
168:."
74:In
42:to
5379::
5216:LR
5164:LL
5034:,
4919:^
4861:.
4857::
4843:;
4832:^
4812:.
4808:.
4791:^
4753:.
4741:β
4670:s1
4572:LR
4534:β
4521:β
4461:8
4438:7
4433:8
4415:6
4410:7
4392:5
4369:4
4346:3
4323:2
4300:1
4295:4
4277:0
4272:B
4269:E
4266:1
4263:0
4260:+
4257:*
3687:β
3679:β
3673:Bw
3663:β
3583:β
3417:3
3401:8
3385:2
3369:6
3353:3
3343:5
3337:4
3322:2
3307:0
3212:r2
3209:r2
3206:r2
3203:r2
3200:r2
3184:r1
3181:r1
3178:r1
3175:r1
3172:r1
3162:8
3153:s2
3150:s1
3134:7
3125:s2
3122:s1
3100:r3
3097:r3
3094:r3
3091:r3
3088:r3
3063:s6
3060:s5
3044:r5
3041:r5
3038:r5
3035:r5
3032:r5
3016:r4
3013:r4
3010:r4
3007:r4
3004:r4
2994:4
2985:s2
2982:s1
2955:$
2851:.
2847:s
2838:$
2702:LC
2688:.
2681:.
2584:1
2406:.
2404:id
2371:id
2080:id
2038:r6
2035:r6
2032:r6
2019:id
2001:r5
1998:r5
1995:r5
1964:r4
1961:r4
1958:r4
1930:r3
1927:r3
1924:r3
1904:6
1775:7
1692:7
1629:id
1539:,
1529:.
1464:id
1452:id
1424:id
1385:a
1308:id
1304:id
1293:id
1249:13
1199:12
1149:11
1094:10
744:id
723:id
694:id
642:*
571:13
555:12
539:11
517:10
393:id
384:id
277:A
270:A
195:,
180:,
176:,
122:.
102:,
98:,
94:,
78:,
5135:e
5128:t
5121:v
4996:.
4946:k
4871:.
4826:.
4820::
4814:8
4747:A
4743:w
4739:A
4735:A
4731:A
4716:β’
4708:β’
4664:1
4661:β’
4656:+
4649:β’
4644:+
4638:β’
4632:E
4629:β’
4554:.
4552:m
4548:i
4544:m
4540:m
4536:w
4532:A
4527:β’
4523:w
4519:A
4515:i
4507:β’
4427:2
4424:1
4404:2
4401:1
4352:6
4349:5
4292:3
4289:2
4286:1
4238:β’
4219:β’
4199:1
4196:β’
4191:+
4187:0
4184:β’
4179:+
4175:B
4172:β’
4146:+
4141:=
4138:x
4126:1
4123:β’
4118:+
4114:0
4111:β’
4106:+
4102:B
4099:β’
4073:*
4068:=
4065:x
4047:β’
4028:β’
4019:β’
4010:β’
3992:β’
3974:β’
3955:.
3953:x
3949:S
3944:.
3942:x
3938:S
3920:}
3917:B
3914:,
3911:E
3908:,
3905:1
3902:,
3899:0
3896:{
3890:x
3872:+
3868:+
3866:"
3858:1
3855:β’
3850:+
3846:0
3843:β’
3838:+
3834:B
3831:β’
3826:+
3819:β’
3814:+
3807:β’
3802:+
3795:β’
3780:β’
3719:I
3715:I
3713:(
3690:β’
3685:B
3677:B
3669:β’
3665:v
3661:A
3652:β’
3646:β’
3639:β’
3625:β’
3619:β’
3613:β’
3607:β’
3592:β’
3586:β’
3581:A
3577:A
3569:β’
3563:B
3560:β’
3551:β’
3542:β’
3254:m
3250:m
3241:n
3237:n
3196:8
3168:7
3140:6
3112:5
3084:4
3056:3
3028:2
3000:1
2991:3
2972:0
2965:B
2960:E
2950:1
2945:0
2940:+
2935:*
2842:L
2836:L
2831:L
2823:L
2819:L
2815:L
2807:L
2799:L
2795:k
2791:k
2783:β’
2749:k
2741:k
2737:k
2730:k
2581:+
2575:8
2567:5
2564:*
2561:4
2555:0
2549:5
2487:k
2475:β’
2463:β’
2455:β’
2443:β’
2432:β’
2413:β’
2394:β’
2388:β’
2381:β’
2367:β’
2356:β’
2347:β’
2338:β’
2322:β’
2317:+
2306:β’
2267:t
2253:n
2239:p
2235:n
2225:p
2212:L
2208:2
2206:S
2204:1
2200:m
2196:m
2185:n
2178:t
2169::
2167:n
2159:t
2155:s
2151:t
2147:s
2118:*
2114:*
2103:β’
2095:β’
2065:β’
2054:+
2023:β’
2014:9
1986:β’
1977:8
1949:β’
1943:7
1915:β’
1909:6
1889:9
1886:8
1880:β’
1874:5
1851:5
1840:β’
1833:β’
1827:4
1804:5
1793:β’
1786:β’
1780:3
1772:3
1759:9
1756:8
1750:β’
1744:2
1726:2
1713:β’
1703:β’
1697:1
1689:4
1686:1
1675:9
1672:8
1663:β’
1657:0
1593:β’
1587:β’
1570:n
1567:r
1563:n
1444:*
1441:+
1374:+
1350:+
1326:,
1324:*
1312:*
1261:1
1255:0
1243:1
1223:3
1217:2
1214:+
1211:1
1205:0
1193:3
1173:7
1167:2
1164:+
1161:1
1155:0
1143:7
1120:8
1112:2
1109:+
1106:1
1100:0
1088:8
1066:2
1063:+
1060:1
1054:0
1048:9
1042:2
1033:1
1030:+
1024:1
1018:0
1012:8
1006:1
996:1
993:+
987:4
981:0
975:7
969:4
959:1
956:+
950:6
944:5
941:*
938:4
932:0
926:6
920:6
907:1
904:+
898:8
890:5
887:*
884:4
878:0
872:5
866:8
846:5
843:*
840:4
834:0
828:4
822:5
810:*
804:4
798:0
792:3
786:4
773:*
767:7
761:0
755:2
749:7
733:*
727:9
719:0
713:1
707:9
687:0
681:0
509:1
503:9
489:8
475:7
461:6
441:5
427:4
413:3
399:2
380:1
364:0
202:k
197:R
193:L
186:n
166:k
162:k
158:k
147:k
139:k
65:)
59:(
54:)
50:(
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.