第2章+文法和語言

1、文法和語言文法和語言n一個程序設(shè)計語言是一個記號系統(tǒng)，它的完整一個程序設(shè)計語言是一個記號系統(tǒng)，它的完整定義應(yīng)包括兩個方面定義應(yīng)包括兩個方面:q語法語法指一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序。q語義語義n靜態(tài)語義是一系列限定規(guī)則，并確定哪些合乎語法的程序是合適的；n動態(tài)語義也稱作運行語義或執(zhí)行語義，表明程序要做些什么，要計算什么。n文法是闡明語法的一個工具文法是闡明語法的一個工具2. 2 符號和符號串符號和符號串n字母表字母表 q字母表是元素的非空有窮集合字母表是元素的非空有窮集合n符號符號q字母表中的元素稱為符號字母表中的元素稱為符號n符號串符號串q由符號組成的任何有窮序列由符號組成的任

2、何有窮序列q符號串符號串x的長度：的長度：x所包含的符號個數(shù)，記作所包含的符號個數(shù)，記作|x|q空符號串空符號串 n符號串的頭、尾、固有頭、固有尾符號串的頭、尾、固有頭、固有尾n符號串的連接符號串的連接q設(shè)設(shè)x和和y是符號串，它們的連接是符號串，它們的連接xy是把是把y的符號寫在的符號寫在x的符號之后得到的符號串。的符號之后得到的符號串。n符號串的方冪符號串的方冪q設(shè)設(shè)x是符號串，把是符號串，把x自身連接自身連接n次得到符號串次得到符號串z，即即z=xx.xx，稱為符號串稱為符號串x的方冪。的方冪。0=, n =n-1 =n-1（n0）n符號串集合及其運算符號串集合及其運算q若集合若集合A中的

3、一切元素都是字母表上的符號串，則中的一切元素都是字母表上的符號串，則稱稱A為該字母表上的符號串集合。為該字母表上的符號串集合。q合并：字符串集合合并：字符串集合A和和B的合并的合并AB=|A或或B。q乘積：字符串集合乘積：字符串集合A和和B的乘積的乘積AB=|A且且B。顯然顯然A=A=A。q冪：冪：An=An-1A=AAn-1（n0），），并規(guī)定并規(guī)定A0=。q正閉包：正閉包：A+ =A1A2An。q閉包：閉包：A*=A0A+。顯然顯然*=012n 。*表示表示上的所有有窮長的串的集合上的所有有窮長的串的集合2.3 文法和語言的形式定義文法和語言的形式定義n引例引例1 =a, A=an|n1n

4、引例引例2 =a,b, A=anbm|n,m1n引例引例3 =a,b, A=anbn|n1n定義定義2.1-文法文法文法文法G定義為四元組定義為四元組(VN，VT，P，S)。其中其中VN: 非終結(jié)符的非空有窮集；非終結(jié)符的非空有窮集；VT: 終結(jié)符的非空有窮集；終結(jié)符的非空有窮集；P: 產(chǎn)生式（也稱規(guī)則）的非空有窮集；產(chǎn)生式（也稱規(guī)則）的非空有窮集； S: 開始符號，它是一個非終結(jié)符，至少要開始符號，它是一個非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。在一條規(guī)則中作為左部出現(xiàn)。通常用通常用V表示表示VN VT，V稱為文法稱為文法G的的文法文法符號集符號集。n例例1=a,b, A=ambn|mn0

5、n例例2=a,b, A=wwR|wR是是w的反向串的反向串n例例3GS:SaSBE|aBEEB BEaB abbB bbbE beeE een定義定義2.2-直接推導(dǎo)、直接歸約直接推導(dǎo)、直接歸約設(shè)設(shè) 是文法是文法G=(VN ，VT，P，S)的規(guī)則，的規(guī)則， 和和 是是V*中的任意符號串。若有符號串中的任意符號串。若有符號串v，w滿滿足：足：v=， w=，則說則說 v（應(yīng)用規(guī)則應(yīng)用規(guī)則 ）直接產(chǎn)生）直接產(chǎn)生w，或說或說w是是v的直接推導(dǎo)，或說的直接推導(dǎo)，或說w直接歸約到直接歸約到v，記作記作 vw。n定義定義2.3 -推導(dǎo)推導(dǎo)若存在若存在v w0 w1 . wn=w (n0)，則則說說v推導(dǎo)出推

6、導(dǎo)出w，或說或說w歸約到歸約到v，記為記為 v w。n定義定義2.4-星推導(dǎo)星推導(dǎo)若有若有v w，或或v=w，則記為則記為v w。*n最左（最右）推導(dǎo)最左（最右）推導(dǎo)q如果在推導(dǎo)的任何一步如果在推導(dǎo)的任何一步 ，其中，其中 V* ，都是，都是對對 中的最左（最右）非終結(jié)符進行替換，則稱這中的最左（最右）非終結(jié)符進行替換，則稱這種推導(dǎo)為最左（最右）推導(dǎo)種推導(dǎo)為最左（最右）推導(dǎo)n規(guī)范推導(dǎo)規(guī)范推導(dǎo)q在形式語言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。在形式語言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。n定義定義2.5-句型、句子句型、句子設(shè)設(shè)有文法有文法G。若若S x，則稱則稱x是文法是文法G的句型；的句型；若若S x，且

7、且xVT*，則稱則稱x是文法是文法G的句子。的句子。n規(guī)范句型規(guī)范句型q由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。*n定義定義2.6- 語言語言由文法由文法G生成的語言記為生成的語言記為L(G),它是文法它是文法G的一切的一切句子的集合。句子的集合。n定義定義2.7-文法等價文法等價若若L(G1) = L(G2)，則稱文法則稱文法G1和和G2是等價的。是等價的。2.4 文法的類型文法的類型nChomsky分類分類q0型文法型文法 短語文法短語文法對任一產(chǎn)生式對任一產(chǎn)生式，都有都有(VNVT)+且至少含有一個且至少含有一個非終結(jié)符，非終結(jié)符， (VNVT)*q1型文法型

8、文法-上下文有關(guān)文法（上下文有關(guān)文法（CSG） 對任一產(chǎn)生式對任一產(chǎn)生式，都有都有|， 僅僅僅僅 S除外除外q2型文法型文法-上下文無關(guān)文法（上下文無關(guān)文法（CFG） 對任一產(chǎn)生式對任一產(chǎn)生式，都有都有VN ， (VNVT)*q3型文法型文法-正規(guī)文法（正規(guī)文法（RG） 任一產(chǎn)生式任一產(chǎn)生式的形式都為的形式都為AaB或或Aa，其中其中AVN ，BVN ，aVT2型文法型文法1型文法型文法0型文法3型文法2型文法型文法1型文法型文法2型文法型文法1型文法型文法2型文法型文法1型文法型文法0型文法3型文法n0型文法產(chǎn)生的語言稱為型文法產(chǎn)生的語言稱為0型語言型語言1型文法或上下文有關(guān)文法產(chǎn)生的語言稱

9、為型文法或上下文有關(guān)文法產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言型語言或上下文有關(guān)語言2型文法或上下文無關(guān)文法產(chǎn)生的語言稱為型文法或上下文無關(guān)文法產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言型語言或上下文無關(guān)語言3型文法或正規(guī)文法產(chǎn)生的語言稱為型文法或正規(guī)文法產(chǎn)生的語言稱為3型語言型語言正則規(guī)語言正則規(guī)語言n例例給出一個正規(guī)文法給出一個正規(guī)文法G，使使L(G)=anbm|n,m12.5 上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹n引例引例GS:SaAS | aASbA | SS | ba寫出寫出aabbaa的最左推導(dǎo)和最右推的最左推導(dǎo)和最右推導(dǎo)。導(dǎo)。n給定文法給定文法G=( VN,VT,P,S)

10、，對于對于G的任何句型的任何句型都能夠造與之關(guān)聯(lián)的語法樹。這棵樹滿足下列都能夠造與之關(guān)聯(lián)的語法樹。這棵樹滿足下列4個條件：個條件：q每個結(jié)點都有一個標記，此標記是每個結(jié)點都有一個標記，此標記是V的一個符號。的一個符號。q根的標記是根的標記是S。q若一結(jié)點若一結(jié)點n至少有一個它自己除外的子孫，并且有至少有一個它自己除外的子孫，并且有標記標記A，則肯定則肯定AVN。q如果結(jié)點如果結(jié)點n有標記有標記A,其直接子孫結(jié)點從左到右的次其直接子孫結(jié)點從左到右的次序是序是n1，n2，nk，其標記分別為其標記分別為A1，A2，Ak，那么那么AA1A2Ak一定是一定是P中的一個產(chǎn)生式。中的一個產(chǎn)生式。n一棵語法樹

11、表示了一個句型的種種可能的一棵語法樹表示了一個句型的種種可能的(但未但未必是所有的必是所有的)不同推導(dǎo)過程，包括最左不同推導(dǎo)過程，包括最左(最右最右)推推導(dǎo)。從左到右讀出推導(dǎo)樹的葉子標記連接成的導(dǎo)。從左到右讀出推導(dǎo)樹的葉子標記連接成的文法符號串為文法符號串為G的的句型。句型。n若一個文法存在某個句子對應(yīng)兩棵不同的語法若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的?；蛘哒f，若一個樹，則稱這個文法是二義的?；蛘哒f，若一個文法存在某個句子有兩個不同的最左（右）推文法存在某個句子有兩個不同的最左（右）推導(dǎo)，則稱這個文法是二義的。導(dǎo)，則稱這個文法是二義的。n例例1GE:EE+E|E*E

12、|(E)|In例例2GE:E-EE|-E|a|b|cn文法的二義性和語言的二義性是兩個不同的概文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法念。因為可能有兩個不同的文法G和和G，其中其中G是二義的，但是卻有是二義的，但是卻有L(G)=L(G)，也就是說也就是說，這兩個文法所產(chǎn)生的語言是相同的。，這兩個文法所產(chǎn)生的語言是相同的。2.6 句型的分析句型的分析n句型分析句型分析q句型分析就是識別一個符號串是否為某文法的句型，句型分析就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。是某個推導(dǎo)的構(gòu)造過程。n分析程序（識別程序）分析程序（識別程序）q在語言的編譯實現(xiàn)中，把

13、完成句型分析的程序稱為分在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為分析程序或識別程序。析程序或識別程序。n分析算法分析算法q自上而下分析法自上而下分析法q自下而上分析法自下而上分析法考慮文法考慮文法GS：S cAdA abA a識別輸入串識別輸入串w=cabd是否該文法的句子。是否該文法的句子。q自上而下分析法的主要問題：自上而下分析法的主要問題：假定要被替換的最左非終結(jié)符是假定要被替換的最左非終結(jié)符是V且有且有n條產(chǎn)生式：條產(chǎn)生式：V 1 | 2 | n，那么如何確定用哪個右部去替那么如何確定用哪個右部去替換換V？q自下而上分析法的關(guān)鍵問題：自下而上分析法的關(guān)鍵問題：從當前串中選擇一個可以

14、歸約到某個非終結(jié)符的子從當前串中選擇一個可以歸約到某個非終結(jié)符的子串（稱為串（稱為“可歸約串可歸約串”）。）。n定義定義3.8-短語，直接短語，句柄短語，直接短語，句柄設(shè)文法設(shè)文法GS如果有如果有S A且且A ，則稱則稱是句型是句型相相對于非終結(jié)符對于非終結(jié)符A的短語。的短語。如果有如果有A ，則稱則稱是句型是句型相對于非終相對于非終結(jié)符結(jié)符A的直接短語（簡單短語）。的直接短語（簡單短語）。一個句型的最左直接短語稱為該句型的句柄一個句型的最左直接短語稱為該句型的句柄。*n例例設(shè)文法設(shè)文法GE：EE+T|TEE+T|TTTTT* *F|FF|FF(E)|iF(E)|i求句型求句型i i* *i+ii+i的短語、直接短語和句柄的短語、直接短語和句柄2.7 有關(guān)文法實用中的一些說明有關(guān)文法實用中的一些說明n在實用中，我們將限制文法中不得含有有害規(guī)則在實用中，我們將限制文法中不得含有有害規(guī)則和多余規(guī)則。和多余規(guī)則。q有害規(guī)則有害規(guī)則是形如是形如 U U的產(chǎn)生式。的產(chǎn)生式。q多余規(guī)則多余規(guī)則是文法中連一個句子