Courses 编译原理

SLR(1)语法分析器

SLR(1)语法分析器

0. 源码地址

xiaoruiruiecho/SLR(1)

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

image-20241217160702684

image-20241217160728703

3. 分析文法项目

根据各产生式编程分析出,所有产生式的初始状态、待约状态和规约状态。

image-20241217160742188

4. 求解First集和Follow集

编程求解各非终结符V的First集和Follow集,用于化解LR(0)自动机中的移进——规约冲突和规约——规约冲突(如果能)。

image-20241217160754194

5. 构建LR(0) DFA自动机

根据LR(0) DFA自动机构建算法编程实现即可。

共46个状态。

image-20241217160807021

6. 生成Action表

根据LR(0) DFA自动机的状态转移情况填表即可。对于自动机中出现的移进——规约冲突和规约——规约冲突尝试使用SLR(1)文法化解,如果不能,则报错。

image-20241217160816106

image-20241217160825315

7. 生成Goto表

根据LR(0) DFA自动机的状态转移情况填表即可。

image-20241217160835471

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:略

9. 源码

https://github.com/xiaoruiruiecho/SLR-1-

你可能也会喜欢...