山東理工大學-編譯原理內部課件-第三章短語直接短語句柄

1、2024/4/1,1,相關概念 短語 p44,,例 E ? E+T ? E+T*F ? E+T*i,句型E+T*i的短語有3個：,(1)E+T*i是句型E+T*i相對于E的短語,(2)T*i是句型E+T*i相對于T的短語,(3)i是句型E+T*i相對于F的短語,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,,短語 若Ｓ==*>αＡδ，且A==+>β，則稱 β是句型αβδ相對于非終結符號A的短語,,不是短語,,,,,,,2024/4/1,2,直接短語 句柄 p44,一個句型的直接短語可能不唯一,句型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相對于F的直接短語,（句型有唯一句柄）,直接短語 若Ｓ?* αＡδ 且 A? β，則稱β是句型 αβδ 相對于非終結符號A的直接短語,句柄 一個句型的最左直接短語 稱為該句型的句柄,,,2024/4/1,3,利用語法樹尋找句型的短語、句柄等,句型η=E+T*i,尋找方法,句型η的語法樹有：,n棵

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

5、子樹如果一棵子樹的根標記為A，且將此子樹的葉節(jié)點 標記自左至右排列來所形成的符號串為β，則β是句型 η 相對于A的一個短語如果子樹是一棵直接子樹，則β是句型 η 相對于A的一個直接短語最左直接子樹對應該句型的句柄,2024/4/1,5,利用語法樹尋找短語、句柄舉例,句型 η=T+T*F+i 的語法樹,例 文法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個短語：,T+T*F+i 是句型η相對于E1的短語T+T*F 是句型η相對于E2的短語T 是句型η相對于E4的短語T*F 是句型η相對于T5的短語i，i 是句型η相對于T3，F(xiàn)6的短語,3個直接短語：,T,,T*F，,i,句柄：,T,,,,,,,,6個內部節(jié)點——6棵子樹,,,2024/4/1,6,利用語法樹尋找短語、句柄課堂練習,句型 η=i1*i2+i3 的語