A tale of three LR(1) syntax analyzers

ABSTRACT

The chronicle and evolution of authors' experience in building LR(1) syntax analyzers is described in the paper. The theory background includes classic and modified interpretation of LR(1) parsing algorithms, Three versions of implemented parsers are to be discussed: parser with fixed control table, flexible table driven LR(1) parser and parser with built-in control table generator. The first version is classified as the most primitive. The second version is more flexible but it requires configuration file and manual construction of the control table. The third version is categorized the most flexible, powerful and user friendly parser implementation. It is much easier job to specify the grammar rules in a suitable format than to construct manually the control table and specify it within the source text of the parser or as contents of a configuration file.

REFERENCES

• 1: Yankov B., Translators and Operating Systems, Sofia, Tehnika Publ., 1993, (in Bulgarian).
• 2: Alfred V. Aho , Monica S. Lam , Ravi Sethi , Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 3: Alfred V. Aho , Jeffrey D. Ullman, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, 1972
• 4: Bonev S., Implementation of LR(1) Parsers, Proc of the 16^th Int. Conf. Systems for Automation of Engineering and Research SAER 2002, Varna, Bulgaria, pp 149--153.
• 5: Stoyan Bonev, A flexible table driven LR(1) parser, Proceedings of the 5th international conference on Computer systems and technologies, June 17-18, 2004, Rousse, Bulgaria [doi>10.1145/1050330.1050397]

INDEX TERMS

Keywords:
bottom up parsing strategy, control table generator, syntax analysis