LALR парсері: компьютерлік тілдерді талдау құралы

Type of parser in computer science

In computer science, an LALR parser (look ahead, left to right, rightmost derivation parser) is part of the compiling process where human readable text is converted into a structured representation to be read by computers. An LALR parser is a software tool to process (parse) text into a very specific internal representation that other programs, such as compilers, can work with. This process happens according to a set of production rules specified by a formal grammar for a computer language. An LALR parser is a simplified version of a canonical LR parser. The LALR parser was invented by Frank DeRemer in his 1969 PhD dissertation, Practical Translators for LR(k) languages, in his treatment of the practical difficulties at that time of implementing LR(1) parsers. He showed that the LALR parser has more language recognition power than the LR(0) parser, while requiring the same number of states as the LR(0) parser for a language that can be recognized by both parsers. This makes the LALR parser a memory efficient alternative to the LR(1) parser for languages that are LALR. It was also proven that there exist LR(1) languages that are not LALR. Despite this weakness, the power of the LALR parser is sufficient for many mainstream computer languages, including Java, though the reference grammars for many languages fail to be LALR due to being ambiguous. In 1982, DeRemer and Tom Pennello published an algorithm that generated highly memory efficient LALR parsers. LALR parsers can be automatically generated from a grammar by an LALR parser generator such as Yacc or GNU Bison. The automatically generated code may be augmented by hand written code to augment the power of the resulting parser.

In 1965, Donald Knuth invented the LR parser (Left to Right, Rightmost derivation). The LR parser can recognize any deterministic context free language in linear bounded time. Rightmost derivation has very large memory requirements and implementing an LR parser was impractical due to the limited memory of computers at that time. To address this shortcoming, in 1969, Frank DeRemer proposed two simplified versions of the LR parser, namely the Look Ahead LR (LALR) and the Simple LR parser (SLR) that had much lower memory requirements at the cost of less language recognition power, with the LALR parser being the most powerful alternative. In 1977, memory optimizations for the LR parser were invented but still the LR parser was less memory efficient than the simplified alternatives. In 1979, Frank DeRemer and Tom Pennello announced a series of optimizations for the LALR parser that would further improve its memory efficiency. Their work was published in 1982. but these do not see practical use. As with other types of LR parsers, an LALR parser is quite efficient at finding the single correct bottom up parse in a single left to right scan over the input stream, because it does not need to use backtracking. Being a lookahead parser by definition, it always uses a lookahead, with LALR(1) being the most common case.

The LALR(j) parsers are incomparable with LL(k) parsers: for any j and k both greater than 0, there are LALR(j) grammars that are not LL(k) grammars and conversely. In fact, it is undecidable whether a given LL(1) grammar is LALR(k) for any .