一个完整的乔姆斯基文法分析工具，支持文法类型判定、合法性验证和统计信息。
-
文法类型判定: 自动判断文法所属的乔姆斯基类型 (0-3型)
- TYPE_3_RIGHT # 右线性正则文法
- TYPE_3_LEFT # 左线性正则文法
- TYPE_2 # 上下文无关文法（但不是正则文法）
- TYPE_1 # 上下文相关文法
- TYPE_0 # 无限制文法
- INVALID # 文法不合法
-
文法合法性验证: 检测文法中的错误
- UNDEFINED_SYMBOL: 产生式中引用了未在 N 或 T 中定义的符号
- UNREACHABLE: 从开始符号无法到达的非终结符
- NON_GENERATING: 无法推导出终结符串的非终结符
- START_NOT_IN_N: 开始符号不在非终结符集合中
- FORMAT_ERROR: 文件格式不符合规范
-
文法统计信息: 提供文法的详细统计数据
- 非终结符数量
- 终结符数量
- 产生式数量
- 是否包含ε产生式
- 开始符号
/workspace/
├── CMakeLists.txt # CMake构建配置
├── examples/ # 示例文法文件
│ └── test.bnf # 简单的BNF文法示例
├── include/ # 头文件
│ ├── grammar.h # 文法类定义
│ ├── grammar_parser.h # 文法解析器
│ ├── chomsky_classifier.h # 乔姆斯基分类器
│ └── validator.h # 文法验证器
├── src/ # 源文件
│ ├── main.cpp # 主程序，命令行接口
│ ├── grammar.cpp # 文法类实现
│ ├── grammar_parser.cpp # 文法解析器实现
│ ├── validator.cpp # 文法验证器实现
│ └── chomsky_classifier.cpp # 乔姆斯基分类器实现
└── 测试文件/ # 测试用例
├── test_grammar1.bnf # 基础2型文法测试
├── test_type3_right.bnf # 3型右线性文法测试
├── test_type3_left.bnf # 3型左线性文法测试
├── test_type1.bnf # 1型文法测试
├── test_error.bnf # 有错误的文法测试
└── test_final.bnf # 综合表达式文法测试
# 文法类型判定
./grammar_analyzer input.txt --check-type
# 文法合法性验证
./grammar_analyzer input.txt --validate
# 文法统计信息
./grammar_analyzer input.txt --stats
cd /workspace
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make
或者直接使用g++编译：
g++ -std=c++17 -I./include -o grammar_analyzer \
src/main.cpp src/grammar_parser.cpp src/grammar.cpp src/validator.cpp src/chomsky_classifier.cpp
文法文件为纯文本文件（UTF-8 编码），格式如下：
# 非终结符集合（空格分隔）
N: S A B C
# 终结符集合（空格分隔）
T: a b c
# 产生式（每行一条，| 分隔同一左部的多个右部，ε 表示空串）
P:
S -> A B C
A -> a A | a
B -> b
C -> c C | ε
# 开始符号
START: S
- 文法解析: 严格按照输入格式规范解析文法文件
- 符号分类: 区分非终结符和终结符，支持ε（epsilon）表示空串
- 产生式分析: 处理多个候选式，记录行号信息
- 可达性分析: 计算从开始符号可达的符号集合
- 生成性分析: 计算可以生成终结符串的符号集合
- 乔姆斯基分类: 按最严格类型原则进行自动分类
- 使用C++17标准
- 严格的类型检查
- 完整的错误处理
- 模块化设计
- 详细的注释文档
项目包含完整的测试用例，覆盖：
- 不同类型文法的分类测试
- 各种错误类型的验证测试
- 边界条件测试
- S->ε例外规则测试
MIT License
About
35/F,Tencent Building,Kejizhongyi Avenue,Nanshan District,Shenzhen
