LL(1) Parser for Arithmetic Expressions

This project implements an LL(1) predictive parser for arithmetic expressions using C++.

Project Structure / 项目结构

LL1-Parser/
├── src/                 # 源代码目录
│   ├── Grammar.h        # 文法类头文件
│   ├── Grammar.cpp      # 文法类实现
│   ├── Parser.h         # 语法分析器类头文件
│   ├── Parser.cpp       # 语法分析器类实现
│   └── main.cpp         # 主程序入口
├── test/                # 测试代码目录
│   └── test_parser.cpp  # 测试程序
├── docs/                # 文档目录
│   ├── report.pdf       # 实验报告（PDF版）
│   └── report.md        # 实验报告
├── README.md            # 项目说明
└── Makefile             # 构建配置文件

Features / 特点

• Grammar Transformation: Automatically eliminates left recursion and extracts left common factors
• FIRST/FOLLOW Sets: Computes FIRST and FOLLOW sets for all non-terminals
• Parsing Table: Constructs LL(1) predictive parsing table
• Predictive Parser: Implements non-recursive predictive parsing
• Error Detection and Recovery: Provides error handling mechanisms

Grammar / 所用文法

The parser handles arithmetic expressions defined by the following grammar:

Original Grammar (with left recursion):

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

Transformed Grammar (after eliminating left recursion):

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

Quick Start / 快速开始

环境要求

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

编译

1. 编译主程序

make
# or
make all

​ 编译成功后，会在项目根目录生成可执行文件 ll1_parser。

2. 编译测试程序

make test-build

​ 编译成功后，会在项目根目录生成可执行文件 test_parser。

3. 清理编译产物

make clean

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

运行主程序

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

程序功能：

• 启动后自动显示转换后的文法
• 显示 FIRST 集合和 FOLLOW 集合
• 显示预测分析表（普通版本和带同步标记版本）
• 进入交互式分析模式，等待用户输入算术表达式

输入格式：

• 符号之间用空格分隔
• 支持直接输入数字（如 3 + 5 * 2）
• 支持使用 num 关键字（如 num + num * num）
• 支持混合使用（如 num + 5 * 3）
• 输入 quit 或 exit 退出程序

使用示例：

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

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

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

> quit
Goodbye!

错误恢复模式：

如果需要使用错误恢复功能，在输入表达式前加上 r: 前缀：

> r:3 + + 5
[显示带错误恢复的语法分析过程]

运行测试程序

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

输出说明

主程序输出结构

1. 文法信息：显示经过左递归消除和左公因子提取后的文法
2. FIRST 集合：显示每个符号的 FIRST 集合
3. FOLLOW 集合：显示每个非终结符的 FOLLOW 集合
4. 预测分析表：显示预测分析表 M（普通版本）
5. 同步分析表：显示带有同步标记的预测分析表
6. 交互式分析：显示每个输入表达式的详细分析过程

分析过程输出格式

Stack                         Input               Output
------------------------------------------------------------------------------------------
$ E                           num + num * num $   E -> T E'
$ E' T                        num + num * num $   T -> F T'
...
$                             $                   Accept

• Stack：当前符号栈的内容（从栈底到栈顶）
• Input：剩余输入符号串
• Output：当前步骤使用的产生式或执行的操作

License

See the LICENSE file for more details.