第2章+文法和語言

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

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

3、一切元素都是字母表上的符號(hào)串，則中的一切元素都是字母表上的符號(hào)串，則稱稱A為該字母表上的符號(hào)串集合。為該字母表上的符號(hào)串集合。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 。*表示表示上的所有有窮長(zhǎng)的串的集合上的所有有窮長(zhǎng)的串的集合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: 開始符號(hào)，它是一個(gè)非終結(jié)符，至少要開始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。在一條規(guī)則中作為左部出現(xiàn)。通常用通常用V表示表示VN VT，V稱為文法稱為文法G的的文法文法符號(hào)集符號(hào)集。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*中的任意符號(hào)串。若有符號(hào)串中的任意符號(hào)串。若有符號(hào)串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* ，都是，都是對(duì)對(duì) 中的最左（最右）非終結(jié)符進(jìn)行替換，則稱這中的最左（最右）非終結(jié)符進(jìn)行替換，則稱這種推導(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(zhǎng)(G),它是文法它是文法G的一切的一切句子的集合。句子的集合。n定義定義2.7-文法等價(jià)文法等價(jià)若若L(G1) = L(G2)，則稱文法則稱文法G1和和G2是等價(jià)的。是等價(jià)的。2.4 文法的類型文法的類型nChomsky分類分類q0型文法型文法 短語文法短語文法對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有都有(VNVT)+且至少含有一個(gè)且至少含有一個(gè)非終結(jié)符，非終結(jié)符， (VNVT)*q1型文法型

8、文法-上下文有關(guān)文法（上下文有關(guān)文法（CSG） 對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有都有|， 僅僅僅僅 S除外除外q2型文法型文法-上下文無關(guān)文法（上下文無關(guān)文法（CFG） 對(duì)任一產(chǎn)生式對(duì)任一產(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例例給出一個(gè)正規(guī)文法給出一個(gè)正規(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、，對(duì)于對(duì)于G的任何句型的任何句型都能夠造與之關(guān)聯(lián)的語法樹。這棵樹滿足下列都能夠造與之關(guān)聯(lián)的語法樹。這棵樹滿足下列4個(gè)條件：個(gè)條件：q每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。的一個(gè)符號(hào)。q根的標(biāo)記是根的標(biāo)記是S。q若一結(jié)點(diǎn)若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有至少有一個(gè)它自己除外的子孫，并且有標(biāo)記標(biāo)記A，則肯定則肯定AVN。q如果結(jié)點(diǎn)如果結(jié)點(diǎn)n有標(biāo)記有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次其直接子孫結(jié)點(diǎn)從左到右的次序是序是n1，n2，nk，其標(biāo)記分別為其標(biāo)記分別為A1，A2，Ak，那么那么AA1A2Ak一定是一定是P中的一個(gè)產(chǎn)生式。中的一個(gè)產(chǎn)生式。n一棵語法樹

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

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

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

14、歸約到某個(gè)非終結(jié)符的子從當(dāng)前串中選擇一個(gè)可以歸約到某個(gè)非終結(jié)符的子串（稱為串（稱為“可歸約串可歸約串”）。）。n定義定義3.8-短語，直接短語，句柄短語，直接短語，句柄設(shè)文法設(shè)文法GS如果有如果有S A且且A ，則稱則稱是句型是句型相相對(duì)于非終結(jié)符對(duì)于非終結(jié)符A的短語。的短語。如果有如果有A ，則稱則稱是句型是句型相對(duì)于非終相對(duì)于非終結(jié)符結(jié)符A的直接短語（簡(jiǎn)單短語）。的直接短語（簡(jiǎn)單短語）。一個(gè)句型的最左直接短語稱為該句型的句柄一個(gè)句型的最左直接短語稱為該句型的句柄。*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)文法實(shí)用中的一些說明有關(guān)文法實(shí)用中的一些說明n在實(shí)用中，我們將限制文法中不得含有有害規(guī)則在實(shí)用中，我們將限制文法中不得含有有害規(guī)則和多余規(guī)則。和多余規(guī)則。q有害規(guī)則有害規(guī)則是形如是形如 U U的產(chǎn)生式。的產(chǎn)生式。q多余規(guī)則多余規(guī)則是文法中連一個(gè)句子