编译原理学习笔记(二)语言及其文法
本节主要介绍了字母表、符号串等概念及其运算,还有文法、语言、文法的分类、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即直接推导)
- 规约:推导的逆过程即为规约(用产生式的左部替换产生式的右部)
回答前面的问题,可以有两种途径去判断某一词串是否是满足该文法的句子
- 句子的推导(派生)-从生成语言的角度:如果从文法的开始符号可以推导出这个词串,则它是该语言的一个句子。
- 句子的规约-从识别语言的角度:如果从这个词串可以规约出文法的开始符号,则它是该语言的一个句子。
句型和句子
如果从开始符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,消除了二义性。
二义性文法的判定
对于任意一个上下文无关文法,不存在一个算法,判定它是无二义性的;但是可以给出一组充分条件,满足这组充分条件的文法是无二义性的(满足的话肯定无二义性,不满足的话也未必就是有二义性的)
感谢阅读 ♪(^∇^*)
- 本文链接:http://www.sunxiaokong.xyz/2020-06-10/lzx-compile-2/
- 版权声明:本站文章除特别声明外,均为本站原创或翻译,采用 知识共享署名 CC BY 4.0 国际协议进行许可,转载前请务必署名及注明出处。