资源描述
第第2章章高级语言高级语言及其文法及其文法关键：让系统知道关键：让系统知道“组成规组成规则则”并按照规则分析！并按照规则分析！2024/7/311本章主要内容本章主要内容语言的形式化描述语言的形式化描述文法文法vv2.1 2.1 语言概述语言概述vv2.2 2.2 基本定义基本定义vv2.3 2.3 文法文法(Grammar)Grammar)的定义的定义vv2.4 2.4 CFGCFG的语法的语法(分析分析)树树(Parse Tree)Parse Tree)vv2.5 2.5 文法的分类文法的分类vv2.6 2.6 文法的构造文法的构造2024/7/3122.1语言概述语言概述v什么是语言什么是语言自然语言自然语言(NaturalLanguage)v是是人与人人与人之间的通讯工具之间的通讯工具v语义语义(Semantics):环境、背景知识、语气、环境、背景知识、语气、二义性二义性难以形式化难以形式化计算机语言计算机语言(ComputerLanguage)v计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具v严格的语法严格的语法(Grammar)、语义语义(Semantics)易于形式化：严格易于形式化：严格语言是用来交换信息的工具语言是用来交换信息的工具功能性描述功能性描述2024/7/3132.1语言概述语言概述v语言的描述方法语言的描述方法现状现状自然语言：自然、方便自然语言：自然、方便-非形式化非形式化数学语言数学语言(符号符号)：严格、准确：严格、准确-形式化形式化机器要掌握规则：形式化描述机器要掌握规则：形式化描述v高度的抽象高度的抽象v严格的理论基础严格的理论基础v方便的计算机表示方便的计算机表示2024/7/3142.1语言概述语言概述v语言语言形式化的内容提取形式化的内容提取字符字符(Character)：语言的基本字符：语言的基本字符单词单词(Token)：满足一定规则字符串满足一定规则字符串句子句子(Sentence)：满足一定规则单词序列满足一定规则单词序列语言语言(Language)：满足一定规则的句子集合满足一定规则的句子集合v语言是字和组合字的规则语言是字和组合字的规则结构性描述结构性描述例：今次课是二日上编译第例：今次课是二日上编译第今日是上第二次编译课今日是上第二次编译课2024/7/3152.1语言概述语言概述v程程序序设设计计语语言言(ProgrammingLanguage)形形式式化化的内容提取的内容提取程序设计语言为组成程序的所有语句的集合程序设计语言为组成程序的所有语句的集合程序程序(Program)：满足语法规则的语句序列满足语法规则的语句序列语句语句(Sentence)：满足语法规则的单词序列满足语法规则的单词序列单词单词(Token)：满足词法规则的字符串满足词法规则的字符串v例例变量变量=表达式表达式if条件条件then语句语句while条件条件do语句语句call过程名过程名(参数表参数表)2024/7/3162.1语言概述语言概述v描述形式描述形式文法文法语法语法语句语句v语句的组成规则语句的组成规则v描述方法：描述方法：BNF范式、语法范式、语法(描述描述)图图词法词法单词单词v单词的组成规则单词的组成规则v描述方法：描述方法：BNF范式、正规式范式、正规式2024/7/3172.2基本定义基本定义v定义定义1字母表字母表（Alphabet）是一个非是一个非空有穷集合，字母表中的元素称为该字母空有穷集合，字母表中的元素称为该字母表的一个字母（表的一个字母（Letter），），也叫字符也叫字符（Character）v例例以下是不同的字母表以下是不同的字母表a，b，c，da，b，c，z0，1v相当于高级语言的字符集相当于高级语言的字符集2024/7/3182.2基本定义基本定义v定义定义2字母表字母表上上符号串符号串(String)(1)是是上的一个符号串上的一个符号串(叫做空串叫做空串)；(2)若若x是是上的符号串，而上的符号串，而a是是的元素的元素,则则xa是是上的符号串；上的符号串；(3)y是是上的符号串上的符号串,当且仅当它由当且仅当它由(1)和和(2)导导出出v由字母表中的符号所组成的的任何有穷序由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串列被称之为该字母表上的符号串,也称作也称作“字字”(Word)2024/7/3192.2基本定义基本定义v定义定义3的的正闭包正闭包(PositiveClosure)：+=x|x是是上的非空字符串上的非空字符串+=234v的的克林闭包克林闭包(KleeneClosure)：*=+=0232024/7/31102.2基本定义基本定义v例例设设=0,10,1+=0，1，00，01，11，000，001，010，011，100，0,1*=，0，1，00，01，11，000，001，010，011，100，2024/7/31112.2基本定义基本定义v例例设设=a，b，c，da，b，c，d+=a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abca，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc，2024/7/31122.2基本定义基本定义v定定义义4设设1、2是是两两个个字字母母表表，1与与2的的乘乘积积(Product)12=ab|a1，b2v例例:1=0,1,2=a,b,12=0a,0b,1a,1b2024/7/31132.2基本定义基本定义v定义定义5设设是一个字母表，是一个字母表，L*，L称为称为字母表字母表上的一个上的一个语言语言（Language），），xL，x叫做叫做L的一个的一个句子句子。v例：例：=0，1上的语言上的语言0，100，110，1，00，110，1，00，11，01，1000，11*01，10*2024/7/31142.2基本定义基本定义设设s是是符号串：符号串：01290273前缀前缀：移走：移走s的尾部的零个或多于零个符号的尾部的零个或多于零个符号后缀后缀：删去：删去s的头部的零个或多于零个符号的头部的零个或多于零个符号子串子串：从：从s中删去一个前缀和一个后缀中删去一个前缀和一个后缀子序列子序列:从从s中删去零个或多于零个符号中删去零个或多于零个符号(这些符号这些符号不要求是连续的）不要求是连续的）长度长度：是该符号串中的符号的数目。例如：是该符号串中的符号的数目。例如|aab|=3,|=0。2024/7/31152.2基本定义基本定义v定义定义6设设x和和y是符号串，它们的是符号串，它们的连接连接(Concatenation)xy是把是把y的符号写在的符号写在x的符号之后得到的符号串。的符号之后得到的符号串。例如，例如，x=ba，y=nana，xy=bananav定义定义7设设x是符号串是符号串,x的的n次次幂幂(power)为为x0=，xn=xn-1x，n0。例如，令例如，令x=ba,x1=ba，x2=baba，x3=bababa，.2024/7/31162.3文法的定义文法的定义如何实现语言结如何实现语言结构的形式化描述？构的形式化描述？2024/7/3117考虑一个句子考虑一个句子文法要素的提取文法要素的提取分析分析：Thegraywolfwilleatthegoat谓语谓语主语主语形容词形容词名词名词动词动词直接宾语直接宾语助动助动句子句子动原动原冠词冠词名词名词Thegraywolfwilleatthegoat冠词冠词提取规则，写在黑板上提取规则，写在黑板上2024/7/3118编译程序编译程序上次课主要内容上次课主要内容v编译程序的组织编译程序的组织编译的扫描遍数编译的扫描遍数前端、后端前端、后端前端前端后端后端中间中间代码代码中间代码中间代码优化优化中间中间代码代码2024/7/3119上次课主要内容上次课主要内容v以语法分析为核心以语法分析为核心源源程程序序符符号号表表管管理理词法分析词法分析代代码码生生成成存存储储分分配配语义分析语义分析语法分析语法分析目目标标程程序序优化优化2024/7/3120上次课主要内容上次课主要内容vT T形图形图源语言源语言表示语言表示语言目标语言目标语言v编译程序实现技术编译程序实现技术移植：用移植：用“C”C”语言写一个语言写一个“C”C”语言编译器语言编译器现有编译器的利用现有编译器的利用：用：用“C”C”语言写一个语言写一个“NEW”NEW”语言编译器语言编译器自展：找一个子集，开始滚雪球自展：找一个子集，开始滚雪球自动生成：自动生成：lex、Yacc2024/7/3121上次课主要内容上次课主要内容v语言语言信息交流的工具信息交流的工具字字和组合字的和组合字的规则规则的统一体的统一体v字母表上的语言字母表上的语言字母表字母表+、*、a，x*、L*、xL前缀、后缀、子串、串长、串的连接、串的幂前缀、后缀、子串、串长、串的连接、串的幂2024/7/3122 句子句子 主语主语 谓语谓语 主语主语 冠词冠词 形容词形容词 名词名词 谓语谓语 动词动词 直接宾语直接宾语 动词动词 助动词助动词 动词原动词原形形 直接宾语直接宾语 冠词冠词 名词名词 产生句子的规则产生句子的规则从产生语言的角度从产生语言的角度 冠词冠词 thethe 形容词形容词 graygray 助动词助动词 will will 动词原动词原形形 eat eat 名词名词 wolfwolf 名词名词 goatgoatProductTerminalVariableStartSymbol2024/7/3123终结符号集终结符号集VT=the,gray,wolf,will,eat,goat非终结符号集非终结符号集VN=句子句子，主语主语，谓语谓语，冠词冠词，形容词形容词，名词名词，动词动词，直接宾语直接宾语，助动词助动词，动词原动词原形形 语法规则集语法规则集P=句子句子 主语主语谓语谓语，开始符号开始符号S=句子句子 句子的语法组成句子的语法组成终结符号集，非终结符号集，语法规则，开始符号终结符号集，非终结符号集，语法规则，开始符号2024/7/3124文法文法G的形式定义的形式定义文法文法G为一个四元组为一个四元组:G=(VT，VN，P，S)vVT：终结符终结符(Terminal)集集vVN：非终结符非终结符(Variable)集，集，VTVN=语法范畴语法范畴某个语言结构某个语言结构vS：开始符号：开始符号(StartSymbol)，SVN至少在产生式左侧出现一次至少在产生式左侧出现一次2024/7/3125文法文法G的形式定义的形式定义vP：产生式产生式(Product)集合集合，被被称称为为产产生生式式（定定义义式式），读读作作：定定义义为为。其其中中(VTVN)+，且且中中至至少少有有VN中中元元素素的的一一个个出出现现。(VTVN)*。称称为为产产生生式式的的左左部部(Left Part)，称称为为产产生生式式的的右部右部(RightPart)2024/7/3126 的语法组成的语法组成vG =（thethe，graygray,wolf,willwolf,will,eat,goat,eat,goat，句子句子，主语主语，谓语谓语，冠词冠词，形容词形容词，名词名词 ，动词动词 ，直接宾语直接宾语 ，助动词助动词 ，动词原动词原形形 ，句子句子 主语主语谓语谓语 ，主语主语 冠词冠词 形容词形容词 名词名词，谓语谓语 动词动词 直接宾语直接宾语，动词动词 助动词助动词 动词原动词原形形，直接宾语直接宾语 冠词冠词 名词名词，冠词冠词 thethe，形容词形容词 graygray ，助动词助动词 will will，动词原动词原形形 eat eat，名词名词 wolfwolf，名词名词 goatgoat ，句子句子）v看起来有点乱！看起来有点乱！2024/7/3127 句子句子 主语主语 谓语谓语 主语主语 冠词冠词 形容词形容词 名词名词 谓语谓语 动词动词 直接宾语直接宾语 动词动词 助动词助动词 动词原动词原形形 直接宾语直接宾语 冠词冠词 名词名词 没有这个看着没有这个看着“舒服舒服”冠词冠词 thethe 形容词形容词 graygray 助动词助动词 will will 动词原动词原形形 eat eat 名词名词 wolfwolf 名词名词 goatgoat只写产生式只写产生式？约定：第一个产生式的左部为开始符号约定：第一个产生式的左部为开始符号2024/7/3128例例2-1算术表达式的文法算术表达式的文法v考虑简单算术表达式组成的语言考虑简单算术表达式组成的语言v递归定义递归定义中缀表示中缀表示标识符标识符(id)（常数、变量）是表达式常数、变量）是表达式；表达式加表达式是表达式；表达式加表达式是表达式；表达式减表达式是表达式；表达式减表达式是表达式；表达式乘表达式是表达式；表达式乘表达式是表达式；表达式除表达式是表达式；表达式除表达式是表达式；表达式加上括号后是表达式表达式加上括号后是表达式2024/7/3129例例2-1算术表达式的文法算术表达式的文法考虑用式子表示这个定义考虑用式子表示这个定义标识符标识符(id)id)是表达式是表达式表达式加表达式是表达式表达式加表达式是表达式EidEE+E表达式减表达式是表达式表达式减表达式是表达式EE-E表达式乘表达式是表达式表达式乘表达式是表达式EE*E表达式除表达式是表达式表达式除表达式是表达式EE/E表达式加上括号后是表达式表达式加上括号后是表达式E(E)2024/7/3130例例2-1算术表达式的文法算术表达式的文法v按照约定：只写产生式按照约定：只写产生式EE+EEE-EEE*EEE/EE(E)EidvG=（id，+，-，*，/，(，)，E，P，E）v简写简写EE+E|E*E|E-E|E/E|(E)|id2024/7/3131产生式的简写产生式的简写v对一组有相同左部的产生式对一组有相同左部的产生式1，2，n简单地记为：简单地记为：1|2|n读作：读作：定义为定义为1，或者或者2，或者或者n，并且称它们为，并且称它们为产生式产生式。1，2，n称为称为候选式候选式(Candidate)v文法如何实现对语言的刻画？产生式很关键！文法如何实现对语言的刻画？产生式很关键！让描述看起来让描述看起来更简洁一点更简洁一点2024/7/3132产生式规定了一些变换产生式规定了一些变换vE由第由第1个候选式可以变成个候选式可以变成E+EvE+E中的第中的第1个个E由第由第2个候选式可以变成个候选式可以变成E*E，从而从而E+E变成变成E*E+Ev根据第根据第4个候选式，个候选式，E*E+E中的中的E都可以变成都可以变成id:E*E+E变成变成id*E+Eid*E+E变成变成id*E+idid*E+id变成变成id*id+idv也就是说，根据第也就是说，根据第4个候选式，个候选式，E*E+E经经3步步变换变成变换变成id*id+iduu1 1 1 1 EE+E EE+E EE+E EE+E uu2 EE*E 2 EE*E 2 EE*E 2 EE*E uu3 E(E)3 E(E)3 E(E)3 E(E)uu4 Eid4 Eid4 Eid4 Eiduu5 EE-E 5 EE-E 5 EE-E 5 EE-E uu6 EE/E 6 EE/E 6 EE/E 6 EE/E 2024/7/3133变换的符号表示变换的符号表示EE+E（1）E*E+E（2）id*E+E（4）id*E+id（4）id*id+id（4）4 Eid4 Eid4 Eid4 Eid5 EE-E 5 EE-E 5 EE-E 5 EE-E 6 EE/E 6 EE/E 6 EE/E 6 EE/E vE可以变成可以变成E+EvE+E第一个第一个E变成变成E*EvE*E+E变成变成id*E+Evid*E+E变成变成id*E+idvid*E+id变成变成id*id+idE经经5步变换变成步变换变成id*id+id：E5id*id+id1 1 1 1 EE+EEE+EEE+EEE+E2 EE*E2 EE*E2 EE*E2 EE*E3 E(E)3 E(E)3 E(E)3 E(E)实质是从实质是从E开始依据产生式对所得串中的特定部开始依据产生式对所得串中的特定部分进行变换，不断获得新的串，最终得到目标分进行变换，不断获得新的串，最终得到目标2024/7/3134变换的分析变换的分析v实质是从实质是从E E开始依据产生式对所得串中的开始依据产生式对所得串中的特定部特定部分分进行变换，不断获得新的串，最终得到目标进行变换，不断获得新的串，最终得到目标E+E 依据产生式依据产生式EE*EE+E*E A依据产生式依据产生式AAE+EE+E*E2024/7/3135直接推导与归约直接推导与归约v根据产生式对符号串进行变换的过程根据产生式对符号串进行变换的过程A是文法是文法G的一个产生式，的一个产生式，且且、（VTVN）*，称称A的直接的直接推导推导/派生派生(Derive)出出，也称也称直接直接归约归约(Reduce)为为A注意到是根据注意到是根据A而将而将中的中的变成了变成了A，所，所以，一般称将以，一般称将归约为归约为A记为记为A（A）2024/7/3136直接推导与归约直接推导与归约v推导：推导：EE+E（1）E*E+E（2）id*E+E（4）id*E+id（4）id*id+id（4）从从E出发，出发，5步推导出句步推导出句子子id*id+idv归约：归约：id*id+idid*E+id（4）id*E+E（4）E*E+E（4）E+E（2）E（1）4 Eid4 Eid4 Eid4 Eid5 EE-E 5 EE-E 5 EE-E 5 EE-E 6 EE/E 6 EE/E 6 EE/E 6 EE/E 1 1 1 1 EE+E EE+E EE+E EE+E 2 EE*E 2 EE*E 2 EE*E 2 EE*E 3 E(E)3 E(E)3 E(E)3 E(E)从从id*id+id出发，出发，5步步归约成开始符号归约成开始符号E2024/7/3137（多步）推导（多步）推导/归约归约v012n记为记为0nn(恰用恰用n步步)0+n（至少一步）至少一步）0*n（若干步若干步:零步或多步）零步或多步）vE5id*id+idvid*id+id5Ev(VTVN)*(VTVN)*2024/7/3138再看推导再看推导/归约归约EE+E（1）串中含有变量串中含有变量id+E（4）串中含有变量串中含有变量id+E*E（2）串中含有变量串中含有变量id+id*E（4）串中含有变量串中含有变量id+id*id（4）串中串中没有没有变量变量到此串中已经没有（语法）变量了，不能到此串中已经没有（语法）变量了，不能再推了再推了得到得到句子句子4 Eid4 Eid4 Eid4 Eid5 EE-E 5 EE-E 5 EE-E 5 EE-E 6 EE/E 6 EE/E 6 EE/E 6 EE/E 1 1 1 1 EE+EEE+EEE+EEE+E2 EE*E2 EE*E2 EE*E2 EE*E3 E(E)3 E(E)3 E(E)3 E(E)2024/7/3139句型与句子句型与句子vEE+EE+E*E3id+id*idvE4id+id*Ev定义定义:如果如果S*，(VTVN)*则称则称是是G产产生的一个生的一个句型句型(SententialForm)vE5id+id*idv定义定义:如果如果S*x，且且xVT*，则称则称x是是G产生产生的一个的一个句子句子(Sentence)2024/7/3140文法文法G产生的产生的语言语言定义：定义：L(G)=x|S*x&xVT*文法文法EE+E|E*E|(E)|id可以派生出多少个句子？可以派生出多少个句子？文法文法G的作用的作用语言的有穷描述语言的有穷描述v以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象有限有限:产生式集合、终结符集合、非终结符集合产生式集合、终结符集合、非终结符集合无限：无限：可以导出无穷多个句子可以导出无穷多个句子v（注：（注：L也可是有穷）也可是有穷）2024/7/3141 句子句子主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 the the 形容词形容词 名词名词 谓语谓语 the graythe gray 名词名词 谓语谓语 the gray wolf the gray wolf 谓语谓语 the gray wolf the gray wolf 动词动词 直接宾语直接宾语 the gray wolf the gray wolf 助动词助动词 动词原动词原形形 直接宾语直接宾语 the gray wolf willthe gray wolf will 动词原动词原形形 直接宾语直接宾语 the gray wolf will eat the gray wolf will eat 直接宾语直接宾语 the gray wolf will eat the gray wolf will eat 冠词冠词 名词名词 the gray wolf will eat the the gray wolf will eat the 名词名词 the gray wolf the gray wolf will eat the goatwill eat the goat句子是根据文法推导的结果句子是根据文法推导的结果2024/7/3142 句子句子 the gray wolf the gray wolf will eat the goatwill eat the goatthe gray wolf the gray wolf will eat the will eat the wolfwolf the gray the gray goatgoat will eat the will eat the wolfwolfthe gray the gray goatgoat will eat the goatwill eat the goat符合语义的句子仅是：符合语义的句子仅是：the gray wolf the gray wolf will eat the goatwill eat the goat还可以还可以“得出得出”其他的其他的“句句子子”2024/7/3143id+id*id的不同推导的不同推导EE+E|E*E|(E)|idE E E E E+E E+E E+E E+E id+E id+E id+E id+E id+E*E id+E*E id+E*E id+E*E id+id*E id+id*E id+id*E id+id*E id+id*id id+id*id id+id*id id+id*idE E E E E+E E+E E+E E+E E+E*E E+E*E E+E*E E+E*E E+E*id E+E*id E+E*id E+E*id E+id*idE+id*idE+id*idE+id*id id+id*id id+id*id id+id*id id+id*idE E E E E*E E*E E*E E*E E+E*E E+E*E E+E*E E+E*E E+id*E E+id*E E+id*E E+id*E id+id*E id+id*E id+id*E id+id*E id+id*id id+id*id id+id*id id+id*id不做限制不做限制句型句型句型句型(sentential Form)sentential Form)sentential Form)sentential Form)（归约归约归约归约）施于最右变量施于最右变量右句型右句型右句型右句型/规范句型规范句型规范句型规范句型 (canonical)canonical)canonical)canonical)(最左最左最左最左/规范归约规范归约规范归约规范归约)施于最左变量施于最左变量左句型左句型左句型左句型(left-)left-)left-)left-)（最右归约）最右归约）最右归约）最右归约）E E5 5 id+idid+id*id*id E E E E*id+idid+idid+idid+id*id*id*id*idE E+id+idid+id*id*id2024/7/3144最左推导与最右推导最左推导与最右推导v最左推导最左推导(Left-mostDerivation)每次推导都施加在句型的最左边的语法每次推导都施加在句型的最左边的语法变量上变量上与最右归约对应与最右归约对应v最右推导最右推导(Right-mostDerivation)每次推导都施加在句型的最右边的语法每次推导都施加在句型的最右边的语法变量上变量上与最左归约（规范规约）对应与最左归约（规范规约）对应的规范的规范(Canonical)句型句型2024/7/3145例例2-2标识符的文法标识符的文法1v标识符：字母开头的字母数字串（递归定义）标识符：字母开头的字母数字串（递归定义）v符号符号“化化”：S-标识符，标识符，L-字母，字母，T-尾，尾，N-数字数字vSL|LTTL|N|TL|TNLa|b|c|dletterN0|1|2|3|4|5 digitv?正整数的文法；正实数的文法正整数的文法；正实数的文法2024/7/3146不同类型的文法不同类型的文法SaBCSaSBCCBBCaBdbBbbbCbcCccEE+EEE*EE(E)EidEE-EEE/ESaBCSaSBCCBBCaBabbBbbbCbccCccSa|bSa|bSaT|bTSaT|bTTa|bTa|bT1|2T1|2TaT|bTTaT|bTT1T|2TT1T|2TSa|bSa|bSHa|HbSHa|HbSH1|H2SH1|H2HHa|HbHHa|HbHH1|H2HH1|H2Ha|bHa|b0型文法型文法(PSG)1型文法型文法(CSG)2型文法型文法(CFG)3型文法型文法(RG)3型文法型文法(RG)2024/7/3147编译原理编译原理(Principles of Compiling)n主讲：蒋宗礼主讲：蒋宗礼2024/7/3148上次课主要内容上次课主要内容v文法文法通过刻画语言的结构描述语言通过刻画语言的结构描述语言有穷描述：有穷描述：递归定义递归定义vG=(VT，VN，P，S)2024/7/3149上次课主要内容上次课主要内容v文法的简写：只写产生式集、开始符约定文法的简写：只写产生式集、开始符约定v产生式的简写：产生式的简写：1|2|n（候选式）候选式）v(VTVN)*(VTVN)*直接派生直接派生/归约：归约：AAn步派生步派生/归约：归约：AnAnv句型：句型：S*(VTVN)*v句子：句子：S*xxVT*v语言：语言：L(G)=x|S*xandxVT*2024/7/3150上次课主要内容上次课主要内容v最左推导（最右归约）最左推导（最右归约）v最右推导（最左归约）最右推导（最左归约）规范推导规范推导/归约，规范句型归约，规范句型v文法是分类的文法是分类的2024/7/31512.2.文法的分类文法的分类(Chomsky体系体系)v语言结构的复杂程度（形式语言）语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择涉及文法的复杂程度、分析方法的选择v如果如果G满足文法定义的要求，则满足文法定义的要求，则G是型文是型文法（短语结构文法法（短语结构文法PSG:PhraseStructureGrammar）vL(G)为为PSL2024/7/3152上下文有关文法上下文有关文法(CSG)v除形如除形如的的产生式外产生式外,若若满足满足则则G是型文法是型文法,又叫上下文又叫上下文有关有关文法文法（CSGContextSensitiveGrammar）vL(G)为为1型型/上下文有关上下文有关/敏感语言敏感语言(CSL)2024/7/3153上下文无关文法上下文无关文法(CFG)v若若满足满足VN，(VNVT)*，则则G是型文法，又叫上下文是型文法，又叫上下文无关无关文法文法(CFG:ContextFreeGrammar)vL(G)为为2型型/上下文无关语言（上下文无关语言（CFL）程序设计语言的多数语法特征为上下文无关的程序设计语言的多数语法特征为上下文无关的2024/7/3154例例2-3标识符的文法标识符的文法2vSL|LTTL|N|TL|TNLa|b|c|dN0|1|2|3|4|5n nSa|b|c|dSaT|bT|cT|dTTa|b|c|d|0|1|2|3|4|5TaT|bT|cT|dT|0TT1T|2T|3T|4T|5TCFG右部最多只有一个变右部最多只有一个变量，且都在右边量，且都在右边2024/7/3155例例2-4标识符的文法标识符的文法3Sa|b|c|dSaT|bT|cT|dTTa|b|c|d0|1|2|3|4|5TaT|bT|cT|dT|0TT1T|2T|3T|4T|5TSSa|b|c|da|b|c|dSHa|Hb|Hc|Hd|H0SHa|Hb|Hc|Hd|H0SH1|H2|H3|H4|H5SH1|H2|H3|H4|H5HHa|Hb|Hc|Hd|H0HHa|Hb|Hc|Hd|H0HH1|H2|H3|H4|H5HH1|H2|H3|H4|H5HHa|b|c|da|b|c|dAaB或或AaABa或或Aa右部最多只有一个变右部最多只有一个变量，且都在量，且都在右边右边右部最多只有一个变右部最多只有一个变量，且都在量，且都在左边左边2024/7/3156正规文法正规文法(RG)v设设A、BVN，aVT v右线性右线性(RightLinear)文法：文法：AaB或或Aav左线性左线性(LeftLinear)文法：文法：ABa或或Aav都是型文法都是型文法(正规文法正规文法RegularGrammar-RG)vL(G)为为3型型/正规集正规集/正则集正则集/正则语言（正则语言（RL）程序设计语言的多数词法特性程序设计语言的多数词法特性左、右线性文法混用不是正规文法左、右线性文法混用不是正规文法2024/7/3157例例非非CFL的文法的文法L=anbncn|n0的文法的文法SaBC|aSBCCBBCaBabbBbbbCbccCccn n“可以证明可以证明”不存在不存在CFGG,使使L(G)=L如如下下是是L=anbncn|n0的文法吗？问什么？的文法吗？问什么？SaBC|aSBCCBBCBbCc2024/7/3158在我们使用的程序语言中在我们使用的程序语言中,有些语言结构有些语言结构并不是总能用上下文无关文法描述的。并不是总能用上下文无关文法描述的。例例 L L1 1=wcw|wwcw|wa,ba,b+。例例,aabcaabaabcaab就是就是L L1 1的一个句子。这个语言是检查程序中标识的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。符的声明应先于引用的抽象。例例 L L2 2=a=an nb bm mc cn nd dm m|n|n,m m00，它是检查过程声，它是检查过程声明的形参个数和过程引用的参数个数是否一明的形参个数和过程引用的参数个数是否一致问题的抽象。致问题的抽象。高级语言中的非高级语言中的非CFL结构结构2024/7/3159不同类型的文法不同类型的文法SaBCSaSBCCBBCaBdbBbbbCbcCccEE+EEE*EE(E)EidEE-EEE/ESaBCSaSBCCBBCaBabbBbbbCbccCccSa|bSa|bSaT|bTSaT|bTTa|bTa|bT1|2T1|2TaT|bTTaT|bTT1T|2TT1T|2TSa|bSa|bSHa|HbSHa|HbSH1|H2SH1|H2HHa|HbHHa|HbHH1|H2HH1|H2Ha|bHa|b0型文法型文法(PSG)1型文法型文法(CSG)2型文法型文法(CFG)3型文法型文法(RG)3型文法型文法(RG)TMLBAPDAFAFA2024/7/3160四种文法之间的关系是将产生式作进一步四种文法之间的关系是将产生式作进一步限制而定义的，他们呈逐级限制而定义的，他们呈逐级“包含包含”关系关系Chomsky体系体系总结总结0 0型文法型文法1 1型文法型文法 2 2型文法型文法3 3型文法型文法 .2024/7/3161范式范式Backus-NaurFormBackus-NormalFormv表示为表示为 v非终结符用非终结符用“”括起来括起来v终结符：基本符号集终结符：基本符号集v其他其他(1|2|n)1|2|n1|2|nul1|2|nml=0,u=m|2024/7/3162范式范式BackusNormalFormv例例简单算术表达式简单算术表达式+*()idv即：即：+|*|()|idv哪些是终结符？哪些是变量？哪些是终结符？哪些是变量？2024/7/3163例例2-5句子结构的表示句子结构的表示(文法文法EE+E|E*E|(E)|id）E EE E E E+E E E EE E E EE+EE+EididididE E E Ei id dE E E EE E E E*E E E EE*EE*EididididE E E Ei id dididididE E E EididE E E EE+EE+E一棵树！一棵树！id+Eid+E id+Eid+E*E E E E id+idid+id*E E E E id+id*idid+id*id2024/7/31642.5CFG的语法树的语法树语语法法树树(ParseTree，语语法法分分析析树树，分分析析树树)v用树的形式表示句型的结构用树的形式表示句型的结构用用VNVT中的符号标记结点中的符号标记结点,标记标记时为独子时为独子树根：开始符号；中间结点：非终结符树根：开始符号；中间结点：非终结符如果一个如果一个中间结点中间结点v v标记为标记为A A，v v的儿子从的儿子从左到右依次为左到右依次为v v1 1，v v2 2，v vn n，并且它，并且它们分别标记为们分别标记为X X1 1，X X2 2，X Xn n，则，则A AX X1 1X X2 2X Xn nPP2024/7/31652.5CFG的语法树的语法树设有文法设有文法G G的一棵语的一棵语法树法树T T，T T的所有叶的所有叶子顶点从左到右依子顶点从左到右依次标记为次标记为X X1 1，X X2 2，X Xn n则称符号串则称符号串X X1 1X X2 2X Xn n是是T T的结果的结果(Yield)(Yield)AT:A1AnBX1X2AA1A2An Xn-1CXnCXn-1Xn 表示句型表示句型X X1 1X X2 2X Xn n的结构的结构2024/7/31662.5CFG的语法树的语法树文法文法G G的一棵语法子的一棵语法子树的树的“结果结果”表示一表示一个句型中某一部分的个句型中某一部分的结构结构 子结构子结构AT:A1AnBY1Y2Ym-1CYm子树子树B B表示其表示其“结果结果”Y Y1 1Y Y2 2Y Ym m的结构。的结构。Y Y1 1Y Y2 2Y Ym m称为称为短语短语(Phrase)2024/7/3167例例2-6语法语法(分析分析)树树(文法文法EE+E|E*E|(E)|id）E EE E E E+E E E Ea a1 1E EE E E EE E E E*a a2 2a a3 3短语短语一棵一棵子树的叶子！子树的叶子！E E*直接短语直接短语句柄句柄(Handle)a1，a2，a3，a1*E，a2*a3，a1*E+a2*a32024/7/3168短语短语(Phrase)v如果如果S*&A则称则称是句型是句型的相对于变量的相对于变量A的的直接短语直接短语v最左直接短语叫做最左直接短语叫做句柄句柄(Handle)v如果如果S*A&A+，则称则称是句型是句型的相的相对于变量对于变量A的的短语短语2024/7/3169例：短语、直接短语、句柄例：短语、直接短语、句柄EE+TT+TF+T(E)+T(E+T)+T(E+T)+TE+T)+T(T+T)+T(T+T)+T(F+T)+T(F+T)+T(a+T)+T(a+T)+T(a+T*F)+T(a+T*F)+T(a+F*F)+T(a+F*F)+T(a+b*F)+T(a+b*F)+TEE+T|T EE+T|T EE+T|T EE+T|T TT*F|F TT*F|F TT*F|F TT*F|F F(E)|idF(E)|idF(E)|idF(E)|ida，b，b*F，a+b*F，(a+b*F)，(a+b*F)+T?(a+ba+b*c)+Tc)+T(a+ba+b*c)+Fc)+F(a+ba+b*c)+dc)+d2024/7/3170EE+TT+TF+Ta1+Ta1+T*Fa1+F*Fa1+a2*FE+TT,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*Fa1,a2,a1+a2*F,a2*Fa1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语短语a a1 1+a a2 2*a*a3 32024/7/3171短语：子树的结果是相对于子树根的短语短语：子树的结果是相对于子树根的短语直接短语：仅有父子两代的子树的结果直接短语：仅有父子两代的子树的结果句柄：一个句型的分析树中最左那棵只有句柄：一个句型的分析树中最左那棵只有父子两代的子树的结果父子两代的子树的结果用子树解释短语，直接短语，句柄用子树解释短语，直接短语，句柄2024/7/31721.描述一个句子的文法不是唯一的（标识符描述一个句子的文法不是唯一的（标识符的文法）；的文法）；2.对于一个句子的分析应是唯一的，但是，对于一个句子的分析应是唯一的，但是，有的时候存在问题。有的时候存在问题。考虑表达式下面的文法考虑表达式下面的文法GE,其产生式如下：其产生式如下：EE+E E*E(E)id关于文法关于文法2024/7/3173文法的二义性文法的二义性(歧义性歧义性/ambiquityambiquity)E E E EE E E E*E E E EididididE E E EE E E E+ididididididididE E E EE E E E+E E E EE E E EE E E Eidididid*ididididididididv一个句子有两棵不同的语法树一个句子有两棵不同的语法树2024/7/3174EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3 EE*EE+E*Ea1+E*Ea1+a2*Ea1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3两个不同的两个不同的最左最左推导推导,对应两不同的语法树对应两不同的语法树2024/7/3175EE*EE*a3E+E*a3E+a2*a3a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3两个不同的两个不同的最右最右推导推导,对应两不同的语法树对应两不同的语法树EE+EE+E*EE+E*a3E+a2*a3a1+a2*a32024/7/3176如果一个文法的句子存在两棵分析树如果一个文法的句子存在两棵分析树,那么那么,该句子是二义性的该句子是二义性的如果一个文法包含二义性的句子如果一个文法包含二义性的句子,则称这个则称这个文法是二义性的文法是二义性的;否则，该否则，该文法是无二义性的文法是无二义性的文法的二义性文法的二义性2024/7/3177文法的二义性文法的二义性(1)(1)一般来说一般来说,高级程序设计语言存在无二义高级程序设计语言存在无二义性文法性文法,但有时用二义性文法。如：表达式文但有时用二义性文法。如：表达式文法、条件语句文法法、条件语句文法v EE+E|E-E|E*E|E/E|(E)|idEE+E|E-E|E*E|E/E|(E)|idvS S if if exprexpr then S then S if if exprexpr then S else then S else S S other other二义性的句子二义性的句子:if eif e1 1 then if e then if e2 2 then then s s1 1 else s else s2 2 2024/7/3178文法的二义性文法的二义性(2)(2)对于任意一个对于任意一个CFGCFG，不存在算法判定它是无，不存在算法判定它是无二义性的；但能给出一组充分条件，满足这二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的组充分条件的文法是无二义性的v一个文法是否为二义性的一个文法是否为二义性的不可判定不可判定2024/7/3179文法的二义性文法的二义性(3)(3)存在先天二义性语言。例如，语言存在先天二义性语言。例如，语言 a ai ib bi ic cj j i,ji,j 1 1 a ai ib bj jc cj j i,ji,j 1 1 存在二义性的句子存在二义性的句子a ak kb bk kc ck kv一个语言是否为先天二义性的，一个语言是否为先天二义性的，在理论上不在理论上不可判定可判定2024/7/3180文法的二义性文法的二义性(4)(4)在能驾驭的情况下，使用在能驾驭的情况下，使用二义性文法二义性文法简单简单vvEE+E|E-E|E*E|E/E|(E)|idEE+E|E-E|E*E|E/E|(E)|idvv无二义性文法较复杂无二义性文法较复杂EE+T|E-T|T EE+T|E-T|T EE+T|E-T|T EE+T|E-T|T TT*F|T/F|F TT*F|T/F|F TT*F|T/F|F TT*F|T/F|F F(E)|idF(E)|idF(E)|idF(E)|id2024/7/3181参考书：参考书：(抽象抽象)语法树不同语法树不同(语法语法语法语法)分析树分析树分析树分析树EE+idE+EEidid(抽象抽象抽象抽象)语法树语法树语法树语法树+id+idid2024/7/31822.6文法的构造文法的构造为了更好地理解文法为了更好地理解文法v目的：给出语言的有穷描述目的：给出语言的有穷描述v途径：刻画语言的结构途径：刻画语言的结构v做法：做法：研究语言句子的结构特点研究语言句子的结构特点用符号代表一些子结构用符号代表一些子结构给出定义的形式化描述给出定义的形式化描述根据经验给出描述根据经验给出描述2024/7/3183文法举例文法举例vx|x是长度为偶数的是长度为偶数的0、1串串RLS00S|01S|10S|11S|v0m1n|m,n1RLS0S|0AA1A|1v0n1n|n1CFLS0S1|01vww|wa,b+PSLSaCAE|bCBE AaaAAbbAAEaREREDaRRabRRbCRaCA|bCBBaaBBbbBBEbREaRRabRRbaDDabDDbCD2024/7/3184例例2-7：w|w为十进制数为十进制数R N|N.DN1|2|3|4|5|6|7|8|9NN0|N1|N2|N3|N4|N5|N6|N7|N8|N9D1|2|3|4|5|6|7|8|9D0D|1D|2D|3D|4D|5D|6D|7D|8D|9DR0|0.D|N.0|0.02024/7/3185无用产生式与无用符号无用产生式与无用符号E T|E+T|E-TT F|T*F|T/FF(E)|idEE|H+TT FH|TQ+PF|EQFM(E)|id单单一一产产生生式式、派派生生不不出出终终极极符符号号行行(H、Q、P)、从开始符号无法派生出来从开始符号无法派生出来(M)2024/7/3186文法构造小结文法构造小结v明确描述对象明确描述对象语言语言合法的语言结构合法的语言结构v确定基本符号集确定基本符号集VTv引入非终结符引入非终结符VT各种句子结构各种句子结构v定义句子的组成规则定义句子的组成规则BNF范式或产生式范式或产生式2024/7/3187值得注意的问题值得注意的问题v文法描述文法描述描述句子的组成规则，不涉及语义描述句子的组成规则，不涉及语义文法正确不能保证语义正确（例）文法正确不能保证语义正确（例）v明确目标明确目标要描述语言的结构要描述语言的结构确认基本符号集确认基本符号集合理引入非终结符（语义明确）合理引入非终结符（语义明确）2024/7/3188本章小结：本章小结：v几个基本概念几个基本概念v文文法法是是语语言言的的一一种种有有穷穷描描述述，它它严严格格、准确、简洁。准确、简洁。v文法的形式定义文法的形式定义v句型、句子、语言句型、句子、语言v文法的分类文法的分类v的语法树的语法树2024/7/3189习题习题v1)给定文法如下：给定文法如下：E T|E+T|E-TT F|T*F|T/FF(E)|id画出表达式画出表达式id*(id+id)+id的分析树的分析树v2)判判断断上上题题的的文文法法属属于于哪哪个个类类型型的的文文法法？为为什么？什么？vP36练习练习68v阅读阅读P12-242024/7/31900 0型文法型文法1 1型文法型文法上次课主要内容上次课主要内容vChomsky体系体系PSG(PSL)：CSG(CSL)：|CFG(CFL)：NRG（RL）v右线性：右线性：AaB或或Aav左线性：左线性：ABa或或Aa2 2型文法型文法3 3型文法型文法2024/7/3191上次课主要内容上次课主要内容vBackus-NaurFormv文法的构造、文法的等价文法的构造、文法的等价vCFG的语法树的语法树语法树：语法树的结果是句型语法树：语法树的结果是句型语法子树：非单一结点的语法子树的结果是短语、语法子树：非单一结点的语法子树的结果是短语、简单短语、句柄简单短语、句柄v文法的二义性文法的二义性2024/7/3192
展开阅读全文