LALR parser

related topics
{math, number, function}
{rate, high, increase}

An LALR parser is a type of parser defined in computer science as a Look-Ahead LR parser.

LALR parsers are based on a finite-state-automata concept, from which they derive their speed[citation needed]. The data structure used by an LALR parser is a pushdown automaton (PDA). A deterministic PDA is a deterministic-finite automaton (DFA) that uses a stack for a memory, indicating which states the parser has passed through to arrive at the current state. Because of the stack, a PDA can recognize grammars that would be impossible with a DFA; for example, a PDA can determine whether an expression has any unmatched parentheses, whereas an automaton with no stack would require an infinite number of states due to unlimited nesting of parentheses.

LALR parsers are driven by a parser table in a finite-state machine (FSM) format. An FSM is very difficult for humans to construct[citation needed] and therefore an LALR parser generator is used to create the parser table automatically from a grammar in Backus–Naur Form which defines the syntax of the computer language the parser will process. The parser table is often generated in source code format in a computer language (such as C++ or Java). When the parser (with parser table) is compiled and/or executed, it will recognize text files written in the language defined by the BNF grammar.

LALR parsers are generated from LALR grammars, which are capable of defining a larger class of languages than SLR grammars, but not as large a class as LR grammars. Real computer languages can often be expressed as LALR(1) grammars, and in cases where a LALR(1) grammar is insufficient, usually an LALR(2) grammar is adequate. If the parser generator handles only LALR(1) grammars, then the LALR parser will have to interface with some hand-written code when it encounters the special LALR(2) situation in the input language.

Contents

History

LR parsing was invented by Donald Knuth in 1965 in a paper, "On the Translation of Languages from Left to Right". LR parsers have the potential of providing the fastest parsing speed of all parsing algorithms. However, LR parsers are considered impractical because of their huge size.

LALR parsing was invented by Frank DeRemer in 1969 in a paper, "Practical LR(k) Translators". LALR parsers offer the same high performance of LR parsers, but are much smaller in size. For this reason, it is LALR parsers that are most often generated by compiler-compilers such as yacc and GNU bison.

Generating LALR Parsers

Full article ▸

related documents
Contraction mapping
Best-first search
Lyapunov fractal
Blum Blum Shub
Nearest neighbour algorithm
Complete measure
Normal morphism
Axiom of union
Sophie Germain prime
Group homomorphism
Composite number
Partition of unity
Baire category theorem
Linear congruence theorem
Multiple inheritance
Mutual recursion
Permutation group
Characteristic subgroup
Up to
Hamiltonian path problem
Tree structure
Complete category
Zhu Shijie
Category of sets
Sed
AVL tree
Chosen-plaintext attack
Data set
Elias delta coding
Identifier