编译原理 第二章下: 推导，规约，句型句子，语言，文法分类，二义性

2.3 推导

2.3.1 直接推导/直接规约

简言之，一步直接退换

例如：有文法GS:S→0S1,S→01

有直接推导 0S1⇒0011

有直接推导 0S1⇒00S11

有直接推导S⇒0S1

2.3.2 推导/规约

若存在直接推导序列，符号串一直进行直接推导，直到没有非终结符号时，推导就必须终止

推导例题：

2.3.3 规范推导

规范推导也叫最右推导，每步只变换符号串中最右边的非终结符，直到推导结束

2.4 句型和句子

1.句型

有文法GZ，若Z 0步以上推导出x，则称x是文法G的句型

2.句子

有文法GZ，若Z 1步以上推导出且x都是终结符号，则称x是文法G的句子

例：GS,S→0S1,S→01

S⇒0S1⇒00S11⇒000S111⇒00001111

G的句型S，0S1，00S11，000S111，00001111等

G的句子00001111等

注意：

1.句子是特殊的句型

2.规范推导产生的句型为规范句型

3.每个句子都有一个规范推导

4.并非每一个句型都有规范推导

练习：

2.5 语言

语言是句子的集合，文法G生成的语言记为L(G(Z)),他是文法G(Z)的一切句子的集合

注意：给定一文法，能从结构上唯一确定其语言，给定一种语言，能确定其文法，但不唯一

我的理解，文法是信息，语言就类似于汉语，英语这种，给我一个信息，我想把翻译出来，用汉语那就是唯一确定的，如果给我一个汉语写的信息，我还可以把用日语，英语翻译，再变成信息。

例：

2.6 文法的分类

对文法中的不同规则施加不同的限制，将文法和语言分为四大类

0型文法：0型语言或短语结构语言

1型文法：1型语言或上下文有关语言

==2型文法==：2型语言或上下文无关语言

2型文法是程序设计语言语法规则

==3型文法==：3型语言或正则语言

3型文法是程序设计语言构词规则

2.6.1 0型文法

对产生式基本无限制

2.6.2 1型文法

文法左部符号个数不超过右部符号个数

2.6.3 2型文法

任意产生式A→B，A属于非终结符号，B终结不终结都可

说明：描述程序设计语言的语法规则

2.6.4 3型文法

任意产生式A→B，都为A→aB，A→a，这种形式，比较严格

通常用来描述单词结构，其中包括标识符，常量，运算符，界符等

总结：四种文法的关系是逐级包括的，限制少的包含限制多的

2.7 推导语法树的构造

写在最前

本文为编译原理重点考察大题之一，理论基础见专栏文章，0基础直接使用也可食用

2.7.1 语法树的概念

推导过程用图表示，即为语法树，也叫推导树

语法树是一棵有序有向树

推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的。

给出一棵语法树的例子：

2.7.2 子树，短语，简单短语，句柄

子树

子树就是以树的某个结点为根，连同他全部的后裔组成。

如上小节给出语法树中，包含根节点S，S1，S2，S3，S4的五棵子树

短语

短语是相对一个句型的，一个句型对应多个短语。

短语就是该句型子树的叶子结点

如何寻找一个句型短语？

1.画出句型语法树

2.找出所有子树

3.子树叶子结点组成的符号串为该句型针对子树根节点的短语

4.去掉重复的短语

简单短语与句柄

所有短语中，一步推导得来的即为简单短语。

最左边的简单短语就是该句型的句柄。

真题实战

题目一：

左图答案：

短语：aa+a* ，aa+，a

简单短语：a

句柄：a

右图答案：

短语 abccdd，ab，ccdd，cd

直接短语：ab，cd

句柄：ab

题目二：

已知文法GE:E→ET+|T , T→TF*|F , F→F^|a

求证FF^^*是文法的句型，指出短语，简单短语和句柄

2.8 递归规则和递归文法

递归规则指的是在规则右部含有和左部相同符号的规则，如U→xUy;其中这种U→Uy称为左递归，还有右递归。

递归文法使人们能用有穷的文法刻画无穷语言。

2.9 文法的二义性

若一个文法存在某个句子或句型，它存在两棵不同的语法树，则称该句子或句型是二义性的，对应的文法也是二义性的。

2.9.1 有关文法的实用限制

• 多余规则：指文法中任何句子的推导都不会用到的规则，若有则删去 - 不可到达：非终结符不再任何规则的右部出现，称该非终结符为不可到达 - 不可终止：由它不能退出终结符号串，称该非终结符为不可终止

后续的学习中，多余的规则去除来优化自动机