computer science

Simple LR parser

Simple LR parser is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Simple LR parser rather than just read about it. In short: In computer science, a Simple LR or SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm. As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct bottom-up parse in a single left-to-right scan over the input stream, without guesswork or backtracking.

Key takeaways

Simple LR parser belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Simple LR parser to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Simple LR parser from memory before moving on to harder problems.

Reference excerpt

In computer science, a Simple LR or SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm. As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct bottom-up parse in a single left-to-right scan over the input stream, without guesswork or backtracking. The parser is mechanically generated from a formal grammar for the language. SLR and the more general methods LALR parser and Canonical LR parser have identical methods and similar tables at parse time; they differ only in the mathematical grammar analysis algorithms used by the parser generator tool. SLR and LALR generators create tables of identical size and identical parser states. SLR generators accept fewer grammars than LALR generators like yacc and Bison. Many computer languages don't readily fit the restrictions of SLR, as is. Bending the language's natural grammar into SLR grammar form requires more compromises and grammar hackery. So LALR generators have become much more widely used than SLR generators, despite being somewhat more complicated tools. SLR methods remain a useful learning step in college classes on compiler theory. SLR and LALR were both developed by Frank DeRemer as the first practical uses of Donald Knuth's LR parser theory. The tables created for real grammars by full LR methods were impractically large, larger than most computer memories of that decade, with 100 times or more parser states than the SLR and LALR methods.

Lookahead sets To understand the differences between SLR and LALR, it is important to understand their many similarities and how they both make shift-reduce decisions. (See the article LR parser now for that background, up through the section on reductions' lookahead sets.) The one difference between SLR and LALR is how their generators calculate the lookahead sets of input symbols that should appear next, whenever some completed production rule is found and reduced. SLR generators calculate that lookahead by an easy approximation method based directly on the grammar, ignoring the details of individual parser states and transitions. This ignores the particular context of the current parser state. If some nonterminal symbol S is used in several places in the grammar, SLR treats those places in the same single way rather than handling them individually. The SLR generator works out Follow(S), the set of all terminal symbols which can immediately follow some occurrence of S. In the parse 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. LALR generators calculate lookahead sets by a more precise method based on exploring the graph of parser states and their transitions. This method considers the particular context of the current parser state. It customizes the handling of each grammar occurrence of some nonterminal S. See article LALR parser for further details of this calculation. The lookahead sets calculated by LALR generators are a subset of (and hence better than) the approximate sets calculated by SLR generators. If a grammar has table conflicts when using SLR follow sets, but is conflict-free when using LALR follow sets, it is called a LALR grammar.

Example A grammar that can be parsed by an SLR parser but not by an LR(0) parser is the following:

(0) S → E (1) E → 1 E (2) E → 1 Constructing the action and goto table as is done for LR(0) parsers would give the following item sets and tables:

Item set 0 S → • E + E → • 1 E + E → • 1 Item set 1 E → 1 • E E → 1 • + E → • 1 E + E → • 1 Item set 2 S → E • Item set 3 E → 1 E • The action and goto tables:

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. This occurs because, when the action table for an LR(0) parser is created, reduce actions are inserted on a per-row basis. However, by using a follow set, reduce actions can be added with finer granularity. The follow set for this grammar:

A reduce only needs to be added to a particular action column if that action is in the follow set associated with that reduce. This algorithm describes whether a reduce action must be added to an action column:

function mustBeAdded(reduceAction, action) { ruleNumber = reduceAction.value; ruleSymbol = rules[ruleNumber].leftHandSide; return (action in followSet(ruleSymbol)) }

for example, mustBeAdded(r2, "1") is false, because the left hand side of rule 2 is "E", and 1 is not in E's follow set. Contrariwise, mustBeAdded(r2, "$") is true, because "$" is in E's follow set. By using mustBeAdded on each reduce action in the action table, the result is a conflict-free action table:

See also LR parser LL parser LALR parser SLR grammar

References

Worked examples

Example 1 — a first encounter with Simple LR parser

Start with the simplest possible case. Write down what Simple LR parser claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Simple LR parser before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Simple LR parser ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Simple LR parser

In research: Simple LR parser appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Simple LR parser in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Simple LR parser is common in secondary-school and first-year university syllabi. It links to neighbouring topics Parsing algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Simple LR parser outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Simple LR parser in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Simple LR parser means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Simple LR parser out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Simple LR parser in simple terms?

Why does Simple LR parser matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Simple LR parser?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Simple LR parser.