高级语言及其文法.ppt-得力文库

资源描述

《高级语言及其文法.ppt》由会员分享，可在线阅读，更多相关《高级语言及其文法.ppt（36页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第2章章高级语言高级语言及其文法（及其文法（3）本章主要内容本章主要内容n n2.1 2.1 语言概述语言概述n n2.2 2.2 基本定义基本定义(语言、句子、形式化方法、语言、句子、形式化方法、串、字母表、串的连接与幂、产生式串、字母表、串的连接与幂、产生式)n n2.3 2.3 文法文法(Grammar)(Grammar)的定义的定义n n2.4 CFG2.4 CFG的语法的语法(分析分析)树树(Parse Tree)(Parse Tree)n n2.5 2.5 文法的分类文法的分类n n2.6 2.6 文法的构造文法的构造2.2.文法的分类文法的分类(Chomsky体系体系)n语言结

2、构的复杂程度（形式语言）语言结构的复杂程度（形式语言）n涉及文法的复杂程度、分析方法的选择涉及文法的复杂程度、分析方法的选择n如果如果G满足文法定义的要求，则是满足文法定义的要求，则是型文法（短语结构文法型文法（短语结构文法PSG:PhraseStructureGrammar）。）。nL(G)为为PSL。文法与语言的分类文法与语言的分类0 0型文法（或称短语文法）型文法（或称短语文法）特点：特点：产产生式行如生式行如，(VN VT)*且至且至少包含一个非终结符，而少包含一个非终结符，而 0 0型文法又称型文法又称为为无限制文法，有无限制文法，有时时也称也称为为短短语语文法（文法（phase s

3、tructure grammar,PSGphase structure grammar,PSG）。）。0 0型文法型文法对应对应的的语语言称言称为为0 0型型语语言或称言或称递归递归可可枚枚举举集，它集，它们们的的识别识别系系统为图统为图灵机（灵机（TuringTuring机）。机）。1 1型文法（或称上下文有关文法）型文法（或称上下文有关文法）特点：限制特点：限制P P中的每个中的每个产产生式生式都要都要满满足足|。1 1型文法相型文法相对应对应的的语语言称言称为为1 1型型语语言或上下文言或上下文有关有关语语言，它的言，它的识别识别系系统统是是线线性界限自性界限自动动机。机。1 1型文法的

4、另一种定义方法是文法型文法的另一种定义方法是文法G(S)G(S)的每一的每一个产生式具有下列形式：个产生式具有下列形式：另一定义：另一定义：2 2型文法（或称上下文无关文法）型文法（或称上下文无关文法）特点：每个特点：每个产产生式的形式限制生式的形式限制为为A A，其中，其中A A为单为单个非个非终结终结符，符，2 2型文法相型文法相对应对应的的语语言称言称为为2 2型型语语言或上下文言或上下文无关无关语语言，它的言，它的识别识别系系统为统为下推自下推自动动机机(PDA)(PDA)。3 3型文法（或称正规文法、正则文法）型文法（或称正规文法、正则文法）特点：文法中每个特点：文法中每个产产生式的

5、形式生式的形式为为 AaBAaB或或AaAa，其中，其中A A、BVBVNN，A A、B B、a a都是都是单单个符号。个符号。3 3型文法型文法对应对应的的语语言称言称为为3 3型型语语言或正言或正规语规语言言（正（正则语则语言，或正言，或正则则集）。集）。例例2-3标识符的文法标识符的文法2nSL|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|5T例例2-4标识符的文法标识符的文法3Sa|b|c|dSa|b|c|dSaT|bT|cT

6、|dTSaT|bT|cT|dTTa|b|c|dTa|b|c|dT0|1|2|3|4|5T0|1|2|3|4|5TaT|bT|cT|dT|0TTaT|bT|cT|dT|0TT1T|2T|3T|4T|5TT1T|2T|3T|4T|5TSa|b|c|dSa|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|H5Ha|b|c|dHa|b|c|dAaB或或AaABa或或Aa正规文法正规文法(RG)n设设A、BV

7、N，aVT n右线性右线性(RightLinear)文法：文法：AaB或或Aan左线性左线性(LeftLinear)文法：文法：ABa或或Aan都是型文法都是型文法(正规文法正规文法RegularGrammar-RG)nL(G)为为3型型/正规集正规集/正则集正则集/正则语言（正则语言（RL）n例：程序设计语言的多数词法特性例：程序设计语言的多数词法特性n左、右线性文法不可混用左、右线性文法不可混用例例非非CFL的文法的文法L=anbncn|n0的文法的文法SaBC|aSBCCBBCaBabbBbbbCbccCccn n“可以证明可以证明”不存在不存在CFGG,使使L(G)=L在我们使用的程序

8、语言中在我们使用的程序语言中,有些语言结构并有些语言结构并不是总能用上下文无关文法描述的。不是总能用上下文无关文法描述的。例例 L L1 1=wcw|wa,b=wcw|wa,b+。例。例,aabcaab,aabcaab就是就是L L1 1的一个句子。这个语言是检查程序中标识符的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。的声明应先于引用的抽象。例例 L L2 2=a=an nb bmmc cn nd dmm|n,m0|n,m0，它是检查过程，它是检查过程声明的形参个数和过程引用的参数个数是否声明的形参个数和过程引用的参数个数是否一致问题的抽象。一致问题的抽象。高级语言中的非高级

10、，N，)是一个文法是一个文法,P*G是是0型文法，型文法，L(G)是是0型语言；型语言；-其能力相当于图灵机其能力相当于图灵机(TM)*|:G是是1型文法，型文法，L(G)是是1型语言型语言(除除);-其识别系统是线性界限自动机其识别系统是线性界限自动机(LBA)*N:G是是2型文法，型文法，L(G)是是2型语言型语言;-其识别系统是不确定的下推自动机其识别系统是不确定的下推自动机(PDA)*AaB或或Aa:G是右线性文法，是右线性文法，L(G)是是3型语言型语言ABa或或A:G是左线性文法，是左线性文法，L(G)是是3型语言型语言-其识别系统是有穷自动机其识别系统是有穷自动机(FA)四种文法

11、之间的关系是将产生式作进一步限制而定义的四种文法之间的关系是将产生式作进一步限制而定义的四种文法之间的逐级四种文法之间的逐级“包含包含”关系如下：关系如下：2型文法型文法1型文法型文法0型文法型文法3型文法型文法Chomsky体系体系总结总结范式范式Backus-NaurFormBackus-NormalFormn表示为表示为 n非终结符用非终结符用“”括起来括起来n终结符：基本符号集终结符：基本符号集n其他其他n(1|2|n)1|2|nn1|2|null=0,u=mn1|2|nmn|n范式范式BackusNormalFormn例例简单算术表达式简单算术表达式(只写产生式只写产生式)n+n*n

12、()n idn即：即：+|*|()|idn哪些是终结符？哪些是变量？哪些是终结符？哪些是变量？例例2-5句子结构的表示句子结构的表示(文法文法EE+E|E*E|(E)|id）E EE E E E+E E E EE E E EE+EE+EididididE E E Eiid dE E E EE E E E*E E E EE*EE*EididididE E E Eiid dididididE E E EididE E E EE+EE+Eid+Eid+Eid+E*id+E*E E E Eid+id*id+id*E E E Eid+id*idid+id*id一棵树！一棵树！1.描述一个句子的文法不是唯

13、一的；描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。对于一个句子的分析应是唯一的。考虑表达式下面的文法考虑表达式下面的文法GE,其产生式如下：其产生式如下：EE+E E*E(E)id文法的二义性文法的二义性(歧义性歧义性/ambiquity)/ambiquity)文法的二义性文法的二义性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*ididididididididn一个句子有两棵不同的语法树一个句子有两棵不同的语

14、法树EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3 EE*EE+E*Ea1+E*Ea1+a2*Ea1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3两个不同的最左推导两个不同的最左推导,对应两不同的语法树对应两不同的语法树EE*EE*a3E+E*a3E+a2*a3a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3两个不同的最右推导两个不同的最右推导,对应两不同的语法树对应两不同的语法树EE+EE+E*EE+E*a3E+a2*a3a1+a2*a3如果一个文法的句子存在两棵分析树如果一个文法的句子存在两棵分析树,那么那么,该句子是二义性的该句子是二义性

15、的如果一个文法包含二义性的句子如果一个文法包含二义性的句子,则称这个则称这个文法是二义性的文法是二义性的;否则，该文法是无二义性否则，该文法是无二义性的的文法的二义性文法的二义性1.一般来说一般来说,高级程序设计语言存在无二义性文法高级程序设计语言存在无二义性文法,但但有时用二义性文法。如：表达式文法、条件语句文法有时用二义性文法。如：表达式文法、条件语句文法S if expr then S if expr then S else S other二义性的句子二义性的句子:if e1 then if e2 then s1 else s2 E EE+E|E-E|E*E|E/E|(E)|idE+E|

16、E-E|E*E|E/E|(E)|id 无二义性文法较复杂无二义性文法较复杂无二义性文法较复杂无二义性文法较复杂 E EE+T|E-T|T E+T|E-T|T T TT*F|T/F|F T*F|T/F|F F F(E)|id(E)|id文法的二义性文法的二义性文法的二义性文法的二义性n1.1.一般来说一般来说,高级程序设计语言存在无二义性高级程序设计语言存在无二义性文法文法,但有时用二义性文法。如：表达式文法、但有时用二义性文法。如：表达式文法、条件语句文法条件语句文法nS S if expr then S if expr then S if expr then S else S|otherif

17、 expr then S else S|othern二义性的句子二义性的句子:if e:if e1 1 then if e then if e2 2 then s then s1 1 else s else s2 2 文法的二义性文法的二义性2.2.对于任意一个对于任意一个CFGCFG，不存在算法判定它，不存在算法判定它是无二义性的；但能给出一组充分条件，是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的满足这组充分条件的文法是无二义性的n一个文法是否为二义性的不可判定一个文法是否为二义性的不可判定文法的二义性文法的二义性3.3.存在先天二义性语言。例如，语言存在先天二义性

18、语言。例如，语言 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 kn一个语言是否为先天二义性的，在理论一个语言是否为先天二义性的，在理论上不可判定上不可判定文法的二义性文法的二义性n4.4.在能驾驭的情况下，使用二义性文法在能驾驭的情况下，使用二义性文法简单简单n nEE+E|E-E|E*E|E/E|(E)|idEE+E|E-E|E*E|E/E|(E)|idn n无二义性文法较复杂无二义性文法较复杂n nEE+T|E-T|T EE+T|E-T|T EE+T

19、|E-T|T EE+T|E-T|T n nTT*F|T/F|F TT*F|T/F|F TT*F|T/F|F TT*F|T/F|F n nF(E)|idF(E)|idF(E)|idF(E)|id参考书：参考书：(抽象抽象)语法树不同语法树不同(语法语法语法语法)分析树分析树分析树分析树EE+idE+EEidid(抽象抽象抽象抽象)语法树语法树语法树语法树+id+idid2.6文法的构造文法的构造为了更好地理解文法为了更好地理解文法n目的：给出语言的有穷描述目的：给出语言的有穷描述n途径：刻画语言的结构途径：刻画语言的结构n做法：做法：n给出定义的形式化描述给出定义的形式化描述n根据经验给出描述根

20、据经验给出描述文法举例文法举例nx|x是长度为偶数的是长度为偶数的0、1串串 RLS00S|01S|10S|11S|n0m1n|m,n1RLS0S|0AA1A|1n0n1n|n1CFLS0S1|01例例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.0无用产生式与无用符号无用产生式与无用符号E T|E+T|E-TT F|T*F|T/FF(E)|idEE|H+TT FH|TQ+PF

21、|EQFM(E)|id单单一一产产生生式式、派派生生不不出出终终极极符符号号行行(H、Q、P)、从开始符号无法派生出来从开始符号无法派生出来(M)文法构造小结文法构造小结n明确描述对象明确描述对象语言语言n合法的语言结构合法的语言结构n确定基本符号集确定基本符号集VTn引入非终结符引入非终结符n各种句子结构各种句子结构n定义句子的组成规则定义句子的组成规则nBNF范式或产生式范式或产生式值得注意的问题值得注意的问题n文法描述文法描述n描述句子的组成规则，不涉及语义描述句子的组成规则，不涉及语义n文法正确不能保证语义正确（例）文法正确不能保证语义正确（例）n明确目标明确目标n要描述语言的结构要描述语言的结构n确认基本符号集确认基本符号集n合理引入非终结符（语义明确）合理引入非终结符（语义明确）本章小结：本章小结：n几个基本概念几个基本概念n文文法法是是语语言言的的一一种种有有穷穷描描述述，它它严严格格、准确、简洁。准确、简洁。n文法的形式定义文法的形式定义n句型、句子、语言句型、句子、语言n文法的分类文法的分类n的语法树的语法树

展开阅读全文