第7章自下而上的语法分析

1、信息学院软件工程教研室信息学院软件工程教研室刘向菊刘向菊QQ: 8064793Tel:息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室i* *EiiEEEE信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e信息学院软件工程教研室信息学

2、院软件工程教研室bdbaceSABA分析树和语法树不一定一致。分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边自下而上分析过程：边输入单词符号，边归约。归约。核心问题：识别可归约串核心问题：识别可归约串信息学院软件工程教研室信息学院软件工程教研室AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别是，如果有特别是，如果有A A, ,则称则称 是句型是句型相对相对于规则于规则A A 的的直接短语直接短语。一个句型的最左。一个句型的最左直接短语称为该句型的直接短语称为该句型的句柄句柄。信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息

3、学院软件工程教研室EFFTTTi1+*EFi3i2信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室把上例倒过来写，则得到：把上例倒过来写，则得到：S S aAcBeaAcBe aAcde aAcde aAbcde aAbcde abbcde abbcde 显然这是一个最右推导。显然这是一个最右推导。规范归约规范归约是关于是一个是关于是一个最右推导最右推导的逆过程的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为由规范推导推出的句型称为规范句型规范句型。信息学院软件工程教研室信息学院软件工程教研室

4、bdbaceSABAdaceSABdbaceSABAaceSABS信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别是，如果有特别是，如果有A A, ,则称则称 是句型是句型相对相对于规则于规则A A 的的直接短语直接短语。一个句型的最左。一个句型的最左直接短语称为该

5、句型的直接短语称为该句型的句柄句柄。AS*A信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室Ei( () )i* *EiEE+ +EEE-ii+ +EEE信息学院软件工程教研室信息学院软件工程教研室Ei( () )i* *EiEE+ +EEE-ii+ +EEE返回信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软

6、件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室S S S S b A b b A b b A b b A b ( B a ( B ( B A a ) A a ) （ B a A a ) (a) (b) (c) (d) 图 6.2 语法树结构 信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室表 6.2 例 6.2 文法的简单优先关系矩阵 S b A ( B a ) # S b = A = = ( = a = ) #

7、= 信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室 A A A a b a B B b P P b a (a)a=b (b)ab 图 6.3 由语法树构造决定优先性 信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室E E E + E E * E E * E E + E (a)+* 图 6.4 二义性文法的语法树 信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学

8、院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室（4）TF（5）FPF| P（6）P(E)（7）Pi信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室表6.5 表 达 式 文 法 算 符 优 先 关 系 表 + * i ( ) # + * i ( # = 信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院

9、软件工程教研室表 6.7 对输入串 i+i#的规范归约过程 步骤 栈 剩余输入串 句柄 归约用产生式 (1) # i+i# (2) # i +i# i Pi (3) # P +i# P FP (4) #F +i# F TF (5) # T +i# T ET (6) # E +i# (7) #E+ i# (8) # E+i # i Pi (9) #E+P # P FP , TF (10) #E+T # E+T EE+T 7（11） #E # 接受信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室EEF+*TiFTFTP+ETP句型：句型：T+F*P+i短语：

10、短语：直接短语：直接短语：句柄：句柄：素短语：素短语：最左素短语：最左素短语：, T+F*P+iT, F, P, F*P, iT+F*PT, F, P, iTF*P, iF*P信息学院软件工程教研室信息学院软件工程教研室表6.8 对 输 入 串i+i#的 算 符 优 先 归 约 过 程 步 骤 栈 优 先 关 系 当 前 符 号 剩 余 输 入 串 移 进 或 归 约 (1) # + i# 归 约 (3) #F + i# 移 进 (4) #F+ # 归 约 (6) #F+F # 归 约 (7) #F = # 接 受 7E信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室 置 初 值 k:=1,Sk:=# 当 前 输 入 符 读 入 a Sk VT? Y N j:=k j:=k-1 Sja? N Sja? Y N N Y Q := Sj 出 错 Sj=a? Y k:=k+1 Sj-1 VT? Sj=#? N Sk:=a Y N Y j:=j-1 j:=j-2 检 查 是 否 正 常 结 束 N 出 错 Y N SjQ 结 束 Y Sj+1 Sk归 约 为 N K:=j+1 Sk:=N 图 6.8 算 符 优 先 分 析 归 约 过 程 框 图 信息学院软件工程教研室信息学院软件工程教研室自左至右，终结符对终结符，非自左至右，终结符对