第四章-语法分析378课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第四章-语法分析378课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 语法分析 378 课件
- 资源描述:
-
1、第四章 语法分析赵建华南京大学计算机系2010.31fhfh程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无关文法或BNF表示法来描述 文法可给出精确易懂的语法规则 可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构,有助于进一步的语义处理/代码生成。支持语言的演化和迭代。2fhfh语法分析器的作用 基本作用 从词法分析器获得词法单元的序列,确认该序列是否可以由语言的文法生成。对于语法错误的程序,报告错误信息 对于语法正确的程序,生成语法分析树。通常并不真的生产这棵语法分析树3fhfh语法分析器的分类 通用语法分析器 可以对任意文法进行语法分析 效率很低,不适合用于编译
2、器 自顶向下语法分析器 从语法分析树的根部开始构造语法分析树 自底向上语法分析器 从语法分析树的叶子开始构造语法分析树 后两种方法 总是从左到右、逐个扫描词法单元。只能处理特定类型的文法,但是这些文法足以用来描述程序设计语言。4fhfh上下文无关文法 定义:一个上下文无关文法包含四个部分 终结符号:组成串的基本符号(词法单元名字)非终结符号:表示串的集合的语法变量。给出了语言的层次结构。在程序设计语言中通常对应于某个程序构造,比如stmt(语句)开始符号:某个被指定的非终结符号。它对应的串的集合就是文法的语言 产生式集合:描述将终结符号和非终结符号组成串的方法 产生式的形式:头/左部 体/右部
3、 头部是一个非终结符号,右部是一个符号串;例子:expression expression+term5fhfh上下文无关文法的例子 简单算术表达式的文法:终结符号:id+-*/()非终结符号:expression,term,factor 开始符号:expression 产生式集合:expression expression+termexpression expression termexpression termterm term*factorterm term/factorterm factorfactor (expression)factor id6fhfh文法书写的约定 终结符号 靠前的
4、小写字母(a,b,c);运算符号(+*);标点符号;数位;黑体字符串(id,if,while)非终结符号 靠前的大小字母(A,B,C);字母S(通常是开始符号);小写斜体字母;表示程序构造的大写字母 X,Y,Z文法符号(终结符号或非终结符号)小写希腊字母表示文法符号串(,)靠后的小写字母表示终结符号串 具有相同头的产生式可以合并成A 1|2|n的形式 通常第一个产生式的左部就是开始符号。7fhfh文法简单形式的例子E E+T|E T|TT T*F|T/F|FF (E)|id 注意:|是元符号(即文法描述方式中的符号,而不是文法符号)这里(,)不是元符号;在有些地方会把()看作元符号8fhfh推
5、导(1)推导:将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体。从开始符号出发,不断进行上面的替换,就可以得到文法的不同句型 例子 文法:E -E|E+E|E*E|(E)|id 推导序列:E=-E=-(E)=-(id)9fhfh推导(2)推导的正式定义 如果A是一个产生式,那么A=最左(右)推导:()中不包含非终结符号 符号:经过零步或者多步推导出:对于任何串 如果 且=,那么 经过一步或者多步推导出:等价于 且不等于10fhfh句型/句子/语言 句型(sentential form):如果S=*=,那么就是文法的句型 可能既包含非终结符号,又包含终结符号;可以是空串 句子(
6、sentence)文法的句子就是不包含非终结符号的句型 语言 文法G的语言就是G的句子的集合,记为L(G)w在L(G)中当且仅当w是G的句子,即S=*=w11fhfh语法分析树 推导的图形表示形式 根结点的标号时文法的开始符号 每个叶子结点的标号是非终结符号、终结符号或 每个内部节点的标号是非终结符号。每个内部结点表示某个产生式的一次应用 内部结点的标号为产生式头,结点的子结点从左到右是产生式的体 有时允许树的根不是开始符号(对应于某个短语)。树的叶子组成的序列是根的文法符号的句型 一棵分析树可对应多个推导序列,但是分析树和最左(右)推导序列之间具有一一对应关系12fhfh语法分析树的例子 文
7、法:E -E|E+E|E*E|(E)|id 句子:-(id+id)13fhfh从推导序列构造分析树 假设有推导序列:A=a1=a2=an 算法:初始化:a1的分析树是标号为A的单个结点 假设已经构造出ai-1=X1X2Xk的分析树,且ai-1到a1的推导是将Xj替换为,那么在当前分析树中找出第j个非结点,向这个结点增加构成的子结点。如果=,则增加一个标号为的子结点)14fhfh构造分析树的例子 推导序列:E=-E=-(E)=-(E+E)=-(id+E)=-(id+id)15fhfh二义性(1)二义性(ambiguous):一个文法可以为某个句子生成多棵语法分析树,这个文法就是二义性的 例子:E
8、=E+E=id+E=id+E*E=id+id*E=id+id*id E=E*E=E+E*E=id+E*E=id+id*E=id+id*id16fhfh二义性(2)程序设计语言的文法通常都应该是无二义性的 否则就会导致一个程序有多种“正确”的解释。比如文法:E -E|E+E|E*E|(E)|id 的句子a+b*c 但有些二义性的情况可以方便文法或语法分析器的设计。但是需要消二义性规则来剔除不要的语法分析树 比如:先乘除后加减17fhfh证明文法生成的语言 证明文法G生成语言L可以帮助我们了解文法可以生成什么样的语言。基本步骤:首先证明L(G)L 然后证明LL(G)一般使用数学归纳法 证明L(G)
9、L的方法之一:构造L,使得LVt*=L;并证明SL,且对于L中的任意,=可推出也在L中。也可以按照推导序列长度进行数学归纳 证明LL(G)时,通常可按照符号串的长度来构造推导序列。18fhfh文法生成语言的例子(1)文法:S(S)S|语言:所有具有对称括号对的串 L(G)L的证明:令L=删除S后括号对称的串,显然有LVt*=L且S L 任意的删除S后括号对称的串,不管使用S还是(S)S 推导出串,删除中的S后得到的串仍然是括号对称的。有上面两点可知:G的所有句型都属于L,且L中的终结符号串就是L。可知L(G)L。19fhfh文法生成语言的例子(2)LL(G)的证明:注意:括号对称的串的长度必然
10、是偶数。归纳基础:如果括号对称的串的长度为0,显然它可以从S推导得到 归纳步骤:假设长度小于2n的括号对称的串都能够由S推导得到。假设w是括号对称且长度为2n的串 w必然以左括号开头,且w可以写成(x)y的形式,其中x也是括号对称的。因为x、y的长度都小于2n,根据归纳假设,x和y都可以从S推导得到。因此S=(S)S=*=(x)y。20fhfh上下文无关文法和正则表达式(1)上下文无关文法比正则表达式的能力更强。即:所有的正则语言都可以使用文法描述 但是一些用文法描述的语言不能用正则文法描述。证明:首先SaSb|ab 描述了语言anbn|n0,但是这个语言无法用DFA识别。假设有DFA识别此语
11、言,且这个文法有K个状态。那么在识别ak+1的输入串时,必然两次到达同一个状态。设自动机在第i个和第j个a时进入同一个状态,那么:因为DFA识别L,ajbj必然到达接受状态,因此aibj必然也到达接受状态。直观地讲:有穷自动机不能数(大)数。21fhfh上下文无关文法和正则表达式(2)证明(续)其次证明:任何正则语言都可以表示为上下文无关文法的语言。任何正则语言都必然有一个NFA。对于任意的NFA构造如下的上下文无关文法 对NFA的每个状态i,创建非终结符号Ai。如果有i在输入a上到达j的转换,增加产生式AiaAj。如果i在输入上到达j,那么增加产生式AiAj.如果i是一个接受状态,增加产生式
12、Ai 如果i是开始状态,令Ai为所得文法的开始符号。22fhfhNFA构造文法的例子 A0aA0|bA0|aA1 A1bA2 A2bA3 A3 考虑baabb的推导和接受过程可知:NFA接受一个句子的运行过程实际是文法推导出该句子的过程。23fhfh设计文法 文法能够描述程序设计语言的大部分语法 但不是全部,比如:标识符的先声明后使用无法用上下文无关文法描述。因此:语法分析器接受的语言是程序设计语言的超集。必须通过语义分析来剔除一些符合文法、但不合法的程序。24fhfh二义性的消除(1)一些二义性文法可以被改成等价的无二义性的文法 例子:stmt if expr then stmt|if ex
13、pr then stmt else stmt|other if E1 then if E2 then S1 else S2的两棵语法树25fhfh二义性的消除(2)为了保证“else和最近未匹配的then匹配”,我们要求在then分支的语句必须是匹配好的。引入matched_stmt表示匹配好的语句,有如下文法:stmt matched_stmt|open_stmtmatched_stmt if expr then matched_stmt else matched_stmt|otheropen_stmt if expr then stmt|if expr then matched_stmt
14、else open_stmt 二义性的消除方法没有规律可循。通常并不是通过改变文法来消除二义性。26fhfh左递归的消除 左递归的定义:如果一个文法中有非终结符号A使得A=*=A,那么这个文法就是左递归的。立即左递归(规则左递归)文法中存在一个形如AA的产生式。自顶向下的语法分析技术不能处理左递归的情况,因此需要消除左递归;但是自底向上的技术可以处理左递归。27fhfh立即左递归的消除 假设非终结符号A存在立即左递归的情形,假设以A为左部的规则有:A A1|A2|Am|1|2|n 可以替换为A1A|2A|n AA1A|2A|mA|由A生成的串总是以某个i开头,然后跟上零个或者多个i的重复。28
15、fhfh通用的左递归消除方法 输入:没有环和产生式的文法G 输出:等价的无左递归的文法 步骤:将文法的非终结符号任意排序为A1,A2,Anfor i=1 to n do for j=1 to i-1 do将形如Ai Aj的产生式替换为Ai1|2|n,其中Aj 1|2|m是以Aj为左部的所有产生式;消除Ai的立即左递归;1.内层循环的每一次迭代保证了Ai的产生式的右部首符号都比Aj更加靠后。2.当内层循环结束时,Ai的产生式的右部首符号不先于Ai。3.消除立即左递归就保证了Ai的产生式的右部首符号必然比Ai后。(不能有环和产生式)4.当外层循环结束时,所有的产生式都是如此。使用这些产生式当然不会
16、产生左递归的情形。29fhfh通用左递归消除的例子 S Aa|bAAc|Sd|步骤1:排列为S,A i=1时:内层循环不运行,S没有立即左递归;i=2时:j=1,处理规则ASd;替换得到 AAc|Aad|bd|消除A的立即左递归 SAa|b AbdA|A AcA|adA|通用左递归消除的问题在于很难找到新文法和旧文法的推导之间的对应关系,因此很难依据新文法进行语义处理。本例子中的产生式恰好没有影响算法的正确性30fhfh预测分析法简介 试图从开始符号推导出输入符号串;以开始符号作为初始的当前句型 每次为最左边的非终结符号选择适当的产生式;通过查看下一个输入符号来选择这个产生式。有多个可能的产生
17、式时预测分析法无能为力 比如文法:E+EE|-EE|id;输入为+id-id id 当两个产生式具有相同的前缀时无法预测 文法:stmt if expr then stmt else stmt|if expr then stmt 输入:if a then 新文法:stmt if expr then stmt elsePart elsePart else stmt|需要提取公因子31fhfh提取公因子的文法变换 算法:输入:文法G 输出:等价的提取了左公因子的文法 方法:对于每个非终结符号A,找出它的两个或者多个可选产生式体之间的最长公共前缀。A 1|2|n|AA|A1|2|n 其中是不以开头的
18、产生式体32fhfh提取公因子的例子 文法:S i E t S|i E t S e S|a E b 对于S而言,最长的前缀是i E t S,因此:S i E t S S|a Se S|E b33fhfh非上下文无关语言的构造 抽象语言 L1=wcw|w在(a|b)*中 这个语言不是上下文无关的语言 它抽象地表示了C或者Java中“标识符先声明后使用”的规则。说明了这些语言不是上下文无关语言,不能使用上下文无关文法描述。通常用上下文无关文法描述其基本结构,不能用文法描述的特性在语义分析阶段完成。原因是上下文文法具有高效的处理算法。34fhfh自顶向下的语法分析 为输入串构造语法分析树 从分析树的
19、根结点开始,按照先根次序,深度优先地创建各个结点 对应于最左推导。基本步骤 确定对句型中最左边的非终结符号应用哪个产生式 然后对句型中的非终结符号和输入符号进行匹配 关键问题是:确定对最左边的非终结符号应用哪个产生式35fhfh自顶向下分析的例子 文法:ETE E+TE|TFT T*FT|F(E)|id 输入id+id*id 分析树序列见右面(图4-12)36fhfh递归下降的语法分析 递归下降语法分析程序由一组过程组成 每个非终结符号对应于一个过程,该过程负责扫描非终结符号对应的结构 程序执行从开始符号对应的过程开始 当扫描整个输入串时宣布分析成功完成37fhfh递归下降分析技术的回溯 如果
20、没有足够的信息来唯一地确定可能的产生式,那么分析过程就产生回溯。前面的算法报告错误(第7行)并不意味着输入串不是句子,而可能是表示前面选错了产生式。第一行上保存当前的扫描指针 在第七行上应该改成 回退到保存的指针;GOTO (1)并选择下一个产生式;如果没有下一个产生式可选,报告错误。回溯需要来回扫描,低效 如果嵌入了语义处理,则需要撤销已经完成的语义处理动作。解决方法:设法通过一些信息确定唯一可能的产生式38fhfh递归下降分析中回溯的例子 文法:ScAdAab|a 输入串:cad 步骤:调用函数S;S选择唯一产生式ScAd 输入中的c和句型中的c匹配,继续调用A A首先选择产生式Aab,a
21、和输入的a匹配,b和输入的d不匹配;回溯并选择下一个产生式Aa;a和输入的a相匹配;对A的调用返回;到S的调用;ScAd中的d和下一个输入匹配;对S的调用返回,已经读入所有输入符号;因此扫描结束,cad是句子。39fhfhFIRST和FOLLOW(1)在自顶向下的分析技术中,通常使用向前看几个符号来唯一地确定产生式(这里假定只看一个符号)当前句型是xA,而输入是xa。那么选择产生式A的必要条件是下列之一:=*=,且以a开头;也就是说在某个句型中a跟在A之后;=*=a;如果按照这两个条件选择时能够保证唯一性,那么我们就可以避免回溯。因此,我们定义FIRST和FOLLOW40fhfhFIRST和F
22、OLLOW(2)FIRST():可以从推导得到的串的首符号的集合;如果=*=,那么也在FIRST()中;FOLLOW(A):可能在某些句型中紧跟在A右边的终结符号的集合。41fhfhFIRST的计算方法 计算FIRST(X)的方法 如果X是终结符号,那么FIRS(X)=X 如果X是非终结符号,且XY1Y2Yk是产生式,如果a在FIRST(Yi)中,且在FIRST(Y1),FIRST(Y2),FIRST(Yi-1)中,那么a也在FIRST(X)中。如果在FIRST(Y1),FIRST(Y2),FIRST(Yk)中,那么在FIRST(X)中。如果X是非终结符号,且X是一个产生式,那么在FIRST(
23、X)中 计算FIRST(X1X2Xn)的方法 向集合中加入FIRST(X1)中所有非的符号;如果在FIRST(X1)中,再加入FIRST(X2)中的所有非的符号;如果在所有的FIRST(X1)中,将加入FIRST(X1X2Xn)中。42fhfhFOLLOW的计算方法 算法 将右端结束标记$放到FOLLOW(S)中 按照下面的两个规则不断迭代,直到所有的FOLLOW集合都不再增长为止。如果存在产生式AB,那么FIRST()中所有非的符号都在FOLLOW(B)中。如果存在一个产生式AB,或者AB且FIRST()包含,那么FOLLOW(A)中的所有符号都加入到FOLLOW(B)中。请注意各个步骤中将
24、符号加入到FOLLOW集合中的理由。43fhfhFIRST/FOLLOW的例子(1)文法:ETEE+TE|T FTT*FT|F(E)|id FIRST集合 FIRST(F)=(,id;FIRST(E)=FIRST(T)=(,id FIRST(E)=+,;FIRST(T)=*,由此可以推出各个产生式右部的FIRST集合。44fhfhFIRST/FOLLOW的例子(2)FOLLOW集合的计算过程$在FOLLOW(E)中(E是开始符号)由规则F(E)可知,)也在FOLLOW(E)中 由规则ETE 可知FOLLOW(E)也包含了$和)。注意:因为E只出现在E和E的产生式的尾部,因此FOLLOW(E)必
25、然等于FOLLOW(E)。由规则E+TE,FIRST(E)中的+在FOLLOW(T)中;且FIRST(E)包含,因此FOLLOW(E)中的$和)也在FOLLOW(T)中。因为T只出现在T和T的产生式的末尾,可以FOLLOW(T)=FOLLOW(T);由规则TFT且T可以推导出,因此可知FOLLOW(F)包含FOLLOW(T);同时FIRST(T)也在FOLLOW(F)中。因此 E:$,)E:$,)T,T:+,),$F:+,*,),$45fhfhLL(1)文法(1)定义:对于文法的任意两个不同的产生式A|不存在终结符号a使得和都可以推导出以a开头的串 和最多只有一个可以推导出空串 如果可以推导出
展开阅读全文