Вы можете отметить интересные вам фрагменты текста, которые будут доступны по уникальной ссылке в адресной строке браузера.


LALR parser

LALR parser

In computer science, a lookahead LR parser or LALR parser is a specialized form of LR parser that can deal with more context-free grammars than Simple LR (SLR) parsers. It is a very popular type of parser because it gives a good trade-off between the number of grammars it can deal with and the size of the parsing tables it requires. It is these types of parsers that are most often generated by compiler-compilers such as yacc and GNU bison.

Like SLR, LALR is a refinement to the technique for constructing LR(0) parse tables. While SLR uses "follow" sets to construct reduce actions, LALR uses "lookahead" sets, which are more specific because they take more of the parsing context into account. "follow" sets are associated with a symbol, while "lookahead" sets are specific to an LR(0) item and a parser state.

Specifically, the "follow" set for a given LR(0) item I in a given parser state S contains all symbols that are allowed by the grammar to appear after I's left-hand-side nonterminal. In contrast, the "lookahead" set for item I in state S contains only those symbols that are allowed by the grammar to appear after I's right-hand-side has been parsed starting from state S. "follow"(I) is effectively the union of the "lookahead" sets for all LR(0) items with the same left-hand-side as I, regardless of parser states or right-hand-sides, therefore losing all context information. Because the "lookahead" set is specific to a particular parsing context, it can be more selective, therefore allowing finer distinctions than the "follow" set.

References

* Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. "" Addison--Wesley, 1986. (AKA The Dragon Book, describes the traditional techniques for building LALR(1) parsers.)
* Frank DeRemer and Thomas Pennello. Efficient Computation of LALR(1) Look-Ahead Sets "ACM Transactions on Programming Languages and Systems (TOPLAS)" 4:4, pp. 615–649. 1982. (Describes a more efficient technique for building LALR(1) parsers.)
* Richard Bornat "Understanding and Writing Compilers", Macmillan, 1979. (Describes the principles of automated left-to-right parsing and how to construct the parser tables, what a follow set is, etc., "in English, not mathematics" – available freely from the author's page at [http://www.cs.mdx.ac.uk/staffpages/r_bornat/#vanitypublishing] .)

See also

* LALR Parser Generator
* Lookahead

External links

* [http://jscc.jmksf.com/ JS/CC] Interactive online implementation of a LALR(1) parser generator running in the web-browser.


Wikimedia Foundation. 2010.

  
Share  

Look at other dictionaries:

  • LALR-Parser — Im Compilerbau ist der LALR Parser (Lookahead LR Parser) ein modifizierter LR(1) Parser. Dabei werden die so genannten LR(1) Mengen, die unter der Relation identisch sind, zu einer Menge zusammengefasst. Die Relation ist wie folgt definiert: die… …   Deutsch Wikipedia

  • LALR Parser Generator — Infobox Software name = LPG caption = developer = Philippe Charles latest release version = latest release date = latest preview version = latest preview date = operating system = platform = genre = parser/scanner generator license = EPL website …   Wikipedia

  • Parser-Generator — Ein Parsergenerator ist ein Computerprogramm, das unter Eingabe einer Spezifikation einen Parser erzeugt. Inhaltsverzeichnis 1 Grundlagen 2 Algorithmen 3 Siehe auch 4 Weblinks // …   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

  • 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… …   Wikipedia

  • LR parser — In computer science, an LR parser is a parser for context free grammars that reads input from Left to right and produces a Rightmost derivation. The term LR( k ) parser is also used; here the k refers to the number of unconsumed look ahead input… …   Wikipedia

  • Text-Parser — Ein Parser [ˈpɑːɹsɚ] (engl. to parse „analysieren“ bzw. von 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… …   Deutsch Wikipedia

  • LR Parser — Ein LR Parser ist ein Bottom Up Parser für LR Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen. Inhaltsverzeichnis 1 Allgemeines 2 Aufbau… …   Deutsch Wikipedia

  • GOLD (parser) — Infobox Software name = GOLD Parsing System caption = developer = Devin Cook [http://www.devincook.com/goldparser/contributors Multiple Contributors] latest release date = 2007 07 29 latest release version = 3.4.4 operating system = Windows… …   Wikipedia

  • LR-Parser — Im Compilerbau ist ein LR Parser ein Bottom Up Parser für LR Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen. Inhaltsverzeichnis 1… …   Deutsch Wikipedia