编译原理语法分析总结ppt课件.ppt

确定的自上而下分析法 自下而上分析法 递归下降分析法 预测分析法 本章小结 本章介绍了四种典型的语法分析方法 算符优先分析法 LR分析法 LR 0 分析法 SLR 1 分析法 LR 1 分析法 LALR 1 分析法 确定的自上而下分析法要求描述语言的文法是LL 1 文法 1 LL 1 文法的判别方法 1 求文法每个产生式右部符号串的FIRST集 2 求文法各个非终结符的FOLLOW集 本章小结 一 确定的自上而下分析法 3 求文法每个产生式的SELECT集 4 求相同左部产生式的SELECT交集 对文法G的每一个非终结符A的产生式 SELECT A i SELECT A j i j 则文法G是一个LL 1 文法 本章小结 A 1 2 n 下面条件成立 2 LL 1 文法是无左递归 无二义性文法 3 将非LL 1 文法改写为LL 1 文法的方法 1 消除文法直接左递归 P P 改写为P P P P 或P 本章小结 2 提取公共左因子 本章小结 若A 1 2 n 提取公共左因子将文法改写成 A A A 1 2 n 4 根据文法规则构造递归下降分析程序和预测分析表的方法 5 注意LL 1 分析法与LR分析法的区别 本章小结 LL 1 分析法 预测分析法 是自上而下的语法分析法 要求文法为LL 1 文法 LR分析法是自下而上的语法分析法 只要文法是上下文无关文法 例1设有文法G E 为消除文法直接左递规 请改写文法 改写后的文法为 本章小结 E E T E T TT T F T F FF E id T T T E 本章小结 E E T E T TT T F T F FF E id F F F T E id F 例2设有文法G S S aAbDe dA BSD eB SAc cD D Se 本章小结 1 计算文法G S 每个非终结符的FIRST集和FOLLOW集 2 判断文法G S 是否LL 1 文法 本章小结 对每一文法符号X V 求FIRST X 的规则 1 若X VT 则FIRST X X 2 若X VN且有X a 则把a加入FIRST X 中 若X 则把 加入FIRST X 中 3 若X Y Y VN 则把FIRST Y 中所有非 元素加入FIRST X 中 FIRST S FIRST aAbDe FIRST d a d 本章小结 FIRST A FIRST B FIRST e FIRST S FIRST cD e a d c e S aAbDe dA BSD eB SAc cD D Se 问 能否 FIRST B FIRST S FIRST cD a d c FIRST D FIRST Se a d 本章小结 则规定 FOLLOW A 求FOLLOW A 的规则 1 对文法的开始符号S 令 FOLLOW S 2 若A B 是一条规则 则将FIRST 加到FOLLOW B 中 FOLLOW S a b c d e FOLLOW A b c 本章小结 FOLLOW B a d FOLLOW D a b c d e S aAbDe dA BSD eB SAc cD D Se 根据LL 1 文法的定义有 SELECT S aAbDe SELECT S d FIRST aAbDe FIRST d 本章小结 SELECT A BSD SELECT A e FIRST BSD FIRST e S aAbDe dA BSD eB SAc cD D Se SELECT B SAc SELECT B cD FIRST SAc FIRST cD SELECT B SAc SELECT B FIRST SAc a d FOLLOW B a d 所以该文法不是LL 1 文法 本章小结 二 LR分析法 大多数用上下文无关文法描述的语言都可以用相应的LR分析器予以识别 1 LR分析法是一种规范归约分析法 本章小结 2 从给定的上下文无关文法构造LR分析表的方法是 对LR 1 或LALR 1 分析表 构造LR 1 项目集规范族 1 对LR 0 或SLR 1 分析表 构造LR 0 项目集规范族 本章小结 2 构造识别文法规范句型活前缀的DFA 3 将DFA转换成相应的LR分析表 注意文法一定要拓广 四种分析表的构造基本相同 仅对含归约项目的项目集构造分析表元素不同 3 四种LR文法的判别方法 1 任何的二义性文法都不是LR类文法 本章小结 SLR 1 文法是LR 0 项目集中所有含冲突的项目集都能用SLR规则解决冲突 或SLR 1 分析表中不含多重定义 2 根据项目集中是否含冲突项目或相应分析表中是否含多重定义元素进行判断 LR 0 文法是所有的LR 0 项目集中没有移进一归约冲突或归约一归约冲突 或LR 0 分析表中不含多重定义 本章小结 SLR规则 I A b B1 1 B2 2 b FOLLOW B1 FOLLOW B1 FOLLOW B2 b FOLLOW B2 a b 移进 a FOLLOW B1 用B1 1归约 a FOLLOW B2 用B2 2归约 本章小结 LR 1 项目集中无移进一归约冲突或归约一归约冲突 或LR 1 分析表中不含多重定义 LALR 1 项目集中无归约一归约冲突 或LALR 1 分析表中不含多重定义 4 四种LR类文法之间的关系 注意搜索符只对归约项目起作用 本章小结 一个文法是LR 0 文法一定也是SLR 1 文法 也是LR 1 LALR 1 文法 反之则不一定成立 即 LR 0 SLR 1 LALR 1 LR 1 例1考虑文法 S AS b A SA a 1 构造识别文法活前缀的DFA 本章小结 3 该文法是SLR 1 的吗 若是 构造它的SLR 1 分析表 2 该文法是LR 0 文法吗 请说明理由 4 该文法是LR 1 或LALR 1 文法吗 请说明理由 解 首先将文法拓广 并对规则进行编号 0 S S 1 S AS 2 S b 3 A SA 4 A a 1 识别文法活前缀的DFA如下图所示 I0 I1 I2 I5 I3 S b I4 A a I6 S A b b b a a a A A a b S S A b a A 识别文法G S 活前缀DFA 1 识别文法活前缀的DFA如下图所示 I0 I1 I2 I7 I5 I3 S b I4 A a I6 S A b b b a a a A A a b S S A b a A S S b A S a 识别文法G S 活前缀DFA 本章小结 2 由上图不难看出 项目集I1 I5 I6中存在着移进 归约冲突 所以该文法不是LR 0 文法 3 由于对该文法句子abab对应下面两棵不同的语法树 见下图 本章小结 S S A a S A S A b a b S S A a S A S A b a b 所以该文法为二义性文法 任何二义性文法绝不是SLR 1 文法 也不是LALR 1 或LR 1 文法 本章小结 例2设有文法G S S S 试判断该文法是否SLR 1 文法 若不是 请说明理由 若是 请构造SLR 1 分析表 解 首先将文法拓广 并给出每条规则编号 0 S S 1 S S 2 S 本章小结 I0 I3 S S 构造该文法的LR 0 项目集族和转换函数如下图所示 该文法不是LR 0 文法 因为I0 I2中含有移进 归约的冲突 I1 S S I2 I4 S S S S 见表 本章小结 但是I0 I2中的移进 归约的冲突可以用SLR 1 方法解决 FOLLOW S 所以该文法是SLR 1 文法 其SLR 1 分析表如下表 本章小结 O 1 2 3 4 S2r2r2 acc 1 S2r2r2 3 S4 r1r1 文法G S 的SLR 1 分析表 见图 本章小结 例3设有文法G S 试证明该文法是SLR 1 文法 但不是LR 0 文法 解 首先将文法拓广 并对规则进行编号 直接构造LR 0 项目集如下 S aSb aSd 0 S S 1 S aSb 2 S aSd 3 S 本章小结 I0 S S S aSb S aSd S I1 S S I2 S a Sb S a Sd S aSb S aSd S I3 S aS b S aS d I4 S aSb I5 S aSd 0 S S2 S aSb1 S aSd3 S 本章小结 检查每个项目集可知 项目集I0和I2中有移进一归约冲突 因此该文法不是LR 0 文法 又因为 所以项目集I0和I2中移进一归约冲突可以用SLR 1 方法解决 因此该文法是SLR 1 文法 但不是LR 0 文法 FOLLOW S b d a 本章小结 例4设有文法G S 2 试判断该文法是否SLR 1 文法 若不是 请说明理由 若是 请构造出SLR 1 分析表 并给出符号串 的分析过程 1 构造识别文法规范句型活前缀的DFA LR 0 项目集族和GO函数 S S S 本章小结 3 试判断该文法是否LR 1 文法 若不是 请说明理由 若是 请构造LR 1 分析表 4 试判断该文法是否LALR 1 文法 请说明理由 本章小结 分析首先将文法拓广 并对规则编号 0 S SS S S S 构造LR 0 项目集规范族和转换函数如下图所示 本章小结 S S S S S S I0 I1 S S I2 I4 S S S S S 0 S SS S S S S S S S S S S S S S I3 本章小结 I1中的移进 归约的冲突可以用SLR 1 方法解决 FOLLOW S 所以该文法是SLR 1 文法 本章小结 FOLLOW S 符号串 的分析过程如下 本章小结 0 S SS S S S 构造LR 1 项目集规范族和转换函数如下图所示 本章小结 I0 S S S S S S I1 S S I2 S S 0 S SS