第四章语法分析t整理.ppt

《第四章语法分析t整理.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析t整理.ppt（150页珍藏版）》请在金锄头文库上搜索。

1、第四章语法分析 南京大学计算机系戴新宇2019 3 1 概要 语法分析器上下文无关文法语法分析技术自顶向下自底向上语法分析器生成工具 2 引言 程序设计语言源程序的构成文法 一种用于描述程序设计语言语法的表示方法 能够自然地描述程序设计语言构造的层次化语法结构 文法给出了一个程序设计语言的精确易懂的语法规约可以基于文法构造语法分析器 帮助确定源程序的语法结构语法结构有助于把源程序翻译为正确的目标代码 以及检测导语法错误 文法的扩展性StandardC GrammarJavaSE7Grammar 3 语法分析器 What 输入 词法分析器输出的词法单元序列输出 语法树表示语法分析器的类型 通用型

2、 CKY Earley 自顶向下 通常处理LL文法自底向上 通常处理LR文法 4 语法分析器 Why 语法分析器功能 验证输入源程序的合法性 并输出良构程序的语法结构对于病构的程序 能够报告语法错误 并进行错误回复写入符号表 类型检查 语义分析 翻译生成中间代码等往往和语法分析过程交错完成 实践中往往和语法分析放入一个模块 图上用 前端的其余部分 表示上述活动 5 文法 本书特指上下文无关文法 ContextFreeGrammar CFG 程序设计语言中往往存在嵌套结构上下文无关文法是一种能够很好描述程序设计语言的表示方法stmt if expr stmtelsestmtexpr stmt 6

3、 CFG的定义 一个CFG由以下几个部分构成终结符号组成串的基本符号 与 词法单元名字 同义非终结符号语法变量 表示特定串的集合给出了语言的层次结构 这种层次结构是语法分析和翻译的关键一个开始符号某个特定的非终结符号 其表示的串集合是这个文法生成的语言一组产生式描述将终结符合和非终结符号组合成串的方法产生式左部 头 是一个非终结符号符号 一个由零个或多个终结符号与非终结符号组成的产生式右部 体 7 用于描述算术表达式的文法定义 8 S NPVPVP VNPNP NAMENP ARTNNAME JohnV ateART theN cat 符号表示约定 终结符号 ab 3id 非终结符号 ABC

4、S stmt文法符号 XY 终结符号串 uvw 文法符号串 不同可选体 1 2 3 开始符号 S 9 推导 产生式又可称为重写规则 Rewritingrule 从开始符号出发 每个重写步骤把一个非终结符号替换为它的某个产生式的体 e g E E E id 称为从E到 id 的推导 这个推导说明了 id 是表达式E的一个实例 或者说由E产生 推导的一般性定义 假设一个产生式A A 符号表示 通过一步推导出 10 推导 续 推导序列 1 2 n 称为 1推导到 n 记作 1 n 指经过零步或多步推导 对于任意串如果表示经过一步或多步推导出句型 如果从文法的开始符号S开始 则称 是G的一个句型 句子

5、 不包括非终结符号的句型 语言 句子的集合 w Sw 由文法G生成的语言被称为上下文无关语言L G 文法的等价性 两个文法生成相同语言 则两文法等价 11 推导例子 12 推导中的问题 从推导的角度看 语法分析的任务是 接受一个终结符号串作为输入 找出从文法的开始符号推导出这个串的方法 推导中可能遇到的两个问题每一步替换哪个非终结符号若以这个非终结符号为头的产生式有多个 用哪个产生式的右部替换 13 非终结符号的替换顺序 通常使用两种方式进行推导最左推导 总是选择每个句型的最左非终结符号 记作最右推导 总是选择最右边的非终结符号 记作每个最左推导步骤可以写成 是应用的产生式如果经过最左推导得到

6、 记作最左句型 S是文法G的识别符号 如果 则是G的最左句型 14 语法分析树 是推导的图形表示形式 树上看不出来推导的顺序能够反映串的语法层次结构语法分析树内部节点 对应于一个非终结符号子节点 对应于其父节点为头的产生式体叶子节点 可以是终结符号或非终结符号 从左到右排列可以得到一个句型 称为这棵树的结果 15 S NP VP NAME John V NP ate ART N the cat S NPVPVP VNPNP NAMENP ARTNNAME JohnV ateART theN cat 推导和语法树 对于推导中的每个句型 我们都可以构造出一个结果为的语法树 17 推导与语法树例子

7、18 词法分析和语法分析比较 19 文法比正则表达式描述能力更强正则表达式描述词法单元比较简洁基于正则表达式构造的词法分析器效率更高正则表达式适合描述词法结构 文法适合描述嵌套结构 补充 文法的类别 Chomsky文法类0型文法 短语结构文法 1型文法 上下文相关文法 A 2型文法 上下文无关文法 A 3型文法 正则文法 A t A tB 20 上下文无关文法和正则表达式 CFG的表达能力更强每个正则表达式都可以用一个上下文无关文法来描述 反之不成立每个正则语言都是一个上下文无关语言 反之不成立正则表达式 a b abb等价于文法 21 为NFA构造等价文法 22 上下文无关文法和正则表达式

8、正则表达式上下文无关文法 上下文无关文法正则表达式 L anbn n 1 描述该语言的文法 可以用正则表达式描述该语言吗 文法及其生成的语言 语言是由文法的开始符号出发 能够推导得到的所有句子的集合 文法G S aS a b L G ai a b i 0 文法G S aSb abL G anbn n 1 文法G S S S L G 所有具有对称括号对的串 如何验证文法G所确定的语言L证明G生成的每个串都在L中证明L中的每个串都能被G生成实质上回归到了原始的定义 证明采用数学归纳法 24 文法的设计 在进行高效的语法分析之前 需要对文法做以下处理消除二义性文法的二义性 文法可以为一个句子生成多颗

9、不同的树消除左递归左递归 文法中一个非终结符号A使得对某个串 存在一个推导 则称这个文法是左递归的 提取左公因子 25 二义性文法 如果一个文法可以为一个句子生成多颗不同的语法分析树 则该文法为二义性文法 通常情况下 我们需要无二义性的文法 26 消除文法的二义性 把二义性文法改写成无二义性文法 27 消除文法的二义性 续 28 消除文法的二义性 续 改写文法 基本思想 在一个then和一个else之间出现的语句必须是 已匹配的 也就是说then和else中间的语句不能以一个尚未匹配的then结尾 解决方案 引入新的非终结符号 用来区分是否是成对的then else 29 消除文法的二义性示例

10、2 消除左递归 左递归 文法中一个非终结符号A使得对某个串 存在一个推导 则称这个文法是左递归的如果存在A A 则称为立即左递归自顶向下的语法分析技术不能处理左递归的文法立即左递归消除 31 A A A A A A 立即左递归消除示例 32 消除立即左递归步骤 首先对A产生式分组 所有 i不等于 i不以A开头 然后将这些产生式替换为 33 消除多步左递归 消除立即左递归的方法并不能消除因为两步或多步推导而产生的左递归文法 S Aa b A Ac Sd S Aa Sda如何消除 34 消除算法 算法原理 给非终结符号排序 A1 A2 An如果只有Ai Aj iAj i j 代入Aj的当前产生式

11、若替换后有Ai的直接左递归 再消除输入 没有环AiAi和A 输出 一个等价的无左递归的文法 35 消除算法 示例 S Aa b A Ac Sd 排序SAi 1 没有处理i 2 替换A Sd中的S 得到A Ac Aad bd 消除立即左递归 36 提取左公因子 在推导的时候 不知道该如何选择 自顶向下算法会详细描述 37 A 1 2 A A A 1 2 提取左公因子算法 输入 文法G输出 一个等价的提取了左公因子的文法方法 对于每个非终结符号A 找出它的两个或多个可选项之间的最长公共前缀 且 那么将A所有的产生式A 1 2 n 替换为A A A 1 2 n 38 提取左公因子 39 自顶向下分析

12、技术 自顶向下分析可以被看作是为输入串构造语法分析树的问题 也可以看作一个寻找输入串的最左推导的过程 40 id id id的自顶向下分析 41 自顶向下语法分析 一种通用的递归下降分析框架由一组过程组成 每个非终结符号对应一个过程程序的执行从开始符号对应的过程开始每个过程的功能是 选择一个产生式体 扫描相应的句子 若遇到非终结符号 调用该符号对应的过程 42 自顶向下分析技术 问题 在推导的每一步 对非终结符号A 应用哪个产生式 以可能产生于输入串相匹配的终结符号串 在递归下降的框架中 对于非终结符号A 选择哪一个产生式 递归下降分析过程示例 输入串w cad文法 S cAdA ab a 4

13、4 递归下降过程示例 续 可能需要回溯 或者说 可能需要重复扫描输入 在回到A时 我们必须把输入指针重新设置到位置2 即我们第一次尝试展开A时该指针指向的位置 这意味着A的过程必须将输入指针存放在一个局部变量中 如果文法中存在左递归 回溯 盲目地试 显然是最愚蠢的办法 45 预测分析技术 一种确定性的 无回溯的分析技术在每一步选择正确的产生式 46 例1 文法G S S pAS qBA cAdA a输入串W pccadd 预测分析技术 续 47 例2 文法G S 为 S ApS BqA a cAB b dB输入W ccap 预测分析技术 续 通过在输入中向前看固定多个符号来选择正确的产生式通常

14、情况下 我们只需要向前看一个符号给出两个与文法相关的两个函数FIRSTFOLLOW基于上述两个函数 可以根据下一个输入符号来选择应用哪个产生式 48 FIRST 定义 可从 推导得到的串的首符号的集合 其中 是任意的文法符号串 如果 那么 也在FIRST 中 FIRST函数的意义如果两个A产生式A 其中First 和First 是不相交的集合 下一个输入符号是a 若a First 则选择A 若a First 则选择A 49 First X 的计算 对于文法符号X的FIRST X 通过不断应用下列规则 直到没有新的终结符号或者 可以加入到任何FIRST集合为止 如果X是终结符号 那么FIRST

15、X X 如果X是非终结符号 且有规则X a 那么将a添加到FIRST X 中 如果X 那么 也在FIRST X 中 对于产生式X Y1Y2 Yn 把FIRST Y1 中的非 符号添加到FIRST X 中 如果 在FIRST Y1 中 把FIRST Y2 中的非 符号添加到FIRST X 中 如果 在FIRST Yn 中 把 添加到FIRST X 中 50 First 的计算 续 对于文法符号串 X1X2 Xn的First集合向First X1X2 Xn 加入First X1 中所有的非 符号 如果 在First X1 中 再加入First X2 中的所有非 符号 如果 在First X1 和F

16、irst X2 中 再加入First X3 中的所有非 符号 依次类推 如果对所有的i 1到n 都在First Xi 中 则 加入First X1X2 Xn 中 51 First的计算示例 First F First T First E id First E First T First TE First T id First TE 52 FOLLOW函数 对于非终结符号A FOLLOW A 定义为可能在某些句型中紧跟在A右边的终结符号的集合 S Aa 终结符号a Follow A 如果A是某些句型的最右符号 那么 Follow A 是特殊的输入串 结束标记 FOLLOW函数的意义 如果A 当 或 时 FOLLOW A 可以帮助我们做出选择恰当的产生式例如 ifA b属于FOLLOW A 如果 则若当前输入符号是b 可以选择A 因为A最终到达了 而且后面跟着b 53 文法G S 输入bcdS AB CDA aD C cDB bCD d FOLLOW计算 计算各个非终结符号A的FOLLOW A 集合 不断应用下列规则 直到没有新的终结符号可以被加入到任意FOLLOW集合中 将 放入FOLL