编译原理:第五章语法分析1_第1页
编译原理:第五章语法分析1_第2页
编译原理:第五章语法分析1_第3页
编译原理:第五章语法分析1_第4页
编译原理:第五章语法分析1_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第 5 章 语法分析 语法分析是编译的第二阶段;其任务是识别和处理比单词更大的语法单位,如:程序设计语言中的表达式、各种说明和语句乃至全部源程序,指出其中的语法错误;必要时,可生成内部形式,便于下一阶段处理。 内容提要:5.1 语法分析的基本概念5.2 递归子程序法5.3 LL(1)分析法5.4 LR()分析法5.5 简单优先分析法5.1 语法分析的基本概念5.1.1 语法分析的定义与分类 【定义】形式上说,语法分析是指对给定的符号串(),判定其是否是某文法G(Z)的句子。即Z 成立吗 ? = + Z 成立吗 ? = .+ 【分类】语法分析方法通常分两大类: 1. 自顶向下法(推导法) 2.

2、自底向上法(归约法) 从开始符号出发,采用推导运算,试图自顶向下构造语法树。 从给定的符号串出发,采用归约运算,试图自底向上构造语法树。或 通常采用“最左推导法”。 通常采用“最左归约法”给定: = a*(b+c), 是否是表达式?(接上页)5.1.2 算法设计分析1【例5.1】 G(E): E - T | E+T | E-T T - F | T*F | T/F F - i | (E) 最左推导分析过程:【结论】自顶向下分析的关键技术是如何确定具有相同左部的产生式之侯选者!即 E a*(b+c) = +=T*F=F*F=a*F=a*(E)=a*(E+T)=a*(T+T)=a*(F+T)=a*(

3、b+T)=a*(b+F)=a*(b+c)- 自顶向下法:E=T 为了清楚每次归约的是什麽?我们观察语法树的 = a*(b+c)5.1.2 算法设计分析2 E - T | E+T | E-T T - F | T*F | T/F F - i | (E) - 自底向上法a*(b+c)=.F*(b+c)=.T*(E+c)=.T*(b+c)=.T*(F+c)=.T*(T+c)=.T*(E+F)=.T*(E+T)=.T*(E)=.T*F=.E=.T=.+E a*(b+c)即【结论】自底向上分析的关键技术是如何确定当前句型的句柄!最左归约分析过程: 构造过程: 5.2.1 递归子程序法的设计原理: 语法分析

4、的核心技术是“文法”的机内表示问题;递归子程序法直接把文法变成程序。 对每一个非终结符,构造一个子程序,用以识别该非终结符所定义的符号串。每个子程序以产生式左部非终结符命名,以产生式右部构造子程序内容。例如:设有如下产生式: A - aBeD | bAc | 则有:递归子程序 A: 递归子程序法属于自顶向下语法分析方法。故又名递归下降法。 设计原理:yn入口出口a?b?NEXT(w)yNEXT(w) NEXT(w)nc?ynerr2e?遇时 B A Dyerr1nNEXT(w)A - aBeD | bAc | 判断当前单词是否是c即w=c?调用子程序A(接上页)读单词函数5.2.2 递归子程序

5、的构造算法 扩展文法:增设一个产生式,作为主程序:Z-Z , 入出口约定: 子程序入口时,其首符号已经读来!子程序出口时,其后继符应该读来! 子程序内容设计:遇终结符,判定之 ,确认后读下一单词;遇非终结符,调用之,返回后不读下一单词; 遇空串( ) ,直接出口; 【例5.2】G(S):令 Z - S , 则 递归子程序:子程序A开始结束 #SNEXT(w)err0yn入口出口 a berr1NEXT(w)A berr2NEXT(w)SNEXT(w)子程序Snnnyyy入口 cNEXT(w)出口遇时ny dNEXT(w)err3yn主程序S - aAb |bS , A - cd | 实际上,上

6、述两点可归纳为同一个条件,即: 递归子程序要求文法应是: 5.2.3 递归子程序法对文法的要求: 递归子程序是根据文法各产生式的首符号与当前所读单词进行匹配,以决定候选产生式的;这就要求文法: 具有相同左部的各产生式,首符号不同; 文法不能有左递归!如:A - a|a (首符号相同,); A - A| (直接左递归,)。 LL(1)文法!(见 5.3节)。 5.2.4 递归子程序的构造例: . 消除左递归后的文法1:G(E) :T - F 2 F F - i | ( E )E - T 1T 【提示】 根据文法变换:A - A | A - 【例5.3】G(E): E - T | E1T T -

7、F | T2F F - i | (E) 其中:1(+,-),2(*,/),i(变量或常数)主程序T - F 2 F F - i | ( E )E - T 1 T 子程序E令 Z - E开始结束 #ENEXT(w)err0yn入口出口NEXT(w)T 1Tyn入口出口NEXT(w)F 2Fyn子程序T(接上页)T - F 2 F F - i | ( E )E - T 1 T 入口出口 i (err1NEXT(w)err2NEXT(w)E )yyynnn子程序F(接上页). 消除左递归后的文法2 :G(E) :T - F 2 F F - i | ( E )E - T 1 T E - T EE -

8、1T E | T - F TT - 2F T | F - i | ( E ) 文法 G(E)消除花括号后可得:令 Z - E ,则可构造递归子程序如下: (主程序 省略)入口出口TE子程序E入口 1NEXT(w)T出口遇时nyE子程序EE - T EE - 1T E | T - F TT - 2F T | F - i | ( E )(接上页)练习题:【习题5.1】解释下述词语: 语法分析 ;语法分析的分类。【习题5.2】构造下述文法的递归子程序: G(S): S - a A S b | B d A - c S | B - b B | d 【习题5.3】构造下述文法的递归子程序: 产生式 S - Bd 的首符号为 b,d ! 产生式 A - 的首符号(后继符) a,b,d提示G(E): E - T + T | - T T - F * F | / F F - i | ( E )a * ( b + c )FTTEFFTETFEaFbFTcFE+T

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论