[工学]编译原理——第五章-1.pptVIP

编译方法 中国人民大学信息学院 陈文萍 第五章 语法分析——自下而上分析 5.1 自下而上分析基本问题 5.2算符优先分析 5.3 LR 分析法 5.4 语法分析器的自动产生工具 YACC 5.1 自下而上分析的基本问题 自下而上语法分析 试图将一个字符串反向归约至开始符号 （推倒的逆过程） 比自上而下语法分析更有效率，对语法的限制更少 移进－归约过程 移进：将一个终结符推进栈 归约：当栈顶形成某个产生式的候选式时，把这些符号从栈中弹出，把产生式的左部符号压入栈 文法G[S]：(1) S → aAcBe(2) A → b(3) A → Ab(4) B → d b b c d e A 3） #ab bcde# 归约(A→b) A 5） #aAb cde# 归约(A→Ab) B 8） # aAcd e# 归约(B→d) S 10） #aAcBe # 归约(S→aAcBe) 分析符号串abbcde是否G[S]的句子 步骤 符号栈 输入符号串 动作 1） # abbcde# 移进 2） #a bbcde# 移进 4） #aA bcde# 移进 6） #aA cde# 移进 7） #aAc de# 移进 9） #aAcB e# 移进 11） #S # 接受 对输入串abbcde#的移进-规约分析过程 S ? aAcBe ? aAcde ? aAbcde ? abbcde a 规范归约 短语、直接短语、句柄的定义： 至少经一步推导 文法G[S]，S αAδ，且A β则称β是句型αβδ相对于非终结符A的短语。（短语是句型的一部分） 若有A ? β，则称β 是句型α β δ相对于该规则A → β的直接短语。 经一步推导 一个句型的最左直接短语称为该句型的句柄。 规范归约: 设α是文法G的一个句子，称序列αn ,αn-1,…, α0 是α的一个规范规约，如果此序列满足： αn ＝ α α0 为文法的开始符，即α0 ＝ S 对任何i,0i=n, αi-1 是对αi，把句柄 替换为相应产生式的左部符号而得到的 自顶向下最右推导的逆过程 规范推导：最右推导 规范句型：规范推导所得的句型 短语举例： 主谓宾：同学 参加 会议 句——》主谓宾 主——》同学 谓——》参加 宾——》会议 同学，参加，会议分别为句的短语 但是如“同参”不是短语 规范归约 例 句型 归约规则 abbcde (2) A → b aAbcde (3) A → Ab aAcde (4) B → d aAcBe (1)S → aAcBe S 从语法树角度看句柄： 最左子树端末结的自左至右排列，这棵子树只有而且必须有父子两代 句柄=最左边的子树的父子子树 （不能是光的叶子节点成为的单子树） S a A c B e A b b S a A c B e A b S d d a A c B e d 规约T ? int T + int | 移进 T + | int 移进 int | * int + int 移进 int * | int + int 移进 |int * int + int E | 规约E ? T + E T + E | 规约E ? T T + T | 移进 T | + int 规约T ? int * T int * T | + int 规约 T ? int int * int | + int 文法G[E]：E ? T + E | T T ? int * T | int | (E) E T E + int * int T int T 移进－归约过程 (1) + int * int int ? |int * int + int 文法G[E]：E ? T + E | T T ? int * T | int | (E) 移进－归约过程(2) + int * int int ? int | * int + int |int * int + int 文法G[E]：E