SLR(1)语法分析器
0. 源码地址
1. 设计文法
设计能推导出算术表达式、逗号表达式、关系表达式和逻辑表达式的SLR(1)文法(如果还要求能推导出赋值表达式,似乎这样的SLR(1)文法不存在,得用更强大的语法分析器?)
SLR(1)文法如下:
1. S -> L
2. L -> B L1
3. L1 -> && B L1 | || B L1 | 4. B -> E R E | E
5. R -><| <= |>| >= | == | !=
6. E -> T E1
7. E1 -> + T E1 | – T E1 | , E E1 |
8. T -> F T1
9. T1 -> * F T1 | / F T1 | $
10. F -> ( L ) | id
2. 词法分析
通过编程实现各产生式的词法分析,分析出所有的非终结符V、终结符T,和产生式P。
3. 分析文法项目
根据各产生式编程分析出,所有产生式的初始状态、待约状态和规约状态。
4. 求解First集和Follow集
编程求解各非终结符V的First集和Follow集,用于化解LR(0)自动机中的移进——规约冲突和规约——规约冲突(如果能)。
5. 构建LR(0) DFA自动机
根据LR(0) DFA自动机构建算法编程实现即可。
共46个状态。
6. 生成Action表
根据LR(0) DFA自动机的状态转移情况填表即可。对于自动机中出现的移进——规约冲突和规约——规约冲突尝试使用SLR(1)文法化解,如果不能,则报错。
7. 生成Goto表
根据LR(0) DFA自动机的状态转移情况填表即可。
8. 分析句子
输入句子所在的文件名(包含后缀),通过一状态栈和一符号栈,并参照Action表和GoTo表一步步分析即可,分析失败则报错。
分析案例1:SLR_Sentence_1.txt
id + ( id ) * ( id / ( id – id ) )
分析结果1:略
分析案例2:SLR_Sentence_5.txt
id ( id + ( id && id ) > ( id || id – id ) / ( id ) )
分析结果2:略
分析案例3:SLR_Sentence_2.txt
id < ( id – ) , id
分析结果3:略