短語、直接短語和句柄

《短語、直接短語和句柄》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2.4短語、直接短語和句柄短語令G是一個(gè)文法，S是文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有則稱β是相對于非終結(jié)符A的,句型αβδ的短語。S??αAδ*+且A?β2.4短語、直接短語和句柄則稱β是直接短語。直接短語S??αAδ*且A?β令G是一個(gè)文法，S是文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有2.4短語、直接短語和句柄注意：短語和直接短語的區(qū)別在于第二個(gè)條件,直接短語中的第二個(gè)條件表示有文法規(guī)則A?β，因此，每個(gè)直接短語都是某規(guī)則右部。2.4短語、直接短語和句柄句柄一個(gè)句型的

2、最左直接短語稱為該句型的句柄。句柄特征：(1)它是直接短語，即某規(guī)則右部。(2)它具有最左性。2.4短語、直接短語和句柄注意:短語、直接短語和句柄都是針對某一句型的，都是指句型中的哪些符號(hào)串能構(gòu)成短語和直接短語，離開具體的句型αβδ來談短語、直接短語和句柄是無意義的。2.4短語、直接短語和句柄例如設(shè)有文法G[S]=({S,A,B},{a,b},P,S)其中P為：求句型baSb的全部短語、直接短語和句柄。S?ABA?Aa

3、bBB?a

4、Sb2.4短語、直接短語和句柄對文法，首先建立該句型的推導(dǎo)過程：最左

5、推導(dǎo):最右推導(dǎo):S?ABA?Aa

6、bBB?a

7、SbS??AB?ASb?bBSb?baSbS??AB?baB?baSb?bBB分析根據(jù)短語定義，可以從句型的推導(dǎo)過程中找出其全部短語、直接短語和句柄。句型baSb2.4短語、直接短語和句柄句型baSb中的子串Sb，是(相對于非終結(jié)符B)句型baSb的短語，且為直接短語。S??AB?bBB?baB?baSb(2)S??baB*B?Sb(1)S??S*S?baSb+句型本身是(相對于非終結(jié)符S)句型baSb的短語。根據(jù)最左推導(dǎo):S??αAδ*+A?β2.4短

8、語、直接短語和句柄句型baSb中的子串a(chǎn)，是(相對于非終結(jié)符B)句型baSb的短語，且為直接短語、句柄。句型baSb中的子串ba，是(相對于非終結(jié)符A)句型baSb的短語。B?a(3)S??bBSb*根據(jù)最右推導(dǎo):S??AB?ASb?bBSb?baSb(4)S??ASb*A?ba+S??αAδ*+A?β2.5語法樹與文法的二義性推導(dǎo)和語法樹1.語法樹對句型的推導(dǎo)過程給出一種圖形表示,這種表示稱為語法樹，也稱推導(dǎo)樹。2.5.1推導(dǎo)和語法樹例如設(shè)有文法G[E]:構(gòu)造句型i*i+i的語法樹。首先給出句型的

9、推導(dǎo)過程(最左推導(dǎo))：E?E+T

10、E–T

11、TT?T*F

12、T/F

13、FF?(E)

14、iE?E+T?T+T?T*F+T?F*F+T?i*F+T?i*i+T?i*i+F?i*i+i2.5.1推導(dǎo)和語法樹根據(jù)推導(dǎo)過程構(gòu)造句型i*i+i的語法樹如下：E?E+TEE+T?T+TT?T*F+TT*F?F*F+TF?i*F+Ti?i*i+Ti?i*i+FF?i*i+ii2.5.1推導(dǎo)和語法樹由例可知，語法樹的構(gòu)造過程是從文法的開始符號(hào)出發(fā)，構(gòu)造一個(gè)推導(dǎo)的過程。因?yàn)槲姆ǖ拿恳粋€(gè)句型(句子)都存在一個(gè)推導(dǎo)，所以文法的每個(gè)句

15、型(句子)都存在一棵對應(yīng)的語法樹。E?E+T?E+F?E+i?T+i?T*F+i?T*i+i?F*i+i?i*i+i2.5.1推導(dǎo)和語法樹對句型i*i+i，還可給出最右推導(dǎo)：EE+TTT*FFiiFi2.5.1推導(dǎo)和語法樹這也就是說，一棵語法樹表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過程,包括最左(最右)推導(dǎo)。3.5.1推導(dǎo)和語法樹2.子樹語法樹的子樹是由某一結(jié)點(diǎn)連同所有分枝組成的部分。EE+TTT*FFiiFi3.5.1推導(dǎo)和語法樹3.簡單子樹語法樹的簡單子樹是指只有單層分枝的子樹。E

16、E+TTT*FFiiFi2.5.1推導(dǎo)和語法樹句型的短語、直接短語和句柄的直觀解釋是：短語：子樹的末端結(jié)點(diǎn)形成的符號(hào)串是相對于子樹根的短語。直接短語：簡單子樹的末端結(jié)點(diǎn)形成的符號(hào)串是相對于簡單子樹根的直接短語。句柄：最左簡單子樹的末端結(jié)點(diǎn)形成的符號(hào)串是句柄。2.5.1推導(dǎo)和語法樹EE+TTT*FFiiFi短語:i*i+ii*i第一個(gè)i第二個(gè)i第三個(gè)i三個(gè)i都是直接短語第一個(gè)i是句柄注意:i+i不是句型的短語句子i*i+i2.5.1推導(dǎo)和語法樹前例對文法G[S]=({S,A,B},{a,b},P,S)

17、其中P為：可用語法樹非常直觀地求出句型baSb的全部短語，直接短語和句柄。S?ABA?Aa

18、bBB?a

19、Sb2.5.1推導(dǎo)和語法樹分析首先根據(jù)句型baSb的推導(dǎo)過程畫出對應(yīng)的語法樹如下：Sb為句型的相對于B的短語、直接短語baSb為句型的相對于S的短語ba為句型的相對于A的短語a句型的相對于B的短語、直接短語和句柄S?AB?bBB?baB?baSbS?AB?ASb?bBSb?baSbSABbBSba由語法樹可知2.5.2文法的二義性從前面的討論可以看出，對于文法G中任