哈工大编译原理4-1.ppt

1 第四章语法分析 该讲语法分析了 这可是很重要的章节 2005 3 15 计算机学院辛明影 2 主要内容 本章将重点介绍典型的语法分析方法及相关的概念和实现技术 语法分析分为 自上而下 自下而上 递归下降分析法 LL 1 预测分析法 推导 算符优先分析法 LR分析法 归约 从根向叶的方向建立分析树 从叶向根的方向建立分析树 2005 3 15 计算机学院辛明影 3 4 1语法分析器的功能 词法分析器 语法分析器 语义分析 符号表 源程序 单词符号 语法树 中间表示 完成的任务 对词法分析器产生的单词符号进行处理 输出分析树 与单词相关的信息记录到符号表中 类型检查 错误处理 4 1 1语法分析器任务 2005 3 15 计算机学院辛明影 4 4 1 2相关约定 一 符号的使用约定 1 终结符 字母表中比较靠前的小写字 如a b c 操作符 如 等 标点符号 如括号 逗号等 数字0 1 9 黑体串 如if id等 2005 3 15 计算机学院辛明影 5 2 下列符号是非终结符 字母表中比较靠前的大写字 如A B C 字母S 常用来表示开始符号 小写斜体名字 如expr stmt 2005 3 15 计算机学院辛明影 6 3 字母表中比较靠后的大写字母 如X Y Z等 用来表示文法符号 也就是说 可以是终结符 也可以是非终结符 4 字母表中比较靠后的小写字母 如u v z等 表示终结符的串联 5 小写希腊字母 等表示文法符号的串 所以一个产生式可写作 A 2005 3 15 计算机学院辛明影 7 4 2自顶向下分析法 4 2 1使用的技术 存在的问题及解决方法 2005 3 15 计算机学院辛明影 8 一 推导 推导 就是用产生式的右部的串来代替左部的非终结符 事实上推导给出了自顶向下构成分析树过程的精确描述 例 有描述算术表达式的文法G 字符串 id id 是该文法的句子 其推导过程如下 E E E E E E E id 2005 3 15 计算机学院辛明影 9 E 几个约定 E E E E id E id id E EE推导出 E 一步或多步推导 零步或多步推导 2005 3 15 计算机学院辛明影 10 最左推导 每一步都坚持替换当前句型中最左非终结符的推导 最右推导 每一步都坚持替换当前句型中最右非终结符的推导 也称为规范推导 句子 S w称终结符串w是文法G句子 句型 S 称 是文法G的句型 语言 L G w S w 2005 3 15 计算机学院辛明影 11 二 语法树 语法描绘了如何从文法的开始符号推导出一个句子的过程 语法树可以看成是推导的图形表示 但它不能显示出替代的顺序 前面句子 id id 推导过程所对应的分析树如下 2005 3 15 计算机学院辛明影 12 E E E E E E E E E E E E E id E E E E E E E id id E 2005 3 15 计算机学院辛明影 13 4 如杲A是某个内结点的非终结符标记 A1 A2 An是该结点从左到右排列的所有子结点的标记 则A A1A2 An是一个产生式 3 每个内结点由一个非终结符标记 1 树根标记为开始符号 2 每个叶结点由终结符或者 标记 语法具有如下特性的树 2005 3 15 计算机学院辛明影 14 语法树的叶结点从左到右的排列 刚好是这个文法所产生的语言的一个句子 一个文法生成的语言就是它的某个分析树所生成的句子的集合 为给定的终结符串 句子 构造一棵分析树的过程称为这个串 句子 的语法分析 parsing 2005 3 15 计算机学院辛明影 15 三 二义性 句子id id id有两棵分析树与之对应 EE EidE Eidid EE EE Eididid 2005 3 15 计算机学院辛明影 16 给定一个文法G 如果L G 中存在一个具有两棵或两棵以上分析树的句子 很显然 描述算术表达式的文法GE E E E E E E id是一个二义性文法 造成二义性的原因是 文法中没有体现出结合率和优先级 我们就称该文法为二义性的 G也叫二义性文法 2005 3 15 计算机学院辛明影 17 大多数的语法分析器都要求文法是无二义性的 消除二义性 可以通过改写文法来消除二义性 例 stmt ifexprthenstmt ifexprthenstmtelsestmt other 2005 3 15 计算机学院辛明影 18 通过例子ifE1thenifE2thenS2elseS3很容易证明这是一个二义性文法 s if E then S else S if E then S 2005 3 15 计算机学院辛明影 19 S if E then S if E then S else S 2005 3 15 计算机学院辛明影 20 在程序设计语言中 我们常常采用 最近匹配 原则来解决这种二义性 文法改写出为 stmt matched stmt unmatched stmtmatched stmt ifexprthenmatched stmtelsematched stmt otherunmatched stmt ifexprthenmatched stmtelseunmatched stmt ifexprthen stmt 2005 3 15 计算机学院辛明影 21 四 消除左递归 如果文法G具有一个非终结符A使得对某个字符串 存在推导A A 例 下面是描述算术表达式的算法S EE E T TT T F FF E id 为句子id id id构造分析树SE TE TE T 则称文法G是左递归的 如果A A 则称文法G是直接左递归的 2005 3 15 计算机学院辛明影 22 左递归会使分析进入到无限循环之中 消除简单左递归的方法 对于含有左递归的产生式A A 可用下面的非左递归的产生式代替 A A A A 2005 3 15 计算机学院辛明影 23 例 下面是描述算术表达式的算法S EE E T TT T F FF E id 消除E和T的直接左递归 得到 S E E TE E TE T FT F E id T FT 2005 3 15 计算机学院辛明影 24 对于一般情况而言 若某一文法G的产生式具有如下形式 则可用如下方法消除左递归 A A 1 A 2 A m 1 2 n A 1A 2A nA A 1A 2A mA 很容易证明改造前后的文法是等价的 2005 3 15 计算机学院辛明影 25 例 文法G P P Q aP aQ Q P P试消除左递归 2005 3 15 计算机学院辛明影 26 消除左递归后 方法改为 P Q aP aQ P Q 2005 3 15 计算机学院辛明影 27 S Qc cQ Rb bR Sa a S 这样的递归无法用前面的方法消除 对于含有间接左递归的文法 Qc Rbc Sabc 出现了左递归 2005 3 15 计算机学院辛明影 28 消除左递归的一般算法 输入 无循环推导和 产生式的方法G 输出 与G等价的无左递归文法 算法 2005 3 15 计算机学院辛明影 29 1 以某种顺序排列非终结符A1A2 An2 fori 1tondobeginforj 1toi 1dobegin改写Ai Aj 规则 方法如下 如果Aj 1 2 k则Ai 1 2 n end消除Ai中的所有直接左递归End3 化简由2所得文法 2005 3 15 计算机学院辛明影 30 S Qc cQ Rb bR Sa a 对如下文法消除左递归 1 将非终结符排序为R Q S 2 R不存在左递归 将R代入Q Q Sab ab b 3 Q不存在左递归 将Q代入SS Sabc abc bc c 4 消除直接左递归后 得文法 2005 3 15 计算机学院辛明影 31 S abcS bcS cS S abcS Q Rb bR Sa a 5 化简文法 S abcS bcS cS S abcS 2005 3 15 计算机学院辛明影 32 五 回溯 提取左因子 为句子ifE1thenS1elseS2构造一棵语法树 文法 stmt ifexprthenstmt S ifexprthenstmtelsestmt stmtifexprthenstmtE1if thenstmt 回溯 2005 3 15 计算机学院辛明影 33 造成这种情况的原因是产生式具有相同的首符号 从而导致不清楚该用哪个来替换非终结符 可通过改写产生式来推迟这种决定 直到看见足够多的输入符号 可以作出正确选择为止 上例可改为 stmt ifexprthenstmtS SS elsestmt 2005 3 15 计算机学院辛明影 34 stmtifexprthenstmtS E1elsestmt 提取左因子算法 输入 文法G 输出 一个等价的提取了左因子的文法 方法 对于A 1 2 n 可改写为 A A A 1 2 n 2005 3 15 计算机学院辛明影 35 例 文法G P P Q aP aQ Q P P试消除回朔 2005 3 15 计算机学院辛明影 36 六 FIRST与FOLLOW集 1 FIRST集 回朔和左递归搞的人真烦哪 怎样才能做到每次选的产生都正确呢 郁闷哪 FIRST a a a VT 如果 则 FIRST 例 stmt ifexprthenstmtS S elsestmtS 定义 FIRST 是由 推导出的所有的第一个终结符号组成的集合 即 2005 3 15 计算机学院辛明影 37 算法 求FIRST X 的算法描述如下 例 First ifexprthenstmtS if First elsestmt else First 2005 3 15 计算机学院辛明影 38 如果X是非终结符 且X Y1Y2 Yk 则a Y1 则FIRST Y1 中的所有符号都在FIRST X 中 b Y1Y2 Yi 1 FIRST Yi 中的所有符号都在FIRST X 中 如果X 是一个产生式 则 FIRST X 如果X是终结符 则FIRST X 是 X c Y1Y2 Yk 则 FIRST X 2005 3 15 计算机学院辛明影 39 例1 有文法G S S BAA BSA dB aAB bSB c试写出其FIRST集 First B a First B b First B c First S First BA a b c First A First BS a b c First A d 2005 3 15 计算机学院辛明影 40 2 FOLLOW集 定义 FOLLOW A 是由所有句型中紧跟在A后面的终结符a组成的集合 FOLLOW A a S Aa a Vt 算法 FOLLOW S 对于A B 的产生式 则FIRST 放入FOLLOW B 对于A B或A B 其中 则将FOLLOW A 放入FOLLOW B 中 2005 3 15 计算机学院辛明影 41 例1 对于文法GE TE E TE T FT T FT F E id求其FIRST和FOLLOW集 解 FIRST F id FIRST T FIRST T FIRST F id FIRST E FIRST E FIRST T id 2005 3 15 计算机学院辛明影 42 FOLLOW F FIRST T FOLLOW T FOLLOW E FOLLOW E FOLLOW E FOLLOW T FOLLOW T FIRST E FOLLW E 2005 3 15 计算机学院辛明影 43 例 A aAA bAA cABA B dC 对句子abcd 进行分析 A FIRST aA a FIRST bA b FIRST cA c FIRST FOLLOW A d aA abA abcAB abcB abcdC First和Follow的用处 2005 3 15 计算机学院辛明影 44 七 LL 1 文法 一个上下文无关文法若满足下列条件 我们就称它为LL 1 文法 文法不含左递归 文法中每个非终结符A的各个产生式的首终结符集两两不相交 即 若A 1 2 n则FIRST i FIRST j 文法中每个非终结符A若其首字符集中含有 则FIRST i FOLLOW A 2005 3 15 计算机学院辛明影 45 这里LL 1 中的 只有LL 1 文法 才可以实现确定的自顶向下语法分析 LL 1 的定义里保证了每一步分析的确定性 你看出不了吗 第一个L表示从左到右扫描输入串 第二个L表示最左推导 1表示分析时每步只需向前查看一个符号 2005 3 15 计算机学院辛明影 46 4 2 2递归下降法 为每一个非终结符编制一个递归下降过程 方法 过程的名字就产生式左部的非终结符 过程体则是按产生式的右部符号顺序编写的 每匹配一个终结符 则再读入下一个输入符号 对于产生式右部的每个非终结符 则递归调用相应过程 2005 3 15 计算机学院辛明影 47 例 对于文法GE TE E TE T FT T FT F E id其递归下降分析程序编写如下 PROCEDUREEBEGINT E END PROCEDURETBEGINF T END 2005 3 15 计算机学院辛明影 48 PROCEDUREE IFSYM THENADVANCE T E END PROCEDURET IFSYM THENADVANCE F T END 这一步实际上就匹配了一个输入符号 2005 3 15 计算机学院辛明影 49 PROCEDUREFIFSYM id THENADVANCE ELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCE ELSEERRORENDELSEERROR 当调用一个过程的时候 就相当于进行了一步推导 2005 3 15 计算机学院辛明影 50 4 2 3LL 1 预测分析法 一 特征 根据当前输入符号 为当前要处理的非终结符选择产生式 二 表驱动的预测分析器包含 一个输入缓冲区一个栈一张分析表一个输出流 要求 文法是LL 1 的 2005 3 15 计算机学院辛明影 51 三 预测分析器模型 a b 预测分析程序 XYZ 分析表M 输出 是输入串的结束标记 也是栈底符号 2005 3 15 计算机学院辛明影 52 四 预测分析表M 预测分析表是一个M A a 形式的矩阵 其中 A为非终结符 a为终结符或 M A a 中存放着一条关于A的产生式 指出当A面临a时所应采取的候选 M A a 中也可能存放一条 出错标志 指出 不应该面临a 2005 3 15 计算机学院辛明影 53 例 对于文法G1E TE 2E TE 3T FT 4T FT 5F E id其预测分析表为 解 FIRST F id FIRST T FIRST T FIRST F id FIRST E FIRST E FIRST T id 2005 3 15 计算机学院辛明影 54 FOLLOW F FIRST E FIRST T id FOLLOW T FOLLOW T FIRST E FOLLW E FOLLOW T FIRST E FOLLOW E FOLLOW E FOLLOW E 2005 3 15 计算机学院辛明影 55 非终结符 输入符号 E E T T F id E TE E TE E TE E E T FT T FT T T T T FT F E F id 预测分析表 124页 2005 3 15 计算机学院辛明影 56 预测分析表的构造 fori A dofora FIRST beginM A a A endif FIRST forb FOLLOW A M A b A 将M的空白处均置为error 即A 2005 3 15 计算机学院辛明影 57 非终结符 输入符号 E E T T F id E TE E TE E TE E E T FT T FT T T T T FT F E F id 预测分析表 124页 FIRST E id FIRST E FOLLOW E FIRST T id FIRST T FOLLOW T FIRST F id 2005 3 15 计算机学院辛明影 58 五 预测分析器的工作方式 3 如果X a 分析成功 1 如果X a 则POP advance 2 如果X Vn 查M X a 表若M X a X UVW 则用WVU替换栈顶 若M X a error 则调用错误恢复程序 当前栈顶符号X和当前输入符号为a 则语法分析器的动作为 2005 3 15 计算机学院辛明影 59 预测分析程序的算法 输入 串w和文法G的分析表M输出 如果w属于L G 则输出w的最左推导 否则报错 方法 开始时 S在栈里w 在输入缓冲区 令ip指向w 的第一个符号令X是栈顶符号 a是ip指向的符号 2005 3 15 计算机学院辛明影 60 RepeatIfX Vt thenifX athenpopX ip指向下一个符号elseerror ElseifM X a X Y1Y2 YkthenpopX pushYkYk 1 Y1 输出X Y1Y2 YkUntilX ifX a 接收elseerror 2005 3 15 计算机学院辛明影 61 句子id id id的分析过程 栈 输入 输出 E E T E T F E T E E T id E T E T E T F E T id E T E T F E T id E T E E T F id id id id id id id id id id id id id id id id id id id id id id id id id id id id E TE T FT F id T E TE T FT F id T FT F id T E 2005 3 15 计算机学院辛明影 62 练习 文法G S S S aT aTT aT 消去左递归 求FIRST和FOLLOW写出句子a a a a的分析过程 解 S aTS S aTS T aT 2005 3 15 计算机学院辛明影 63 FIRST S a FIRST S FIRST T FOLLOW S FOLLOW S FOLLOW T 126页 2005 3 15 计算机学院辛明影 64 a SS aTS S S aTS S TT T aTT 2005 3 15 计算机学院辛明影 65 句子a a a a的分析过程 栈 输入 输出 S S Ta S T S Ta S T S S S Ta S T S Ta S T S a a a a a a a a a a a a a a a a a a a a a a a a S aTS T T T aT T S aTS S aTS S end 2005 3 15 计算机学院辛明影 66 七 预测分析的错误恢复 1 发现错误 栈顶的终结符与当前输入符不匹配 非终结符A位于栈顶 面临的输入符为a 但分析表M的M A a 为空 2 应急 恢复策略跳过输入串中的一些符号直至遇到 同步符号 为止 2005 3 15 计算机学院辛明影 67 3 同步符号的选择 把FOLLOW A 中的所有符号作为A的同步符号 跳过输入串中的一些符号直至遇到这些 同步符号 把A从栈中弹出 可使分析继续 把FIRST A 中的符号加到A的同步符号集 当FIRST A 中的符号在输入中出现时 可根据A恢复分析 2005 3 15 计算机学院辛明影 68 可以把表示语句开始的一些关键字加入到同步记号集中 如果栈顶的终结符不能被匹配 就可以弹出该终结符 此时相当于把所有的符号都看作同步符号 用synch表示由相应非终结符的FOLLOW集得到的同步符号 则前面的预测分析表变为 2005 3 15 计算机学院辛明影 69 FOLLOW F FIRST E FIRST T FOLLOW T FOLLOW T FIRST E FOLLW E FOLLOW T FIRST E FOLLOW