課件及課后答案第3章文法和語法lly

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

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

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

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

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

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

7、 x3=ABABAB對于 n0, x n = xxn-1 = xn-1x 4）符號串集合：若集合A中一切元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。* = 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）兩個符號串集合A和B的乘積定義為AB =xy|xA且yB 若 集合A=a,b B = c,d 則 AB =ac,ad,bc,bd A = A = A (x = x= x)6）使用 * 表示上的所有有窮長的串（包括）的

8、集合。 *稱為的閉包。7）從*中除去得到的集合記為+ 。 +稱為的正閉包。1、規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）： 是形如或=的（，）有序?qū)?，其中是某字母表V的正閉包V+中的一個符號，是V*中的一個符號。（V+，V* why?) 稱為規(guī)則的左部(或生成式的左部)。 稱為規(guī)則的右部(或生成式的右部)。例：句子:= 主語謂語主語:= 代詞|名詞代詞:= 你 | 我 | 他3.3 文法和語言的形式定義2、文法G定義為四元組（VN，VT，P，S）元素說明：VN ：非終結(jié)符集VT ：終結(jié)符集P：產(chǎn)生式（規(guī)則）集合S：開始符號（識別符號）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為開始符號例3.2 文法G=（VN，VT，P，S）VN =標識符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, z 0, 9 S=思考： C語言的標識符（變量命名）如何用文法定義？文法習慣上只將產(chǎn)生式寫出。并有如下約定：第一條產(chǎn)生式的左部是開始符號用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符G可寫成GS，其中S是開始符號例3.1 文法G=（VN，VT，P，S）VN =

10、S , VT = 0, 1 P= S0S1, S01 S為開始符號可寫成： G：S0S1 S01或?qū)懗桑?GS：S0S1 S013、推導的定義直接推導“”是文法G產(chǎn)生式，,V*，若v,w滿足：v=, w = ,則說：v（應(yīng)用規(guī)則）直接產(chǎn)生w或說：w是v的直接推導 或說：w直接歸約到v記作 v w例：G： S0S1， S01 的直接推導：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 =標識符，字母，數(shù)字VT =

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

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

13、法）：對任一產(chǎn)生式，都有(VNVT)+且至少含一個非終結(jié)符， (VNVT)*1型文法（上下文有關(guān)文法）：對任一產(chǎn)生式，都有|， 僅僅 A除外。2型文法（上下文無關(guān)文法） ：對任一產(chǎn)生式，都有VN ， (VNVT)*3型文法（正規(guī)文法）：任一產(chǎn)生式的形式都為AaB或Aa，AVN ，BVN ，aVT (右線性文法)ABa或Aa，AVN ，BVN ，aVT (左線性文法)思考：四種文法之間的關(guān)系？四種文法之間的逐級“包含”關(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 ？文法和語言0型文法( PSG )產(chǎn)生的語言稱為0型語言1型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言（CSL）2型文法或上下文無關(guān)文法（ CFG ）產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語言稱為3型語言正則（正規(guī)）語言（ RL ）思考：文法與語言的關(guān)系？ 3.5 上下文無關(guān)文法及其語法樹1、上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計語言的語法結(jié)構(gòu)

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

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

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

18、棵不同的語法樹，則稱這個文法是二義的。（或者，若一個文法存在某個句子有兩個不同的最左（右）推導）語言先天二義： 產(chǎn)生某上下文無關(guān)語言的每一個文法都是二義的。說明：判定任何文法或語言的二義性是不可解的。但可以為無二義性尋找一組充分條件。例：二義文法改造為無二義文法（如：i*i+i的推導）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 句型的分析句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構(gòu)造過程。在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為分析程序或識別程序。分析算法又稱識別算法。分析

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

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

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