《第2章高级言及其语法描述》由会员分享，可在线阅读，更多相关《第2章高级言及其语法描述（60页珍藏版）》请在金锄头文库上搜索。
1、第第2 2章章 高级语言及其语法描述高级语言及其语法描述2.1 程序语言的定义及特性2.2 形式语言基础2.3 文法的直观理解2.4 文法和语言的定义2.5 文法的类型2.6 语法树与二义性2.7 有关文法的限制阜暖耽拖笋气慕拳吱帮功穷魂橡爸骋值熬孕李挚赖坏里罗胀崩景抒衣铬矛第2章高级言及其语法描述第2章高级言及其语法描述2.1 2.1 程序语言的定义及特性程序语言的定义及特性 显然，用高级语言编程比用低级语言来得方便，但要解决两个问题：显然，用高级语言编程比用低级语言来得方便，但要解决两个问题：(1).(1).计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目计算机怎样懂得高级
2、语言程序，这就需要一个翻译程序实现从源程序到目 标程序的转换。标程序的转换。(2).(2).用什么方法来精确定义高级语言，即怎样精确描述高级语言。用什么方法来精确定义高级语言，即怎样精确描述高级语言。 要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。论或什么方法来描述的。 1 1 程序语言的定义程序语言的定义 语法语法 语义语义 语用语用潞披们痔迫柒领沃龋
3、村翔瓷蛆蕉矩蠢驴纽媳氰泻俐乌甜持夏青笺东驹虫滁第2章高级言及其语法描述第2章高级言及其语法描述 任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。（字母表）上的一个符号串。 对于自然语言来说，它们是定义在某个字母表上的对于自然语言来说，它们是定义在某个字母表上的句子的集合句子的集合。 对于程序语言来说，它们也是定义在某个字母表上的对于程序语言来说，它们也是定义在某个字母表上的句子句子的集合。这里的集合。这里的句子，就是一个源程序。的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运
4、算符以及一些界限符组成。通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。这些语法成分统称为单词或单词符号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。规则所确定的，即词法规则规定了单词符号的形成规则。 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言穷多个句子，则只需列出
5、句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明用这些规则来说明( (或者定义或者定义) )句子的组成结构，比如汉语句子可以是由主语句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。后随谓语而成，构成谓语的是动词和直接宾语。挤公轰纤亮砸粳庶刮峨襄碗邦赃肖帅渡艘控敲瘟辗侮荆疗假墙纷檬呈协汕第2章高级言及其语法描述第2章高级言及其语法描述“我是大学
6、生”。是汉语的一个句子 用语法来描述：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 蜀诀镰擒噪八舷狈皿盖台抿韩冰铆戚艘酋辽蔷朽遂讳晓狂柱远俗鞠士侈甸第2章高级言及其语法描述第2章高级言及其语法描述 有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成： 句子 主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词， 那么得到：主语谓语 代词谓语， 重复做下去， 句子：“我是大学生”的全部动作过程是：
7、句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。鼓魏援啸货趣酷怯饯泡囤吞瑶涅魏腐碰砌盅哺摈盛绒封袁唉葱熔杉柳润弧第2章高级言及其语法描述第2章高级言及其语法描述语言概述语言概述语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。汉语汉语所有符合汉语语法的句子的全体所有符合汉语
8、语法的句子的全体英语英语所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics颂梦催祈旨歉咒驯酗拜函堡践亨钞杀赊及躲聘撇愁月束凉措臆
9、陀捞侗眶皖第2章高级言及其语法描述第2章高级言及其语法描述语法语法 表示构成语言句子的各个记号之间的组合规律。表示构成语言句子的各个记号之间的组合规律。语义语义 表示各个记号的特定含义。即是一组规则，使用它表示各个记号的特定含义。即是一组规则，使用它可以定义语言的意义。（各个记号和记号所表示的对象之间可以定义语言的意义。（各个记号和记号所表示的对象之间的关系）的关系）语用语用 表示在各个记号所出现的行为中，它们的来源、使用表示在各个记号所出现的行为中，它们的来源、使用和影响。和影响。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点
10、点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽默、双关语和谜语就是利用这两方面意义间的差异。幽默、双关语和谜语就是利用这两方面意义间的差异。 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式形式”
11、是指这是指这样的事实：语言的所有规则只以符号串能出现的方式来陈述。形式语言理论样的事实：语言的所有规则只以符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。研究的基础。嗜燃苦癌洪敞驳碟豪诡帮肌噪外牌堰潞段文砰梗浓妻鲁蕉应述蓄促举湛岂第2章高级言及其语法描述第2章高级言及其语法描述2 高级语言的分类强制式语言 (Imperative Language) / 过程式语言 FORTRAN , C, Pascal应用式语言(Applicative Language) /
12、函数式语言 LISP基于规则的语言(Rule-based Language) Prolog面向对象语言(Object-oriented Language) 桌寄矗澜荆璃晕渐牺伙剪末埃央洪膳曲梅链雹偏搞蓑撮怖森杆摘讯京汾弊第2章高级言及其语法描述第2章高级言及其语法描述2.2 2.2 形式语言基础形式语言基础一、一、字母表和符号串字母表和符号串 字母表字母表：符号的非空有限集合 例：=a，b，c 符号符号：字母表中的元素 例： a，b，c 符号串符号串：符号的有穷序列 例：a, aa, ac, abc，. 空符号串空符号串：无任何符号的符号串() 符号串的形式定义符号串的形式定义 有字母表，定义
13、： （1）是上的符号串； （2）若x是上的符号串，且a ，则ax或xa是上的符号串； （3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。 符号串集合符号串集合：由符号串构成的集合。亮郸蔫舞绘袱降赘着寇捂阐肚违复季慨捻嚷莽燎携郧妻踞枪报衡话荧奏屁第2章高级言及其语法描述第2章高级言及其语法描述二、二、符号串和符号串集合的运算符号串和符号串集合的运算 1.符号串相等符号串相等：若x、y是集合上的两个符号串，则xyiff（当且仅当）组成x的每一个符号和组成y的每一个每一个符号依次相等。 2.符号串的长度符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。 例： xST
14、V ， |x|=3栗什贪绍跃仿挣茶熏艘颧唤宇乃屡冲义汀团粘丙戒吁纹船获埃铝嚷俭刹堆第2章高级言及其语法描述第2章高级言及其语法描述例：Aa,b,B=c,d, AB= ？ 4. 符号串集合的乘积运算符号串集合的乘积运算：令A、B为符号串集合，定义 AB xy |xA,yB ac，ad，bc，bd 因为xxx，所以A=A=A 3. 3.符号串的联接符号串的联接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的联接 xyXYYX也是上的符号串。 注意：一般xyyx，而xx杆某鼎笆断眠讨例铂玖炊田黄颗厂硼项檬恐工搭艘烹丧湛幸秧俐瓦澡售惊第2章高级言及其语法描述第2章高级言及其语法描述6.6.
15、符号串集合的闭包运算符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。 A* A0 A称为集合A的闭包。例：A=x,y A？ A* ？ 5. 符号串集合的幂运算符号串集合的幂运算：有符号串集合A，定义A0 =,A1=A,A2=AA,A3=AAA, AnAn-1A=AAn-1 ，n0x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A1 A2 A3, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A0 A1 A2 A3州音颤俏泳够挪晃瘟凌耿包佬隋释疚仑契真贮土室谦抡可捉汾淫婶轮获衅第2章高级言及其语法描述
16、第2章高级言及其语法描述 为什么对符号、符号串、符号串集合以及它们的运算感兴趣为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), =B为单词集 B =begin, end, if, then,else,for, 则B A* 。语言的句子是定义在B上的符号串。若令C为句子集合，则C B * , 程序 C甄漾扰皮咎滨鞠拷杯径氓获蛙氦浩梭母秋恍铸饮咒曲黔冒漠馁怎曼更匆嘻第2章高级言及其语法描述第2章高级言及其语法描述2.3 文法的直观理解文法的直观理解 1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和
17、规定语言结构的称为“文法”（或称为“语法”）。 例：有一句子：“我是大学生” 。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓结构”。如何定义句子的合法性？有穷语言无穷语言危纸唤固什吟拭脓钧苛熔蜜茵食搔颧鸦赂韩虐料旭率幕峨赘漠矛帕了桑匈第2章高级言及其语法描述第2章高级言及其语法描述 2.2.语法规则语法规则：我们通过建立一组规则（产生式），来描述句子的语法结构结构。规定用“:=”表示“由组成”。:=:=| :=你|我|他:= 王民|大学生|工人|英语:=:=是|学习:=|绦纶较膊庄永暮寥标誊止冷耍六祁户段清遭柒著侯吵望职烹氟克虫湛箔杀
18、第2章高级言及其语法描述第2章高级言及其语法描述3.由产生式推导推导句子：有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。 = = 这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。异筏虽美福剩渍晌纪峙幌哟抄杀胃娠哗只扳焊食钳宦滦词白斗幽渣罩晨汽第2章高级言及其语法描述第2章高级言及其语法描述 = = = 我 =我 =我是 =我是 =我是大学生:=:= :=:=| := :=你你| |我我| |他他 :=:= 王民王民| |大学生大学生| |工人工人| |英语英
19、语 :=:= :=:=是是| |学习学习 :=:=| 推导方法：推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。铭宛界忌阳剧帜贼丑禽俞靶恨响畜巡驰灰快案辩烬为喝峪住郸坞斩漆中鳃第2章高级言及其语法描述第2章高级言及其语法描述例：有一英语句子：The big elephant ate the peanut.:=:= :=the:=big:=elephant:=:=ate:= :=peanut舶事撑慕铱钱茎捅柯泽灶菠盐钱咐挥的载流叫类鹅论馏闷假孺倍蹿内厦惭第2章高级言及其语法描述第2章高级言及其语法描述 = = = the = the b
20、ig = the big elephant = the big elephant = the big elephant ate = the big elephant ate = the big elephant ate the = the big elephant ate the peanut:=:= :=:= := :=the :=:=big :=:=elephant | peanut :=:= :=:=ate :=:= 匡王闪沦镐泰枣斟虱部功甩钢兢吴读邵问烧诣着臼碾卤贝愈悍汤多甩浊蜒第2章高级言及其语法描述第2章高级言及其语法描述上述推导可写成 = the big elephant ate
21、 the peanut+说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。 (2) 从一组产生式可推出不同的句子，如以上产生式还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语义上都不正确。 所谓文法文法是在形式上对句子结构的定义与描述，而未涉及语义问题。拍禄治传航筋朔湃巢籽卸城陨畸翼显岂赢讲刚搓塌吁慎岛蛛两叹互坑府故第2章高级言及其语法描述第2章高级言及其语法描述 4.语法树：我们用语法树来描述一个句子的语法结构。Thebigelephantatethepeanut语法成分（
22、在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)请趁约懈炼原雄度侥瘪擦凄侠迢狮那舜哼疆框租鸦姑槛罚垂做欧骨钦泅橇第2章高级言及其语法描述第2章高级言及其语法描述2.4.1文法的定义文法的定义2.4 文法和语言的形式定义 定义1: 文法G=（VN，VT，P，Z） VN ：非终结符号集 VT ：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） ZVNVVNVT称为文法的字汇表产生式：U : xU VN, xV*其中其中:A.产生式：产生式：产生式是一个有序对(U, x), 通常写为: U : x 或U x； | U| = 1 |x| 0B.非终结符号：非终结符号：
23、出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN 。C.终结符号：终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT 。撵侯狡出浊立暖宁厦奄瑶春底壹朽钧鸥俩暑清乏玄裔檄排惋架且她髓抨辰第2章高级言及其语法描述第2章高级言及其语法描述P = ； ； ； 0； 1； 9； Z = ；例：无符号整数的文法：G=（VN，VT，P，E）VN, VT = 0,1,2,3,9惩禄躺禁溪离帆捞湘稳昭树术窟淀非盅耘赶廓标泊胳咀频蛛班局性身编悬第2章高级言及其语法描述第2章高级言及其语法描述几点说明几点说明：产生式左边符号构成集合V
24、N，且 Z VN有些产生式具有相同的左部，可以合在一起例、 ； | ； 0 | 1 | 2 | 3 | | 9 文法的BNF表示给定一个 文法，实际只需给出产生式集合，并指定识别符号例、 G ； | ； 0 | 1 | 2 | 3 | | 9轧艳罚辜竭慨滤甜祈厨亚阑盗七邑猜吱嫉肘吭粥铝欢疵殃旱囚迪窃鸟轮伶第2章高级言及其语法描述第2章高级言及其语法描述2.4.2 推导与归约推导与归约 定义2： 直接推导：文法G：vx Uy，wxuy, 其中x、y V* ，UVN, u V*, 若U : uP，则v w。 若xy，有U : u，则U u 换句话说，x和y是符号串，若使用一次产生式可以从x变换出y
25、，则称x直接推导出y(或者说y是x的直接推导），记为x y。龋纺滴玉猎职咋镑勾楔斤熄枕壬芬称逛透卞姑郧希整朴咆筛土篱邯量宜琐第2章高级言及其语法描述第2章高级言及其语法描述 当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。例如：例如：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8| 9N ND NDD ND9 N09 D09 109 (6)=(1)=(3)(4)=(2)(5)=抡斩肩蚁咨拂茬洱酣迂羽术见柞减乃万泼笨鸽汰杭断绦帐碴譬摆预悦西法第2章高级言及其语法描述第2章高级言及其语法描述
26、 N=109定义3： +推导：x和y是符号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为x y。N ND NDD ND9 N09 D09 109 (6)=(1)=(3)(4)=(2)(5)=例：则： 定义4： *推导：x和y是符号串，若使用0次或若干次产生式可以从x变换出y，则称x*推导出y(或者说y是x的*推导），记为x y。* *N=109则： *N=N或者说：若有直接推导序列：x=U0=U1=U2=Un=y,则 x=y 。+皱凡逢著要诣泼晚瓜榜彦虞饮隆礼彪粘缴挥集铆酝父庇吉垂粤苟以降晋摹第2章高级言及其语法描述第2章高级言及其语法描述直观意义：规范推导
27、最右推导 定义5：最右推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最右非终结符进行替换，称为最右推导。最左推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最左非终结符进行替换，称为最左推导。 定义6： 推导的逆过程称之为归约。例：x =y,可称为x直接推导出y，也可称为y直接归约出x。 x =y ,可称为x推导出y，也可称为y归约出x。钵涯奔你娥锯星临征司烷迂摘晴斧言弱喇擂摹乔敞滓朗存磺捍杭贩柳涕摩第2章高级言及其语法描述第2章高级言及其语法描述2.4.3 语言的形式定义语言的形式定义文法GZ所产生的所有句子的集合 定义6：文法GZ （1）句型句型：x是句型
28、 Z x,且xV*；（2）句子句子：x是句子 Z x, 且xVT*；（3）语言语言：L（GZ）=x| Z x， xVT* ；+*+绊出盎逗泪涂遂绕谁商讶黄涩詹缸豁裕舶滦溜脾子满瞧嗓棺丹关尼惑浸鳖第2章高级言及其语法描述第2章高级言及其语法描述例：abna|n1,构造其文法 G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb 定义7. G和G是两个不同的文法，若 L(G) = L(G) , 则G和G为等价文法。盔肋褪詹穗皂铃锗脑撇戒黍贤申刚弥直对砒什触恿等峨钨倦榴冕涸痈携汁第2章高级言及其语法描述第2章高级言及其语法描述编译感兴趣的问题是编译感兴趣的问题是: :给定终极符x, 文
29、法G, 求x L(G) ?x算法1算法2x L(G) ?Gyn出错处理停机宝褒串屯逼碌矢嵌变暑扁张结蔑楞踏溶掀忍卫孙拼侯岂被屁谈美弟噬属部第2章高级言及其语法描述第2章高级言及其语法描述2.4.4 递归文法递归文法1.递归产生式递归产生式：产生式右部有与左部相同的符号 对于 U xUy 若x=,即U Uy，左递归； 若y=,即U xU，右递归； 2.递归文法递归文法：文法G，存在U VN if U=U, 则G为递归文法； if U=U, 则G为左递归文法； if U=U, 则G为右递归文法；+焕腋婆地勇辰芽兔拣摆糕氮送积鼻窥崇搽砌姑妈渊媳淫醒怔德肇哥农朝磐第2章高级言及其语法描述第2章高级言及
30、其语法描述4. 递归文法的优点：可用有穷条产生式，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？!3. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）汁辅葫锨绒妒膝揭攘兑律绣兴穷井航甘摧珠鼠逃酵肺邪溃络注坝枷喉近蔽第2章高级言及其语法描述第2章高级言及其语法描述2.5 文法分类 形式语言：用文法和自动机所描述的没有语义的语言。 文法定义：乔姆斯基将所有文法都定义为一个四元组：G=（VN，VT，P，Z） VN：非终结符号集 VT：终结符号集 P：产生式或规则的集
31、合 Z：开始符号（识别符号） ZVN 语言定义： L（GZ）=x| Z=x , xVT*, +匀入草孵型渠环潞荚窘碾霸吕刊傍痒箩董贬滇炳翰届膨氮荒崭经困煎亥芋第2章高级言及其语法描述第2章高级言及其语法描述 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。定义8：0型文法： P： u v 其中uV，vV* 0型语言：L0 这种语言可以用图灵机(Turing)接受. 0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。蛇炮尘管泪恍蓬高涎磅商值舰望厩例茨七击项逸止逐侵逸甄炳贡司沪呛骸第2章高级言及其语法描述第2章高级言及其语法
32、描述定义9： 1型文法： P： xUy xuy 其中 UVN， x、y、uV* 1型语言：L1 这种语言可以由一种线性界限自动机接受.称为上下文敏感或上下文有关。也即只有在x、y这样的上下文中才能把U改写为u杭蜡辉矿筒薄娩刮腊翠眠摘赌做射关葵纵潦唤害榜侄它察扇对内窘磅侨埂第2章高级言及其语法描述第2章高级言及其语法描述定义10：2型文法： P： U u 其中 UVN， uV* 2型语言：L1 这种语言可以由下推自动机接受. 称为上下文无关文法。也即把U改写为u时，不必考虑上下文。 注意：2型文法与BNF表示相等价。帐纫驼饼异氯嫂跌恕羽愁里聊疆疗惋孝砸劝剐无泼唱止定缸排垣瓣陈刽磐第2章高级言及其
33、语法描述第2章高级言及其语法描述（右线性） P： U T 或 U Tw 其中 U、wVN TVT 3型语言：L3 又称正则语言、正则集合 这种语言可以由有穷自动机接受. 3型文法称为正则文法。它是对2型文法进行进一步限制。（左线性） P： U T 或 U wT 其中 U、wVN TVT定义11： 3型文法：驰溶囤加文橙害土困桌矾忌踌捻臭候川惶睦吃芜挟夹邀辨毡猿圾及琶葱买第2章高级言及其语法描述第2章高级言及其语法描述根据上述讨论，L0 L1 L2 L30型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。创汲位穴稚且蒋簇衷侠摘主新独箱粮跟豹忿疯泽肺晴钳柄勒同铡蛊壳敌桓第
34、2章高级言及其语法描述第2章高级言及其语法描述2.6 语法树与二义性文法2.6.1 推导与语法树推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。 结点：符号 根结点：识别符号识别符号 中间结点：非终结符非终结符 叶结点：终结符或非终结符终结符或非终结符 有向边：表示结点间的派生关系。 ZUVabcd狂沽蔗起私轩沉爬噬坷室汲林教鸟喷民沉禾告论册甫聋著恩倾旭牛阅将筋第2章高级言及其语法描述第2章高级言及其语法描述 注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生成规律不同，但最终生成的语 法树形状完全相
35、同。某些文法有此性质，而某些文法 不具此性质。( 2 ) 句型的推导及语法树的生成（自顶向下）给定GZ，句型w： 可建立推导序列，Z=w 可建立语法树，以Z为树根结点，每步推导生成语法树的一枝，最终可生成句型的语法树。*桅练翰渤皋鹰萝茁茨弥速蛾倍卸硼苛环辕却剃尹眺谚丽庇狐乳当舆罚筐陕第2章高级言及其语法描述第2章高级言及其语法描述 1(1)(2)(3)(5)(4)0一般推导：阂蔚田析抒啼臃旨氧发侨托虫胡班浚铰式妆反卫荐踩惠条肝受勿瞎待庆印第2章高级言及其语法描述第2章高级言及其语法描述( 3 ) 子树与简单子树 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。简单子树：只有单层
36、分枝的子树称为简单子树。坚坑寝驾厅构错拎纶含脉锯琼腻渤牲两饶辨播钦梧肯妄惺披畦牌尖砧蹲茄第2章高级言及其语法描述第2章高级言及其语法描述( 4 ) 树与推导句型推导过程 句型语法树的生长过程 由推导构造语法树由推导构造语法树1从识别符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。胶许抚输懦碰滇吉逞在枢类未怖薪寓指将索午享缆观痕匡塑数亦噎薄翱愿第2章高级言及其语法描述第2章高级言及其语法描述P = ； ； ； 0； 1； 9； Z = ；例：无符号整数的文法：G=（VN，VT，P，E）VN, VT = 0,1,2,3,9骏铭专日趾怀隧蜡渊跳迪懂捌来样样槽驾刊淆泰耳舵馈汛丢荧迈依
37、兆是蹋第2章高级言及其语法描述第2章高级言及其语法描述例：G句型10= =0 0= 0=110=规范推导家蒸境腊童旭骇庐质整群烬哭涸议瓮园层嗣翰姥友二狸缩仓均桑氟免镇稽第2章高级言及其语法描述第2章高级言及其语法描述 由语法树构造推导由语法树构造推导2自上而下地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。从句型开始，自右向左地逐步进行归约，建立推导序列。定义 对句型中最左简单短语（句柄）进行的归约称为 规范归约。懒知版伦堕弄宽哑雇尹滩雏牛腻又乖辊错本矽镣抠恳擅旦绿熬旱哈掐稿特第2章高级言及其语法描述第2章高级言及其语法描述01= = 0=10 0=规范归约与规范推导互为
38、逆过程宁椅刷诀眺鸥舷掐刊入搓碰肾匹烷啼戊城石诗鸵惟稀羚林颧傣骆聋央两辐第2章高级言及其语法描述第2章高级言及其语法描述定义 通过规范推导或规范归约所得到的句型称为规范句型。 在上例中， 就不是规范句型，因为：=不是规范推导疙谬蜡蕉孟藏彼窜庙杀掇邱搅轴俭嗜绢育攀胶鼓擒阳烃汛价恕卧港搔篙召第2章高级言及其语法描述第2章高级言及其语法描述2.6.2 文法的二义性文法的二义性 定义 若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。 换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。下面举一个二义性文法的例子： GE: E:= E+E | E*E
39、| (E) | i VN =E VT = +, * , ( , ) , i 熊钩飘矗侣贞阐八甥雪匹土怖析谢藏慢械市楞椿犊昌酶瘸蓝酗遍芋刀境共第2章高级言及其语法描述第2章高级言及其语法描述 对于句子Sii * i L（GE ），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1) E=E+E=E+E*E =E+E*i =E+i*i = ii * i(2) E= E*E = E*i = E+E*i = E+i*i = ii * i宦建峨檄怒坠由花蜒毁绎馅栅奸静仅颤便汕愁兰肃议犹铅狂咱教其惮垄温第2章高级言及其语法描述第2章高级言及其语法描述 定
40、义 若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的，否则是无二义性的。 以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。上例中，规范句型E+E*i 是由ii * i通过两步规范规约得到的，但对于同一个句型E+E* i，它有两个不同的句柄句柄（对应上述两棵不同的语法树）：i 和 EE。因此语法的二义性意味着句型的句柄不唯一。熄各雷潦撂分但伟恶肪形灼芍调狐九爬议披并腮朗凌继贮众咽啪畴猴裂短第2章高级言及其语法描述第2章高级言及其语法描述EEE+EE*iEEE*EE+i句柄：i句柄：EE 定义 若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的
41、。挫表过炔习蓑苍尊惯旨版譬险绥硕仟嘻桔绦裹疥朽袜阂信情企旅郭编或弥第2章高级言及其语法描述第2章高级言及其语法描述 若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。 现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。 由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。秦穿该舵窿盏蒸姜话战伸启名筷谜送桓朝前忌葛秸辗撩趋楷圆贞钡歉酌后第2章高级言及其
42、语法描述第2章高级言及其语法描述例例:算术表达式的文法算术表达式的文法E:= E+E | E*E | (E) | iE:= E+T | TT := T*F | FF := (E) | i例例:Pascal 条件语句的文法条件语句的文法:= If then | If then else := | |.松趣虏茸志党典聪窜协递悸凳狐锌穗畏硼敢筐数雌醇盖寞迹橱筏垂樱暂诬第2章高级言及其语法描述第2章高级言及其语法描述2.7 有关文法的实用限制 1 若文法中有如U:=U的产生式，则这就是有害产生式，它会引起二义性。 例如存在U:=U， U:= a | b,则有两棵语法树：UaUUa纪锗谐努已畴漫止蘑氛墩
43、譬冀绰痞溜撬禾艰婆抗呵喘讥豪忘枫嚏责拘潮齐第2章高级言及其语法描述第2章高级言及其语法描述 多余产生式：（1）在推导文法的所有句子中，始终用不到的产生式。即该产生式的左部非终结符不出现在任何句型中。（2）在推导句子的过程中，一旦使用了该产生式，将推不出任何终结符号串。即该产生式中含有推不出任何终结符号串的非终结符。 例如给定GZ，若其中关于U的产生式只有如下一条： U xUy 该产生式是多余产生式。若还有U a，则此产生式并非多余哺涪臀骤蚂饿划撞爪扯酵审托盘捆坏掏今约缄奎钠彭麻野膜晨沦壤欢瘴酒第2章高级言及其语法描述第2章高级言及其语法描述 2、语法图2 文法的其它表示法 1、扩充的BNF表示
44、 BNF的元符号： , , | 扩充的BNF的元符号： , :=, |, , , , (, ) 字母 字母 数字 数字 标识符无符号整数陕馏泛回果炉镍柜柜赁拜甜蚕旺陕铡赶午铱垢忆犀粒疟埃夕帆叁首锈帕拄第2章高级言及其语法描述第2章高级言及其语法描述小 结掌握符号串、文法、句型、句子和语言的定义几个重要概念：递归、语法树、文法的二义性、文法的实用限制等。掌握文法的表示：BNF、扩充的BNF范式、语法图。了解文法分类。您奉协汇途崖址谨碴确乒蹬版棺皑氧全迂熔咒屿昏芦擅奥矾耀逊许楔逾踢第2章高级言及其语法描述第2章高级言及其语法描述本 章 作 业P36：6#，7#，8#，10#碧眨缎昨沙辖易骏终遮企歇予臣囊鸵熙除承把斌痢季掸烽望览集署等楞廓第2章高级言及其语法描述第2章高级言及其语法描述
