编译原理课件-cha

1、第四章 语法分析自上而下分析 编译原理 本章主要内容 n本章主要介绍语法分析的处理 语法分析的任务 自顶向下分析法 四元式 单词符号 语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 优化段 源程序 表 格 管 理 出 错 处 理 目标代码生成器 语法分析的任务 n语法分析程序以单词串形式的源程序作为 输入或分析的对象。 n它的基本任务是： 根据语言的语法规则 ，分析源程序的语 法结构，即分析如何由这些单词组成各种语 法范畴 (如下标变量、各种表达式、各种语句 、程序段或分程序，乃至整个源程序等等)， 并在分析过程中，对源程序进行语法检查。 n作为语法分析程序的输出，可以有多种不 同的形式。在下面的讨论中，为简便起见 ，我们假定语法分析程序的输出，是用某 种方法表示的语法树 语法分析 l如何精确描述和刻画语言中的基本 语法成分-如表达式、语句和函数 ？ l如何识别语法成分及语法错误并执 行某些相关的处理动作？ 什么是语言 自然语言(Natural Language) n是人与人的通讯工具 n语义(Semantics):环境、背景知识、 语气、二义性难以形式

2、化 计算机语言(Computer Language) n计算机系统间、人机间通讯工具 n严格的语法(Grammar)、语义 (Semantics) 易于形式化：严格 语言是用来交换信息的工具功能性描 述 什么是语言 语言 单词(Token)：满足一定规则字符 (Character)串 句子(Sentence)：满足一定规则单词序列 语言(Language)：满足一定条件的句子集合 语言是字和组合字的规则结构性描述 例：去吃我们中汉堡午 中午我们去吃汉堡 如何描述一种语言？ 1. 如果语言是有穷的（只含有有穷多 个句子），可以通过枚举法将语言所 有的句子列出表示。 n例如，只含两个句子的语言：“I am a teacher”, “You are students”; 如何描述一种语言？ 2. 如果语言是无穷的，描述语言有两种途径 ： l制定有限条规则，用于产生所要描述的语言 的全部句子（可无限多），这些规则构成了 该语言的文法。 l设计一种装置（算法或过程），它以某字母 表上的符号串为输入，判别该符号串是否为 所描述语言的句子。此装置称为自动机。 语言概述 程序设计语言形式化的内容提取

3、程序设计语言(Programming Language) ：组成程序的所有语句的集合 程序(Program)：满足语法规则的语句序 列 语句(Sentence) ：满足语法规则的单词 序列 单词(Token) ：满足词法规则的字符串 文法和语法分析 正规式的局限性：不能用于描述 配对或嵌套的结构 l例1：配对括号串的集合 l例2：wcw | w是a和b的串 仅能表示给定结构的 固定次数的重复或者没有 指定次数的重复 适合描述和识别语言 的单词符号； 文法和语法分析 高级语言的语法结构适合使用 上下文无关文法描述。 文法及语言的形式定义 文法是对语言结构的定义与描述（ 或称为“语法”），即用适当条数 的规则把语言的全部句子描述出来 。 文法是以有穷的集合刻划无穷的集 合的工具。 文法 l文法能清晰地描述程序设计语言的语法 构成易于理解。 l文法能自动地构造有效的语法分析器， 检查源程序是否符合语言规定的语法形 式。 l文法定义可以了解程序设计语言的结构 ，有利于将源程序转化为目标代码，以 及检查出语法错误。 l基于文法实现的语言易于扩展。 文法及语言的形式定义 例：有一句子：“He ha

4、s a pen.” 这是一个在语法、语义上都正确的句 子，该句子的结构（称为语法结构） 是由它的语法决定的 。在本例中它 为“主谓宾结构”。 文法的形式定义 语法规则：我们通过建立一组 规则，来描述句子的语法结构 。 文法的形式定义 := := := he := a := pen := := has := := pen 括起来的 部分是语言 的一个语法 实体（称为 语法单位、 语法范畴、 语法变量等 ） 规定用“:=” 表示“由组 成” l终结符号集VT = he, has, a, pen l非终结符号集VN = 句子，主语，谓语， 冠词，形容词，名词 ， 动词 ，宾语 ，名词 l产生式集合P = 句子 主语谓语 ， l开始符号S = 句子 句子的语法组成 句子的推导_根据规则 n由规则推导句子：有了一组规则之 后，可以按照一定的方式用它们去 推导或产生句子。 n推导方法：从一个要识别的符号开 始推导，即用相应产生式的右部来 替代产生式的左部，每次仅用一条 规则去进行推导。 = = = he = he has = he has = he has a = he has a pen :=

5、:= := he := a := pen := := has := := pen 上下文无关文法的形式定义 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现 一次。 n例，定义只含+，*的算术表达式的文法 G=， 其中，P由下列产生式组成： E i E E+E E E*E E (E) 4.1 语法分析器的功能 n语法分析的任务是分析一个文法的句子 结构。 n语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)。 源程序 单词符号 取下一单词 . 语法分 析树 词法分 析器 语法分 析器 符号表 编译程序 后续部分 n语法分析的方法： n自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“ 归约”，直到文法的开始符号。即从树 末端开始，构造语法树。所谓归约，是指 根据文法的产生式规则，把产生式的

6、右部 替换成左部符号。 算符优先分析法：按照算符的优先关系 和结合性质进行语法分析。适合分析表达 式。 LR分析法：规范归约 G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + * E i i E EE E n语法分析的方法： n自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发 ，反复使用各种产生式，寻找“匹配“的 推导。 递归下降分析法 预测分析程序 F优点：直观、简单和宜于手工 实现。 4.2 自顶向下分析法 4.2.1 自顶向下分析的一般过程 从S出发采用最左推导，试图逐步推出输入串 ,L(GS)? S作为语法树的根，试图自上而下地为构造一棵语法 树 若叶结点从左向右排列恰好，则表示是文法的 句子，而这棵语法树就是句子的语法结构 若构造不出语法树，则不是文法的句子 【例4.1】 =acb GS: SaAb Acd|c 分析过程是设法建立一 棵语法树,使语法树的末端结 点与给定符号串相匹配. 1.开始:令S为根结点 S 2.用S的右部,符号串去匹配输入串 S aAb 完成一

7、步推导SaAb 检查 a-a匹配 A是非终结符,将匹配任务交给A 3.选用A的右部符号串匹配输入串 A有两个右部,选第一个 aAb cd S 完成进一步推导Acd 检查,c-c匹配,b-d不匹配(失败) 但是还不能冒然宣布 L(GS) 4.回溯 即砍掉A的子树 改选A的第二右部 S aAb c Ac 检查 c-c匹配 b-b匹配 建立语法树,末端结点为acb与输入acb相匹配, 建立了推导序列 SaAbacb acbL(GS) =acb GS: SaAb Acd|c 自顶向下分析方法分类 确定的 不确定的 回溯 1.回溯问题 什么是回溯（backtracking）? 分析工作要部分地或全部地退回去重做叫回溯 造成回溯的条件： 文法中，对于某个非终结符号的规则其右部 有多个选择，并根据所面临的输入符号不能准确 的确定所要选择时，就可能出现回溯。 回溯带来的问题： 严重的低效率，只有在理论上的意义而无实际意义 自顶向下分析存在的主要问题 n例如： 假定有文法G(S): (1) SxAy (2) A*|* 分析输入串x*y(记为)。 Sx*y IP Sx*y IP Axy Sx*y IPAx

8、y Sx*y IPAxy * Sx*y IP Axy * Sx*y IPAxy * Sx*y IP Axy * 效率低的原因 1)语法分析要重做 2)语义处理工作要推倒重来 因此我们要想办法消除回溯！ 2.左递归问题 【例】文法GE： EE+T|T TT*F|F F(E)|i 给出i*i+i自顶向下的分析过程。 左递归文法会使自顶向下分析法陷入死循环 如果文法具有间接左递归，则也将发生上述问题，只不过循 环的圈子兜的更大 要实行自顶向下分析，必须要消除文法的左递归 从左向右扫描源程 序，同时实施最左 推导 n在上述自上而下分析过程中，当一个非终 结符用某一候选式匹配成功时，这种成功 可能只是暂时的。由于这种虚假现象，我 们需要采用更复杂的回溯。 n当最终报告分析不成功时，我们难于知道 输入串中出错的确切位置。 4.3 LL(1)分析法 n构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 1.递归规则：产生式右部有与左部相同的符号 左递归规则：AA 右递归规则：AA 自嵌入递归规则：AA 递归文法 递归文法 2.递归文法：含有递归规则的文法，为 直接递归文法 GS： SL|

9、SL|SD La|b|z D0|1|9 递归文法 ABa BAb 间接递归文法 4.3.1 左递归的消除 n直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为 PP | 其中不以P开头。 我们可以把P的规则等价地改写为如下 的非直接左递归形式： PP PP| 左递归变 右递归 n一般而言，假定P关于的全部产生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些 规则改写成： P1P | 2P | | nP P1P | 2P | | mP | 左递归变 右递归 n例 文法G(E): EET | T TT*F | F F(E) | i 经消去直接左递归后变成 ： ETE E+TE | TFT T*FT | F(E) | i (4.2) PP1 | P2 | | Pm | 1 | 2|n P1P | 2P | | nP P1P | 2P | | mP | n例如文法G(S): SQc|c QRb|b RSa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc 一个文法消除左递归的条件： F不含以为右部的产生式 F不含回路。 n消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列 成P1，P2，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1

《编译原理课件-cha》由会员shaoy****1971分享，可在线阅读，更多相关《编译原理课件-cha》请在金锄头文库上搜索。