第11讲编译原理.ppt

3 7分析器的生成器 3 7 1分析器的生成器Yacc Lex编译器 Lex源程序lex l lex yy c C编译器 lex yy c a out a out 输入流 记号序列 用Lex建立词法分析器的步骤 Yacc程序包括三个部分声明 翻译规则 支持例程 3 7分析器的生成器 例 声明部分 include 常量 变量的声明 tokenDIGIT 3 7分析器的生成器 E E T TT T F FF E digit 例 翻译规则部分line expr n printf d n 1 expr expr term 1 3 term term term factor 1 3 factor factor expr 2 DIGIT 3 7分析器的生成器 E E T TT T F FF E digit 例 支持例程部分yylex intc c getchar if isdigit c yylval c 0 returnDIGIT returnc 3 7分析器的生成器 E E T TT T F FF E digit 3 7分析器的生成器 3 7 2用Yacc处理二义文法解决分析动作冲突的两大默认规则 对于归约 归约冲突 选择在Yacc程序中最先出现的那个产生式归约对于移进 规约冲突 优先移进 3 7分析器的生成器 3 7 2用Yacc处理二义文法例台式计算器输入一个表达式并回车 显示计算结果 也可以输入一个空白行 lines linesexpr n lines n eE E E E E E E E E E E number 3 7分析器的生成器 include include defineYYSTYPEdouble 将栈定义为double类型 tokenNUMBER left left rightUMINUS lines linesexpr n lines n eE E E E E E E E E E E number 3 7分析器的生成器 lines linesexpr n printf g n 2 lines n expr expr expr 1 3 expr expr 1 3 expr expr 1 3 expr expr 1 3 expr 2 expr precUMINUS 2 NUMBER lines linesexpr n lines n eE E E E E E E E E E E number 3 7分析器的生成器 yylex intc while c getchar if c isdigit c ungetc c stdin scanf lf lines linesexpr n lines n eE E E E E E E E E E E number 3 7分析器的生成器 3 7 3Yacc的错误恢复编译器设计者的工作决定哪些 主要的 非终结符将有错误恢复与它们相关联加入A error 的错误产生式 其中A是主要非终结符 是文法符号串为这样的产生式配上语义动作Yacc把错误产生式当作普通产生式处理 3 7分析器的生成器 遇到语法错误时从栈中弹出状态 直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error 移进 栈若 为 直接进行产生式规约 并执行相关的语义动作 忽略若干输入符号 直至发现能回到正常处理的符号为止 若 不为 找到 把 移进栈把error 归约为A 恢复正常分析 3 7分析器的生成器 lines linesexpr n printf g n 2 lines n error n printf 重新输入上一行 yyerrok 语法分析内容总结 文法和语言的基本知识自上而下的分析方法 预测分析 非递归的预测分析 LL 1 文法自下而上的分析方法 SLR 1 方法 规范LR 1 方法和LALR 1 方法 语法分析内容总结 自上而下分析LL 1 文法判定原则FIRST FOLLOW集的计算 重点 LL 1 文法判定方法LL 1 分析实现方法递归函数实现非递归的预测分析实现先求FIRST FOLLOW集画预测分析表 语法分析内容总结 书后3 19 3 20等题目都是判断是否属于某类文法 判定文法是否是LL 1 文法步骤如下 如果有以下两种情况一定不是左递归公共左因子如果不是 则改写文法消除左递归提取左因子改写后进行LL 1 分析 语法分析内容总结 例1文法G S S aSb PP bPc bQcQ Qa a 1 判断这个文法是不是LL 1 的 2 消除左递归 提取左因子之后的文法G 是否是LL 1 的 语法分析内容总结 解答 首先 G S 不是LL 1 的 G S S aSb PP bPc bQcQ Qa a 语法分析内容总结 例1解答 提取左因子 将P bPc bQc变为P bP P Pc Qc 消除左递归 将Q Qa a变为Q aQ Q aQ G S S aSb PP bPc bQcQ Qa a 语法分析内容总结 例1解答 判定文法G S 是否LL 1 步骤 计算FIRST FOLLOW集 G S S aSb PP bP P Pc QcQ aQ Q aQ 语法分析内容总结 FIRST S a b FIRST P b FIRST P a b FIRST Q a FIRST Q a FOLLOW S b FOLLOW P b c FOLLOW P b c FOLLOW Q c FOLLOW Q c G S S aSb PP bP P Pc QcQ aQ Q aQ 是LL 1 的 语法分析内容总结 例2文法G E E TT TE F F a aF 1 判断这个文法是不是LL 1 的 2 消除左递归 提取左因子之后的文法G 是否是LL 1 的 语法分析内容总结 例1解答 提取左因子 消除左递归后文法变为G E E TT F T T ET F aF F F G S E TT TE F F a aF 语法分析内容总结 FIRST E FIRST T a FIRST T FIRST F a FIRST F a FOLLOW E FOLLOW T FOLLOW T FOLLOW F FOLLOW F G E E TT F T T ET F aF F F 不是LL 1 文法 通过提取左因子和消除左递归的方法 并不一定能够把文法改写为一个LL 1 文法 语法分析内容总结 左递归的消除G S S Qc cQ Sa a间接左递归 语法分析内容总结 左递归的消除G S S Qc cQ Sa a这是一类间接左递归S Sac ac cQ Sa a 语法分析内容总结 左递归的消除G S S Qc cQ Sa a间接左递归S Sac ac cQ Sa aS acS cS S acS Q Sa a 语法分析内容总结 自下而上分析部分知识点SLR的DFA的构造及分析表的构成初始项目集合的产生 拓广文法 能够识别同一符号的项目都转移到同一集合中求闭包过程中每一个 后面的非终结符都要重新考虑是否已经在状态中列出对产生式A 规约 ri 写在FOLLOW A 集合中元素对应的位置 语法分析内容总结 LR LALR的构造方法 在SLR的基础上加上搜索符 搜索符的求法 根据造成目前项目出现的那个父项目来求 求闭包的过程中可能出现要添加的项目已经存在 但是搜索符不同的情况 相当于其父项目已经改变 此时需要再求一遍搜索符 SLR LR LALR的区别及判别方法通过构造DFA 看其中的状态是否有冲突 移进 规约 或 规约 规约 若有冲突则不属于该文法类型 通过构造分析表 看其中某项是否有冲突 语法分析内容总结 文法G S S AaS bAe BeS bBaA dB d判断这个文法类型是SLR 1 LR 1 还是LALR 1 补充题1 下面的二义文法描述命题演算公式的语法 为它写一个等价的非二义文法S SandS SorS notS p q S 非二义文法的产生式如下 E EorT TT TandF FF notF E p q 补充题1 下面的二义文法描述命题演算公式的语法 为它写一个等价的非二义文法S SandS SorS notS p q S 非二义文法的产生式如下 E EorT TT TandF FF notE E p q 补充题1 下面的二义文法描述命题演算公式的语法 为它写一个等价的非二义文法S SandS SorS notS p q S 非二义文法的产生式如下 E EorT TT TandF FF notE E p qnotpandq有两种不同的最左推导 补充题2 设计一个文法 字母表 a b 上a和b的个数相等的所有串的集合二义文法 S aSbS bSaS abababab 补充题2 设计一个文法 字母表 a b 上a和b的个数相等的所有串的集合二义文法 S aSbS bSaS abababab二义文法 S aB bA A aS bAAB bS aBB 补充题2 设计一个文法 字母表 a b 上a和b的个数相等的所有串的集合二义文法 S aSbS bSaS abababab二义文法 S aB bA A aS bAAB bS aBBBB bSbS的选择bbabbbab非二义文法 S aBS bAS A a bAAaabbababB b aBB 补充题3 试说明下面文法不是LR 1 的 L MLb aM 补充题4 下面的文法不是LR 1 的 对它略做修改 使之成为一个等价的SLR 1 文法program begindeclist statementenddeclist d declist dstatement s statement s 补充题4 下面的文法不是LR 1 的 对它略做修改 使之成为一个等价的SLR 1 文法program begindeclist statementenddeclist d declist dstatement s statement s该文法产生的句子的形式是begind d d s s send 补充题4 下面的文法不是LR 1 的 对它略做修改 使之成为一个等价的SLR 1 文法program begindeclist statementenddeclist d declist dstatement s statement s该文法产生的句子的形式是begind d d s s send当d在栈顶 是下一个输入的时候不知该移进还是规约 补充题4 下面的文法不是LR 1 的 对它略做修改 使之成为一个等价的SLR 1 文法program begindeclist statementenddeclist d declist dstatement s statement s该文法产生的句子的形式是begind d d s s send修改后的文法如下 prog