高级语言及其文法.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。,2.4.1文法与语言的分类,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|LT T L|N|TL|TN L a|b|c|d N 0|1|2|3|4|5,S a|b|c|d S aT|bT|cT|dT T a|b|c|d|0|1|2|3|4|5 T aT|bT|cT|dT|0T T 1T|2T|3T|4T|5T,例2-4 标识符的文法3,S a|b|c|d S aT|bT|cT|dT T a|b|c|d T 0|1|2|3|4|5 T aT|bT|cT|dT|0T T 1T|2T|3T|4T|5T,S a|b|c|d S Ha|Hb|Hc|Hd|H0 S H1|H2|H3|H4|H5 H Ha|Hb|Hc|Hd|H0 H H1|H2|H3|H4|H5 H 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|aSBC CBBC aBab bBbb bCbc cC 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 Form Backus-Normal Form,表示为 非终结符用“”括起来 终结符：基本符号集 其他 (1|2|n)1|2|n 1|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+E a1+E*E a1+a2*E a1+a2*a3,E E*E E+E*E a1+E*E a1+a2*E a1+a2*a3,E,E,两个不同的最左推导,对应两不同的语法树,E E*E E*a3 E+E*a3 E+a2*a3 a1+a2 *a3,E,E,两个不同的最右推导,对应两不同的语法树,EE+E E+E*E E+E*a3 E+a2*a3 a1+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串 RL S00S|01S|10S|11S| 0 m 1 n |m,n 1 RL S0S|0A A1A|1 0 n 1 n |n 1 CFL S0S1|01,例2-7：w|w为十进制数,R N|N.D N 1|2|3|4|5|6|7|8|9 N N0|N1|N2|N3|N4|N5|N6|N7|N8|N9 D 1|2|3|4|5|6|7|8|9 D 0D|1D|2D|3D|4D|5D|6D|7D|8D|9D,R 0|0.D|N.0|0.0,无用产生式与无用符号,E T | E + T | E - T T F | T * F | T / F F ( E ) | id E E | H + T T FH | TQ+PF | EQF M ( E ) | id 单一产生式、派生不出终极符号行(H、Q、P)、从开始符号无法派生出来(M),文法构造小结,明确描述对象语言 合法的语言结构 确定基本符号集