LR(k)-Parser Generator

A complete implementation of an LR(k)-parser generator based on formal algorithms from Aho & Ullman's classic compilers textbook.

Table of Contents

• Features
• Build Instructions
• Usage
• Input Format
• Examples
• Implementation Details
• Contributing

Features

✅ Complete implementation of all key LR(k) algorithms:

• FIRSTₖ and EFFₖ set construction (Algorithm 5.5)
• LR(k) parsing with control tables (Algorithm 5.7)
• Valid item set construction (Algorithm 5.8)
• System of valid item sets (Algorithm 5.9)
• LR(k) condition checking (Algorithm 5.10)
• Control table construction (Algorithm 5.11)

✅ Clean CMake build system
✅ Well-structured code following textbook algorithms
✅ Handles epsilon productions and complex grammars

Input Format

1. Grammar Rules:

   • One rule per line in format A->α
   • Epsilon rules: A-> (nothing after arrow)
   • Terminals: lowercase letters
   • Non-terminals: uppercase letters
   • End rules with / on new line

2. Input Strings:

   • Enter strings to parse (one per line)
   • Program will output parse sequences or -1 for invalid strings

Examples

Balanced Parentheses Grammar

S->SS
S->(S)
S->
/
()
(())
()()
((()()))

Arithmetic Expressions

E->E+T
E->T
T->T*F
T->F
F->(E)
F->a
/
a+a*a
(a+a)*a

Implementation Details

The implementation closely follows the algorithms from: Aho, Alfred V., and Jeffrey D. Ullman. The Theory of Parsing, Translation, and Compiling. Vol. 1, Prentice-Hall, 1972.

File Structure:

• L$_5.cpp - Algorithm 5.5 (FIRSTₖ/EFFₖ)
• L$_7.cpp - Algorithm 5.7 (Parsing)
• L$_8.cpp - Algorithm 5.8 (Valid Items)
• L$_9.cpp - Algorithm 5.9 (Item Sets)
• L$_10.cpp - Algorithm 5.10 (LR(k) Check)
• L$_11.cpp - Algorithm 5.11 (Control Table)
• main.cpp - Driver program
• lib.cpp - Utilities

Contributing

Contributions are welcome! Please open an issue or pull request for:

• Bug fixes
• Performance improvements
• Additional test cases
• Documentation enhancements