编译原理第四章 语法分析和语法分析程序.ppt

编译原理 语法分析和语法分析程序 编译程序的逻辑结构 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 信息表管理程序 错误检查和处理程序 源程序 目标代码 编译程序的组织 语法分析程序 语义分析及代码生成程序 词法分析程序 整理目标程序 源程序 目标程序 停机 开始 语法树 语法树 分析树 推导树 每个结点均有标记 VN VT根的标记为开始符号S内部结点标记 VN若以A为标记的结点有k个孩子分别标记为X1 X2 Xk 则A X1X2 Xk必然是G的一个产生式文法的二义性 一个句子对应多个语法树对无二义文法 一个句子只对应一个语法树 两类语法分析方法 按产生语法树的方向分自顶向下递归下降法LL自底向上算符优先法LR 自顶向下的语法分析例子 文法G E E T EATT F TMFF E iA M 建立从E到i i i的最左推导左递归与死循环 E EAT 必须消除左递归 直接左递归的消除 前提 掌握算法2 1 2 6消除无用符号和产生式 产生式和单产生式直接左递归的形式 A A V 直接左递归的消除方法一 将A A 改写为A 方法二 引入A 改写为A A 和A A 一般化 将A A 1 A 2 A n 1 2 m改写为 A 1A 2A mA 和A 1A 2A nA 左递归的消除 从线性方程组到矩阵方程从3类文法到2类文法只关心产生式右部各符号串的首字符对n个非终结符X1 Xn 得到矩阵方程或表示为 X XA B方程的解为 X BA 回避闭包A 的计算 由于A I A A2 I AA r rr 若令A Z 则对X BA 可得X BZ和Z I AZX会不会产生左递归Z会不会产生左递归 例子与练习 消除下列文法的左递归1 S Sa Ab a A Sc2 S AS b A SA a FIRST集的定义 对符号串 FIRST a a 且a VT V 当 约定 FIRST 即FIRST 由 推导出的每个符号串的首个终结符组成 若 以终结符a打头 则FIRST FIRST a a 若 以非终结符X打头 则FIRST FIRST X 构造FIRST X 集1 2 令X Yi VN a VT X的产生式具有下述3种形式 构造FIRST X 集2 2 SetFIRST X ft if X VT return X if X P ft forEach X Y1Y2 Yk P forEach Yi if FIRST Yi ft FIRST Yi if i k ft else ft FIRST Yi break returnft 例题与练习 对文法G E E TE E ATE T FT T MFT F E iA M 求每个非终结符的FIRST集合 练习 P173 4 4之求FIRST集 FOLLOW集的定义 对非终结符X FOLLOW X a S Xa 且a VT V 即FOLLOW X 由语言中可能出现在X后面的终结符组成 构造FOLLOW集1 2 令X VN V X的产生式具有下述4种形式 构造FOLLOW集2 2 SetFOLLOW X if X S G S return fw forEach A X P if FIRST fw FIRST fw FOLLOW A elsefw FIRST forEach A X P fw FOLLOW A returnfw X 例题与练习 对文法G E E TE E ATE T FT T MFT F E iA M 求每个非终结符的FOLLOW集合 练习 P173 4 4之求FOLLOW集 4 1FIRST和FOLLOW的区别 令X VN 有如下断言 FIRST X FOLLOW X FIRST X FOLLOW X 可能为真 一定不为真 一定不为真 可能为真 FOLLOW X 为真的条件是什么 LL 1 文法 自顶向下的语法分析过程 为了实现无回溯的自顶向下语法分析 需满足对于G中的每个产生式A 1 2 m 满足FIRST i FIRST j 1 i j m i j 若有 j 则FIRST i FOLLOW A i 1 m i j 把满足上述条件的文法称为LL 1 文法自左向右扫描L最左推导L向前查看一个字符 1 某些非LL 1 文法的改造 1 消除左递归2 提取公因子若有形如A 1 2 n则提取公因子 后 上述产生式被替换为以下两个产生式 A A A 1 2 n 若 1 n之间还有公因子 则继续提取 LL 1 文法的递归下降分析法 递归下降分析法的原理 对于文法的每个非终结符 根据其各候选式的结构 为其建立一个递归的子程序 函数 用于识别该非终结符所表示的语法范畴 递归下降分析法1 2 例如 产生式E TE 相应的子程序 函数 expr prime if match PLUS Lookahead PLUSadvance Lookahead nexttokenterm expr prime i i j k 递归下降分析法2 2 验证4 2文法G statements statements exression statements expression termexpression expression termexpression term factorterm term factorterm factor num or id expression 为LL 1 文法条件 阅读P114 119程序4 1 4 2 4 3 LL 1 文法回顾 LL 1 文法 无 最 左递归 最 左公因子要合并 First集不相交 或First集与Follow集 当产生式的某可选右则可推出 不相交 递归下降分析法 非终结符 一个递归的子函数 自顶向下分析程序的手工构造 是否存在向顶向下分析程序的自动构造方法 自动构造自顶向下分析程序的思想 预测语法分析机 预测分析表 预制软件 1 预测分析机的逻辑结构 t1t2 ti tn tiYZ 输入单词流 分析栈 分析表为二维数组 M VN VT P ERR M A ti 的值按下述规则确定 对于每个产生式A 1 2 m 1 若ti FIRST i 则置M A ti A i 2 FIRST i ti FOLLOW A 置M A ti A i 3 除上述两种情况外 其它元素均填 ERR 分析表元素的含义 指明当前应用何产生式进行推导 或指明输入串出现错误 2 分析机的工作原理 1初始化分析栈 S 2 分析机的工作原理 2 1分析栈顶为VN 分析栈 输入单词流 X1X2 Xm V Xm X2X1 VN出栈查分析表 if单元格非ErrorthenVN产生式右则逆向压栈 V VN V X1X2 Xm 2 分析机的工作原理 2 2分析栈顶为VT 分析栈 输入单词流 Xm X2Yn a2 t1 t1 2 分析机的工作原理 2 3分析成功格局 分析成功意味着什么 输入串是分析表所对应文法的句子 2 分析机的工作原理 2 4语法错误的识别 1 分析栈 输入单词流 Xm X2Yn Y2 Y1 分析栈顶Y1为VN 2 分析机的工作原理 2 4语法错误的识别 2 分析栈 输入单词流 Xm X2Yn Y2 a1 分析栈顶a1为VT 3 预测分析法实例 1文法 G E E TE E ATE T FT T MFT F E iA M G E 是LL 1 文法吗 3 预测分析法实例 2预测分析表 G E E TE E ATE T FT T MFT F E iA M i ETE TE E ATE ATE TFT FT T MFT MFT Fi E A M 在分析表单元格中我们有意省略了左侧的非终结符 why 实际存储表时 还可用产生式编号作为单元格内容 以进一步减少表的存储空间 1 i i i E 初始化分析栈 3 预测分析法实例 步骤分析栈余留输入串所用产生式 E TE 2 i i i E T 逆向压入分析栈 VN 出栈 E 3 预测分析法实例 步骤分析栈余留输入串所用产生式 1 Ei i i E TE T FT 2 E Ti i i 3 E T Fi i i F i 4 E T ii i i 3 预测分析法实例 步骤分析栈余留输入串所用产生式 1 Ei i i E TE 2 E Ti i i 3 E T Fi i i 4 E T ii i i T FT F i 5 E T i i 3 预测分析法实例 步骤分析栈余留输入串所用产生式 1 Ei i i E TE 2 E Ti i i 3 E T Fi i i 4 E T ii i i T FT F i 5 E T i i T 6 E i i 下一步是什么 3 预测分析法实例 步骤分析栈余留输入串所用产生式 6 E i i i ETE TE E ATE ATE TFT FT T MFT MFT Fi E A M 请大家写完余下的分析 3 预测分析法实例 6 E i i E ATE 步骤分析栈余留输入串所用产生式 7 E TA i i A 8 E T i i 9 E Ti i T FT 10 E T Fi i F i 11 E T ii i 12 E T i T MFT 13 E T FM i M 14 E T F i 15 E T Fi F i 3 预测分析法实例 步骤分析栈余留输入串所用产生式 15 E T Fi F i 16 E T ii 17 E T T 18 E E 19 成功 回顾与扩展 为什么要限制为LL 1 文法 LL 1 文法的设计思想 LL k 文法 练习 设计文法G S 的LL 1 分析表 请给出构造过程S i E E SFF SF SF 自底向上的语法分析 例子 S AB cA bA aB aSb c用最左归约分析符号串bbaacb是否句子的过程两个重要动作 移近与归约简单优先分析法算符有限分析法LR分析法 简单优先分析法1 3 对规范句型 中任意两个相邻符号Si和Sj 它们和 的句柄间的关系必然是如下4种情况之一Si在句柄中 Sj不在句柄中Si先于Sj被归约 Sj必为终结符 Si和Sj均在句柄中Si和Sj同时被归约Si不在句柄中 Sj在句柄中Sj先于Si被归约 Si是否必为终结符 Si和Sj均不在句柄中在其它规范句型中可能存在先后被归约的次序也可能不具有先后关系 简单优先分析法2 3 例4 4 P128 如何求优先关系 简单优先分析算法 程序4 4 P130 理解表4 5 P131 简单优先分析法3 3 局限性与文法改造进一步扩展 算符优先分析法 T T 算符优先分析法1 2 广义运算符 终结符 文法限制 产生式右部不允许出现两个非终结符相连的情况确定终结符 算符 间的优先级U ab 或U aAb a b有U aA 和 A b 或A Bb ab若满足任何一对终结符间至多只有一种关系成立 则称为算符优先分析 算符优先分析法2 2 素短语与最左素短语树架子特点与优缺点 回顾 特点和局限性LL 1 分析法往前看一个字符 根据它来选定产生式各候选式的First集互不相交 出现 还包括Follow集 简单优先分析法各个符号间至多只能有一种优先关系算符优先分析法各个终结符间至多只能有一种优先关系至多有一产生式对应终结符的组成形式 N1aN2bN3c 一个例子 对A X1X2 Xn 用有历史的状态表示归约到哪 S A BA aAb cB aBb d若w是文法的句子 则w应可归约为S 又因为S A B 则w应可归约为A或B 又因为A aAb cB aBb d 则w应可归约为aAb或c或aBb或d综合起来 若w是文法的句子 则其应可归约为S A B aAb c aBb或d 因为尚无已归约出的符号 记为 S A B aAb c aBb和 d 记为起始状态S0 若w w1 w2 进一步分析 若w w1 w2且w1 VN VT若w1已归约为S 记为S 状态S1 若w2为 则w是句子 否则不是 若w1已归约为A 记为A 状态S2 则应将A归约为S 若w1已归约为B 记为B 状态S3 则应将B归约为S 若w1为a 记为a Ab或a Bb 状态S4 则应先分析w2能否归约为Ab或Bb 分析到aAb 或aBb 时再归约为A或B 若w1为c 记为c 状态S5 则应将c归约为A若w1为d 记为d 状态S6 则应将d归约为B 若w2 w21 w22 若w1为a 记为a Ab或a Bb 状态S4 则应先分析w2能否归约为Ab或Bb 分析到aAb 或aBb 时再归约为A或B 若w21已归约为A 记为aA b 状态S7 则需先分析w22是否为b 分析到aAb 时再归约为A 若w221为b 记为aAb 状态S8 则应将aAb归约为A若w21已归约为B 记为aB b 状态S9 则需先分析w22是否为b 分析到aBb 时再归约为B 若w221为b 记为aBb 状态S10 则应将aBb归约为B因为A aAb cB aBb d 所以w21可能为aAb或c或aBb或d若w211为a 记为a Ab或a Bb 则应先分析w212能否归约为Ab或Bb 分析到aAb 或aBb 时再归约为A或B 状态S4 若w211为c 记为c 则应将c归约为A 状态S5 若w211为d 记为d 则应将d归约为B 状态S6 LR分析器简介 总控程序 分析表 分析栈 a1a2 ai an 根据 现在 状态 输入V 分析表决定 移进 归约 接受 报错 一个LR分析例子 1 L E L3 E a2 L E4 E bP148表4 9 4 10 4 11 4 12Action 移近 归约 接受 出错Goto 状态转移程序4 6 pop 第i个产生式右部文法符号的个数 如何产生分析表 LR 0 SLR 1 LR 1 LALR 1 LR 0 分析表1 3 为了预防开始符号S出现在产生式右部导致分析复杂化 引入新的开始符号S 和S S G 称为G的拓广文法 显然L G L G 加入圆点 分隔已识别部分 得到LR 0 项目S S产生S S和S S 两个项目 对LR 0 项目 对应刚才的分析过程 建立DFAI0 S S S A S B A aAb A c B aBb B d 也称为基本项目集 S S 的闭包 闭包如何计算 LR 0 分析表2 3 DFA与活前缀规范句型不含句柄右部符号的前缀称为活前缀LR 0 项目的分类归约项目 在产生式最右端移近项目 紧跟在 后的符号为终结符待约项目 紧跟在 后的符号为非终结符LR 0 的限制不允许移近和归约项目并存不允许多个归约项目并存 LR 0 分析表3 3 1 A X 项目属于Ii 且GO Ii X Ij若X VT 则置ACTION i X sj 否则 X VN 置GOTO i X j 2 A 项目属于Ii 且A 是P中第j