6533b872fe1ef96bd12d4134

RESEARCH PRODUCT

Construction and Implementation of LR(1) Parsers

Seppo SippuEljas Soisalon-soininen

subject

Set (abstract data type)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESParsingLR parserComputer scienceProgramming languageEncoding (memory)computer.software_genreLALR parsercomputerCanonical LR parser

description

This chapter is devoted to the practical issues involved in the construction and use of deterministic LR(1) parsers. We shall show how the practical versions of LR (1) parsers, most notably the LALR (1) parsers, can be constructed efficiently, and we shall present methods for encoding LR(1) parsers as efficient RAM programs. Two versions of RAM program implementation are considered: in the first implementation the parsing program is table-driven, that is, the rules of the parser are encoded in a two-dimensional array which is simulated by a program body; in the other implementation the tabular information is further transformed into a set of program statements.

yearjournalcountryeditionlanguage
1990-01-01
https://doi.org/10.1007/978-3-662-08424-3_2