高级语言及其文法.ppt
第2章 高级语言及其文法（3）,本章主要内容,2.1 语言概述2.2 基本定义(语言、句子、形式化方法、串、字母表、串的连接与幂、产生式)2.3 文法(Grammar)的定义2.4 CFG的语法(分析)树(Parse Tree)2.5 文法的分类2.6 文法的构造,2.文法的分类(Chomsky体系),语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择如果G满足文法定义的要求，则是型文法（短语结构文法PSG:Phrase Structure Grammar）。L(G)为PSL。,文法与语言的分类,0型文法（或称短语文法）,特点：产生式行如，(VNVT)*且至少包含一个非终结符，而,0型文法又称为无限制文法，有时也称为短语文法（phase structure grammar,PSG）。0型文法对应的语言称为0型语言或称递归可枚举集，它们的识别系统为图灵机（Turing机）。,1型文法（或称上下文有关文法）,特点：限制P中的每个产生式都要满足|。,1型文法相对应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。,1型文法的另一种定义方法是文法G(S)的每一个产生式具有下列形式：,另一定义：,2型文法（或称上下文无关文法）,特点：每个产生式的形式限制为A，其中A为单个非终结符，,2型文法相对应的语言称为2型语言或上下文无关语言，它的识别系统为下推自动机(PDA)。,3型文法（或称正规文法、正则文法）,特点：文法中每个产生式的形式为,AaB或,Aa，其中A、BVN，,A、B、a都是单,个符号。,3型文法对应的语言称为3型语言或正规语言（正则语言，或正则集）。,例2-3 标识符的文法2,S L|LTT L|N|TL|TN L a|b|c|dN 0|1|2|3|4|5,S a|b|c|dS aT|bT|cT|dTT a|b|c|d|0|1|2|3|4|5T aT|bT|cT|dT|0TT 1T|2T|3T|4T|5T,例2-4 标识符的文法3,S a|b|c|dS aT|bT|cT|dTT a|b|c|dT 0|1|2|3|4|5T aT|bT|cT|dT|0TT 1T|2T|3T|4T|5T,S a|b|c|dS Ha|Hb|Hc|Hd|H0S H1|H2|H3|H4|H5 H Ha|Hb|Hc|Hd|H0H H1|H2|H3|H4|H5H a|b|c|d,正规文法(RG),设A、BVN，aVT 右线性(Right Linear)文法：AaB或Aa左线性(Left Linear)文法：ABa或Aa都是型文法(正规文法 Regular Grammar-RG)L(G)为3型/正规集/正则集/正则语言（RL）例：程序设计语言的多数词法特性左、右线性文法不可混用,例 非CFL的文法,L=anbncn|n0的文法SaBC|aSBCCBBCaBabbBbbbCbccC cc,“可以证明”不存在CFG G,使L(G)=L,在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。例 L1=wcw|wa,b+。例,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。例 L2=anbmcndm|n,m0，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。,高级语言中的非CFL结构,Chomsky体系总结,Chomsky体系总结,=(T，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),四种文法之间的关系是将产生式作进一步限制而定义的四种文法之间的逐级“包含”关系如下：,Chomsky体系总结,范式Backus-Naur FormBackus-Normal Form,表示为非终结符用“”括起来终结符：基本符号集其他(1|2|n)1|2|n1|2|n ul l=0,u=m 1|2|nm|,范式Backus Normal Form,例 简单算术表达式(只写产生式)+*()id即：+|*|()|id哪些是终结符？哪些是变量？,例2-5 句子结构的表示(文法EE+E|E*E|(E)|id）,EE+Eid+Eid+E*Eid+id*Eid+id*id,一棵树！,1.描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。考虑表达式下面的文法 GE,其产生式如下：EE+EE*E(E)id,文法的二义性(歧义性/ambiquity),文法的二义性,一个句子有两棵不同的语法树,EE+E a1+Ea1+E*Ea1+a2*Ea1+a2*a3,E E*EE+E*E a1+E*Ea1+a2*E a1+a2*a3,E,E,两个不同的最左推导,对应两不同的语法树,E E*EE*a3 E+E*a3E+a2*a3a1+a2*a3,E,E,两个不同的最右推导,对应两不同的语法树,EE+EE+E*E E+E*a3E+a2*a3a1+a2*a3,如果一个文法的句子存在两棵分析树,那么,该句子是二义性的如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的,文法的二义性,1.一般来说,高级程序设计语言存在无二义性文法,但有时用二义性文法。如：表达式文法、条件语句文法S if expr then S if expr then S else S other二义性的句子:if e1 then if e2 then s1 else s2 EE+E|E-E|E*E|E/E|(E)|id无二义性文法较复杂EE+T|E-T|T TT*F|T/F|F F(E)|id,文法的二义性,文法的二义性,1.一般来说,高级程序设计语言存在无二义性文法,但有时用二义性文法。如：表达式文法、条件语句文法S if expr then S if expr then S else S|other二义性的句子:if e1 then if e2 then s1 else s2,文法的二义性,2.对于任意一个CFG，不存在算法判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的一个文法是否为二义性的不可判定,文法的二义性,3.存在先天二义性语言。例如，语言 aibicji,j1 aibjcji,j1存在二义性的句子akbkck一个语言是否为先天二义性的，在理论上不可判定,文法的二义性,4.在能驾驭的情况下，使用二义性文法简单EE+E|E-E|E*E|E/E|(E)|id无二义性文法较复杂EE+T|E-T|T TT*F|T/F|F F(E)|id,参考书：(抽象)语法树不同,2.6 文法的构造为了更好地理解文法,目的：给出语言的有穷描述途径：刻画语言的结构做法：给出定义的形式化描述根据经验给出描述,文法举例,x|x是长度为偶数的0、1串 RLS00S|01S|10S|11S|0 m 1 n|m,n 1RLS0S|0AA1A|10 n 1 n|n 1CFLS0S1|01,例2-7：w|w为十进制数,R N|N.DN 1|2|3|4|5|6|7|8|9N N0|N1|N2|N3|N4|N5|N6|N7|N8|N9D 1|2|3|4|5|6|7|8|9D 0D|1D|2D|3D|4D|5D|6D|7D|8D|9D,R 0|0.D|N.0|0.0,无用产生式与无用符号,E T|E+T|E-TT F|T*F|T/FF(E)|idE E|H+TT FH|TQ+PF|EQFM(E)|id单一产生式、派生不出终极符号行(H、Q、P)、从开始符号无法派生出来(M),文法构造小结,明确描述对象语言合法的语言结构确定基本符号集VT引入非终结符各种句子结构定义句子的组成规则BNF范式或产生式,值得注意的问题,文法描述描述句子的组成规则，不涉及语义文法正确不能保证语义正确（例）明确目标要描述语言的结构确认基本符号集合理引入非终结符（语义明确）,本章小结：,几个基本概念文法是语言的一种有穷描述，它严格、准确、简洁。文法的形式定义句型、句子、语言文法的分类的语法树,
