编译语言原理与编译实验报告

实验内容

阅读ppt，阅读教材第3章

理解LR（0） DFA的构建过程

简介构造：

• 构造NFA

  • 

• 构造DFA

  • 利用子集构造法进行确定化后得到DFA

直接构造：

• 构造DFA

  • 在LR(0)文法基础上增加增广文法，使分析器只有一个接收状态

  • 在某个LR(0)文法的所有LR(0)项目中，点后面是非终结符的项目存在重复项目，这些项目集合称为项目集闭包，对应着DFA的一个状态（使用CLOSURE()函数）

  • 从增广文法开始，遍历DFA状态里每个项目的后继LR(0)项目（使用GOTO()函数），每遍历一个就作为一个状态，并使用该符号链接。例如：

  • 如果遇到归约项目，则该分支结束；当所有都结束后，构建DFA结束

理解如何从DFA状态图，进行LR分析表的构建

• 根据DFA中结点个数确定分析表内状态数
• 从DFA开始结点开始遍历，如果遇到终结符，则为ACTION跳转；如果遇到非终结符，则为GOTO跳转
• 对于ACTION表，如果DFA内的动作为归约项目，则为rn（归约）操作；如果不是归约项目，则为sn（移入）操作

教材 p50 3.4.3 理解冲突产生原因

1. 移进/归约冲突：在一个状态内存在多个项目，其一要求执行移进操作，其一要求执行归约项目
2. 归约/归约冲突：在一个状态内存在多个项目，两者要求执行不同的归约操作
3. 混合冲突：混合移进/归约冲突、归约/归约冲突

如果没有冲突就为LR(0)文法，否则为LR(1)文法

p51 理解图3-13 LR 状态表，找到其中的冲突项

在状态9、11、13、15均存在移进/归约冲突

找到其中的 Action Table（动作表） ，Goto Table（状态转换表）的定义

教材 p50 3.4.2.优先级指导

理解在语法说明文件中，优先级的指定方式

什么是左/右结合/非结合 ，如何在语法说明文件里面声明 p53

• +和-是左结合的且具有相同的优先级：*和/是左结合的且它们的优先级高于＋；^是右结合的且具有最高优先级：=和!=是非结合的，它们的优先級低于＋
• 利用LR(1)的展望符来限制，只有当下一个输入为展望符才进行归约操作

如何用 %prec 指示，自定义某规则的优先级 p53

• 当规则和单词的优先级相等时，用%1eft 指明的优先级偏向于归约，%right 指明的偏向于移进，而由%nonassoo 指明的则导致一个错误动作。

http://mdaines.github.io/grammophone/# 核对你的作业

设有如下文法

S -> S A b .
S -> a c b .
A -> b B c .
A -> b c .
B -> b a .
B -> A c .
1
2
3
4
5
6

分析栈上的内容如下,请分别写出可归约串是什么（▽ 表示栈底）：

(a)▽SSAb
(b)▽SSbbc
(c)▽SbBc
(d)▽Sbbc
1
2
3
4

(a)可归约串：SAb
(b)可归约串：bc
(c)可归约串：bBc
(d)可归约串：bc
1
2
3
4

设有如下输入串，请用2中的文法，采用 shift/reduce分析下面的串。

请按ppt 中 构造表格，列出分析栈，输入流， shift/reduce操作 的内容

(a) acb
(b) acbbcb
(c) acbbbacb
(d) acbbbcccb
(e) acbbcbbcb
1
2
3
4
5

• 步骤	栈	输入字符串
  0	$	acb$
  2	$a	cb$
  5	$ac	b$
  11	$acb	$
  acc	$	$

  步骤	栈	输入字符串
  0	$	acbbcb$
  2	$a	cbbcb$
  5	$ac	bbcb$
  11	$acb	bcb$
  0	$	bcb$
  1	$S	bcb$
  4	$Sb	cb$
  8	$Sbc	b$
  1	$SA	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

  步骤	栈	输入字符串
  0	$	acbbbacb$
  2	$a	cbbbacb$
  5	$ac	bbbacb$
  11	$acb	bbacb$
  0	$	bbacb$
  1	$S	bbacb$
  4	$Sb	bacb$
  9	$Sbb	acb$
  13	$Sbba	cb$
  4	$Sb	cb$
  7	$SbB	cb$
  12	$SbBc	b$
  1	$S	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

  步骤	栈	输入字符串
  0	$	acbbbcccb$
  2	$a	cbbbcccb$
  5	$ac	bbbcccb$
  11	$acb	bbcccb$
  0	$	bbcccb$
  1	$S	bbcccb$
  4	$Sb	bcccb$
  9	$Sbb	cccb$
  15	$Sbbc	ccb$
  4	$Sb	ccb$
  10	$SbA	ccb$
  16	$SbAc	cb$
  4	$Sb	cb$
  7	$SbB	cb$
  12	$SbBc	b$
  1	$S	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

  步骤	栈	输入字符串
  0	$	acbbcbbcb$
  2	$a	cbbcbbcb$
  5	$ac	bbcbbcb$
  11	$acb	bcbbcb$
  0	$	bcbbcb$
  1	$S	bcbbcb$
  4	$Sb	cbbcb$
  8	$Sbc	bbcb$
  1	$S	bbcb$
  3	$SA	bbcb$
  6	$SAb	bcb$
  0	$	bcb$
  1	$S	bcb$
  4	$Sb	cb$
  8	$Sbc	b$
  1	$S	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

设有如下文法和输入串，请说明是否有shift/reduce冲突 或者 reduce/reduce 冲突

S -> S a b .
S -> b A .
A -> b b .
A -> b A .
A -> b b c .
A -> c .
1
2
3
4
5
6

输入串

(a) b c
(b) b b c a b
(c) b a c b
1
2
3

• 步骤	栈	输入字符串
  0	$	bc$
  2	$b	c$
  6	$bc	$
  2	$b	$
  4	$bA	$
  acc	$	$

  步骤	栈	输入字符串
  0	$	bbcab$
  2	$b	bcab$
  5	$bb	cab$
  6	$bbc	ab$
  5	$bb	ab$
  9	$bbA	ab$
  2	$b	ab$
  4	$bA	ab$
  0	$	ab$
  1	$S	ab$
  3	$Sa	b$
  7	$Sab	$
  acc	$	$

  步骤	栈	输入字符串
  0	$	bacb$
  2	$b	acb$
  err

存在reduce/reduce 冲突，但情况3并不是因为这个报错，而是一个非产生式报错

阅读lecture03.p31.fsyacc.pdf p31页 掌握fslex,fsyacc使用

阅读 calcvar 中

• 词法说明 lexer.fsl
• 语法说明 parser.fsy
• 调试运行代码
• 理解优先级指导的写法
  • 阅读 ReadME

plzoofs calcvar项目，给fsyacc 工具添加 -v 参数，查看生成语法分析器的 LR 状态表

// calcvar.fsproj 
<FsYacc *Include*="parser.fsy">
    <OtherFlags> -v --module Parser</OtherFlags>
</FsYacc>
1
2
3
4

注意下特定状态的

• action table
• goto table

阅读Fun语言中

• 词法说明 FunLex.fsl
• 语法说明 FunPar.fsy
• 调试运行代码
• 同上fsyacc工具添加 -v查看 LR 分析状态表

阅读MicroC 语法分析器

• https://gitee.com/sigcc/plzoofs/blob/master/microc/CPar.fsy
• 由于 C 语言的指针，数组语法分析比较复杂，构造语法树时用到了比较高级的函数式编程技巧
• 大家慢慢理解

Fsharp参考案例（自选）

• Postfix/ 后缀式 运算 1 2 + 3 *
• Usql/ sql 语言语法解析