山東理工大學(xué)-編譯原理內(nèi)部課件-第三章短語(yǔ)直接短語(yǔ)句柄

1、2024/4/1,1,相關(guān)概念 短語(yǔ) p44,,例 E ? E+T ? E+T*F ? E+T*i,句型E+T*i的短語(yǔ)有3個(gè)：,(1)E+T*i是句型E+T*i相對(duì)于E的短語(yǔ),(2)T*i是句型E+T*i相對(duì)于T的短語(yǔ),(3)i是句型E+T*i相對(duì)于F的短語(yǔ),E ==0> εEε且 E==+>E+T*i,Ｓ,,,,α Ａ δ,,β,E ==*>E+T 且 T==+>T*i,E ==*>E+T*F 且 F=

2、=>i,E,,,,ε E ε,,E+T*i,,,,E,E+ T ε,T*i,,,,E,E+T* F ε,i,,短語(yǔ) 若Ｓ==*>αＡδ，且A==+>β，則稱 β是句型αβδ相對(duì)于非終結(jié)符號(hào)A的短語(yǔ),,不是短語(yǔ),,,,,,,2024/4/1,2,直接短語(yǔ) 句柄 p44,一個(gè)句型的直接短語(yǔ)可能不唯一,句型E+T*i的句柄是：i,E ==0>εEε 且 E==+>E+T*i,E ==*>E+

3、T 且 T==+>T*i,E ==*>E+T*F 且 F==>i,i是句型E+T*i相對(duì)于F的直接短語(yǔ),（句型有唯一句柄）,直接短語(yǔ) 若Ｓ?* αＡδ 且 A? β，則稱β是句型 αβδ 相對(duì)于非終結(jié)符號(hào)A的直接短語(yǔ),句柄 一個(gè)句型的最左直接短語(yǔ) 稱為該句型的句柄,,,2024/4/1,3,利用語(yǔ)法樹(shù)尋找句型的短語(yǔ)、句柄等,句型η=E+T*i,尋找方法,句型η的語(yǔ)法樹(shù)有：,n棵

4、子樹(shù)——n個(gè)短語(yǔ),m棵直接子樹(shù)——m個(gè)直接短語(yǔ),最左直接子樹(shù)——句柄,①,②,③,3個(gè)短語(yǔ),1個(gè)直接短語(yǔ),i,句柄,i,,,,E+T*i,T*i,i,只有父子兩代,,,n個(gè)內(nèi)部節(jié)點(diǎn)——n棵子樹(shù),每顆子樹(shù)的葉結(jié)點(diǎn)從左至右排列組成一個(gè)短語(yǔ),2024/4/1,4,利用語(yǔ)法樹(shù)尋找短語(yǔ)、句柄等方法總結(jié),,,句型η的語(yǔ)法樹(shù)有若干個(gè)內(nèi)部節(jié)點(diǎn)（包括根節(jié)點(diǎn)）每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)一棵以該內(nèi)部節(jié)點(diǎn)為根的子樹(shù)如果一棵子樹(shù)只有父子兩代（兩層節(jié)點(diǎn)），則稱該子樹(shù)為直接

5、子樹(shù)如果一棵子樹(shù)的根標(biāo)記為A，且將此子樹(shù)的葉節(jié)點(diǎn) 標(biāo)記自左至右排列來(lái)所形成的符號(hào)串為β，則β是句型 η 相對(duì)于A的一個(gè)短語(yǔ)如果子樹(shù)是一棵直接子樹(shù)，則β是句型 η 相對(duì)于A的一個(gè)直接短語(yǔ)最左直接子樹(shù)對(duì)應(yīng)該句型的句柄,2024/4/1,5,利用語(yǔ)法樹(shù)尋找短語(yǔ)、句柄舉例,句型 η=T+T*F+i 的語(yǔ)法樹(shù),例 文法G[E]： E→E+T|T T→T*F|F F→(E)|i,E,,,,E + T,,F,,i,,,,E +

6、 T,,,,T * F,,T,①,②,③,④,⑤,⑥,句型η有6個(gè)短語(yǔ)：,T+T*F+i 是句型η相對(duì)于E1的短語(yǔ)T+T*F 是句型η相對(duì)于E2的短語(yǔ)T 是句型η相對(duì)于E4的短語(yǔ)T*F 是句型η相對(duì)于T5的短語(yǔ)i，i 是句型η相對(duì)于T3，F(xiàn)6的短語(yǔ),3個(gè)直接短語(yǔ)：,T,,T*F，,i,句柄：,T,,,,,,,,6個(gè)內(nèi)部節(jié)點(diǎn)——6棵子樹(shù),,,2024/4/1,6,利用語(yǔ)法樹(shù)尋找短語(yǔ)、句柄課堂練習(xí),句型 η=i1*i2+i3 的語(yǔ)