吉林大学：《编译原理》课程教学资源（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),有#<s,;且#<Z S∈LAST(Z),有S>#,;且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 (归约) 。 ◆ 重复上述过程，直至输入符结束。如果归 约出文法的开始符号则成功。否则失败