编译原理学习笔记（二）语言及其文法

本节主要介绍了字母表、符号串等概念及其运算，还有文法、语言、文法的分类、CFG的分析树、二义性文法等内容

参考自中国大学Mooc网上的哈尔滨工业大学的编译原理课程，用到的图也是从Mooc网中下载的原课程课件

字母表

一个字母表是一个有穷符号集合，符号包括字母、数字、标点符号等，ASCII字符集和Unicode字符集都是字母表。

字母表上的运算

既然是集合，那么就有运算。

字母表上的乘运算：

字母表上的幂运算：

字母表的n次幂等于n个字母表相乘

字母表的正闭包：

字母表的正闭包是该字母表各个正次幂的并集

字母表的克林闭包：

在正闭包的基础上添加一个空串

符号串

串是字母表中符号的一个有穷序列

长度为0的串称为空串。

串上的运算

串的连接运算：

x和y的连接，是把y附加到x后面而形成的串，记作xy

串的幂运算

串s的n次幂，等于将n个s进行连接

文法

文法的定义

当我们要描述一种语言时，需要给出这种语言的所有句子，当句子的数目是有限时，则可以穷举；而当一门语言的句子是不可穷举时，就要给出可以表示它们的结构的描述方法，即 该语言的句子的组成规则。这种规则就是文法。

以自然语言为例子，例如英语的一个文法：

文法的形式化定义：

G=(VT, VN, P, S)，G代表文法，由终结符集合、非终结符集合、产生式集合和开始符组成。

• VT 终结符集合

  终结符是文法所定义的语言的基本符号，有时也称为token

  

• VN 非终结符集合

  非终结符是用来表示语法成分的符号，有时也称为“语法变量”

  

• P 产生式集合

  产生式( production)描述了将终结符和非终结符组合成串的方法

  

  

• S 开始符号

  第一条产生式的左部（该语法钟最大的语法成分）

  

在不引起歧义的情况下，可以只写产生式。

语言

有了文法（语言规则），如何判定一个词串是否是满足文法的句子？

推导和规约

• 直接推导：用产生式的右部替换产生式的左部
• 推导：经过n次直接推导表示n步推导（n=1即直接推导）
• 规约：推导的逆过程即为规约（用产生式的左部替换产生式的右部）

回答前面的问题，可以有两种途径去判断某一词串是否是满足该文法的句子

1. 句子的推导(派生)-从生成语言的角度：如果从文法的开始符号可以推导出这个词串，则它是该语言的一个句子。
2. 句子的规约-从识别语言的角度：如果从这个词串可以规约出文法的开始符号，则它是该语言的一个句子。

句型和句子

如果从开始符S可以推导出a，则a是G的一个句型，如果句型中不包含非终结符，则它是一个句子

语言的形式化定义

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G)

既然语言是一个集合，那么也有集合的运算：

文法的分类

• 0型文法

  也称无限制文法/短语结构文法

  对于产生式几乎没有限制，只要产生式左部至少包含1个非终结符就可以了

  生成的语言成为0型语言

• 1型文法

  也称上下文有关文法（CSG）

  在0型文法的基础上，进一步要求，产生式左部的长度<=产生式右部的长度，并且形如下图，注意a1和a2，用产生式的右部替换产生式的左部需要考虑上下文(a1、a2)，这也是1型文法称为上下文有关文法的原因

  

  上下文有关文法中不包含空产生式，产生的语言成为上下文有关语言

• 2型文法

  也称上下文无关文法（CFG）

  要求产生式的左部必须是一个非终结符，形如下图，用产生式的右部替换产生式的左部，不需要考虑上下文的情况

  

  生成的语言成为上下文无关语言

• 3型文法

  又成为正则语言（RG）

  • 右线性文法，在2型文法的基础上，进一步对产生式的右部进行约束，每一个产生式的右部，要么是一个终结符号串w，要么是终结符号串w右边添加一个非终结符B

    

  • 左线性文法，在2型文法的基础上，进一步对产生式的右部进行约束，每一个产生式的右部，要么是一个终结符号串w，要么是终结符号串w左边添加一个非终结符B

    

  生成的语言成为正则语言，正则文法能描述程序设计语言的多数单词，例如下面的文法，描述字母打头的字母数字串（标识符）

  

四种文法之间的关系：

CFG的分析树

正则文法虽然可以描述程序设计语言的大多数单词，但是它生成能力有限，它几乎描述不了程序设计语言中的句子构造，而上下文无关文法可以描述大部分程序设计语言的语法构造。

分析树是用来描述句子结构的。分析树的组成成分：根节点、内部节点、叶节点

分析树是推导的图形化表示，给定一个推导过程，对于推导过程中得到的每一个句型a，都可以构造出一个边缘为a的分析树。

（句型的）短语

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语

如果子树只有父子两代节点，那么这棵子树的边缘称为该句型的一个直接短语

直接短语一定是某产生式的右部，但产生式的右部不一定是给定句型的直接短语

例子：

上图中，高人、民生、活水都是产生式的右部，但并不是该句型的直接短语，该句型的直接短语：提高、人民、生活、水平

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。

例如，一个条件语句的文法：

对于句型if E1 then if E2 then S1 else S2，可以构造出两棵分析树：

上面这个句型出现两棵分析树的原因是，句中有两个if，只有一个else，所以这个else既可以和第一个if匹配（分析树2），也可以和第二个if匹配（分析树1）。

因此可以增加一个消岐规则（正如大多数编译器所做的那样）：每个else和最近的尚未匹配的if匹配，这样的话，就可以保留分析树1，删除分析树2，消除了二义性。

二义性文法的判定

对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但是可以给出一组充分条件，满足这组充分条件的文法是无二义性的（满足的话肯定无二义性，不满足的话也未必就是有二义性的）