new文法和語(yǔ)言

1、1第三章第三章 文法和語(yǔ)言文法和語(yǔ)言 一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，它的完整定義包括兩個(gè)方面：一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，它的完整定義包括兩個(gè)方面：語(yǔ)法語(yǔ)法是指是指一組規(guī)則一組規(guī)則，應(yīng)用這組規(guī)則可以形成和產(chǎn)生一個(gè)合適的，應(yīng)用這組規(guī)則可以形成和產(chǎn)生一個(gè)合適的程序。通常用程序。通常用上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法作為描述語(yǔ)法的工具作為描述語(yǔ)法的工具.語(yǔ)義語(yǔ)義：程序設(shè)計(jì)語(yǔ)言的語(yǔ)義分為兩種：程序設(shè)計(jì)語(yǔ)言的語(yǔ)義分為兩種： 1）靜態(tài)語(yǔ)義是一系列限定規(guī)則，并確定哪些合乎語(yǔ)法）靜態(tài)語(yǔ)義是一系列限定規(guī)則，并確定哪些合乎語(yǔ)法的程序是合適的；的程序是合適的； 2）動(dòng)態(tài)語(yǔ)義（運(yùn)行語(yǔ)義或執(zhí)行語(yǔ)義）表明程序要做什）動(dòng)

2、態(tài)語(yǔ)義（運(yùn)行語(yǔ)義或執(zhí)行語(yǔ)義）表明程序要做什么，要計(jì)算什么么，要計(jì)算什么. 主要內(nèi)容：主要內(nèi)容：文法和語(yǔ)言、上下文無(wú)關(guān)文法、句型分析等文法和語(yǔ)言、上下文無(wú)關(guān)文法、句型分析等例如：賦值語(yǔ)句：例如：賦值語(yǔ)句：A=B+C 合法；合法；A=B+ 非法；語(yǔ)義則匹配類型非法；語(yǔ)義則匹配類型2 3.1 3.1 文法的直觀概念文法的直觀概念文法的直觀認(rèn)識(shí)：文法的直觀認(rèn)識(shí)：如何給出語(yǔ)言的有窮表示？如何給出語(yǔ)言的有窮表示？ 語(yǔ)言是由句子組成的，因此，可以用一些規(guī)則說(shuō)明或定義句子的語(yǔ)言是由句子組成的，因此，可以用一些規(guī)則說(shuō)明或定義句子的組成結(jié)構(gòu)。組成結(jié)構(gòu)。例如：我是大學(xué)生例如：我是大學(xué)生:=:=| :=我我|你你|他

3、他:=王明王明|大學(xué)生大學(xué)生|工人工人|英語(yǔ)英語(yǔ):=:=是是|學(xué)習(xí)學(xué)習(xí):=這些規(guī)則成為判別句這些規(guī)則成為判別句子結(jié)構(gòu)合法與否的依子結(jié)構(gòu)合法與否的依據(jù)據(jù).這些規(guī)則看成是一這些規(guī)則看成是一種元語(yǔ)言，這樣的語(yǔ)種元語(yǔ)言，這樣的語(yǔ)言描述稱為文法言描述稱為文法.3應(yīng)用規(guī)則推導(dǎo)句子：應(yīng)用規(guī)則推導(dǎo)句子：= = =我我 =我我 =我是我是 =我是我是 =我是大學(xué)生我是大學(xué)生“=”的含義是使用一條規(guī)則代替的含義是使用一條規(guī)則代替=左邊的某個(gè)符號(hào)并產(chǎn)生左邊的某個(gè)符號(hào)并產(chǎn)生=右端右端的符號(hào)串的符號(hào)串.應(yīng)用這些規(guī)則可以產(chǎn)生很多句子應(yīng)用這些規(guī)則可以產(chǎn)生很多句子.這樣，使用文法作為工具，不僅這樣，使用文法作為工具，不僅定義

4、了句子的結(jié)構(gòu)，而且通過(guò)有窮的規(guī)則描述出語(yǔ)言的全部句子定義了句子的結(jié)構(gòu)，而且通過(guò)有窮的規(guī)則描述出語(yǔ)言的全部句子.4字母表是元素的非空有窮集合字母表是元素的非空有窮集合字母表中至少包含一個(gè)元素。字母表中至少包含一個(gè)元素。字母表中的元素，可以是字母、數(shù)字或其他符號(hào)。字母表中的元素，可以是字母、數(shù)字或其他符號(hào)。3.2 符號(hào)和符號(hào)串符號(hào)和符號(hào)串一一. .字母表字母表 alphabetalphabet【例如】【例如】 = a,b,c是字母表，由是字母表，由a,b,ca,b,c三個(gè)元素組成。三個(gè)元素組成?！纠纭俊纠纭?= 0,1是字母表，由是字母表，由0,10,1兩個(gè)元素組成。兩個(gè)元素組成。不同的語(yǔ)言有

5、不同的字母表。不同的語(yǔ)言有不同的字母表。英文的字母表是英文的字母表是26個(gè)字母、數(shù)字和標(biāo)點(diǎn)符號(hào)的集合；個(gè)字母、數(shù)字和標(biāo)點(diǎn)符號(hào)的集合；C語(yǔ)言的字母表是字母、數(shù)字和若干專用符號(hào)組成。語(yǔ)言的字母表是字母、數(shù)字和若干專用符號(hào)組成。任何語(yǔ)言的字母任何語(yǔ)言的字母表指出了該語(yǔ)言表指出了該語(yǔ)言中允許出現(xiàn)的一中允許出現(xiàn)的一切符號(hào)。切符號(hào)。5二二. .符號(hào)（字符）符號(hào)（字符）symbolsymbol字母表中的元素稱為符號(hào)，或稱為字符。字母表中的元素稱為符號(hào)，或稱為字符?！纠纭俊纠纭?= a,b,ca,b,c是字母表是字母表中的符號(hào)。中的符號(hào)?！纠纭俊纠纭?= 0,10,1是字母表是字母表中的符號(hào)。中的符號(hào)

6、。6三三. .符號(hào)串（字）符號(hào)串（字）stringstring符號(hào)的有窮序列稱為字符串。符號(hào)的有窮序列稱為字符串。【例如】設(shè)有字母表【例如】設(shè)有字母表 = a,b,c，則有符號(hào)串則有符號(hào)串 a,b,ab,ba,cba,abc,(a,b,ab,ba,cba,abc等都是字母表等都是字母表上的符號(hào)串上的符號(hào)串)符號(hào)串總是建立在某個(gè)特定字母表上的且只能由字母表上符號(hào)串總是建立在某個(gè)特定字母表上的且只能由字母表上的的多個(gè)符號(hào)組成。多個(gè)符號(hào)組成。符號(hào)串中符號(hào)的順序是很重要的，符號(hào)串中符號(hào)的順序是很重要的，如如 ab 和和 ba 是字母表是字母表上的兩個(gè)不同的符號(hào)串。上的兩個(gè)不同的符號(hào)串。不包含任何符號(hào)的

7、符號(hào)串，稱為空符號(hào)串，用不包含任何符號(hào)的符號(hào)串，稱為空符號(hào)串，用 (epsilon)表示，即空符號(hào)串由表示，即空符號(hào)串由 0 個(gè)符號(hào)組成，其長(zhǎng)度個(gè)符號(hào)組成，其長(zhǎng)度| |=07r符號(hào)串的頭尾符號(hào)串的頭尾：如果zxy是一符號(hào)串，那么x是z的頭，y是z的尾。 如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有頭。r符號(hào)串集合：符號(hào)串集合：若集合若集合A A中的一切元素都是某字母中的一切元素都是某字母表上的符號(hào)串，則稱表上的符號(hào)串，則稱A A為該字母表上的為該字母表上的符號(hào)串集符號(hào)串集合合。四四. .符號(hào)串的運(yùn)算相關(guān)概念符號(hào)串的運(yùn)算相關(guān)概念例如例如:zabc，那么，那么z的頭是的頭是 , a

8、, ab, abc.Z的尾是的尾是 , c, bc, abc.8四四. .符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算1.1.符號(hào)串的連接符號(hào)串的連接 connectionconnection設(shè)設(shè) x 和和 y 是符號(hào)串，則串是符號(hào)串，則串 xy 稱為它們的連接。即稱為它們的連接。即 xy 是將是將 y 符號(hào)串寫在符號(hào)串寫在 x 符號(hào)串之后得到的符號(hào)串。符號(hào)串之后得到的符號(hào)串。【例如】設(shè)【例如】設(shè) x abc，y = 10a，則則 xy abc10a則則 yx 10aabc特別，對(duì)任意一符號(hào)串特別，對(duì)任意一符號(hào)串 x 有：有： x x x92.2.符號(hào)串的冪運(yùn)算符號(hào)串的冪運(yùn)算 powerpower設(shè)設(shè) x 是符號(hào)

9、串，則是符號(hào)串，則 x 的冪運(yùn)算定義為：的冪運(yùn)算定義為：x0 x1 xx2 xxxn xxx = xxn-1 (n0) n【例如】設(shè)【例如】設(shè) x = abc,則則x0 x1 abcx2 abcabc103.3.集合的乘積集合的乘積 productproduct設(shè)設(shè) A 和和 B 是符號(hào)串的集合，則是符號(hào)串的集合，則 A 和和 B 的乘積定義為：的乘積定義為：AB = xy | x A, y B即集合即集合 AB 中的符號(hào)串是由中的符號(hào)串是由 A 和和 B 的符號(hào)串連接而成的。的符號(hào)串連接而成的。【例如】設(shè)【例如】設(shè) A = a,b,B = c,d則則 AB ac,ad,bc,bd因?yàn)閷?duì)任意一

10、符號(hào)串因?yàn)閷?duì)任意一符號(hào)串 x 有：有： x x x所以，對(duì)任意集合所以，對(duì)任意集合 A，有，有 A = A = A11空集空集 empty setempty set 表示不含任何元素的表示不含任何元素的空集空集 = 注意：注意： 是符號(hào)串，不是集合，是符號(hào)串，不是集合， 表示由空符號(hào)串表示由空符號(hào)串 所組成的集合，但這樣的集合不是空集所組成的集合，但這樣的集合不是空集， 即即不包含空串。不包含空串。 (不屬于不屬于)對(duì)任意集合對(duì)任意集合 A，有，有 A = A = 124.4.集合的冪運(yùn)算集合的冪運(yùn)算設(shè)設(shè) A 是符號(hào)串的集合，則集合是符號(hào)串的集合，則集合 A 的冪運(yùn)算定義為：的冪運(yùn)算定義為：A

11、0 A1 AA2 AAAn AAA = AAn-1 (n0) n【例如】設(shè)【例如】設(shè) A = a,b,則則A0 A1 a,bA2 AA = aa,ab,ba,bbA3 AAA = A2A = aaa,aab,aba,abb,baa,bab,bba,bbb135.5.集合集合A A的正閉包的正閉包A A+ +與閉包與閉包A A* *設(shè)設(shè) A 是符號(hào)串的集合，是符號(hào)串的集合，則集合則集合 A 的正閉包的正閉包A+和閉包和閉包A*分別定義為：分別定義為：A+ A1 U A2 U A3 U U An U A* A0 U A1 U A2 U A3 U U An U = U A+【例如】設(shè)【例如】設(shè) A

12、= a,b,則則A+ a,b,aa,ab,ba,bb,aaa,aab,A* ,a,b,aa,ab,ba,bb,aaa,aab, 正閉包：正閉包：Positive closure閉包閉包：Star closure（星閉包）（星閉包）14【例如】設(shè)【例如】設(shè) A = a,則則A+ a,aa,aaa, = an | n=1A* , a,aa,aaa, = an | n=0A* = A0 A1 A2 A3 ，稱，稱 A* 是是 A 的的閉包閉包。A+ = AA* ，稱，稱 A+ 是是A的的正則閉包正則閉包。*表示表示上的上的所有符號(hào)串的全體所有符號(hào)串的全體153.3 文法和語(yǔ)言的形式定義1、規(guī)則、規(guī)則

13、規(guī)則規(guī)則，也稱重寫規(guī)則重寫規(guī)則、產(chǎn)生式產(chǎn)生式或生成式生成式，是形如或 =的( ，)有序?qū)Γ渲惺亲帜副鞻的正閉包V+中的一個(gè)符號(hào)，是V*中的一個(gè)符號(hào)。 稱為規(guī)則的左部， 稱作規(guī)則的右部?；蚧?162 、文法定義定義文法G定義為四元組(VN，VT，P，S )其中VN:非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；VT:終結(jié)符號(hào)集；P: 規(guī)則的集合； VN，VT和P是 非空有窮集。 S:稱作識(shí)別符號(hào)或開(kāi)始符號(hào)的一個(gè)非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，稱為文法G的字母表或字匯表 規(guī)則規(guī)則，也稱重寫規(guī)則重寫規(guī)則、產(chǎn)生式產(chǎn)生式或生成式生

14、成式，是形如或 =的( ，)有序?qū)?，其中是字母表V的正閉包V+中的一個(gè)符號(hào)，是V*中的一個(gè)符號(hào)。 稱為規(guī)則的左部， 稱作規(guī)則的右部。17例例 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S為開(kāi)始符號(hào)為開(kāi)始符號(hào)例例 文法文法G=（VN，VT，P，S）VN =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a zz 00 99 S=19文法的寫法文法的寫法 元元符號(hào): = | = | 習(xí)慣習(xí)慣 大寫字母表示非終結(jié)符大寫字母表示非終結(jié)符 小寫字母表示終結(jié)符小寫字母表示終結(jié)符(1) G(1) G：SaASaAb

15、Aab Aab AaA AaAb A A (2) GS (2) GS： Aab Aab AaA AaAb A A SaS SaSb (3) GS:Aab |aA(3) GS:Aab |aAb | | SaSSaSb20推導(dǎo)的定義推導(dǎo)的定義直接推導(dǎo)直接推導(dǎo)“”是文法是文法G G的產(chǎn)生式，若有的產(chǎn)生式，若有v,wv,w滿足：滿足：v=,w= , v=,w= , 其中其中VV* *,V,V* * 則稱則稱v v直接直接推導(dǎo)推導(dǎo)到到w,w,記作記作 v v w w 也稱也稱w w直接直接歸約歸約到到v v例：例：G G： S0S1， S01 0S1 00S11 00S11 000S111 000S11

16、1 00001111 S 0S121推導(dǎo)推導(dǎo). ( . ). . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A)VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A)22 若存在若存在v =w0 w1 . wn=w,(n0) 則記為則記為v w，稱作，稱作v推導(dǎo)出推導(dǎo)出w，或，或w歸約到歸約到v 若有若有v w 或或 v=w， 則記為則記為v w推導(dǎo)的定義推導(dǎo)的定義+=+=*=23例：例：G G： S0S1， S010S1 00S1100S11 000S111000S111 0

17、0001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11+=*=*=24句型、句子的定義句型、句子的定義z句型句型有文法有文法G，若，若S =* x，則稱，則稱x是文法是文法G的句型。的句型。z句子句子有文法有文法G，若，若S =* x，且，且xVVT T* *，則稱，則稱x是文法是文法G的句子。的句子。例：例：G G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00001111, 0125句型、句子句型、句子例：例：

18、GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符號(hào)句子：用符號(hào)a，+，*，(和和)構(gòu)成的算術(shù)表達(dá)式構(gòu)成的算術(shù)表達(dá)式26( (文法生成的文法生成的) )語(yǔ)言的定義語(yǔ)言的定義由文法由文法G生成的語(yǔ)言記為生成的語(yǔ)言記為L(zhǎng)(G),它是文法它是文法G的的一切句子的集合一切句子的集合: L(G)=x|S =* x，其中，其中S為文法的開(kāi)始為文法的開(kāi)始符號(hào)，且符號(hào)，且x VVT T* * 例：例：G G： S0S1， S01 L(G)=0n1n|n1例例 文法文法GS：

19、（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）= anbnen | n1 G生成的每個(gè)串都在生成的每個(gè)串都在L(G)中中L(G)中的每個(gè)串確實(shí)能被中的每個(gè)串確實(shí)能被G生成生成根據(jù)1式進(jìn)行n-1次得到an-1 S（BE）n-1 由2式an(BE)n由3式得到anBnEn由4式得anbBn-1En由5式n-1次得到anbnEn由6式1次，7式n-1次得到anbnen28文法的等價(jià)文法的等價(jià)z若若L（G1）=L（G2），則稱文法），則稱文法G1和和G2是是等價(jià)的。等價(jià)的。如文法如文法G G1AA：ADB ADB 與與G G2SS：S0S

20、1 S0S1 等價(jià)等價(jià) ADE S01 ADE S01 EAB EAB D0 D0 B1 B129【例】設(shè)計(jì)一個(gè)表示所有標(biāo)識(shí)符的文法【例】設(shè)計(jì)一個(gè)表示所有標(biāo)識(shí)符的文法分析：標(biāo)識(shí)符的定義是字母或以字母開(kāi)頭的字母數(shù)字串，分析：標(biāo)識(shí)符的定義是字母或以字母開(kāi)頭的字母數(shù)字串，其結(jié)構(gòu)如下：其結(jié)構(gòu)如下：字母字母字母或數(shù)字字母或數(shù)字串串用用 I 表示標(biāo)識(shí)符，表示標(biāo)識(shí)符，L 代表字母，代表字母，D 代表數(shù)字，則定義標(biāo)代表數(shù)字，則定義標(biāo)識(shí)符的文法為：識(shí)符的文法為：G =（VN，VT，P，S）其中：其中：VN = I,L,DVT = a,b,x,y,z,0,1,2,9P = IL | IL |ID L a | b

21、| | x | y | z D 0 | 1 | |9 S = I30【例】用文法定義一個(gè)含【例】用文法定義一個(gè)含+ +、* *的算術(shù)表達(dá)式。的算術(shù)表達(dá)式。變量是表達(dá)式；變量是表達(dá)式；若若 E1 和和 E2 是算術(shù)表達(dá)式，則是算術(shù)表達(dá)式，則 E1+E2，E1*E2，(E) 也也是算術(shù)表達(dá)式。是算術(shù)表達(dá)式。算術(shù)表達(dá)式的文法為：算術(shù)表達(dá)式的文法為：G =（VN，VT，P，S）其中：其中：VN = EVT = i,+,*,(,)P = E i | E+E | E*E |(E) S = E31【例】設(shè)字母表【例】設(shè)字母表 a,ba,b，設(shè)計(jì)一個(gè)文法，描述，設(shè)計(jì)一個(gè)文法，描述語(yǔ)言語(yǔ)言 L=abL=abn

22、na | na | n 0 0 分析：該語(yǔ)言中符號(hào)串的結(jié)構(gòu)特征是：分析：該語(yǔ)言中符號(hào)串的結(jié)構(gòu)特征是：當(dāng)當(dāng) n=0L = aa(b0= )當(dāng)當(dāng) n=1L = aba當(dāng)當(dāng) n=2L = abbaL = aa,aba,abba,abbba,語(yǔ)言的文法為：語(yǔ)言的文法為：G =（A,B，a,b，P，A）其中其中P為：為：AaBaB |Bb32【例】描述語(yǔ)言【例】描述語(yǔ)言L=abL=abn na | na | n 0 0 的的等價(jià)文法等價(jià)文法（1）AaBaB |Bb（2）AaBaB |bB（3）AaBB a |bB（4）ABaB a |Bb33【例】設(shè)有文法【例】設(shè)有文法GS: GS: S S01 | 0

23、S101 | 0S1求該文法所描述的語(yǔ)言求該文法所描述的語(yǔ)言分析：分析：?jiǎn)栴}歸結(jié)為由識(shí)別符號(hào)問(wèn)題歸結(jié)為由識(shí)別符號(hào) S 出發(fā)，將推導(dǎo)出什么樣的句子，出發(fā)，將推導(dǎo)出什么樣的句子，也就是說(shuō)也就是說(shuō) L(GS)是由一些什么樣的符號(hào)串所組成的集合，是由一些什么樣的符號(hào)串所組成的集合，找出其中的規(guī)律，用式子或自然語(yǔ)言描述出來(lái)。找出其中的規(guī)律，用式子或自然語(yǔ)言描述出來(lái)。應(yīng)用第二個(gè)規(guī)則應(yīng)用第二個(gè)規(guī)則 n-1 次，然后再使用第一個(gè)規(guī)則次，然后再使用第一個(gè)規(guī)則 1 次，次，有有S=0S1=00S11=000S111=0n1S1n1=0n1n即即S 0n1n所以此文法定義的語(yǔ)言為所以此文法定義的語(yǔ)言為 +=34【例

24、】設(shè)有文法【例】設(shè)有文法GS: GS: S S0S|1S|0S|1S| 求該文法所定義的語(yǔ)言求該文法所定義的語(yǔ)言該文法所確定的語(yǔ)言為該文法所確定的語(yǔ)言為L(zhǎng)(GS) = ,0,1,00,01,10,11, = x | x0,10,1* * 35【例】設(shè)有文法【例】設(shè)有文法GA: GA: A AyB,BxB|xyB,BxB|x求該文法求該文法所定義的語(yǔ)言所定義的語(yǔ)言從從開(kāi)始符號(hào)開(kāi)始符號(hào) A 出發(fā)，我們可以推出如下句子：出發(fā)，我們可以推出如下句子：A = yB = yxA = yB = yxB =yxx A = yB = yxB = = yxx歸納得出從歸納得出從 A 出發(fā)可推導(dǎo)出所有以出發(fā)可推導(dǎo)出

25、所有以 y 開(kāi)頭后跟一個(gè)或任開(kāi)頭后跟一個(gè)或任意多個(gè)意多個(gè) x 得字符串，即得字符串，即L(GA) = yxn | n 1 36【例】考慮文法【例】考慮文法 G1:S A BA a A | aB b B | b 我們可以分析得出我們可以分析得出 L(G1) = am bn | m, n1【例】構(gòu)造一個(gè)文法【例】構(gòu)造一個(gè)文法 G2 使使L(G2) = an bn | m, n1G2 和和 G1 的區(qū)別在于，的區(qū)別在于，G2 的每個(gè)句子中的每個(gè)句子中 a 和和 b 的個(gè)的個(gè)數(shù)必須相同。數(shù)必須相同。我們可以寫出文法我們可以寫出文法 G2:S a S b | a b【例】【例】37【例】設(shè)字母表【例】設(shè)

26、字母表 a,b,a,b,試設(shè)計(jì)文法，描述語(yǔ)試設(shè)計(jì)文法，描述語(yǔ)言言 L=aL=a2n2n,b,b2n2n | n | n 11分析：設(shè)計(jì)文法來(lái)描述一個(gè)語(yǔ)言，關(guān)鍵是設(shè)計(jì)一組規(guī)則生分析：設(shè)計(jì)文法來(lái)描述一個(gè)語(yǔ)言，關(guān)鍵是設(shè)計(jì)一組規(guī)則生成語(yǔ)言中的符號(hào)串。成語(yǔ)言中的符號(hào)串。設(shè)計(jì)語(yǔ)言的文法，必須分析這個(gè)語(yǔ)言是由怎樣一些符號(hào)串設(shè)計(jì)語(yǔ)言的文法，必須分析這個(gè)語(yǔ)言是由怎樣一些符號(hào)串組成，即首先分析語(yǔ)言中符號(hào)串的結(jié)構(gòu)特征：組成，即首先分析語(yǔ)言中符號(hào)串的結(jié)構(gòu)特征：當(dāng)當(dāng) n=1L = aa,bb當(dāng)當(dāng) n=2L = aaaa,bbbb當(dāng)當(dāng) n=3L = aaaaaa,bbbbbbL = aa,bb,aaaa,bbbb,aaa

27、aaa,bbbbbb,語(yǔ)言語(yǔ)言 L 是由偶數(shù)個(gè)是由偶數(shù)個(gè) a，偶數(shù)個(gè)，偶數(shù)個(gè) b 這樣的符號(hào)串組成的這樣的符號(hào)串組成的集合。集合。383.4 3.4 文法的類型文法的類型通過(guò)對(duì)產(chǎn)生式施加不同的限制，通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將將文法分為四種類型：文法分為四種類型：0型文法：對(duì)任一產(chǎn)生式型文法：對(duì)任一產(chǎn)生式，都有，都有(V(VN NVVT T) )+ +， (V(VN NVVT T) )* *1 1型文法：型文法：對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有，都有|， 僅僅僅僅 SS除外除外2 2型文法：型文法：對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有，都有VVN N 3 3型文法：型文法：任一產(chǎn)生式任

28、一產(chǎn)生式的形式都為的形式都為AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T * *39文法的類型文法的類型例：例：1 1型（上下文有關(guān)）文法型（上下文有關(guān)）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD Ca CaBDbDBDbD Db DbAabDAabD40文法的類型文法的類型例：例：2 2型（上下文無(wú)關(guān)）文法型（上下文無(wú)關(guān)）文法 文法文法GS： SABABABS|0BS|0BSA|1SA|1413 3型文法型文法GS： S0A|1B|00A|1B|0A0

29、A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d42文法的類型文法的類型2型文法型文法1型文法型文法0型文法型文法四類四類文法文法之間之間的的逐級(jí)逐級(jí)“包含包含”關(guān)系關(guān)系3型文法型文法43文法和語(yǔ)言文法和語(yǔ)言0型文法產(chǎn)生的語(yǔ)言稱為型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言型語(yǔ)言1 1型文法或上下文有關(guān)文法（型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語(yǔ)言產(chǎn)生的語(yǔ)言稱為稱為1 1型語(yǔ)言型語(yǔ)言或上下文有關(guān)或上下文有關(guān)語(yǔ)言（語(yǔ)言（CSL）2 2型文法或上下文無(wú)關(guān)文法（型文法或上下文無(wú)關(guān)文法（ CFG ）產(chǎn)生的語(yǔ)言產(chǎn)生的語(yǔ)言稱為稱為

30、2型語(yǔ)言型語(yǔ)言或上下文無(wú)關(guān)或上下文無(wú)關(guān)語(yǔ)言（語(yǔ)言（ CF L ） 3 3型文法或正則（正規(guī)）文法（型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語(yǔ)言產(chǎn)生的語(yǔ)言稱為稱為3型語(yǔ)言型語(yǔ)言正則（正規(guī)）正則（正規(guī)）語(yǔ)言（語(yǔ)言（ RL ） 44文法和語(yǔ)言文法和語(yǔ)言 四種文法之間的關(guān)系四種文法之間的關(guān)系 是將產(chǎn)生式做進(jìn)一步是將產(chǎn)生式做進(jìn)一步限制而定義的。限制而定義的。 語(yǔ)言之間的關(guān)系依次：有不是上下文有關(guān)語(yǔ)言之間的關(guān)系依次：有不是上下文有關(guān)語(yǔ)言的語(yǔ)言的0型語(yǔ)言，有不是上下文無(wú)關(guān)語(yǔ)言的型語(yǔ)言，有不是上下文無(wú)關(guān)語(yǔ)言的1型語(yǔ)言，有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)型語(yǔ)言，有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)言。言。45根據(jù)形式語(yǔ)言理

31、論根據(jù)形式語(yǔ)言理論, ,文法和識(shí)別系文法和識(shí)別系統(tǒng)間有這樣的關(guān)系統(tǒng)間有這樣的關(guān)系 0型文法（短語(yǔ)結(jié)構(gòu)文法）的能力相當(dāng)于圖型文法（短語(yǔ)結(jié)構(gòu)文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且靈機(jī)，可以表征任何遞歸可枚舉集，而且任何任何0型語(yǔ)言都是遞歸可枚舉的型語(yǔ)言都是遞歸可枚舉的 1型文法（上下文有關(guān)文法）：產(chǎn)生式的形型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為式為1 1AA2 21 12 2，即只有，即只有A A出現(xiàn)在出現(xiàn)在1 1和和2 2的上下文中時(shí)，才允許的上下文中時(shí)，才允許取代取代A A。其。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。46 帶帶 a0 a1 a2 a3 a4

32、a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁頭磁頭任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述47 2型文法（上下文無(wú)關(guān)文法型文法（上下文無(wú)關(guān)文法CFG）：產(chǎn)生式）：產(chǎn)生式的形式為的形式為AA，取代取代A A時(shí)與時(shí)與A A的上下文無(wú)的上下文無(wú)關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。 3型文法（正規(guī)文法型文法（正規(guī)文法RG）：產(chǎn)生的語(yǔ)言是）：產(chǎn)生的語(yǔ)言是有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FA）所接受的集合）所接受的集合48 3 3型文

33、法產(chǎn)生的語(yǔ)言是有窮自動(dòng)機(jī)（型文法產(chǎn)生的語(yǔ)言是有窮自動(dòng)機(jī)（FAFA）所接）所接受的集合受的集合. .定理定理 設(shè)設(shè)G=（VN，VT，P，S）是3 3型文法，則存在一個(gè)有窮自型文法，則存在一個(gè)有窮自 動(dòng)機(jī)動(dòng)機(jī) M=(K, , f, A, Z)M=(K, , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)NFA M NFA M 這樣構(gòu)造：這樣構(gòu)造： = = VT K= K= VN N, NN, N為一個(gè)新?tīng)顟B(tài)為一個(gè)新?tīng)顟B(tài), ,它不在它不在VN中 A=S A=S Z=N Z=N 對(duì)對(duì)G G中的形如中的形如 DtBDtB的產(chǎn)生式的產(chǎn)生式,t,t為終結(jié)符或?yàn)榻K結(jié)符或,

34、有有f(D,t)=Bf(D,t)=B； 對(duì)對(duì)G G中形如中形如DtDt的產(chǎn)生式，的產(chǎn)生式， t t為終結(jié)符或?yàn)榻K結(jié)符或,有有f(D,t)=N;f(D,t)=N; 對(duì)對(duì)VT中的每一個(gè)a ,有有f(N,a)=f(N,a)=493 3型文法型文法 和 有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FAFA）G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab503 3型文法型文法 和 有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FAFA）定理定理 已知一有窮自動(dòng)機(jī)M= (K, , f, A, Z),存在有一個(gè)3型文法G = （VN，VT，P，S）,使得L(G)=L(M)G 的定義：

35、 VT = VN= K S = A 若 f(D,t)=B ，則DtB在P中 若 f(D,t)=B ，且B在Z中，則Dt在P中513 3型文法型文法 和 有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FAFA）G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDBASaaabba,bb52正規(guī)文法和正規(guī)式 對(duì)上的正規(guī)式r ,存在一個(gè)RG=(VN,VT,P,S)：L(G)=L(r) 初始， VT= ,S VN ，生成正規(guī)產(chǎn)生式 Sr (R.1) 對(duì)形如 Ar1r2的正規(guī)產(chǎn)生式：Ar1B Br2 BVN (R.2)對(duì)形如Arr1的正規(guī)產(chǎn)生式： ArB Ar1 BrB Br1 BVN (R.3)對(duì)

36、形如Ar1r2的正規(guī)產(chǎn)生式:Ar1 A r2 不斷應(yīng)用(R.x)做變換，直到每個(gè)產(chǎn)生式右端至多有一個(gè)VN53例 r=a(ad)(1) Sa(ad)(2) SaA A(ad) z A(ad)B Az B(ad)Bz B Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B54正規(guī)文法和正規(guī)式 對(duì)G=(VN,VT,P,S),存在一個(gè) =VT上的正規(guī)式r : L(r)=L(G) AxB, By 形成正規(guī)式 A=xy AxAy 形成正規(guī)式 A=xy Axy 形成正規(guī)式 A=xy55正規(guī)文法和正規(guī)式Gs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad)

37、 S=a(ad)(ad)a=a(ad)(ad)=a(ad) R=a(ad)563.5 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法有足夠的能力描述程序設(shè)計(jì)語(yǔ)言的上下文無(wú)關(guān)文法有足夠的能力描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)語(yǔ)法結(jié)構(gòu)語(yǔ)法樹(shù)語(yǔ)法樹(shù)-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示57語(yǔ)法樹(shù)語(yǔ)法樹(shù)-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示 ( (句型、推導(dǎo))GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE+T E+T*F E+T*a E+F*a E+a*

38、a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a58語(yǔ)法樹(shù)語(yǔ)法樹(shù)設(shè)G=( VN,VT,P,S)為一cfg，若一棵樹(shù)滿足下列4個(gè)條件，則此樹(shù)稱作G的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))(派生樹(shù)）：1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2. 根的標(biāo)記是S3. 若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定AVN4. 如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個(gè)產(chǎn)生式語(yǔ)法樹(shù)的結(jié)果：語(yǔ)法樹(shù)的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂

39、之 59上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)z句型句型aabbaa的可能的可能推導(dǎo)序列和語(yǔ)法樹(shù)推導(dǎo)序列和語(yǔ)法樹(shù) 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa60語(yǔ)法樹(shù)語(yǔ)法樹(shù)-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示給定文法給定文法G=(VN,VT,P,S)，對(duì)于，對(duì)于G的任何句型都能的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù)推導(dǎo)樹(shù))定理：定理： G為上下文無(wú)關(guān)文法，對(duì)于，有S

40、=* ，當(dāng)且僅當(dāng)文法G有以為結(jié)果的一棵語(yǔ)法樹(shù)(推導(dǎo)樹(shù))61規(guī)范推導(dǎo)規(guī)范推導(dǎo) 規(guī)范句型規(guī)范句型z最左（最右）推導(dǎo)：在推導(dǎo)的任何一步最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中，其中、是句型，都是對(duì)是句型，都是對(duì)中中的最左（右）非終結(jié)符進(jìn)行替換的最左（右）非終結(jié)符進(jìn)行替換z最右推導(dǎo)被稱為規(guī)范推導(dǎo)。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。z由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型62z一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的( (但未必是所有的但未必是所有的) )不同推導(dǎo)過(guò)程，包括最不同推導(dǎo)過(guò)程，包括最左左( (最右最右) )推導(dǎo)。推導(dǎo)。z但是，一個(gè)句型是否只對(duì)應(yīng)

41、唯一的一棵語(yǔ)但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢法樹(shù)呢? ?一個(gè)句型是否只有唯一的一個(gè)最左一個(gè)句型是否只有唯一的一個(gè)最左( (最右最右) )推導(dǎo)呢推導(dǎo)呢? ?63例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+

42、E i*i+E i*i+i64二義文法二義文法z若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是語(yǔ)法樹(shù)，則稱這個(gè)文法是二義二義的的z若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是左（右）推導(dǎo)，則稱這個(gè)文法是二義二義的的z判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，但可語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，但可以為無(wú)二義性尋找一組充分條件以為無(wú)二義性尋找一組充分條件 6

43、5文法的二義性和語(yǔ)言的二義性文法的二義性和語(yǔ)言的二義性文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法的文法G G和和GG，其中，其中G G是二義的，但是卻有是二義的，但是卻有L(G)=L(G)L(G)=L(G)，也就是說(shuō)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。二義文法改造為無(wú)二義文法二義文法改造為無(wú)二義文法GE:E i GEGE:E i GE： E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E

44、E）|i|i E (E) E (E) 規(guī)定算符優(yōu)先性和結(jié)合性規(guī)定算符優(yōu)先性和結(jié)合性 如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。663.6 3.6 句型的分析（句型的分析（上下文無(wú)關(guān)文法）上下文無(wú)關(guān)文法）z句型分析句型分析就是就是識(shí)別識(shí)別一個(gè)符號(hào)串是否為某文法一個(gè)符號(hào)串是否為某文法的的句型句型，是某個(gè)，是某個(gè)推導(dǎo)推導(dǎo)的

45、構(gòu)造過(guò)程。的構(gòu)造過(guò)程。z在語(yǔ)言的編譯實(shí)現(xiàn)中，把在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析完成句型分析的的程程序序稱為稱為分析程序分析程序或或識(shí)別程序識(shí)別程序。分析算法又稱。分析算法又稱識(shí)別算法識(shí)別算法。z從左到右的分析算法從左到右的分析算法，即，即總是從總是從左左到到右右地地識(shí)識(shí)別輸入符號(hào)串別輸入符號(hào)串，首先識(shí)別符號(hào)串中的，首先識(shí)別符號(hào)串中的最左最左符符號(hào)，進(jìn)而號(hào)，進(jìn)而依次識(shí)別右邊依次識(shí)別右邊的一個(gè)符號(hào)，的一個(gè)符號(hào)，直到分直到分析結(jié)束析結(jié)束。67句型的句型的分析算法分類分析算法分類分析算法可分為：分析算法可分為：z自上而下分析法自上而下分析法：從文法的開(kāi)始符號(hào)出發(fā)從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的，

46、反復(fù)使用文法的產(chǎn)生式，產(chǎn)生式，尋找尋找與與輸入符號(hào)串輸入符號(hào)串匹配匹配的的推導(dǎo)，推導(dǎo)，或者說(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。z自下而上分析法自下而上分析法：從從輸入符號(hào)串輸入符號(hào)串開(kāi)始開(kāi)始，逐步進(jìn)行逐步進(jìn)行歸約歸約，直至，直至歸約歸約到到文法的文法的開(kāi)始符號(hào)開(kāi)始符號(hào)。 68兩種方法反映了兩種語(yǔ)法樹(shù)的構(gòu)造過(guò)程。兩種方法反映了兩種語(yǔ)法樹(shù)的構(gòu)造過(guò)程。y自上而下方法自上而下方法是從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串y自下而上方法自下而上方法則是從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果，自底向上的構(gòu)造語(yǔ)法樹(shù)691 1、自上而下

47、的語(yǔ)法分析、自上而下的語(yǔ)法分析例：文法例：文法G： S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法的句子句子SSScAdcAd a b推導(dǎo)過(guò)程：推導(dǎo)過(guò)程：S cAd cAd cabd702 2、自下而上的語(yǔ)法分析、自下而上的語(yǔ)法分析例：文法例：文法G： S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd是否該文法的是否該文法的句子句子SAA c a b d c a b d c a b d 規(guī)約規(guī)約過(guò)程構(gòu)造的推導(dǎo)：過(guò)程構(gòu)造的推導(dǎo)： cAd cabd S cAd71自上而下的語(yǔ)法分析自上而下的語(yǔ)法分析(1)S cAd (2) A ab (3) A

48、a 識(shí)別輸入串識(shí)別輸入串w=cad是否為該文法的是否為該文法的句子句子若S cAd 后選擇(2)擴(kuò)展A，S cAd cabd那將會(huì)？ w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號(hào)卻不能與下一葉子結(jié)點(diǎn)d匹配？宣告分析失?。ㄆ湟馕吨?，識(shí)別程序不能為串cad構(gòu)造語(yǔ)法樹(shù)，即cad不是句子）-顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。 S c A d a b 這時(shí)應(yīng)該回溯回溯，把A為根的子樹(shù)剪掉，掃描過(guò)的輸入串中的a吐出來(lái),再試探用產(chǎn)生式（3）72(1)S cAd (2) A ab (3)A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法的句子句子自下而上的語(yǔ)

49、法分析自下而上的語(yǔ)法分析對(duì)串cabd的分析中，如果不是選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么在c A b d中無(wú)法找到一個(gè)可歸約串了，最終就達(dá)不到歸約到S的結(jié)果，因而也無(wú)從知道cabd是一個(gè)句子c a b d c A b d a733、句型分析的有關(guān)問(wèn)題、句型分析的有關(guān)問(wèn)題1）在自上而下的分析方法中）在自上而下的分析方法中如何如何選擇選擇使用使用哪個(gè)哪個(gè)產(chǎn)生式進(jìn)產(chǎn)生式進(jìn)行推導(dǎo)行推導(dǎo)？假定要被代換的最左非終結(jié)符號(hào)是假定要被代換的最左非終結(jié)符號(hào)是B，且有，且有n條規(guī)則：條規(guī)則：BA1|A2|An，那么如何確定用哪個(gè)右部去替代，那么如何確定用哪個(gè)右部去替代B？2）在自下而上的分析方法中）在自下而上的分析方法中如何如何識(shí)別可歸約的串識(shí)別可歸約的串？在分析程序工作的每一步，都是從當(dāng)前串中在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)選擇一個(gè)子子串串，將它，將它歸約歸約到到某個(gè)非終結(jié)符號(hào)某個(gè)非終結(jié)符號(hào)，該子串稱為，該子串稱為“可歸約可歸約串串”743、句型分析的有關(guān)問(wèn)題、句型分析的有關(guān)問(wèn)題z若若G是一文法，是一文法，S是文法的開(kāi)始符號(hào)，是文法的開(kāi)