課件及課后答案第3章文法和語(yǔ)法lly

1、第3章文法和語(yǔ)言考查重點(diǎn)基本概念 ： 文法；推導(dǎo)/歸約；句型；句子；語(yǔ)言；文法的二義性；文法遞歸；語(yǔ)法樹(shù)；短語(yǔ)；直接短語(yǔ)；句柄；正規(guī)文法；上下文無(wú)關(guān)文法。基本方法構(gòu)造句型的推導(dǎo)/歸約，規(guī)范推導(dǎo)/規(guī)范歸約畫出指定句型的語(yǔ)法樹(shù)判別文法的二義性給出句型的短語(yǔ)、直接短語(yǔ)、句柄。文法與語(yǔ)言的互求（較簡(jiǎn)單）1、語(yǔ)言語(yǔ)言是由句子組成的集合，是由一組記號(hào)所構(gòu)成的集合。漢語(yǔ)-所有符合漢語(yǔ)語(yǔ)法的句子的全體英語(yǔ)-所有符合英語(yǔ)語(yǔ)法的句子的全體程序設(shè)計(jì)語(yǔ)言-所有該語(yǔ)言的程序的全體研究語(yǔ)言 ：每個(gè)句子構(gòu)成的規(guī)律每個(gè)句子的含義每個(gè)句子和使用者的關(guān)系3.1 語(yǔ)言與文法的直觀概念研究程序設(shè)計(jì)語(yǔ)言及研究的三個(gè)方面： 每個(gè)程序構(gòu)成

2、的規(guī)律（語(yǔ)法 Syntax）每個(gè)程序的含義（語(yǔ)義 Semantics）每個(gè)程序和使用者的關(guān)系（語(yǔ)用 Pragmatics）語(yǔ)言三個(gè)方面定義：語(yǔ)法 - 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律語(yǔ)義 - 表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）語(yǔ)用 -表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、使用和影響。以自然語(yǔ)言為例（用 EBNF 描述一種語(yǔ)言：）補(bǔ)講：終端符與非終端符思考：“我是大學(xué)生”是否是該語(yǔ)言的句子？句子:= 主語(yǔ)謂語(yǔ)主語(yǔ):= 代詞|名詞代詞:= 你 | 我 | 他名詞:= 王明 | 大學(xué)生 | 工人 | 英語(yǔ)謂語(yǔ):= 動(dòng)詞直接賓語(yǔ)動(dòng)詞:=

3、 是 | 學(xué)習(xí)直接賓語(yǔ):= 代詞|名詞2、文法文法：僅僅涉及語(yǔ)言句子的結(jié)構(gòu)描述。句子 主語(yǔ)謂語(yǔ) 代詞謂語(yǔ) 我謂語(yǔ) 我動(dòng)詞直接賓語(yǔ) 我是直接賓語(yǔ) 我是名詞 我是大學(xué)生思考： “”的含義？“我大學(xué)生是” 與“大學(xué)生是王明”是句子?句子:= 主語(yǔ)謂語(yǔ)主語(yǔ):= 代詞|名詞代詞:= 你 | 我 | 他名詞:= 王明 | 大學(xué)生 | 工人 | 英語(yǔ)謂語(yǔ):= 動(dòng)詞直接賓語(yǔ)動(dòng)詞:= 是 | 學(xué)習(xí)直接賓語(yǔ):= 代詞|名詞語(yǔ)法規(guī)則（文法）3、程序設(shè)計(jì)語(yǔ)言與文法關(guān)系：一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，如自然語(yǔ)言一樣，由語(yǔ)句組成，完整的定義應(yīng)包含語(yǔ)法與語(yǔ)義兩個(gè)方面。語(yǔ)法規(guī)定了語(yǔ)句形成的規(guī)則，（哪些符號(hào)序列是合法的，而與

4、其含義無(wú)關(guān)）；語(yǔ)義不僅要限定語(yǔ)法規(guī)則（靜態(tài)），而且要表明程序要做什么（動(dòng)態(tài)）。文法是闡述語(yǔ)法規(guī)則的工具，是形式語(yǔ)言理論基礎(chǔ)。為語(yǔ)言的語(yǔ)法描述尋求工具工具要對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀）形式工具-形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问健笔侵高@樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。字母表：元素的非空有窮集合。（符號(hào)集）符號(hào)：字母表中的元素。例如：漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)符號(hào)等。C語(yǔ)言字母表是由字母、數(shù)字、若干專用符號(hào)及保留字組成。3.2 符號(hào)和符號(hào)串1、符號(hào)例如： =0,1,0,1,00,01,11,1001110等都是上的符號(hào)串.注意

5、：符號(hào)串中的符號(hào)排列是有順序的.可以用字母表示符號(hào)串，如 x=aaca1）符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列稱為該字母表上的符號(hào)串?？辗?hào)串(沒(méi)有符號(hào)的符號(hào)串)是上的符號(hào)串 若x是上符號(hào)串,a是的元素,則xa和ax是上符號(hào)串 y是上的符號(hào)串,當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。2、符號(hào)串2）串的頭與尾如果 z = xy 是一符號(hào)串，那么：x 是 z 的頭，y 是 z 的尾；如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有頭。例：設(shè) z = abc, 那么z 的頭是： ,a ,ab , abc（固有頭呢？）z 的尾是： ,c ,bc , abc（固有尾呢？）3）串的幾種表示法

6、（x,z是符號(hào)串,t是符號(hào)）：z = xx 是符號(hào)串 z 的頭z = xx 在符號(hào)串z 中某處出現(xiàn)z = t符號(hào) t 是 符號(hào)串 z 的第一個(gè)符號(hào)3、符號(hào)串的運(yùn)算1）符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù).符號(hào)串s的長(zhǎng)度記為|s|。 的長(zhǎng)度為02）連接：符號(hào)串x、y的連接,是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串xy例： x=ST,y=abu 則 xy=STabu |x|=2,|y|=3,|xy|=5 x = x= x3）方冪：符號(hào)串x自身連接n次得到的符號(hào)串 xxxx(n個(gè)x)定義為 x n x0=, x1=x, x2=xx, x3=xxx x=AB, 則 x0=, x1=AB, x2=ABAB,

7、 x3=ABABAB對(duì)于 n0, x n = xxn-1 = xn-1x 4）符號(hào)串集合：若集合A中一切元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。* = 0 1 2 n + = 1 2 n * = 0 + = * = * + = * -例：設(shè)=a,b，則 *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,5）兩個(gè)符號(hào)串集合A和B的乘積定義為AB =xy|xA且yB 若 集合A=a,b B = c,d 則 AB =ac,ad,bc,bd A = A = A (x = x= x)6）使用 * 表示上的所有有窮長(zhǎng)的串（包括）的

8、集合。 *稱為的閉包。7）從*中除去得到的集合記為+ 。 +稱為的正閉包。1、規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）： 是形如或=的（，）有序?qū)?，其中是某字母表V的正閉包V+中的一個(gè)符號(hào)，是V*中的一個(gè)符號(hào)。（V+，V* why?) 稱為規(guī)則的左部(或生成式的左部)。 稱為規(guī)則的右部(或生成式的右部)。例：句子:= 主語(yǔ)謂語(yǔ)主語(yǔ):= 代詞|名詞代詞:= 你 | 我 | 他3.3 文法和語(yǔ)言的形式定義2、文法G定義為四元組（VN，VT，P，S）元素說(shuō)明：VN ：非終結(jié)符集VT ：終結(jié)符集P：產(chǎn)生式（規(guī)則）集合S：開(kāi)始符號(hào)（識(shí)別符號(hào)）VN、VT 和 P 是非空有窮集。S 至少在一條規(guī)則中作為左部出現(xiàn)。V

9、NVT= ， SVNV=VNVT，稱為文法G的字母表（字匯表）例3.1 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S為開(kāi)始符號(hào)例3.2 文法G=（VN，VT，P，S）VN =標(biāo)識(shí)符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, z 0, 9 S=思考： C語(yǔ)言的標(biāo)識(shí)符（變量命名）如何用文法定義？文法習(xí)慣上只將產(chǎn)生式寫出。并有如下約定：第一條產(chǎn)生式的左部是開(kāi)始符號(hào)用尖括號(hào)括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符G可寫成GS，其中S是開(kāi)始符號(hào)例3.1 文法G=（VN，VT，P，S）VN =

10、S , VT = 0, 1 P= S0S1, S01 S為開(kāi)始符號(hào)可寫成： G：S0S1 S01或?qū)懗桑?GS：S0S1 S013、推導(dǎo)的定義直接推導(dǎo)“”是文法G產(chǎn)生式，,V*，若v,w滿足：v=, w = ,則說(shuō)：v（應(yīng)用規(guī)則）直接產(chǎn)生w或說(shuō)：w是v的直接推導(dǎo) 或說(shuō)：w直接歸約到v記作 v w例：G： S0S1， S01 的直接推導(dǎo)：0S10011 （v=0S1，w=0011，使用規(guī)則S01，=0，=1）S 0S1 （v=S，w=0S1，使用規(guī)則S0S1，=，= ）0S100S11 （v=0S1，w=00S11，使用規(guī)則？）例 文法G=（VN，VT，P，S）VN =標(biāo)識(shí)符，字母，數(shù)字VT =

11、a,b,c,x,y,z,0,1,9P= a, z 0, 9 S=思考：指出下面直接推導(dǎo)所使用的規(guī)則 ？ abc abc5例：G： S0S1， S010S1 00S11 000S111 00001111 即 0S1 00001111也記作 0S1 00001111思考： 的區(qū)別？若存在v =w0 w1 . wn=w, (n0) 則稱v推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長(zhǎng)度為n），或稱w歸約到v. 記作 v w若有v w，或v=w，則記為v w+*+*+*和+*和4、文法的句型、句子的定義句型：設(shè)GS是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即S x，則稱x是文法GS的句型。句子：x僅由終結(jié)符號(hào)組成（即S

12、 x，且xVT*），則稱x是GS的句子。例：G： S0S1， S01S 0S1 00S11 000S11100001111*思考：文法的句型與句子的關(guān)系？文法G能得到哪些句子？ 5、語(yǔ)言的定義：由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的一切句子的集合: 即L(G)=x|S x，其中S為文法的開(kāi)始符號(hào)，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1*6、文法的等價(jià)：若L（G1）=L（G2），則稱文法G1和G2是等價(jià)的。課堂作業(yè)：P44 2思考：文法G1A：A0R A01 RA1的語(yǔ)言？3.4 文法的類型Chomsky將文法分四類（對(duì)產(chǎn)生式施加不同限制 ）：0型文法（短語(yǔ)文

13、法）：對(duì)任一產(chǎn)生式，都有(VNVT)+且至少含一個(gè)非終結(jié)符， (VNVT)*1型文法（上下文有關(guān)文法）：對(duì)任一產(chǎn)生式，都有|， 僅僅 A除外。2型文法（上下文無(wú)關(guān)文法） ：對(duì)任一產(chǎn)生式，都有VN ， (VNVT)*3型文法（正規(guī)文法）：任一產(chǎn)生式的形式都為AaB或Aa，AVN ，BVN ，aVT (右線性文法)ABa或Aa，AVN ，BVN ，aVT (左線性文法)思考：四種文法之間的關(guān)系？四種文法之間的逐級(jí)“包含”關(guān)系2型文法1型文法0型文法3型文法例：判斷下列文法的類型1： 文法GS： SaSBE SaBE EBBE aBab / aBbab ？ bBbb bEbe eEee2： 文法GS

14、： SaB|bA Aa|aS|bAA Bb|bS|aBB /B ？3: 文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0 / BB1|1|0 ？文法和語(yǔ)言0型文法( PSG )產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言1型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語(yǔ)言稱為1型語(yǔ)言或上下文有關(guān)語(yǔ)言（CSL）2型文法或上下文無(wú)關(guān)文法（ CFG ）產(chǎn)生的語(yǔ)言稱為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語(yǔ)言稱為3型語(yǔ)言正則（正規(guī)）語(yǔ)言（ RL ）思考：文法與語(yǔ)言的關(guān)系？ 3.5 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)1、上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)

15、。 注：無(wú)特殊說(shuō)明，“文法”均指上下文無(wú)關(guān)文法算術(shù)表達(dá)式語(yǔ)句賦值語(yǔ)句條件語(yǔ)句讀語(yǔ)句例：算術(shù)表達(dá)式文法表示（i為變量）G=(E, +,*,i,(,), P, E P:E iE E+EE E*EE (E)例：賦值語(yǔ)句文法表示 i = E例：條件語(yǔ)句文法表示 ifthen | ifthenelse 思考：是上下文無(wú)關(guān)文法？文法的VN,VT, P, S ?2、上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)用于描述上下文無(wú)關(guān)文法的句型推導(dǎo)的直觀方法 例: GS:SaASASbAASSSaAba能得到句型aabbaa？ S a A S S b A a a b a句型aabbaa的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）葉子結(jié)點(diǎn)：樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。從左

16、到右讀出推導(dǎo)樹(shù)的葉子標(biāo)記，所得的句型為推導(dǎo)樹(shù)的結(jié)果。也把該推導(dǎo)樹(shù)稱為該句型的語(yǔ)法樹(shù)。推導(dǎo)過(guò)程中施用產(chǎn)生式的順序 例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型aabbaa的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型 例: GS:SaASASbAASSSaAbaSaASaAaaSbAaa

17、SbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa思考：最右推導(dǎo)的逆過(guò)程？ 一個(gè)句型是否對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)？問(wèn)題：一個(gè)句型是否對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)？例：GE:E iE E+EE E*EE (E)思考：構(gòu)造句型 i*i+i語(yǔ)法樹(shù)？ E E + E E * E i i i E E * E i E + E i i句型 i*i+i 的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i二義性文法二義性： 若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩

18、棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。（或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)）語(yǔ)言先天二義： 產(chǎn)生某上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的。說(shuō)明：判定任何文法或語(yǔ)言的二義性是不可解的。但可以為無(wú)二義性尋找一組充分條件。例：二義文法改造為無(wú)二義文法（如：i*i+i的推導(dǎo)）GE: E i GE： E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 規(guī)定優(yōu)先順序和結(jié)合律（第6章）3.6 句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法又稱識(shí)別算法。分析

19、算法可分為：自上而下分析法：從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的推導(dǎo)。自下而上分析法：從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)。 兩種方法反映了兩種不同的語(yǔ)法樹(shù)的構(gòu)造過(guò)程自上而下的語(yǔ)法分析例：文法G：S cAd A ab A a識(shí)別輸入串 w = cabd 是否該文法的句子推導(dǎo)過(guò)程：S cAd cabd思考：此種分析方法的關(guān)鍵是什么？自下而上的語(yǔ)法分析例：文法G：S cAd A ab A a識(shí)別輸入串 w = cabd 是否該文法的句子。規(guī)約過(guò)程：S cAd cabd思考：此種分析方法的關(guān)鍵是什么？句型分析的有關(guān)問(wèn)題1）如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？

20、假定要被代換的最左非終結(jié)符號(hào)是V，且有n條規(guī)則：VA1|A2|An，那么如何確定用哪個(gè)右部去替代V？2）如何識(shí)別可歸約的串？在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱為“可歸約串”短語(yǔ)、直接短語(yǔ)、句柄的定義：文法GS， 是G的一個(gè)句型， 如果：S A且A ， 則稱是句型相對(duì)于非終結(jié)符A的短語(yǔ)。 若有A 則稱是句型相對(duì)于規(guī)則A的直接短語(yǔ)（或簡(jiǎn)單短語(yǔ)）。 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。*+例 文法：GE：EE+T|T TT*F|F F(E)|a1|a2|a3求句型：a1+a2*a3的短語(yǔ)，直接短語(yǔ)與句柄？求解方式：定義或

21、語(yǔ)法樹(shù)來(lái)判定.例 文法：GE：EE+T|T TT*F|F F(E)|a句型：a1+a2*a3短語(yǔ)：a1 , a2 , a3 , a2*a3 , a1+a2*a3 直接短語(yǔ)：a1 , a2 , a3句柄：a1思考：+是短語(yǔ)嗎？a1 + a2是短語(yǔ)？F*a3是短語(yǔ)？語(yǔ)法樹(shù)中句型,短語(yǔ)和句柄(1)每一句型都有一棵語(yǔ)法樹(shù)，每個(gè)語(yǔ)法樹(shù)的所有有序葉子組成一句型（句子？）。(2)每棵子樹(shù)的所有葉子組成短語(yǔ)，每棵直接子樹(shù)的所有葉子組成直接短語(yǔ)，最左直接子樹(shù)的葉子組成句柄（直接子樹(shù)？一層分支） 思考：句型的a1+T*F的短語(yǔ)？注：若語(yǔ)法樹(shù)不易判時(shí)，可結(jié)合定義判定！3.8有關(guān)文法實(shí)用中的一些說(shuō)明1、有關(guān)文法的實(shí)用限制 （文法中不得含有有害規(guī)則和多余規(guī)則）有害規(guī)則：形如UU的產(chǎn)生式。引起文法二義性（why）。多余規(guī)則：文法中任何句子推導(dǎo)都不會(huì)用到的規(guī)則。文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)（開(kāi)始符號(hào)除外），該非終結(jié)符稱為不可到達(dá)的文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串來(lái)，稱為不可終止的對(duì)于文法GS，為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個(gè)條件：1）A（