《上下文无关文法自顶向下分析》由会员分享，可在线阅读，更多相关《上下文无关文法自顶向下分析（52页珍藏版）》请在金锄头文库上搜索。
1、上下文无关文法 自顶向下分析,4.14.4,上下文无关文法的相关概念,3,3.2 上下文无关文法(CFG),CFG的定义与表示 上下文无关文法，Context Free Grammar，CFG 定义3.1 CFG是一个四元组： G =（N，T，P，S），其中 （1） N是非终结符（Nonterminals）的有限集合； （2） T是终结符（Terminals）的有限集合，且NT=； （3） P是产生式（Productions）的有限集合，形如： A，其中AN（左部），(NT)*（右部）， 若=，则称A为空产生式（也可以记为A ）； （4） S是非终结符，称为文法的开始符号（Start symb
2、ol）。,4,3.2 上下文无关文法(CFG),例3.2 简单算术表达式的上下文无关文法可表示如下： N = E T = +，*，(，)，-，id S = E P: E E + E （1） E E * E （2） E （E） （3） (G3.1) E -E （4） E id （5） 产生式的一般读法 记号 读作“定义为”或者“可导出”。 “E E + E” 表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。,5,3.2 上下文无关文法(CFG),由产生式集表示CFG 前提： 若文法正确 结论： 文法开始符号S是第一个产生式的左部；
3、N是可以出现在产生式左边符号的记号集合； T是绝不出现在产生式左边符号的记号集合； P: E E + E （1） E E * E （2） E （E） （3） E -E （4） E id （5） 产生式表示也被称为巴克斯范式（Backus-Naur Form，BNF），其中用:=表示,S=E N=E T=+，*，(，)，-，id,6,3.2 上下文无关文法(CFG),CFG产生语言的基本方法推导 CFG（产生式）通过推导的方法产生语言。 通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=表
4、示），直到得到一个终结符序列。 例3.4 用(G3.2)产生终结符序列-(id+id)可如下： E E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）,E = -E by(4) = -(E) by(3) = -(E+E) by(1) = -(id+E) by(5) = -(id+id) by(5),7,3.2 上下文无关文法(CFG),定义3.2 利用产生式产生句子的过程中，将产生式A的右部代替文法符号序列A中的A得到的过程，称A直接推导出，记作：A=。 若对于任意文法符号序列1，2，.n，均有1=2=.=n，则称此过程为零步或多步推
5、导，记为： 1=*n，其中1=n的情况为零步推导。 若1n，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：1=+n。 两点注意： ，有=*，即推导具有自反性； 若=*，=*，则=*，即推导具有传递性。,8,3.2 上下文无关文法(CFG),定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = S=+ and T* ， L(G)称为上下文无关语言(Context Free Language, CFL)，称为句子。 若S=*，(NT)*，则称为G的一个句型。 定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型
6、被称为左句型。 类似可定义最右推导与右句型，最右推导也被称为规范推导。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4 5 6 6是句子，所有i (i=1.6)均是句型。,语言与文法简介,10,3.3 语言与文法简介,正规式与上下文无关文法 正规式到CFG的转换 推论3.1 正规式描述的语言结构均可用CFG描述，反之不一定 从正规式到CFG的对应关系： 构造正规式的NFA； 若0为初态，则A0为开始符号； 对于move(i,a)=j，引入产生式AiaAj； 对于move(i,)=j，引入产生式 AiAj； 若i是终态，则引入产生式Ai 。
7、 例3.11 从正规式r=(a|b)*abb的NFA构造CFG： A0 aA0|bA0|aA1 A1 bA2 A2 bA3 A3 ,经验的方法： A HT H | Ha | Hb T abb,11,3.3 语言与文法简介,为什么用正规式而不用CFG描述词法？ 词法规则简单，用正规式描述已足够； 正规式的表示比CFG更直观、简洁、易于理解； 有限自动机的构造比下推自动机简单，且分析效率高； 区分词法和语法，为编译器前端的模块划分提供方便。 贯穿词法分析和语法分析始终的思想： 语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自动机） 用正规式和CFG描述的语言，对应
8、的识别方法（自动机）不同； 正规式适合描述线性结构，如标识符、关键字、注释等；CFG适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、while-do等。,12,3.3 语言与文法简介,上下文有关语言 Context Sensitive Language, CSL 程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。 典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。 描述它们的文法被称为上下文有关文法（Context Sensitive Grammar, CSG）。,13,3.3 语言与文法
9、简介,例3.12 不能用CFG描述的语言： L1=c|(a|b)* (标识符声明与引用一致性的抽象) L2=anbmcndm|n1和m1 (形参与实参一致性的抽象) L3=anbncn|n1 (计数问题的抽象) 相近的CFL： L1=cr|(a|b)* L2=anbmcmdn|n1, m1 L2=anbncmdm|n1, m1 L3=ambmcn|m, n1,SaSa|bSb|c SaSd|aAd AbAc|bc SAB AaAb|ab BcBd|cd AAC AaAb|ab CcC|c,14,3.3 语言与文法简介,计数问题 L3=anbncn|n1 CSL L3=ambmcn|m,n1 C
10、FL L3=akbmcn|k，m，n1 正规集 命题：L3不是正规集，因为构造不出可以识别L3的DFA。 证明：（反证） 假设L3是正规集，则可构造n个状态的DFA D，它接受L3； 考察D读完，a，aa，.，an，分别到达S0，S1，.，Sn，共有n+1个状态。根据鸽巢原理，序列中至少有两个状态相同，设Si=Sj（ji），因为aibickL3，所以存在路径aibick。但是D中也有路径ajbick，矛盾。故L3不是正规集。,AAC AaAb|ab CcC|c ? a+b+c+,15,3.3 语言与文法简介,形式语言与自动机简介 定义3.8 若文法G=(N，T，P，S)的每个产生式中，均有(N
11、T)*，且至少含有一个非终结符，(NT)*，则称G为0型文法。 对0型文法施加以下第i条限制，即得到i型文法。 G的任何产生式（S除外）满足|； G的任何产生式形如A，其中AN，(NT)*； G的任何产生式形如Aa或者AaB(或者ABa)，其中A和BN，aT。,16,3.3 语言与文法简介,再考察L3： L3=anbncn|n1 例3.15 L3可用下述CSG描述： SaSBC (1) SaBC (2) CBBC (3) aBab (4) bBbb (5) bCbc (6) cCcc (7) CSG、CFG、正规式能力递减，但是能力越强的文法，其文法设计和自动机的构造越困难，因此语法分析仅用到
12、CFG（除特别指出，文法即指CFG ）,句子akbkck 的推导： S =.= ak-1S(BC)k-1 (by 1) = ak(BC)k (by 2) =.= akBkCk (by 3) = akbBk-1Ck (by 4) =.= akbkCk (by 5) = akbkcCk-1 (by 6) =.= akbkck (by 7),二义性与二义性的消除,18,3.2 上下文无关文法(CFG),二义性与二义性的消除 二义性问题：一个句子可能对应多于一棵分析树 例3.7 文法G3.2为 EE+E | E*E |（E）| -E | id 句子id+id*id和id+id+id可能的分析树有：,1
13、9,3.2 上下文无关文法(CFG),定义3.7 若文法G对同一句子产生不止一棵分析树，则称G是二义的。 原因：在产生句子的过程中某些直接推导有多于一种选择 注意： 一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关； 文法中缺少对文法符号优先级和结合性的规定。 “悬空（dangling）else”问题 S if C then S (1) | if C then S else S (2) | id := E (3) (G3.3) C E = E | E E (4).(6) E E + E | - E | id | n (7).(10),20,3.2 上下文无关文法(CFG),例
14、3.8 条件语句 if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5 else与离它远的then匹配,if x0 then x:=5 else x:=-5 else与离它近的then匹配,21,3.2 上下文无关文法(CFG),文法二义不能说明它所产生的语言一定是二义的。 消除语言二义有两种方法： 改写二义文法为非二义文法； 规定二义文法中符号的优先级和结合性。 改写 例3.9 与G3.2等价的非二义文法： E E + T | T T T * F | F (G3.4) F （E） | -F | id 问题：如何改写？,EE+E | E*E
15、 |（E） (G3.2) | -E | id,22,3.2 上下文无关文法(CFG),观察结论： 新引入的非终结符限制每一步直接推导均有唯一选择； 最终分析树的形状，仅与文法有关，而与推导方法无关； 非终结符的引入，增加了推导步骤(分析树增高)； 越接近S的文法符号的优先级越低。(如EE+T) 对于AA，若A在终结符左边出现(即终结符在中)，则A产生式具有左结合性质。,改写二义文法的关键步骤： 引入新的非终结符，增加一个子结构并提高一级优先级； 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。,23,3.2 上下文无关文法(CFG),例3.10 改写二义文法G3.2为G3.4 ： 引入新的非终结符，增加一个子结构并提高一级优先级； 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。 优先级： + * ( ), -, id 结合性： 左结合 +, * 右结合 - 无结合 id 非终结符与运算： E: + （E产生式，左递归） T: * （T产生式，左递归） F: -, ( ), id（F产生式，右递归）,E
