LR(1) Parser for Arithmetic Expressions

This project implements an LR(1) bottom-up parser for arithmetic expressions using C++.

Project Structure / 项目结构

LR1-Parser/
├── src/                 # 源代码目录
│   ├── Grammar.h        # 文法类头文件
│   ├── Grammar.cpp      # 文法类实现
│   ├── ItemSet.h        # 项目集类头文件
│   ├── ItemSet.cpp      # 项目集类实现
│   ├── DFA.h            # DFA 类头文件
│   ├── DFA.cpp          # DFA 类实现
│   ├── LR1Parser.h      # LR(1) 分析器类头文件
│   ├── LR1Parser.cpp    # LR(1) 分析器类实现
│   └── main.cpp         # 主程序入口
├── test/                # 测试代码目录
│   └── test_parser.cpp  # 测试程序
├── build/               # 编译产物目录
│   └── *.o              # 目标文件
├── docs/                # 文档目录
│   ├── report.pdf       # 实验报告（PDF版）
│   └── report.md        # 实验报告
├── README.md            # 项目说明
└── Makefile             # 构建配置文件

Features / 特点

• Grammar Augmentation: Automatically augments grammar with new start symbol
• FIRST Sets: Computes FIRST sets for symbols and symbol strings
• LR(1) Item Sets: Constructs canonical collection of LR(1) items (DFA)
• Parsing Table: Builds ACTION and GOTO tables
• Shift-Reduce Parser: Implements LR(1) parsing algorithm
• Conflict Detection: Detects shift-reduce and reduce-reduce conflicts
• DFA Visualization: Exports DFA to Graphviz DOT format
• Comprehensive Testing: 17 test cases covering various scenarios

Grammar / 所用文法

The parser handles arithmetic expressions defined by the following grammar:

Original Grammar:

E → E+T | E-T | T
T → T*F | T/F | F
F → (E) | num

Augmented Grammar:

E' → E
E  → E+T | E-T | T
T  → T*F | T/F | F
F  → (E) | num

Note: Unlike LL(1) parsers, LR(1) parsers can handle left-recursive grammars directly without transformation.

Quick Start / 快速开始

环境要求

• 编译器：支持 C++17 标准的编译器（推荐 clang++ 或 g++）
• 操作系统：macOS、Linux 或 Windows
• 构建工具：make
• 可视化工具（可选）：Graphviz（用于 DFA 可视化）

编译

1. 编译主程序

make
# or
make all

​ 编译成功后，会在项目根目录生成可执行文件 lr1_parser，编译产物（.o 文件）存放在 build/ 目录下。

2. 清理编译产物

make clean

​ 此命令会删除所有编译生成的文件，包括 build/ 目录和可执行文件。

运行主程序

./lr1_parser
# 或者使用 make 命令：
make run

程序功能：

• 启动后自动显示原始文法和拓广后的文法
• 显示 LR(1) 项目集规范族（共 30 个状态）
• 显示 ACTION 表和 GOTO 表
• 自动导出 DFA 可视化文件（lr1_dfa.dot）
• 进入交互式分析模式，等待用户输入算术表达式

输入格式：

• 支持直接输入数字（如 3 + 5 * 2）
• 支持使用 num 关键字（如 num + num * num）
• 支持混合使用（如 num + 5 * 3）
• 输入 quit 或 exit 退出程序

使用示例：

> 3 + 5 * 2
[显示完整的 LR(1) 语法分析过程]

> ( 3 + 5 ) * 2
[显示完整的 LR(1) 语法分析过程]

> num + num
[显示完整的 LR(1) 语法分析过程]

> quit
Goodbye!

运行测试程序

./test_parser
# 或者使用 make 命令：
make test

​ 测试程序包含 4 个测试套件，共 17 个测试用例，全面验证 LR(1) 分析器的正确性。

测试套件：

• 基本表达式（5 个测试）
• 复合表达式（4 个测试）
• 错误检测（5 个测试）
• 边界情况（3 个测试）

DFA 可视化

主程序运行后会自动生成 lr1_dfa.dot 文件。使用 Graphviz 工具可以将其转换为图像：

# 安装 Graphviz（macOS）
brew install graphviz

# 生成 PNG 图片
dot -Tpng lr1_dfa.dot -o dfa.png

# 在 Linux 上安装 Graphviz
sudo apt install graphviz

输出说明

主程序输出结构

1. 使用说明：显示程序功能和输入格式
2. 原始文法：显示算术表达式文法
3. 拓广文法：显示添加了 E' -> E 的拓广文法
4. LR(1) 项目集规范族：显示所有 30 个状态及其包含的 LR(1) 项目
5. ACTION 表：显示移进-归约分析表
6. GOTO 表：显示非终结符状态转移表
7. 交互式分析：接收用户输入并显示详细分析过程

分析过程输出格式

=== LR(1) Parsing Steps ===
Step  State Stack          Symbol Stack          Input String    Action
----------------------------------------------------------------------
  0   0                    $                     num + num $     shift 5
  1   0 5                  $ num                 + num $         reduce 7
  2   0 6                  $ F                   + num $         reduce 5
  3   0 7                  $ T                   + num $         reduce 2
  ...

• Step：步骤编号
• State Stack：当前状态栈（从栈底到栈顶）
• Symbol Stack：当前符号栈（从栈底到栈顶）
• Input String：剩余输入符号串
• Action：执行的动作（shift n / reduce k / accept）

License

See the LICENSE file for more details.