吉林大学：《编译原理》课程教学资源（PPT课件讲稿）简单优先分析方法

简单优先分析方法 一种 shift-reduce分析方法 ◆根据文法符号的优先关系确定句柄 文法符号的优先关系的确定

简单优先分析方法 一种shift-reduce分析方法 根据文法符号的优先关系确定句柄 文法符号的优先关系的确定

简单优先分析中的三种关系 XY:当且仅当存在一个产生式A→.XY Ⅹ<Y:当且仅当存在一个产生式A→…XB 并有B→+Y. XY:当且仅当存在一个产生式A→.BC 并有B→+X,C→*Y.。 文法G为简单优先文法如果满足 对于任意两个语法符号X和Y,至多成立一种 优先关系; 任意两个产生式都具有不同的右部

简单优先分析中的三种关系 X  Y ：当且仅当存在一个产生式A→…XY… X ⊳ Y ：当且仅当存在一个产生式A→…XB… 并有B+Y…。 X ⊲ Y ：当且仅当存在一个产生式A→…BC… 并有B+ …X，C*Y…。 文法G为简单优先文法如果满足： • 对于任意两个语法符号X和Y，至多成立一种 优先关系； • 任意两个产生式都具有不同的右部

文法优先关系的确定 ÷ FIRST (W)=|W→+s.,S∈NVN) ÷LAST()=S|W→+…S,S∈VN∪V) 若有U→…SS1…:则有S;S;; 若有U>.SwW.:任S∈FRST),有S;S 若有UW.任S∈ LAST(V S∈(F| RST (W)∪W)则有S1>S 输入流的结束标志‘#,,文法的开始符为Z, S∈ FIRST(Z),有##,;且Z>#

文法优先关系的确定  FIRST(W) ={S | W + S…，S(VNVT)}  LAST(W) ={S | W + …S，S(VN VT)} 若有U→…SiSj…: 则有Si  Sj ; 若有U→…SiW…:任SjFIRST(W),有Si⊳ Sj 若有U→…VW…:任SiLAST(V), Sj(FIRST(W) {W})则有Si ⊲Sj 输入流的结束标志 ‘＃’，文法的开始符为Z， SFIRST(Z),有#⊳S，; 且＃⊳Z SLAST(Z)，有S⊲#，; 且Z⊲＃

M 例: FIRST b a M(a Z→)bMb LAST b a M→)a Z ML b M→>(L L→>Ma) Z—=MLb a #

 例： Z → bMb M → a M → (L L → Ma) # ) a ( b L M Z Z M L b ( a ) # b a L ) ) b a ( M ( a Z M L FIRST LAST      ⊳ ⊳ ⊲ ⊲ ⊲ ⊳ ⊳ ⊳ ⊲ ⊲ ⊲ ⊲ ⊲ ⊳ ⊳

简单优先分析算法要点 找第一个使S>S+的S ◆从S开始往前(左)找第一个使S1S的S 用SS115去查产生式的右部,并用相应 的左部符号代替句柄SS*1s:(归约)。 重复上述过程,直至输入符结束。如果归 约出文法的开始符号则成功。否则失败

简单优先分析算法要点 ◆ 找第一个使Sj⊲Sj+1的Sj ◆ 从Sj开始往前(左)找第一个使Si-1⊳Si的Si ◆ 用SiSi+1…Sj去查产生式的右部，并用相应 的左部符号代替句柄SiSi+1…Sj (归约) 。 ◆ 重复上述过程，直至输入符结束。如果归 约出文法的开始符号则成功。否则失败

简单优先分析实例 符号栈 关系 输入流 b(a a )b# f b (a a b# #b( a a)b# f b(a a)b# +b(m a)b# f b(ma )b# # b(ma) b# # b(l b# #b m b#t tomb #Z

简单优先分析实例 符号栈 关系 输入流 # ⊳ b ( a a ) b # # b ⊳ ( a a ) b # # b ( ⊳ a a ) b # # b ( a ⊲ a ) b # # b ( M  a ) b # # b ( M a  ) b # # b ( M a ) ⊲ b # # b ( L ⊲ b # # b M  b # # b M b ⊲ # # Z ⊲ #

二义性文法的处理 任何语法分析方法都拒绝二义性,会引 起分析动作的不确定。 ÷解决二义性的方法: 改变文法,消除二义性。 增加额外的规则 ◆利用二义性简化语法分析

二义性文法的处理  任何语法分析方法都拒绝二义性，会引 起分析动作的不确定。  解决二义性的方法： 改变文法，消除二义性。 增加额外的规则  利用二义性简化语法分析

例条件语句定义: [i]s→ ifE then s ese s [j]s→ ife then s 表达式文法: E→E+E E→E*E E→id E→(E)

 例条件语句定义： [i] S → if E then S else S [j] S → if E then S  表达式文法： E → E + E E → E * E E → id E → ( E )

第四章总结 上下文无关文法(GFG):…Vn,S,P) 语法分析树:二义性文法,句柄 文法分析算法:三个集合的定义及求法 语法分析作用:目的是判定输入串是否为 文法所接受的语言

第四章总结 • 上下文无关文法(CFG) ： (VN,VT,S,P) • 语法分析树：二义性文法，句柄 • 文法分析算法：三个集合的定义及求法 • 语法分析作用：目的是判定输入串是否为 文法所接受的语言

语法分析方法 自顶向下分析: 思想:从文法开始符出发,适当选择产生式, 力图推导出输入串。 关键问题:产生式的选择 主要方法: 递归下降法 分析条件 分析方法: LL(1)分析方法 分析过程: 等价变换消除公共前缀,消除左递归

语法分析方法 • 自顶向下分析： 思想：从文法开始符出发，适当选择产生式， 力图推导出输入串。 关键问题：产生式的选择 主要方法： 递归下降法 LL(1)分析方法 等价变换:消除公共前缀，消除左递归 分析条件： 分析方法： 分析过程：