编译原理 第五章 语法分析-自下而上分析.ppt

第五章语法分析 自下而上分析 5 1自下而上分析基本问题5 2算符优先分析5 3LR分析法5 4语法分析器的自动产生工具YACC 5 1自下而上分析基本问题 5 1 1归约5 1 2规范归约简述5 1 3符号栈的使用与语法树的表示 5 1 1归约 移进 归约 法 用一个寄存符号的先进后出栈 把输入符号一个一个地移进到栈里 当栈顶形成某个产生式的一个候选式时 即把栈顶的这一部分替换成 归约为 该产生式的左部符号 例子 假定文法GS aAcBeA bA AbB d输入串abbcde归约到S过程 图5 1规约中符号栈的变迁 问题 如果步骤5用规则 2 而不是用规则 3 则会有不同的结果 这就是 可规约串 问题 对可规约串的刻画不同 分析的方法也不同 本课程讨论 最左素短语 和 句柄 两种可规约串刻画方法 5 1 2规范归约简述 短语 直接短语和句柄定义 令G是一个文法 S是文法的开始符号 假定 是文法的一个句型 如果有S A 且A 则 称是句型 相对于非终结符A的短语 特别是 如果有A 则称 是句型 相对于规则A 的直接短语一个句型的最左直接短语称为该句型的句柄 利用句柄规约的例子 句型归约规则abbcde 2 A baAbcde 3 A AbaAcde 4 B daAcBe 1 S aAcBeS 规范规约的一般定义 假设 是文法G的一个句子 我们称序列 n n 1 0是 的一个规范规约 如果此序列满足 1 n 2 0 S 3 对任意的i i 1是从 i经句柄替换的结果 规范推导 最右推导常被称为规范推导规范句型 最右推导的句型称为规范句型规范归约 规范推导的逆过程 最左规约 称为规范归约 5 1 3符号栈的使用与语法树的表示 规范规约的数据结构和动作 采用栈作为语法分析的基本数据结构 符号栈输入串 w S 语法分析对符号栈的使用有四类操作 移进 归约 接受 和 出错处理 任何可规约串的出现必须在栈顶 例5 3 输入串i1 i2 i3的分析步骤 步骤符号栈输入串所用产生式0 i1 i2 i3 预备1 i1 i2 i3 进2 F i2 i3 归 用F i3 T i2 i3 归 用T F4 T i2 i3 进5 T i2 i3 进 13 E 归 用E E T14 E 接受 5 2算符优先分析 5 2 1算符优先文法及优先表构造5 2 2算符优先分析算法5 2 3优先函数5 2 4算符优先分析中的出错处理 算符优先分析法的主要思想 是自下而上的归约过程 但这种归约未必是严格的最左归约 而是借助于两个终结符之间的优先关系来寻找 可归约串 进行归约 算符优先关系定义 1 a b a的优先性低于b 当且仅当G中含有形如P aR 的产生式 而R b 或R Qb 但并不意味b高于a 2 a b a的优先性等于b 当且仅当G中含有形如P ab 的产生式或P aQb 的产生式 但并不意味b等于a 3 a b a的优先性高于b 当且仅当G中含有形如P Rb 的产生式 而R a或R aQ a的优先性高于b 5 2 1算符优先文法及优先表构造 算符文法定义 一个文法 如果它的任一产生式的右部都不含两个相继 并列 的非终结符 即不含如下形式的产生式右部 QR 算符优先文法定义 如果一个算符文法G中的任何终结符对 a b 至多只满足下述三关系之一 a b a b a b 例5 4构造下面算法优先文法的优先表 1 E E T T 2 T T F F 5 3 3 F P F P 4 P E i解 由 4 可得 由 2 3 可得 最后可得表5 1所示优先表 算符优先文法G构造优先关系表的算法 FIRSTVT P 和LASTVT P 定义 FIRSTVT P a P a 或P Qa a VT而Q VN LASTVT P a P a或P aQ a VT而Q VN FIRSTVT P 构造 若有产生式P a 或P Qa 则a FIRSTVT P 若a FIRSTVT Q 且产生式P Q 则a FIRSTVT P 算法程序运算如下 PROCEDUREINSERT P a IFNOTF P a THENBEGINF P a TRUE 把 P a 下推进STACK栈END 主程序 BEGINFOR每个非终结符P和终结符aDOF P a FALSE FOR每个形如P a 或P Qa 的产生式DOINSERT P a WHILESTACK非空DOBEGIN把STACK的栈顶记为 Q a 上托出去 FOR每条形如P Q 的产生式DOINSERT P a ENDOFWHILE END 构造优先表的算法 FOR每条产生式P X1X2 XnDOFORi 1TOn 1DOBEGINIFXi和Xi 1均为终结符THEN置Xi Xi 1IFi n 2且Xi都为终结符 但Xi 1为非终结符THEN置Xi Xi 2 IFXi为终结符 而Xi 1为非终结符THENFORFIRSTVT Xi 1 中的每个aDO置Xi a IFXi为非终结符而Xi 1为终结符THENFORLASTVT Xi 中的每个aDO置a Xi 1END 5 2 2算符优先分析算法 素短语 是一个短语 它至少含有一个终结符 并且 除它自身之外不再含任何更小的素短语 最左素短语 最左边的素短语是最左素短语 例子 对文法 5 3 p p和i是句型p p i的素短语 而p p i本身也是素短语 算符优先文法 算符优先文法 我们把句型 括在两个 之间 的一般形式写成 N1a1N2a2 NnanNn 1 其中 每个ai都是终结符 Ni是可有可无的非终结符 文法G的任何短语是满足如下条件的最左子串Njaj NiaiNi 1aj 1 ajaj aj 1 aj 1 aiai ai 1 算符优先分析算法 k 1S k REPEAT把下一个输入符号读进a中 IFS k VTTHENj kELSEj k 1 WHILES j aDOBEGINREPEATQ S j IFS j 1 VTTHENj j 1ELSEj j 2UNTILS j Q 把S j 1 S k 归约为某个N k j 1 S k NENDOFWHILE IFS j aORS j aTHENBEGINk k 1 S k aENDELSEERROR 调用出错诊察程序 UNTILa 算法分析 没有定义非终结符的优先级 它无法发现单个非终结符组成的 可规约串 所以算符优先分析不是规范规约 优点 速度快 缺点 忽略了非终结符的规约过程 存在一定的危险 5 2 3优先函数 入栈优先函数f和比较优先函数g定义 若Q1 Q2则f Q1 g Q2 采用优先函数的优缺点 便于比较运算 节省空间 由任何两个非终结符都可以进行比较 所以可能掩盖一些问题 从优先表构造优先函数的方法是 对于每个终结符a 包括 令其对应两个符号fa和ga 画一张以fa和ga所有符号为结点的方向图 如果a b 那么 就从fa画一箭弧至gb 如果a b 就画一条从gb到fa的箭弧 对每个结点都赋予一个数 此数等于从该结点能到达结点 包括出发结点自身在内 的个数 赋给fa的数作为f a 赋给gb的数作为g b 检查所构造出来的函数f和g 看它们同原来的关系表是否有矛盾 如果没有矛盾 则f和g就是所要的优先函数 如果有矛盾 那么 就不存在优先函数 5 2 4算符优先分析中的出错处理 错误类型 若找到某一 句柄 此处 句柄 指素短语 但不存在任一产生式 其右部为此 句柄 若在栈顶终结符号与下一输入符号之间不存在任何优先关系 算法5 2 1 对规约中发现的问题 1 找出相近的素短语 2 分析差异 3 给出可能的错误信息 对算符优先分析中的问题 1 如 或 被规约 则检查其两端是否出现非终结符 否则 打印错误信息 缺表达式 2 如i被规约 则检查其左端或右端是否有非终结符 如果有 则给出信息 表达式无运算符连接 3 如果 被规约 则检查是否在括号间有一非终结符 如果没有 则给出信息 括号无表达式 算法5 2 1 采用对输入串进行 改变 插入和删除 等方法 如 当 结束 将 从站顶移去 并给出错误信息 非法左括号 当I或 后跟I或 时 在输入端插入 并给出错误信息 缺少运算符 当表达式以右括号开始 从输入串中删除 并给出错误信息 非法右括号 若站顶有非终结符E 则表达式分析完毕 若为空 则在输入端插入I 给出错误信息 缺少表达式 5 3LR分析法 5 4语法分析器的自动产生工具YACC YACC LALR 1 分析程序的生成器工作方式 Yacc程序的构成 3个部分 中间以 分割声明 变量 常量的声明 正规定义翻译规则 形式如下 其中pi是正规式p1 动作1 p2 动作2 用C语言编写的支持例程 include include tokenNUMBER 此处声明了允许的记号 command exp printf d n 1 command为开始符号 allowsprintingoftheresult exp exp term 1 3 记号可以直接出现在语法规则中 exp term 1 3 term 1 term term factor 1 3 factor 1 factor NUMBER 1 expr 2 main returnyyparse intyylex void intc while c getchar eliminatesblanks if isdigit c ungetc c stdin scanf d allowsforprintingofanerrormessages Yacc分析冲突与消除二义性的规则 在y output中报告调查的分析冲突二义性消除的规则Yacc可以为分析冲突发生产生一个分析程序 并消除二义性指明有二义性的文法相分割开得算符优先及结合性的机制 使得文法描述更简单 left left 表明 有相同的优先权且是左结合的 而 具有更高的优先