ch3-new文法和语言.ppt

第三章 文法和语言 一个程序设计语言是一个记号系统，它的完整定义包括两个方面： 语法是指一组规则，应用这组规则可以形成和产生一个合适的 程序。通常用上下文无关文法作为描述语法的工具. 语义：程序设计语言的语义分为两种： 1）静态语义是一系列限定规则，并确定哪些合乎语法 的程序是合适的； 2）动态语义（运行语义或执行语义）表明程序要做什 么，要计算什么. 主要内容： 文法和语言、上下文无关文法、句型分析等 1 3.1 文法的直观概念 文法的直观认识： 如何给出语言的有穷表示？ 语言是由句子组成的，因此，可以用一些规则说明或定义句子的 组成结构。 例如：我是大学生 := :=| :=我|你|他 :=王明|大学生|工人|英语 := :=是|学习 := 这些规则成为判别句 子结构合法与否的依 据.这些规则看成是一 种元语言，这样的语 言描述称为文法. 2 应用规则推导句子： = = =我 =我 =我是 =我是 =我是大学生 “=”的含义是使用一条规则代替 =左边的某个符号并产生=右端 的符号串. 应用这些规则可以产生很多句子.这样，使用文法作为工具，不仅定 义了句子的结构，而且通过有穷的规则描述出语言的全部句子. 3 字母表是元素的非空有穷集合 字母表中至少包含一个元素。 字母表中的元素，可以是字母、数字或其他符号。 3.2 符号和符号串 一.字母表 alphabet 【例如】 = a,b,c 是字母表，由a,b,c三个元素组成。 【例如】 = 0,1 是字母表，由0,1两个元素组成。 不同的语言有不同的字母表。 英文的字母表是26个字母、数字和标点符号的集合； C语言的字母表是字母、数字和若干专用符号组成。 任何语言的字母 表指出了该语言 中允许出现的一 切符号。 4 二.符号（字符）symbol 字母表中的元素称为符号，或称为字符。 【例如】 = a,b,c a,b,c是字母表中的符号。 【例如】 = 0,1 0,1是字母表中的符号。 5 三.符号串（字）string 符号的有穷序列称为字符串。 【例如】设有字母表 = a,b,c， 则有符号串 a,b,ab,ba,cba,abc, (a,b,ab,ba,cba,abc等都是字母表上的符号串) 符号串总是建立在某个特定字母表上的且只能由字母表上 的有穷有穷多个符号组成。 符号串中符号的顺序是很重要的， 如 ab 和 ba 是字母表上的两个不同的符号串。 不包含任何符号的符号串，称为空符号串，用 (epsilon)表示，即空符号串由 0 个符号组成，其长度 |=0 6 r符号串的头尾：如果zxy是一符号串，那么x 是z的头，y是z的尾。 如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固 有头。 r符号串集合：若集合A中的一切元素都是某字母 表上的符号串，则称A为该字母表上的符号串集 合。 四.符号串的运算相关概念 例如: zabc，那么z的头是, a, ab, abc. Z的尾是, c, bc, abc. 7 四.符号串的运算 1.符号串的连接 connection 设 x 和 y 是符号串，则串 xy 称为它们的连接。即 xy 是将 y 符号串写在 x 符号串之后得到的符号串。 【例如】设 x abc，y = 10a， 则 xy abc10a 则 yx 10aabc 特别，对任意一符号串 x 有： x x x 8 2.符号串的幂运算 power 设 x 是符号串，则 x 的幂运算定义为： x0 x1 x x2 xx xn xxx = xxn-1 (n0) n 【例如】设 x = abc,则 x0 x1 abc x2 abcabc 9 3.集合的乘积 product 设 A 和 B 是符号串的集合，则 A 和 B 的乘积定义为： AB = xy | x A, y B 即集合 AB 中的符号串是由 A 和 B 的符号串连接而成的 。 【例如】设 A = a,b,B = c,d 则 AB ac,ad,bc,bd 因为对任意一符号串 x 有： x x x 所以，对任意集合 A，有 A = A = A 10 空集 empty set 表示不含任何元素的空集 = 注意： 是符号串，不是集合，表示由空符号串 所组成的集合，但这样的集合不是空集， 即不包含空串 。 (不属于) 对任意集合 A，有 A = A = 11 4.集合的幂运算 设 A 是符号串的集合，则集合 A 的幂运算定义为： A0 A1 A A2 AA An AAA = AAn-1 (n0) n 【例如】设 A = a,b,则 A0 A1 a,b A2 AA = aa,ab,ba,bb A3 AAA = A2A = aaa,aab,aba,abb,baa,bab,bba,bbb 12 5.集合A的正闭包A+与闭包A* 设 A 是符号串的集合， 则集合 A 的正闭包A+和闭包A*分别定义为： A+ A1 U A2 U A3 U U An U A* A0 U A1 U A2 U A3 U U An U = U A+ 【例如】设 A = a,b,则 A+ a,b,aa,ab,ba,bb,aaa,aab, A* ,a,b,aa,ab,ba,bb,aaa,aab, 正闭包：Positive closure 闭包：Star closure（星闭包） 13 【例如】设 A = a,则 A+ a,aa,aaa, = an | n=1 A* , a,aa,aaa, = an | n=0 A* = A0 A1 A2 A3 ，称 A* 是 A 的闭包 。 A+ = AA* ，称 A+ 是A的正则闭包。 *表示上的所有符号串的全体 14 3.3 文法和语言的形式定义 1、规则 规则，也称重写规则、产生式或生成式， 是形如或 =的( ，)有序对， 其中是字母表V的正闭包V+中的一个符号 ，是V*中的一个符号。 称为规则的左 部， 称作规则的右部。 或 := := 表示表示“ “定义为定义为” ”或或“ “生成生成” ”，意，意 思是左部符号用右部符号串定义或左部符思是左部符号用右部符号串定义或左部符 号生成右部符号串。号生成右部符号串。 15 2 、文法定义 文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至 少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如 或 =的( ，)有序对，其中是字母表V 的正闭包V+中的一个符号，是V*中的一个符号 。 称为规则的左部， 称作规则的右部。 16 例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号 17 例 文法G=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a z 0 9 S= 18 文法的写法 元符号: = | 习惯 大写字母表示非终结符 小写字母表示终结符 (1) G：SaAb Aab AaAb A (2) GS： Aab AaAb A SaSb (3) GS:Aab |aAb | SaSb 19 推导的定义 直接推导“” 是文法G的产生式，若有v,w满足： v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w 也称w直接归约到v 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 20 推导 . ( . ) . . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A) 21 若存在v =w0 w1 . wn=w,(n0) 则记为v w，称作v推导出w，或w归约到v 若有v w 或 v=w， 则记为v w 推导的定义 + = + = * = 22 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11 + = * = * = 23 句型、句子的定义 z句型 有文法G，若S =* x，则称x是文法G的句型。 z句子 有文法G，若S =* x，且xVT*，则称x是文法G的句子 。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01 24 句型、句子 例：GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+，*，(和)构成的算术表达 式 25 (文法生成的)语言的定义 由文法G生成的语言记为L(G),它是文法G的 一切句子的集合: L(G)=x|S =* x，其中S为文法的开始 符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1 26 例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L（G）= anbnen | n1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成 根据1式进行n-1次得到 an-1 S（BE）n-1 由2式an(BE)n 由3式得到anBnEn 由4式得anbBn-1En 由5式n-1次得到anbnEn 由6式1次，7式n-1次得到 anbnen 27 文法的等价 z若L（G1）=L（G2），则称文法G1和G2 是等价的。 如文法G1A：ADB 与G2S：S0S1 等 价 ADE S01 EAB D0 B1 28 【例】设计一个表示所有标识符的文法 分析：标识符的定义是字母或以字母开头的字母数字串， 其结构如下： 字母字母或数字串 用 I 表示标识符，L 代表字母，D 代表数字，则定义标 识符的文法为：G =（VN，VT，P，S） 其中： VN = I,L,D VT = a,b,x,y,z,0,1,2,9 P = IL | IL |ID L a | b | | x | y | z D 0 | 1 | |9 S = I 29 【例】用文法定义一个含+、*的算术表达式。 变量是表达式； 若 E1 和 E2 是算术表达式，则 E1+E2，E1*E2，(E) 也 是算术表达式。 算术表达式的文法为：G =（VN，VT，P，S） 其中： VN = E VT = i,+,*,(,) P = E i | E+E | E*E |(E) S = E 30 【例】设字母表a,b，设计一个文法，描述 语言 L=abna | n0 分析：该语言中符号串的结构特征是： 当 n=0L = aa(b0=) 当 n=1L = aba 当 n=2L = abba L = aa,aba,abba,abbba, 语言的文法为：G =（A,B，a,b，P，A） 其中P为： AaBa B |Bb 31 【例】描述语言L=abna | n0的等价文法 （1）AaBa B |Bb （2）AaBa B |bB （3）AaB B a |bB （4）ABa B a |Bb 32 【例】设有文法GS: S01 | 0S1 求该文法所描述的语言 分析： 问题归结为由识别符号 S 出发，将推导出什么样的句子， 也就是说 L(GS)是由一些什么样的符号串所组成的集合 ，找出其中的规律，用式子或自然语言描述出来。 应用第二个规则 n-1 次，然后再使用第一个规则 1 次， 有 S=0S1=00S11=000S111=0n1S1n1=0n1n 即S 0n1n 所以此文法定义的语言为 L(GE) = 0L(GE) = 0 n n1 1 n n | | n n 0 0 + = 33 【例】设有文法GS: S0S|1S| 求该文法所定义的语言 该文法所确定的语言为 L(GS) = ,0,1,00,01,10,11, = x | x0,1* 34 【例】设有文法GA: AyB,BxB|x求该文法 所定义的语言 从开始符号 A 出发，我们可以推出如下句子： A = yB = yx A = yB = yxB =yxx A = yB = yxB = = yxx 归纳得出从 A 出发可推导出所有以 y 开头后跟一个或任 意多个 x 得字符串，即 L(GA) = yxn | n1 35 【例】考虑文法 G1:S A B A a A | a B b B | b 我们可以分析得出 L(G1) = am bn | m, n1 【例】构造一个文法 G2 使 L(G2) = an bn | m, n1 G2 和 G1 的区别在于，G2 的每个句子中 a 和 b 的个 数必须相同。 我们可以写出文法 G2:S a S b | a b 【例】 36 【例】设字母表a,b,试设计文法，描述语 言 L=a2n,b2n | n1 分析：设计文法来描述一个语言，关键是设计一组规则生 成语言中的符号串。 设计语言的文法，必须分析这个语言是由怎样一些符号串 组成，即首先分析语言中符号串的结构特征： 当 n=1L = aa,bb 当 n=2L = aaaa,bbbb 当 n=3L = aaaaaa,bbbbbb L = aa,bb,aaaa,bbbb,aaaaaa,bbbbbb, 语言 L 是由偶数个 a，偶数个 b 这样的符号串组成的 集合。 37 3.4 文法的类型 通过对产生式施加不同的限制，Chomsky将 文法分为四种类型： 0型文法：对任一产生式，都有 (VNVT)+， (VNVT)* 1型文法：对任一产生式，都有| ， 仅仅 S除外 2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为AaB或 Aa，其中AVN ，BVN ，aVT * 38 文法的类型 例：1型（上下文有关）文法 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaD Ca BDbD Db AabD 39 文法的类型 例：2型（上下文无关）文法 文法GS：SAB ABS|0 BSA|1 40 3型文法 GS： S0A|1B|0 A0A|1B|0S B1B|1|0 GI：I lT I l T lT T dT T l T d 41 文法的类型 2型文法 1型文法 0型文法 四类文法之间的逐级“包含”关系 3型文法 42 文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语 言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言 称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语 言称为3型语言正则（正规）语言（ RL ） 43 根据形式语言理论,文法和识别系 统间有这样的关系 0型文法（短语结构文法）的能力相当于 图灵机，可以表征任何递归可枚举集，而 且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的 形式为1A212，即只有A出现在 1和2的上下文中时，才允许取代A。 其识别系统是线性界限自动机。 44 2型文法（上下文无关文法CFG）：产生 式的形式为A，取代A时与A的上下 文无关。其识别系统是不确定的下推自动 机。 3型文法（正规文法RG）：产生的语言是 有穷自动机（FA）所接受的集合 45 3型文法产生的语言是有穷自动机（FA）所接 受的集合. 定理 设G=（VN，VT，P，S）是3型文法，则存在一个有穷 自 动机 M=(K, , f, A, Z)，使得L(M)=L(G) 有穷自动机NFA M 这样构造： = VT K= VN N, N为一个新状态,它不在VN中 A=S Z=N 对G中的形如 DtB的产生式,t为终结符或,有 f(D,t)=B； 对G中形如Dt的产生式， t为终结符或,有f(D,t)=N; 对VT中的每一个a ,有f(N,a)= 46 3型文法 和 有穷自动机（FA） G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b B A S a a a b b b a,b DZ a b a b 47 3型文法 和 有穷自动机（FA） 定理 已知一有穷自动机M= (K, , f, A, Z),存在有一个3型文法G = （VN，VT，P，S ）,使得L(G)=L(M) G 的定义： VT = VN= K S = A 若 f(D,t)=B ，则DtB在P中 若 f(D,t)=B ，且B在Z中，则Dt在P中 48 3型文法 和 有穷自动机（FA） G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDB A S a a a b b a,b b 49 正规文法和正规式 对上的正规式r ,存在一个RG=(VN,VT,P,S)： L(G)=L(r) 初始， VT= ,S VN ，生成正规产生式 Sr (R.1) 对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R.2)对形如Arr1的正规产生式： ArB Ar1 BrB Br1 BVN (R.3)对形如Ar1r2的正规产生式:Ar1 A r2 不断应用(R.x)做变换，直到每个产生式右端至多有一个VN 50 例 r=a(ad) (1) Sa(ad) (2) SaA A(ad) zA(ad)B A B(ad)B B Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B 51 正规文法和正规式 对G=(VN,VT,P,S),存在一个 =VT上的正规式r : L(r)=L(G) AxB , By 形成正规式 A=xy AxAy 形成正规式 A=xy Axy 形成正规式 A=xy 52 正规文法和正规式 Gs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a =a(ad)(ad) =a(ad) R=a(ad) 53 3.5 上下文无关文法及其语法树 上下文无关文法有足够的能力描述程序设计语言 的语法结构 语法树-句型推导的直观表示 54 语法树-句型推导的直观表示 (句型、推导) GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a 55 语法树 设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件 ，则此树称作G的语法树(推导树)(派生树）： 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且 有标记A，则肯定AVN 4. 如果结点n有标记A,其直接子孙结点从左到右的 次序是n1，n2，nk，其标记分别为A1，A2， ，Ak，那么AA1A2，Ak一定是P中的一 个产生式 语法树的结果： 从左到右读出叶子的标记而构成的行谓之 56 上下文无关文法的语法树 z句型aabbaa的可能推导序列和语法树 例: GS: SaAS ASbA ASS Sa Aba S a A S S b A a a b a SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa 57 语法树-句型推导的直观表示 给定文法G=(VN,VT,P,S)，对于G的任何句型都能 构造与之关联的语法树(推导树) 定理： G为上下文无关文法， 对于，有S =* ，当且仅当 文法G有以为结果的一棵语法树(推导树) 58 规范推导 规范句型 最左（最右）推导：在推导的任何一步 ，其中、是句型，都是对中 的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 59 一棵语语法树树表示了一个句型的种种可能的( 但未必是所有的)不同推导过导过 程，包括最 左(最右)推导导。但是，一个句型是否只对对 应应唯一的一棵语语法树树呢?一个句型是否只 有唯一的一个最左(最右)推导导呢? 60 例：GE: E i E E+E E E*E E (E) E E + E E * E i i i E E * E i E + E i i 句型 i*i+i 的两个不同的最左推导： 推导1：E E+E E*E+E i*E+E i*i+E i*i+i 推导2：E E*E i*E i*E+E i*i+E i*i+i 61 二义文法 z若一个文法存在某个句子对应两棵不同的 语法树，则称这个文法是二义的 z若一个文法存在某个句子有两个不同的最 左（右）推导，则称这个文法是二义的 z判定任给的一个上下文无关文法是否二义 ，或它是否产生一个先天二义的上下文无 关语言，这两个问题是递归不可解的，但 可以为无二义性寻找一组充分条件 62 文法的二义性和语言的二义性 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同 的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说 ，这两个文法所产生的语言是相同的。 二义文法改造为无二义文法 GE:E i GE： E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先 天二义的。对于一个程序设计语言来说，常常希望它的文法是无二 义的，因为希望对它的每个语句的分析是唯一的。 63 3.6 句型的分析（上下文无关文法） 句型分析就是识别一个符号串是否为某文法 的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程 序称为分析程序或识别程序。分析算法又 称识别算法。 从左到右的分析算法，即总是从左到右地识 别输入符号串，首先识别符号串中的最左 符号，进而依次识别右边的一个符号，直 到分析结束。 64 句型的分析算法分类 分析算法可分为： 自上而下分析法： 从文法的开始符号出发，反复使用文法的 产生式，寻找与输入符号串匹配的推导， 或者说，为输入串寻找一个最左推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，直至 归约到文法的开始符号。 65 两种方法反映了两种语法树的构造过程。 y自上而下方法是从文法符号开始，将它做为 语法树的根，向下逐步建立语法树，使语法 树的结果正好是输入符号串 y自下而上方法则是从输入符号串开始，以它 做为语法树的结果，自底向上的构造语法树 66 1、自上而下的语法分析 例：文法G： S cAd A ab A a 识别输入串w=cabd是否为该文法的句子 SSS cAdcAd a b 推导过程：S cAd cAd cabd 67 2、自下而上的语法分析 例：文法G： S cAd A ab A a 识别输入串w=cabd是否该文法的句子 S AA c a b d c a b d c a b d 规约过程构造的推导： cAd cabd S cAd 68 自上而下的语法分析 (1)S cAd (2) A ab (3) A a 识别输入串w=cad是否为该文法的句子 若S cAd 后选择(2)扩展A ，S cAd cabd 那将会？ w的第二个符号可以与叶子 结点a得以匹配，但第三 个符号却不能与下一叶子 结点d匹配 ？宣告分析失败（其意味着 ，识别程序不能为串cad 构造语法树，即cad不是 句子） -显然是错误的结论。 导致失败的原因是在分析中 对A的选择不是正确的。 S c A d a b 这时应该回溯，把A为 根的子树剪掉，扫描过 的输入串中的a吐出来, 再试探用产生式（3） 69 (1)S cAd (2) A ab (3)A a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析 对串cabd的分析中，如果不 是选择ab用产生式(2),而 是选择a用产生式(3)将a 归约到了A， 那么在c A b d中无法找 到一个可归约串了，最 终就达不到归约到S的结 果，因而也无从知道 cabd是一个句子 c a b d c A b d a 70 3、句型分析的有关问题 1）在自上而下的分析方法中如何选择使用哪个产生式进 行推导？ 假定要被代换的最左非终结符号是B，且有n条规则： BA1|A2|An，那么如何确定用哪个右部去替代B ？ 2）在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个 子串，将它归约到某个非终结符号，该子串称为“可归 约串” 71 3、句型分析的有关问题 z若G是一文法，S是文法的开始符号，