高級(jí)程序設(shè)計(jì)語(yǔ)言

高級(jí)程序設(shè)計(jì)語(yǔ)言任何語(yǔ)言實(shí)現(xiàn)的基礎(chǔ)是語(yǔ)言的定義。在定義方面，編譯程序研制者與一般用戶(hù)有所不同用戶(hù)關(guān)心語(yǔ)言如何使用開(kāi)發(fā)人員關(guān)心語(yǔ)言的定義。他們對(duì)哪些構(gòu)造允許出現(xiàn)更感興趣。即使一時(shí)不能看出某種構(gòu)造的實(shí)際應(yīng)用，或者判斷實(shí)現(xiàn)該結(jié)構(gòu)會(huì)導(dǎo)致嚴(yán)重的困難，但仍必須嚴(yán)格根據(jù)語(yǔ)言的定義實(shí)現(xiàn)它。程序語(yǔ)言主要由語(yǔ)法和語(yǔ)義兩方面定義。2.1程序語(yǔ)言的定義第2頁(yè),共96頁(yè)，2024年2月25日，星期天2.1.1語(yǔ)法所謂一個(gè)語(yǔ)言的語(yǔ)法是指這樣的一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。這些規(guī)則一部分稱(chēng)為詞法規(guī)則，另一部分能稱(chēng)為語(yǔ)法規(guī)則（或產(chǎn)生規(guī)則）。第3頁(yè),共96頁(yè)，2024年2月25日，星期天幾個(gè)概念a.一個(gè)語(yǔ)言只是用一個(gè)有限字符集作為字母表；b.詞法規(guī)則是指單詞符號(hào)的形成規(guī)則。單詞符號(hào)一般包括：各類(lèi)型的常數(shù)、標(biāo)識(shí)符、基本字、算符和界符等。C.語(yǔ)言的語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)形成更大的結(jié)構(gòu)（即語(yǔ)法單位或語(yǔ)法范疇），換言之，語(yǔ)法規(guī)則是語(yǔ)法單位的形成規(guī)則。一般程序語(yǔ)言的語(yǔ)法單位有：表達(dá)式、語(yǔ)句、分程序、函數(shù)、過(guò)程和程序等。第4頁(yè),共96頁(yè)，2024年2月25日，星期天

對(duì)于一個(gè)語(yǔ)言來(lái)說(shuō)，不僅要給出它的詞法、語(yǔ)法規(guī)則，而且要定義它的單詞符號(hào)和語(yǔ)法單位的意義。這就是語(yǔ)義問(wèn)題。語(yǔ)義是指這樣的一組規(guī)則，使用它可以定義一個(gè)程序的意義。我們采用的方法為：屬性文法和基于屬性文法的語(yǔ)法制導(dǎo)翻譯方法。2.1.2語(yǔ)義第5頁(yè),共96頁(yè)，2024年2月25日，星期天

程序語(yǔ)言的基本功能是描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序，從本質(zhì)上來(lái)說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。程序子程序或分程序語(yǔ)句表達(dá)式算符函數(shù)調(diào)用數(shù)據(jù)引用程序第6頁(yè),共96頁(yè)，2024年2月25日，星期天程序設(shè)計(jì)語(yǔ)言的定義建立在有限字母集之上的一個(gè)符號(hào)系統(tǒng)有一定的語(yǔ)法和語(yǔ)義規(guī)則語(yǔ)法規(guī)則：詞法規(guī)則和語(yǔ)法規(guī)則語(yǔ)義規(guī)則：描述語(yǔ)法單位的功能和含義程序設(shè)計(jì)語(yǔ)言的功能是描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算第7頁(yè),共96頁(yè)，2024年2月25日，星期天2.2高級(jí)語(yǔ)言的一般特性2.2.1高級(jí)語(yǔ)言分類(lèi)2.2.2程序結(jié)構(gòu)2.2.3數(shù)據(jù)類(lèi)型與操作2.2.4語(yǔ)句與控制結(jié)構(gòu)第8頁(yè),共96頁(yè)，2024年2月25日，星期天2.2.1高級(jí)語(yǔ)言分類(lèi)從不同的角度看，對(duì)高級(jí)程序設(shè)計(jì)語(yǔ)言有不同的分類(lèi)方法。如果我們從語(yǔ)言范型分類(lèi)，當(dāng)今的大多數(shù)程序設(shè)計(jì)語(yǔ)言可劃分為四類(lèi)。

一、強(qiáng)制式語(yǔ)言強(qiáng)制式語(yǔ)言也稱(chēng)過(guò)程式語(yǔ)言。其特點(diǎn)是命令驅(qū)動(dòng)，面向語(yǔ)句。一個(gè)強(qiáng)制式語(yǔ)言程序由一系列的語(yǔ)句組成，每個(gè)浯句的執(zhí)行引起若干存儲(chǔ)單元中的值的改變。這種語(yǔ)言的語(yǔ)法形式通常具有如下形式：語(yǔ)句1；語(yǔ)句2；語(yǔ)句n；許多廣為使用的語(yǔ)言，如FORTRAN、C、Pascal，等等，屬于這類(lèi)語(yǔ)言。第9頁(yè),共96頁(yè)，2024年2月25日，星期天2.2.1高級(jí)語(yǔ)言分類(lèi)

二、應(yīng)用式語(yǔ)言與強(qiáng)制式語(yǔ)言不同的是，應(yīng)用式語(yǔ)言更注重程序所表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)句地執(zhí)行。程序的開(kāi)發(fā)過(guò)程是從前面已有的函數(shù)出發(fā)構(gòu)造出更復(fù)雜的函數(shù)，對(duì)初始數(shù)據(jù)集進(jìn)行操作直至最終的函數(shù)可以用于從初始數(shù)據(jù)計(jì)算出最終的結(jié)果。這種語(yǔ)言通常的語(yǔ)法形式是：函數(shù)n(…函數(shù)2(函數(shù)1(數(shù)據(jù)))…)因此，這種語(yǔ)言也稱(chēng)函數(shù)式語(yǔ)言。LISP和ML屬于這種語(yǔ)言。第10頁(yè),共96頁(yè)，2024年2月25日，星期天2.2.1高級(jí)語(yǔ)言分類(lèi)三、基于規(guī)則的語(yǔ)言基于規(guī)則的語(yǔ)言程序的執(zhí)行過(guò)程是：檢查一定的條件，當(dāng)它滿(mǎn)足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作。最有代表性的基于規(guī)則語(yǔ)言是Prolog，它也稱(chēng)邏輯程序設(shè)計(jì)語(yǔ)言，因?yàn)樗幕驹试S條件是謂詞邏輯表達(dá)式。這類(lèi)語(yǔ)言的語(yǔ)法形式通常為：條件1→動(dòng)作l

條件2→動(dòng)作2

條件n→動(dòng)作3第11頁(yè),共96頁(yè)，2024年2月25日，星期天2.2.1高級(jí)語(yǔ)言分類(lèi)四、面向?qū)ο笳Z(yǔ)言面向?qū)ο笳Z(yǔ)言如今已成為最流行、最重要的語(yǔ)言。它主要的特征是支持封裝性、繼承性和多態(tài)性等。把復(fù)雜的數(shù)據(jù)和用于這些數(shù)據(jù)的操作封裝在一起，構(gòu)成對(duì)象；對(duì)簡(jiǎn)單對(duì)象進(jìn)行擴(kuò)充、繼承簡(jiǎn)單對(duì)象的特性，從而設(shè)計(jì)出復(fù)雜的對(duì)象。通過(guò)對(duì)象的構(gòu)造可以使面向?qū)ο蟪绦颢@得強(qiáng)制式語(yǔ)言的有效性，通過(guò)作用于規(guī)定數(shù)據(jù)的函數(shù)的構(gòu)造可以獲得應(yīng)用式語(yǔ)言的靈活性和可靠性。第12頁(yè),共96頁(yè)，2024年2月25日，星期天2.2.2程序結(jié)構(gòu)不同程序語(yǔ)言都有各自的程序結(jié)構(gòu)C語(yǔ)言程序可以包含多個(gè)函數(shù)Pascal支持過(guò)程的嵌套定義程序結(jié)構(gòu)的不同，決定了符號(hào)表構(gòu)造方法的不同第13頁(yè),共96頁(yè)，2024年2月25日，星期天Pascal是一個(gè)允許子程序嵌套定義的語(yǔ)言

programmain

…procedureP1;…procedureP11;…begin…end;begin…end;procedureP2;…begin…end;begin…end第14頁(yè),共96頁(yè)，2024年2月25日，星期天程序設(shè)計(jì)語(yǔ)言支持特定的數(shù)據(jù)類(lèi)型與操作。一個(gè)數(shù)據(jù)類(lèi)型通常包括以下三種要素：a.用于區(qū)別這種類(lèi)型的數(shù)據(jù)對(duì)象的屬性b.這種類(lèi)型的數(shù)據(jù)對(duì)象可以具有的值c.可以作用于這種類(lèi)型數(shù)據(jù)對(duì)象的操作2.2.3數(shù)據(jù)類(lèi)型與操作第15頁(yè),共96頁(yè)，2024年2月25日，星期天一.初等數(shù)據(jù)類(lèi)型（基本數(shù)據(jù)類(lèi)型）常見(jiàn)的初等數(shù)據(jù)類(lèi)型有：

a.數(shù)值數(shù)據(jù)

b.邏輯數(shù)據(jù)

c.字符數(shù)據(jù)

d.指針類(lèi)型不同的數(shù)據(jù)類(lèi)型占存儲(chǔ)空間不同，表示的數(shù)的范圍也不相同第16頁(yè),共96頁(yè)，2024年2月25日，星期天名字和標(biāo)識(shí)符標(biāo)識(shí)符：無(wú)意義的符號(hào)串名字：可以看成是代表一個(gè)抽象的存儲(chǔ)單元名字的值：名字所代表的單元的內(nèi)容則認(rèn)為是此名字的值。名字的屬性：一個(gè)名字的屬性包括類(lèi)型和作用域。標(biāo)識(shí)符、名字與存儲(chǔ)空間的關(guān)系:同一標(biāo)識(shí)符可以表示不同的名字；同一名字可以表示不同的存儲(chǔ)空間；同一存儲(chǔ)空間可以有多個(gè)名字第17頁(yè),共96頁(yè)，2024年2月25日，星期天二.構(gòu)造數(shù)據(jù)類(lèi)型

a.數(shù)組特點(diǎn)：一個(gè)數(shù)組是由同一類(lèi)型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)。每個(gè)元素占相同的存儲(chǔ)空間下標(biāo)：沿著每一維的距離稱(chēng)為一個(gè)下標(biāo)。數(shù)組元素的命名：數(shù)組名+下標(biāo)確定數(shù)組與可變數(shù)組：在編譯時(shí)數(shù)組所需的存儲(chǔ)空間是否確定數(shù)組元素的存儲(chǔ)與地址的計(jì)算內(nèi)情向量表：數(shù)據(jù)類(lèi)型，數(shù)組的維數(shù)，下標(biāo)的變化范圍，首地址設(shè)計(jì)符號(hào)表的構(gòu)造方法，需要在符號(hào)表中存儲(chǔ)更多的信息，并需要定義不同的屬性文法以便對(duì)其語(yǔ)義進(jìn)行描述第18頁(yè),共96頁(yè)，2024年2月25日，星期天b.記錄從邏輯上說(shuō)，記錄結(jié)構(gòu)是由已知類(lèi)型的數(shù)據(jù)組合起來(lái)的一種結(jié)構(gòu)。記錄結(jié)構(gòu)是許多程序語(yǔ)言的一類(lèi)重要的數(shù)據(jù)結(jié)構(gòu)。第19頁(yè),共96頁(yè)，2024年2月25日，星期天Pascal語(yǔ)言采用下面形式定義記錄：CARD:recordNAME:array[1…20]ofchar;AGE:integer;MARRIED:booleanend;structNode{ chardata； inta; intmark;}；第20頁(yè),共96頁(yè)，2024年2月25日，星期天多種基本數(shù)據(jù)類(lèi)型組成的新的數(shù)據(jù)類(lèi)型記錄分量的訪(fǎng)問(wèn)：記錄名.分量名記錄的存放：連續(xù)存放記錄的長(zhǎng)度：每個(gè)分量的長(zhǎng)度之和記錄分量地址的計(jì)算：首地址+各分量相對(duì)于首地址的偏移（offset）特點(diǎn)：第21頁(yè),共96頁(yè)，2024年2月25日，星期天如：就CARD而言，NAME,AGE,MARRIED的相對(duì)數(shù)OFFSET分別為0、20、24。于是，假定CARD的首地址為a，那么，

CARD.NAME地址為aCARD.AGE地址為a+20CARD.MARRIED地址為a+24

第22頁(yè),共96頁(yè)，2024年2月25日，星期天2.2.4語(yǔ)句與控制結(jié)構(gòu)表達(dá)式數(shù)值、關(guān)系、邏輯、字符串語(yǔ)句賦值語(yǔ)句控制語(yǔ)句（無(wú)條件、條件、循環(huán)、過(guò)程調(diào)用、返回）

說(shuō)明句簡(jiǎn)單句和復(fù)合句第23頁(yè),共96頁(yè)，2024年2月25日，星期天一.表達(dá)式組成：運(yùn)算量（亦稱(chēng)操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。表示形式:

前綴式：+a*bc

中綴式：a+b*c

后綴式：abc*+第24頁(yè),共96頁(yè)，2024年2月25日，星期天表達(dá)式中的算符算符的優(yōu)先級(jí)和結(jié)合性乘冪（**或↑）一元負(fù)（-）乘、除（*，/，÷）加、減（+，-）關(guān)系符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)與（∧，&,and或.AND.)或（∨，∣，or或.OR.)消除文法的二義性第25頁(yè),共96頁(yè)，2024年2月25日，星期天算符的代數(shù)性質(zhì)作用：（交換率、結(jié)合率和分配率）常?？捎脕?lái)優(yōu)化目標(biāo)程序的質(zhì)量。但是必須注意兩點(diǎn)：代數(shù)性質(zhì)引用到什么程度視具體語(yǔ)言的不同而不同。如在ALGOL中把A*B+C*D處理成C*D+A*B,則至少是對(duì)ALGOL不夠忠實(shí)。數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完全成立。如：(A+B)+C=A+(B+C)在計(jì)算機(jī)上并不普遍成立。決定了在優(yōu)化的過(guò)程中應(yīng)采取的優(yōu)化策略第26頁(yè),共96頁(yè)，2024年2月25日，星期天二.語(yǔ)句從功能上說(shuō)語(yǔ)句大體可分執(zhí)行性語(yǔ)句和說(shuō)明性語(yǔ)句，說(shuō)明性語(yǔ)句旨在定義不同數(shù)據(jù)類(lèi)型的變量或運(yùn)算。執(zhí)行性語(yǔ)句旨在描述程序的動(dòng)作。對(duì)不同的語(yǔ)句，編譯器的處理方式不同。執(zhí)行性語(yǔ)句又可分賦值語(yǔ)句、控制語(yǔ)句和輸入/輸出語(yǔ)句.從形式上說(shuō)，語(yǔ)句還可分為簡(jiǎn)單句、復(fù)合句和分程序等。根據(jù)屬性文法的定義進(jìn)行處理第27頁(yè),共96頁(yè)，2024年2月25日，星期天2.3程序語(yǔ)言的語(yǔ)法描述對(duì)于高級(jí)程序語(yǔ)言及編譯程序而言，語(yǔ)言的語(yǔ)法定義是非常重要的。本節(jié)將介紹語(yǔ)法結(jié)構(gòu)的形式描述問(wèn)題。第28頁(yè),共96頁(yè)，2024年2月25日，星期天字母表：由若干元素組成的有限非空集合，用

表示，它的每個(gè)元素稱(chēng)為一個(gè)符號(hào)。符號(hào)串：由中的符號(hào)所構(gòu)成的有窮序列。符號(hào)串的前綴和后綴及子串：設(shè)x是一個(gè)符號(hào)串，將x的尾（前）部刪掉幾個(gè)字符后形成的符號(hào)串，稱(chēng)為x的前（后）綴；從一個(gè)符號(hào)串中刪去他的一個(gè)前綴和后綴后所剩下部分稱(chēng)為x的子串。與文法定義相關(guān)的幾個(gè)概念和術(shù)語(yǔ)：第29頁(yè),共96頁(yè)，2024年2月25日，星期天空串（字）：不包含符號(hào)的序列稱(chēng)為空串（字）

，記為

。用

*表示上的所有符號(hào)串的全體，空字也包括在其中。如：若={a,b}則*={,a,b,aa,ab,bb,aaa,…}。表示不含人何元素的空集{}。這里要注意、{}和{}的區(qū)別。與文法定義相關(guān)的幾個(gè)概念和術(shù)語(yǔ)：第30頁(yè),共96頁(yè)，2024年2月25日，星期天符號(hào)串及符號(hào)串集合的運(yùn)算符號(hào)串的連接運(yùn)算：設(shè)x和y是兩個(gè)符號(hào)串，如果將y直接拼接在x之后，稱(chēng)這種操作為符號(hào)串的連接,記作：x.y符號(hào)串的方冪：一個(gè)符號(hào)串與其自身的n-1的任意連接稱(chēng)為符號(hào)串的n次冪，記作：xnxn=xn-1.x=x.xn-1特別地:x0=

第31頁(yè),共96頁(yè)，2024年2月25日，星期天符號(hào)串及符號(hào)串集合的運(yùn)算字符串集合的和(等價(jià)于集合的并運(yùn)算)：設(shè)A、B是兩個(gè)符號(hào)串的集合，則將集合A、B的和記為A+B或A∪B,定義為：A∪B={w|wA或wB}符號(hào)串集合的連接：*的子集U和V中的（連接）積定義為:UV={∣U&V}

即集合UV中的符號(hào)串是由U和V的符號(hào)串連接而成的。注意，一般UVVU，但（UV)W=U(VW).第32頁(yè),共96頁(yè)，2024年2月25日，星期天令X1=“abc”,X2=“def”表示、術(shù)語(yǔ)舉例|X1||abc|=3ε|ε|=0X1.X2“abc”“def”=“abcdef”X1n

“abc”3=“abcabcabc”X1的前綴“abc”的前綴可以是：ε，a，ab,abcX1的后綴“abc”的前綴可以是：ε，c，bc,abcX1的子串“abc”的子串可以是：ε，a，b,c,…X1的真前綴“abc”的真前綴可以是：a，abX1的真后綴？X1的真子串？X1的子序列“abdf”是“abcdef”的一個(gè)子序列（X1中去掉若干個(gè)不一定連續(xù)的字符后形成的字符串）第33頁(yè),共96頁(yè)，2024年2月25日，星期天符號(hào)串集合V自身的n次（連接）積記為：

Vn=VV…V=Vn-1V

=VVn-1(n個(gè)V)規(guī)定V0={}.V的閉包：令：V*=V0∪V1∪V2∪…

稱(chēng)V*是V的閉包。V的正則包（正閉包，正則閉包）：記V+=VV*,稱(chēng)V+是V的正則包，即V+

=V1∪V2∪V3∪…。第34頁(yè),共96頁(yè)，2024年2月25日，星期天一個(gè)例子有一個(gè)字母表：A={a,b,c}A0={ε}A1=？A2=？A3=？A*=？

A+=?第35頁(yè),共96頁(yè)，2024年2月25日，星期天

文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（即語(yǔ)法規(guī)則）。所謂上下文無(wú)關(guān)文法是這樣一種文法，它所定義的語(yǔ)法范疇（或語(yǔ)法單位)是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。特點(diǎn)：獨(dú)立性缺點(diǎn)：不能用來(lái)描述自然語(yǔ)言，但對(duì)于程序語(yǔ)言基本上夠用，所以以后凡“文法”一詞，若無(wú)特殊說(shuō)明，均指上下文無(wú)關(guān)文法2.3.1上下文無(wú)關(guān)文法第36頁(yè),共96頁(yè)，2024年2月25日，星期天引例例子：對(duì)于英文句子：Hegavemeabook.是由如下語(yǔ)法規(guī)則產(chǎn)生的：第37頁(yè),共96頁(yè)，2024年2月25日，星期天由語(yǔ)法規(guī)則“推導(dǎo)”出句子的過(guò)程第38頁(yè),共96頁(yè)，2024年2月25日，星期天“推導(dǎo)”過(guò)程對(duì)應(yīng)的語(yǔ)法分析樹(shù)第39頁(yè),共96頁(yè)，2024年2月25日，星期天上下文無(wú)關(guān)文法的定義一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終結(jié)符，一個(gè)開(kāi)始符號(hào)，以及一組產(chǎn)生式。形式上定義一個(gè)上下文無(wú)關(guān)文法Ｇ是一個(gè)四元式（ＶＴ，ＶＮ，Ｓ，P）第40頁(yè),共96頁(yè)，2024年2月25日，星期天上下文無(wú)關(guān)文法的形式定義形式上定義一個(gè)上下文無(wú)關(guān)文法Ｇ是一個(gè)四元式（ＶＴ，ＶＮ，Ｓ，P）其中ＶＴ是一個(gè)非空有限集，它的每一個(gè)元素稱(chēng)為終結(jié)符號(hào)；ＶＮ是一個(gè)非空有限集，它的每一個(gè)元素稱(chēng)為非終結(jié)符號(hào)，ＶＴ∩ＶＮ＝；Ｓ是一個(gè)非終結(jié)符號(hào)，稱(chēng)為開(kāi)始符號(hào)；P是一個(gè)產(chǎn)生式（有限）集合，每個(gè)產(chǎn)生式形式是A→

，其中，A∈ＶＮ，

∈（ＶＴ∪ＶＮ）＊開(kāi)始符號(hào)S至少必須在某一產(chǎn)生式的左部出現(xiàn)一次。第41頁(yè),共96頁(yè)，2024年2月25日，星期天上下文無(wú)關(guān)文法的定義所謂終結(jié)符號(hào)乃是組成語(yǔ)言的基本符號(hào)，“終結(jié)”含義在于是具有獨(dú)立意義的最小語(yǔ)法單位，即不能再分解了的語(yǔ)法單位，如，He，book，如程序語(yǔ)言中的基本字，標(biāo)識(shí)符，常數(shù)，算符和界符等.如：{*,+,a,b,c,(,),<,>,+,-}終結(jié)符號(hào)一般用小寫(xiě)字母表示第42頁(yè),共96頁(yè)，2024年2月25日，星期天上下文無(wú)關(guān)文法所謂非終結(jié)符號(hào)（也稱(chēng)語(yǔ)法變量）用來(lái)代表語(yǔ)法范疇。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過(guò)程”等。一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念。因此非終結(jié)符是一個(gè)類(lèi)（或集合）記號(hào)，而不是個(gè)體記號(hào)。非終結(jié)符號(hào)一般用大寫(xiě)字母表示如：{E，T，F(xiàn)}第43頁(yè),共96頁(yè)，2024年2月25日，星期天開(kāi)始符號(hào)是一個(gè)特殊的非終結(jié)符號(hào)，它代表所定義的語(yǔ)言中我們最感興趣的語(yǔ)法范疇。例：E上下文無(wú)關(guān)文法第44頁(yè),共96頁(yè)，2024年2月25日，星期天產(chǎn)生式（也稱(chēng)為產(chǎn)生規(guī)則或簡(jiǎn)稱(chēng)規(guī)則）是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。一個(gè)產(chǎn)生式的形式是A→α其中箭頭左邊的A是一個(gè)非終結(jié)符，稱(chēng)為產(chǎn)生式的左部符號(hào)；箭頭右邊的α是終結(jié)符號(hào)或與非終結(jié)符號(hào)組成的一符號(hào)串，稱(chēng)為產(chǎn)生式的右部，或稱(chēng)候選式。上下文無(wú)關(guān)文法第45頁(yè),共96頁(yè)，2024年2月25日，星期天文法簡(jiǎn)寫(xiě)約定只寫(xiě)出產(chǎn)生式集合；第一個(gè)產(chǎn)生式的左部符號(hào)約定為文法的開(kāi)始符號(hào)所有產(chǎn)生式中的大寫(xiě)字母組成文法的非終結(jié)符號(hào)集；小寫(xiě)字母組成文法的終結(jié)符號(hào)集；第46頁(yè),共96頁(yè)，2024年2月25日，星期天產(chǎn)生式實(shí)例變量是一個(gè)算術(shù)表達(dá)式；若E1和E2是算術(shù)表達(dá)式，E1+E2是算術(shù)表達(dá)式E1*E2是算術(shù)表達(dá)式(E1)是算術(shù)表達(dá)式

E→i

Ｅ→Ｅ＋ＥＥ→Ｅ＊Ｅ

Ｅ→（Ｅ）第47頁(yè),共96頁(yè)，2024年2月25日，星期天關(guān)于產(chǎn)生式可能用多個(gè)產(chǎn)生式對(duì)一個(gè)非終結(jié)符進(jìn)行定義

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）定義產(chǎn)生式，可以采用遞歸的形式直接遞歸間接遞歸第48頁(yè),共96頁(yè)，2024年2月25日，星期天利用語(yǔ)法規(guī)則進(jìn)行分析的方法推導(dǎo)——對(duì)于當(dāng)前符號(hào)串中的非終結(jié)符，用對(duì)應(yīng)的產(chǎn)生式的右部去替換之。構(gòu)造語(yǔ)法樹(shù)——文法的開(kāi)始符號(hào)作為根結(jié)點(diǎn)，每推導(dǎo)一步，將非終結(jié)符作為父結(jié)點(diǎn)，對(duì)應(yīng)的產(chǎn)生式的右部作為其孩子結(jié)點(diǎn)。第49頁(yè),共96頁(yè)，2024年2月25日，星期天用文法定義語(yǔ)言采用推導(dǎo)的方法：利用產(chǎn)生式，對(duì)非終結(jié)符進(jìn)行替換、展開(kāi)

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）第50頁(yè),共96頁(yè)，2024年2月25日，星期天推導(dǎo)與直接推導(dǎo)直接推導(dǎo)：僅當(dāng)A—>γ是一個(gè)產(chǎn)生式，有αAβ

αγβ該推導(dǎo)稱(chēng)為直接推導(dǎo)（直接導(dǎo)出）推導(dǎo)的描述形式：

：任意次推導(dǎo)：至少一次推導(dǎo)*+第51頁(yè),共96頁(yè)，2024年2月25日，星期天句型與句子假定G是一個(gè)文法，S是它的開(kāi)始符號(hào)。如果S(表示從S出發(fā)，經(jīng)0步或若干步可推出），則稱(chēng)是一個(gè)句型。若是僅含終結(jié)符號(hào)的句型，則稱(chēng)是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，將它記為L(zhǎng)(G).L(G)={|S

，∈VT*}

*+第52頁(yè),共96頁(yè)，2024年2月25日，星期天句型與句子例如：終結(jié)符號(hào)串（i*i+i)是文法

E→E+E|E*E|(E)|ｉ(2.1)

的一個(gè)句子。從開(kāi)始符號(hào)E至（i*i+i)的一個(gè)推導(dǎo)過(guò)程如下：

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)

其中：E,(E),(E*E+E)等是文法的句型。第53頁(yè),共96頁(yè)，2024年2月25日，星期天例2.1考慮一個(gè)文法G1:S→bAA→aA|a它定義了一個(gè)什么語(yǔ)言呢？從開(kāi)始符S出發(fā)，我們可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫(xiě)為：L(G1)={ban|n≥1}第54頁(yè),共96頁(yè)，2024年2月25日，星期天例2.2設(shè)有文法GS→P|aPPbP→ba|bQaQ→ab

求語(yǔ)言L(fǎng)(G).

解：

L(G)={ba,baba,abab,ababab…}第55頁(yè),共96頁(yè)，2024年2月25日，星期天例2.3構(gòu)造一個(gè)文法G3使

L(G3)={an|n≥1}

解;S→aS|a第56頁(yè),共96頁(yè)，2024年2月25日，星期天例2.4構(gòu)造一個(gè)文法G4使

L(G4)={anb|n≥1}

解;S→aS|ab第57頁(yè),共96頁(yè)，2024年2月25日，星期天例2.5構(gòu)造一個(gè)文法G5使

L(G5)={anbm|n≥1,m≥1}

解;S→AB A→aA|a B→bB|b第58頁(yè),共96頁(yè)，2024年2月25日，星期天例2.6構(gòu)造一個(gè)文法G6使

L(G6)={anbn|n≥0}

解;S→aSb|

第59頁(yè),共96頁(yè)，2024年2月25日，星期天

例2.7：已知語(yǔ)言L(fǎng)={anbbn|n1},寫(xiě)出產(chǎn)生L的文法。[解]：

G[S]:SaAbAaAb|b如果寫(xiě)成

G[S]:SaSb|b

可不可以？第60頁(yè),共96頁(yè)，2024年2月25日，星期天例2.8：試構(gòu)造生成語(yǔ)言L(fǎng)={anbnci|n

0,i1}的文法解：G(Z):ZABAaAb|BcB|c第61頁(yè),共96頁(yè)，2024年2月25日，星期天

例2.9：已知語(yǔ)言L(fǎng)={x|x{a,b,c}*,且x的排列是對(duì)稱(chēng)的（aabcbaa,aabbaa,等)寫(xiě)出該語(yǔ)言的文法。解：G(Z)：

ZaZa|bZb|cZc|a|b|c|第62頁(yè),共96頁(yè)，2024年2月25日，星期天最左（右）推導(dǎo)最左推導(dǎo)或最右推導(dǎo)：所謂最左推導(dǎo)是指：任何一步都是對(duì)中的最左非終結(jié)符進(jìn)行替換的。同樣，可定義最右推導(dǎo)。最右推導(dǎo)又稱(chēng)為規(guī)范推導(dǎo)。第63頁(yè),共96頁(yè)，2024年2月25日，星期天例如：對(duì)于文法：

E→E+E|E*E|(E)|ｉ(2.1)符號(hào)串（i*i+i)的一個(gè)最左推導(dǎo)過(guò)程如下：

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)

最左（右）推導(dǎo)第64頁(yè),共96頁(yè)，2024年2月25日，星期天課堂作業(yè)：第65頁(yè),共96頁(yè)，2024年2月25日，星期天語(yǔ)法分析樹(shù)：簡(jiǎn)稱(chēng)語(yǔ)法樹(shù)。用來(lái)表示推導(dǎo)過(guò)程。2.3.2語(yǔ)法分析樹(shù)與二義性第66頁(yè),共96頁(yè)，2024年2月25日，星期天語(yǔ)法樹(shù)示例

例如對(duì)于文法E→E+E|E*E|(E)|ｉ,

關(guān)于（i*i+i)的推導(dǎo)形成語(yǔ)法樹(shù)如圖第67頁(yè),共96頁(yè)，2024年2月25日，星期天語(yǔ)法樹(shù)的構(gòu)造：語(yǔ)法樹(shù)的根結(jié)點(diǎn)由開(kāi)始符號(hào)所標(biāo)記。隨著推導(dǎo)的展開(kāi)，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符的相應(yīng)結(jié)點(diǎn)就產(chǎn)生了下一代新結(jié)點(diǎn)。每個(gè)新結(jié)點(diǎn)和其父親結(jié)點(diǎn)間都有一條連線(xiàn)。在一棵語(yǔ)法樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻，所有那些沒(méi)有后代的端末結(jié)點(diǎn)自左至右排列起來(lái)就是一個(gè)句型。2.3.2語(yǔ)法分析樹(shù)與二義性第68頁(yè),共96頁(yè)，2024年2月25日，星期天語(yǔ)法樹(shù)的不唯一性一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢？也就是說(shuō)它是否只有唯一的一個(gè)最左（最右)推導(dǎo)呢？

第69頁(yè),共96頁(yè)，2024年2月25日，星期天語(yǔ)法樹(shù)的不唯一性E→E+E|E*E|(E)|ｉ,

關(guān)于（i*i+i)的推導(dǎo)E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)第70頁(yè),共96頁(yè)，2024年2月25日，星期天

E→E+E|E*E|(E)|ｉ,關(guān)于（i*i+i)的語(yǔ)法樹(shù)第71頁(yè),共96頁(yè)，2024年2月25日，星期天文法的二義性二義文法:如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的。也就是說(shuō)，若一個(gè)文法存在某個(gè)句子，它有兩個(gè)不同的最左（最右)推導(dǎo)，則這個(gè)文法是法是二義的。第72頁(yè),共96頁(yè)，2024年2月25日，星期天文法二義性的幾個(gè)問(wèn)題文法二義不等于語(yǔ)言二義文法的二義性問(wèn)題是不可判定的文法的二義性證明：找出一個(gè)句子，它有兩個(gè)不同的最左推導(dǎo)或最右推導(dǎo)文法二義性的消除：給每個(gè)產(chǎn)生式定義優(yōu)先級(jí)第73頁(yè),共96頁(yè)，2024年2月25日，星期天消除文法二義性示例一個(gè)二義文法E--->E+EE--->E*EE--->(E)E--->i二義原因分析沒(méi)有定義運(yùn)算符優(yōu)先級(jí)和結(jié)合性消除方法定義優(yōu)先級(jí)和結(jié)合性給每個(gè)候選式定義一個(gè)優(yōu)先級(jí)引入新的非終結(jié)符，建立新的產(chǎn)生式第74頁(yè),共96頁(yè)，2024年2月25日，星期天一個(gè)二義文法E——>E+EE——>E*EE——>(E)E——>i一個(gè)無(wú)二義文法E——>T|E+TT——>F|T*FF——>(E)F——>i第75頁(yè),共96頁(yè)，2024年2月25日，星期天上下文無(wú)關(guān)文法的幾點(diǎn)限制（1）文法中不含任何下面形式的產(chǎn)生式：P→P因?yàn)檫@種產(chǎn)生式除了產(chǎn)生二義性外沒(méi)有任何用處。（2）每個(gè)非終結(jié)符P必須有用處。這一方面意味著，必須存在含P的句型；也就是，從開(kāi)始符號(hào)出發(fā)，存在推導(dǎo)S

*P.

另一方面意味著，必須存在終結(jié)符串

VT*,使得P

+

；也就是，對(duì)于P不存在永不終結(jié)的回路。第76頁(yè),共96頁(yè)，2024年2月25日，星期天形式語(yǔ)言分類(lèi)

喬姆斯基把文法分為四種類(lèi)型0型1型2型3型

0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型。這幾種文法的差別在于對(duì)產(chǎn)生式施加不同的限制。第77頁(yè),共96頁(yè)，2024年2月25日，星期天0型文法G=(VT,VN,S,P)是一個(gè)0型文法，如果它的每個(gè)產(chǎn)生式是這樣的結(jié)構(gòu)

(VN∪VT)*

且至少有一個(gè)非終結(jié)符，而(VN∪VT)*。0型文法也稱(chēng)短語(yǔ)文法0型文法的描述能力相當(dāng)于圖靈機(jī)該文法所描述的語(yǔ)言稱(chēng)為0型語(yǔ)言，或者稱(chēng)遞歸可枚舉語(yǔ)言第78頁(yè),共96頁(yè)，2024年2月25日，星期天1型文法特點(diǎn)：產(chǎn)生式的形式為

其中||<=||；但Sε除外，且S不得出現(xiàn)于任何產(chǎn)生式的右部1型文法又稱(chēng)為上下文有關(guān)文法另一種定義形式:Aγ該文法所描述的語(yǔ)言又稱(chēng)上下文有關(guān)語(yǔ)言第79頁(yè),共96頁(yè)，2024年2月25日，星期天2型文法特點(diǎn)：該文法的產(chǎn)生式滿(mǎn)足：A A為非終結(jié)符，為終結(jié)符和非終結(jié)符組成的符號(hào)串，可以是空串該文法又稱(chēng)為上下文無(wú)關(guān)文法該文法所描述的語(yǔ)言又稱(chēng)為上下文無(wú)關(guān)語(yǔ)言

第80頁(yè),共96頁(yè)，2024年2月25日，星期天3型文法特點(diǎn)：該文法的產(chǎn)生式滿(mǎn)足：AB或ABA、B為非終結(jié)符，為終結(jié)符組成的符號(hào)串，可以是空串該文法又稱(chēng)為右線(xiàn)性文法，或左線(xiàn)性文法，通稱(chēng)正規(guī)文法該文法所描述的語(yǔ)言又稱(chēng)為正規(guī)語(yǔ)言第81頁(yè),共96頁(yè)，2024年2月25日，星期天四種文法的關(guān)系第82頁(yè),共96頁(yè)，2024年2月25日，星期天四種文法的比較產(chǎn)生式形式文法名稱(chēng)定義的語(yǔ)言描述能力包含關(guān)系0型文法

短語(yǔ)文法遞歸可枚舉語(yǔ)言最強(qiáng)1型文法

||<=||上下文有關(guān)文法上下文有關(guān)語(yǔ)言次之又是0型文法2型文法A上下文無(wú)關(guān)文法上下文無(wú)關(guān)語(yǔ)言次之又是0，1文法3型文法ABAB正規(guī)文法正規(guī)語(yǔ)言最弱又是0，1，2型文法第83頁(yè),共96頁(yè)，2024年2月25日，星期天內(nèi)容回顧關(guān)于文法描述的幾個(gè)重要概念字母表，字符串，空串，等等字符串的連接，字符串集合的連接，字符串的冪，字符串集合的冪上下文無(wú)關(guān)文法G=(VT,VN,S,P)產(chǎn)生式的特點(diǎn)，產(chǎn)生式的形式推導(dǎo)、最左（右）推導(dǎo)，語(yǔ)法樹(shù)句型與句子文法的二義性形式語(yǔ)言分類(lèi)第84頁(yè),共96頁(yè)，2024年2月25日，星期天

例2.10已知文法G=({A,B,C},{a,b,c},A,P)其中產(chǎn)生式P由以下組成：

AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa

問(wèn)：此文法是那種文法？他所描述的語(yǔ)言有何特點(diǎn)？第85頁(yè),共96頁(yè)，2024年2月25日，星期天[解]：由于A為開(kāi)始符。由于Aa