Simple LR parser

Simple LR parser

In computer science, a Simple LR parser or SLR parser is created by an SLR parser generator which reads a BNF grammar and constructs an LR(0) state machine and computes the look-aheads sets for each reduction in a state by examining the Follow Set for the nonterminal associated with the reduction. The Follow Set for each nonterminal symbol is computed by seeing which terminal symbols follow the nonterminal symbol in the rules of the BNF grammar. It is useful to have the First Set already computed when creating the Follow Set.

At runtime, the SLR parser will perform a reduction based on a grammar rule "A" → "w" if the next symbol in the input stream is in the Follow Set of "A" (see LL parser for a definition of Follow Set, and [http://www.jambe.co.nz/UNI/FirstAndFollowSets.html] ).

The problem with SLR parsers is that the computation of the look-ahead sets is too simplistic, using only the rules of the grammar to determine look-ahead sets. The more accurate way to determine look-ahead sets is to examine the nonterminal transitions in each state within the LR(0) state machine. These more accurate look-ahead sets are called the LALR(1) look-ahead sets.

An SLR parser will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool.

A grammar that has no conflicts reported by an SLR parser generator is an "SLR grammar".

Algorithm

The SLR parsing algorithm

Initialize the stack with S Read input symbol while (true) if Action(top(stack), input) = S NS <- Goto(top(stack),input) push NS Read next symbol else if Action(top(stack), input) = Rk output k pop |RHS| of production k from stack NS <- Goto(top(stack), LHS_k) push NS else if Action(top(stack),input) = A output valid, return else output invalid, return

Example

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

: (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:

"action""goto"
"state"1$E
0s12
1s1/r2r23
2acc
3r1r1

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. However, the follow set of E is { $ } so the reduce actions r1 and r2 are only valid in the column for $. The result are the following conflict-less action and goto table:

"action""goto"
"state"1$E
0s12
1s1r23
2acc
3r1

ee also

* LR parser
* LL parser
* LALR parser


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Simple precedence parser — In computer science, a Simple precedence parser is a type of bottom up parser for context free grammars that can be used only by Simple precedence grammars.The implementation of the parser is quite similar to the generic bottom up parser. A stack …   Wikipedia

  • Simple precedence grammar — A simple precedence grammar is a context free formal grammar that can be parsed with a simple precedence parser. TOC =Formal definition=G = ( N , Sigma;, P , S ) is a simple precedence grammar if all the production rules in P comply with the… …   Wikipedia

  • Parser combinator — In functional programming, a parser combinator is a higher order function which accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some… …   Wikipedia

  • Simple API for XML — Die Simple API for XML (SAX) ist ein De facto Standard, der ein Application Programming Interface (API) zum Parsen von XML Daten beschreibt. Die aktuelle Hauptversion SAX 2.0 wurde 2000 von David Megginson veröffentlicht und ist Public Domain.… …   Deutsch Wikipedia

  • Parser — Ein Parser [ˈpɑːʁzɐ] (engl. to parse, „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein für …   Deutsch Wikipedia

  • Parser Combinator — In mathematics and functional programming, Higher Order functions (HOF) are defined as the functions that can take functions as their input and can also produce functions as their output. The use of a HOF as an infix operator in a function… …   Wikipedia

  • Parser Grammar Engine — The Parser Grammar Engine (originally Parrot Grammar Engine) or PGE is a compiler and runtime for a Perl 6 rules for the Parrot virtual machine. [cite web | url=http://search.cpan.org/ ltoetsch/parrot 0.2.2/compilers/pge/README | title=Parrot… …   Wikipedia

  • Parser (CGI language) — Infobox programming language name = Parser paradigm = multiparadigm macro, object oriented year = since 1997 designer = Konstantin Morshnev (Art. Lebedev Studio) developer = Alexander Petrosyan (Art. Lebedev Studio) latest release version = 3.2.2 …   Wikipedia

  • Parser — Analyse syntaxique Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur… …   Wikipédia en Français

  • Simple Object Access Protocol — SOAP im TCP/IP‑Protokollstapel: Anwendung SOAP HTTP HTTPS … Transport TCP Internet IP (IPv4 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”