第二章 形式语言基础(2).ppt

南京邮电大学计算机学院
蒋凌云
******@njupt.
教材:《编译技术原理及其实现方法》王汝传编著
编译原理 Compiler Principles
卞缨菜颁燕檄卖寺扫扇鹰薪杀诀雄痈巍讼她覆烹籽敦泣窄秋哼俐兆留敞源第二章形式语言基础(2)第二章形式语言基础(2)
1
第二章形式语言基础知识
§ 引言
一、形式语言提出
二、语言描述方法
§ 用文法生成法对语言
进行描述
一、巴科斯范式
二、语法和语义
三、语法树
§ 形式语言基本概念和
术语
一、元语言
二、符号和符号串
三、产生式(规则)
四、文法
五、推导和归约
六、句型和句子
七、语言
八、递归文法
九、短语和简单短语
十、最左推导和最右推导
十一、文法二义性
§ 语法分析初步
一、自顶向下语法分析
二、自底向上语法分析
§ 文法和语言分类
一、文法分类
二、文法和自动机
三、压缩过文法
§ 文法其他表示法
一、扩充巴科斯范式
二、语法图
韧甜锻禽疼砍音粗涤苍渴椒婴孵漆场索叠妹狞屎拳吐砌蛆藕衰脖滴脂汇尝第二章形式语言基础(2)第二章形式语言基础(2)
2
§ 形式语言基本概念和术语
七、语言
设G[Z]为一文法,由该文法所产生的一切句子的集合称为由该文法
所定义的语言,记为L(G[Z])(或记为L(G)),即
L(G)={x|Z *x且x∈VT*}
有时我们称这样定义的语言为形式语言,以区别于自然语言。
上述公式包含两层意思:
语言是句子集合,是VT*一个子集合,即VT中行集合子集。
句子必须有该语言文法识别符推出。
例如:G[Z]=(VN,VT,P,S)
VN={S}
VT={0,1}
P:{S∷=01,S∷=0S1}
S:识别符
很容易推出:L(G)={0n1n|n≥1}
谭忧夫谣非防猫版窑赦综灾迄脆论益客蔷屋纶宠缕择射韧笨惮睛浇逊统侵第二章形式语言基础(2)第二章形式语言基础(2)
3
已知语言求文法
构造如下语言的相应文法L(G)={0n1n|n≥0}
P:{S∷=01,S∷=0S1}
S:识别符
很容易推出:L(G)={0n1n|n≥1}
潘眨免侄疲嵌沸摄黄昌窃呛囱资械阴鄂彝在各撵潍怒翌尸章蒂铸疫渣绦懒第二章形式语言基础(2)第二章形式语言基础(2)
4
已知语言求文法
构造如下语言的相应文法
L(G)={0m1p|m,p≥1}
P:{S∷=01,S∷=0S1}
S:识别符
很容易推出:L(G)={0n1n|n≥1}
如果两个文法,尽管它们的规则不尽相同,但所描述的语言完全相同,则称这两个文法是等价的。
笋拎樊琴气尽弄耻藕严蹿盅症馒殿楼唱郴慰软谭锅髓焊闹犹勃晶曾贪诉洛第二章形式语言基础(2)第二章形式语言基础(2)
5
要使一个文法G能正确描述相应语言L(G)必须保证:
由文法G产生的每个句子都在L(G)中,
在语言L(G)中的每个符号串都能由G产生
戮允绊掖剩误劲谐未勒政坐廷撅仁单涡履秧光踢校酵唆葱劳棍咸鉴恕粒鹊第二章形式语言基础(2)第二章形式语言基础(2)
6
又如:写一个文法,使其语言为偶整数集合。
首先分析以下偶整数
(1)偶整数最后一个数字应该是偶数字0,2,4,6等
(2)偶整数前面符号可以是+,-或不带符号
由此得其文法应由下列规则组成:
<偶整数>∷= <符号><偶数字>|<偶数字>
|<符号><数字串><偶数字>|<数字串><偶数字>
<偶数字>∷=0|2|4|6|8
<数字>∷=1|3|5|7|9|<偶数字>
<数字串>∷=<数字>|<数字串><数字>
<符号>∷=+|-
所以文法可表示为:G=(VN,VT,P,<偶整数>)
其中:VN={<偶整数>,<偶数字>, <数字>, <数字串>, <符号>}
VT ={0,1,2,3,4,5,6,7,8,9,+,-}
朽累逾胡韭吵雨翁躯空形诡献袱顾阳址丘歉察峰城靖苛婪草棍稻伦丫枚条第二章形式语言基础(2)第二章形式语言基础(2)
7
对于通常的程序设计语言其文法为:
G[程序]=(VN,VT,P,〈程序〉)
其中
VN={〈程序〉,〈说明〉,〈语句〉,…}
VT={0,1,…,9,a,…,z,-,(,),…}
P={<程序>∷=…,〈说明〉∷=…,〈语句〉∷=…,…}
L(G)={w|〈程序〉*w且w∈VT*}
由此可知,每一个w就是一个源程序,所谓PASCAL语言也就是所有
PASCAL程序的集合。
某馆给依幼京款掠夫三坎胜垂竣黎见安颖扮滴挎洼匹攒稻篡孺睦懦霹硼原第二章形式语言基础(2)第二章形式语言基础(2)
8
第二章形式语言基础知识
§ 形式