LALR parser generator
Encyclopedia
An LALR parser generator is a software tool that reads a BNF grammar and creates an LALR parser
which is capable of parsing text files written in the computer language defined by the BNF grammar. LALR parser
s are desirable because they are very fast and small in comparison to other types of parsers.
There are other types of parser generators, such as SLR, LR, GLR and LL parser generators. What differentiates one from another is the type of BNF grammar which they are capable of accepting and the type of parsing algorithm which is used in the generated parser. Obviously, an LALR parser generator accepts an LALR grammar as input and generates a parser that uses an LALR parsing algorithm (which is driven by LALR parser tables).
In practice, LALR offers a good solution, because LALR(1) grammars are more powerful than SLR(1) and LL(1) grammars. LR(1) grammars are more powerful than LALR(1), however, canonical LR(1) parsers can be extremely large in size and are considered not practical. Minimal LR(1) parsers are small in size and comparable to LALR(1) parsers.
in his 1965 paper, "On the Translation of Languages from Left to Right", were much too large for implementation on computer systems in the 1960s and 70's.
One of the first LALR parser generators was the XPL
compiler generator, created by William McKeeman in 1968 at Stanford University. Another early LALR parser generator and probably the most popular one for many years was "yacc", created by Stephen Johnson in 1975 at AT&T Labs. Another, "TWS", was created by Frank DeRemer and Tom Pennello.
Today, there are many LALR parser generators available.
- For a more complete list, which also includes LL, SLR, GLR and LR parser generators.
LALR parser
In computer science, an LALR parser is a type of LR parser based on a finite-state-automata concept. The data structure used by an LALR parser is a pushdown automaton...
which is capable of parsing text files written in the computer language defined by the BNF grammar. LALR parser
LALR parser
In computer science, an LALR parser is a type of LR parser based on a finite-state-automata concept. The data structure used by an LALR parser is a pushdown automaton...
s are desirable because they are very fast and small in comparison to other types of parsers.
There are other types of parser generators, such as SLR, LR, GLR and LL parser generators. What differentiates one from another is the type of BNF grammar which they are capable of accepting and the type of parsing algorithm which is used in the generated parser. Obviously, an LALR parser generator accepts an LALR grammar as input and generates a parser that uses an LALR parsing algorithm (which is driven by LALR parser tables).
In practice, LALR offers a good solution, because LALR(1) grammars are more powerful than SLR(1) and LL(1) grammars. LR(1) grammars are more powerful than LALR(1), however, canonical LR(1) parsers can be extremely large in size and are considered not practical. Minimal LR(1) parsers are small in size and comparable to LALR(1) parsers.
History
Frank DeRemer invented LALR parsers with his PhD dissertation, called "Practical LR(k) Translators", in 1969, at MIT. This was an important breakthrough, because LR(k) translators, as defined by Donald KnuthDonald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
in his 1965 paper, "On the Translation of Languages from Left to Right", were much too large for implementation on computer systems in the 1960s and 70's.
One of the first LALR parser generators was the XPL
XPL
XPL is a dialect of the PL/I programming language, developed in 1967, used for the development of compilers for computer languages. It was designed and implemented by a team with , James J. Horning, and at Stanford University and the University of California, Santa Cruz...
compiler generator, created by William McKeeman in 1968 at Stanford University. Another early LALR parser generator and probably the most popular one for many years was "yacc", created by Stephen Johnson in 1975 at AT&T Labs. Another, "TWS", was created by Frank DeRemer and Tom Pennello.
Today, there are many LALR parser generators available.
See also
Comparison of parser generatorsComparison of parser generators
This is a list of notable lexer generators and parser generators for various language classes.- Regular languages :- Deterministic context-free languages :-Parsing expression grammars, deterministic boolean grammars:...
- For a more complete list, which also includes LL, SLR, GLR and LR parser generators.