高級程序設計語言

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

對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。這就是語義問題。語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義。我們采用的方法為：屬性文法和基于屬性文法的語法制導翻譯方法。2.1.2語義第5頁，課件共96頁，創(chuàng)作于2023年2月

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

一、強制式語言強制式語言也稱過程式語言。其特點是命令驅(qū)動，面向語句。一個強制式語言程序由一系列的語句組成，每個浯句的執(zhí)行引起若干存儲單元中的值的改變。這種語言的語法形式通常具有如下形式：語句1；語句2；語句n；許多廣為使用的語言，如FORTRAN、C、Pascal，等等，屬于這類語言。第9頁，課件共96頁，創(chuàng)作于2023年2月2.2.1高級語言分類

二、應用式語言與強制式語言不同的是，應用式語言更注重程序所表示的功能，而不是一個語句接一個語句地執(zhí)行。程序的開發(fā)過程是從前面已有的函數(shù)出發(fā)構造出更復雜的函數(shù)，對初始數(shù)據(jù)集進行操作直至最終的函數(shù)可以用于從初始數(shù)據(jù)計算出最終的結(jié)果。這種語言通常的語法形式是：函數(shù)n(…函數(shù)2(函數(shù)1(數(shù)據(jù)))…)因此，這種語言也稱函數(shù)式語言。LISP和ML屬于這種語言。第10頁，課件共96頁，創(chuàng)作于2023年2月2.2.1高級語言分類三、基于規(guī)則的語言基于規(guī)則的語言程序的執(zhí)行過程是：檢查一定的條件，當它滿足值，則執(zhí)行適當?shù)膭幼?。最有代表性的基于?guī)則語言是Prolog，它也稱邏輯程序設計語言，因為它的基本允許條件是謂詞邏輯表達式。這類語言的語法形式通常為：條件1→動作l

條件2→動作2

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

programmain

…procedureP1;…procedureP11;…begin…end;begin…end;procedureP2;…begin…end;begin…end第14頁，課件共96頁，創(chuàng)作于2023年2月程序設計語言支持特定的數(shù)據(jù)類型與操作。一個數(shù)據(jù)類型通常包括以下三種要素：a.用于區(qū)別這種類型的數(shù)據(jù)對象的屬性b.這種類型的數(shù)據(jù)對象可以具有的值c.可以作用于這種類型數(shù)據(jù)對象的操作2.2.3數(shù)據(jù)類型與操作第15頁，課件共96頁，創(chuàng)作于2023年2月一.初等數(shù)據(jù)類型（基本數(shù)據(jù)類型）常見的初等數(shù)據(jù)類型有：

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

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

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

d.指針類型不同的數(shù)據(jù)類型占存儲空間不同，表示的數(shù)的范圍也不相同第16頁，課件共96頁，創(chuàng)作于2023年2月名字和標識符標識符：無意義的符號串名字：可以看成是代表一個抽象的存儲單元名字的值：名字所代表的單元的內(nèi)容則認為是此名字的值。名字的屬性：一個名字的屬性包括類型和作用域。標識符、名字與存儲空間的關系:同一標識符可以表示不同的名字；同一名字可以表示不同的存儲空間；同一存儲空間可以有多個名字第17頁，課件共96頁，創(chuàng)作于2023年2月二.構造數(shù)據(jù)類型

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

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

第22頁，課件共96頁，創(chuàng)作于2023年2月2.2.4語句與控制結(jié)構表達式數(shù)值、關系、邏輯、字符串語句賦值語句控制語句（無條件、條件、循環(huán)、過程調(diào)用、返回）

說明句簡單句和復合句第23頁，課件共96頁，創(chuàng)作于2023年2月一.表達式組成：運算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。表示形式:

前綴式：+a*bc

中綴式：a+b*c

后綴式：abc*+第24頁，課件共96頁，創(chuàng)作于2023年2月表達式中的算符算符的優(yōu)先級和結(jié)合性乘冪（**或↑）一元負（-）乘、除（*，/，÷）加、減（+，-）關系符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)與（∧，&,and或.AND.)或（∨，∣，or或.OR.)消除文法的二義性第25頁，課件共96頁，創(chuàng)作于2023年2月算符的代數(shù)性質(zhì)作用：（交換率、結(jié)合率和分配率）常?？捎脕韮?yōu)化目標程序的質(zhì)量。但是必須注意兩點：代數(shù)性質(zhì)引用到什么程度視具體語言的不同而不同。如在ALGOL中把A*B+C*D處理成C*D+A*B,則至少是對ALGOL不夠忠實。數(shù)學上成立的代數(shù)性質(zhì)在計算機上未必完全成立。如：(A+B)+C=A+(B+C)在計算機上并不普遍成立。決定了在優(yōu)化的過程中應采取的優(yōu)化策略第26頁，課件共96頁，創(chuàng)作于2023年2月二.語句從功能上說語句大體可分執(zhí)行性語句和說明性語句，說明性語句旨在定義不同數(shù)據(jù)類型的變量或運算。執(zhí)行性語句旨在描述程序的動作。對不同的語句，編譯器的處理方式不同。執(zhí)行性語句又可分賦值語句、控制語句和輸入/輸出語句.從形式上說，語句還可分為簡單句、復合句和分程序等。根據(jù)屬性文法的定義進行處理第27頁，課件共96頁，創(chuàng)作于2023年2月2.3程序語言的語法描述對于高級程序語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結(jié)構的形式描述問題。第28頁，課件共96頁，創(chuàng)作于2023年2月字母表：由若干元素組成的有限非空集合，用表示，它的每個元素稱為一個符號。符號串：由中的符號所構成的有窮序列。符號串的前綴和后綴及子串：設x是一個符號串，將x的尾（前）部刪掉幾個字符后形成的符號串，稱為x的前（后）綴；從一個符號串中刪去他的一個前綴和后綴后所剩下部分稱為x的子串。與文法定義相關的幾個概念和術語：第29頁，課件共96頁，創(chuàng)作于2023年2月空串（字）：不包含符號的序列稱為空串（字）

，記為。用*表示上的所有符號串的全體，空字也包括在其中。如：若={a,b}則*={,a,b,aa,ab,bb,aaa,…}。表示不含人何元素的空集{}。這里要注意、{}和{}的區(qū)別。與文法定義相關的幾個概念和術語：第30頁，課件共96頁，創(chuàng)作于2023年2月符號串及符號串集合的運算符號串的連接運算：設x和y是兩個符號串，如果將y直接拼接在x之后，稱這種操作為符號串的連接,記作：x.y符號串的方冪：一個符號串與其自身的n-1的任意連接稱為符號串的n次冪，記作：xnxn=xn-1.x=x.xn-1特別地:x0=第31頁，課件共96頁，創(chuàng)作于2023年2月符號串及符號串集合的運算字符串集合的和(等價于集合的并運算)：設A、B是兩個符號串的集合，則將集合A、B的和記為A+B或A∪B,定義為：A∪B={w|wA或wB}符號串集合的連接：*的子集U和V中的（連接）積定義為:UV={∣U&V}

即集合UV中的符號串是由U和V的符號串連接而成的。注意，一般UVVU，但（UV)W=U(VW).第32頁，課件共96頁，創(chuàng)作于2023年2月令X1=“abc”,X2=“def”表示、術語舉例|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”的一個子序列（X1中去掉若干個不一定連續(xù)的字符后形成的字符串）第33頁，課件共96頁，創(chuàng)作于2023年2月符號串集合V自身的n次（連接）積記為：

Vn=VV…V=Vn-1V

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

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

=V1∪V2∪V3∪…。第34頁，課件共96頁，創(chuàng)作于2023年2月一個例子有一個字母表：A={a,b,c}A0={ε}A1=？A2=？A3=？A*=？

A+=?第35頁，課件共96頁，創(chuàng)作于2023年2月

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

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

E→i

Ｅ→Ｅ＋ＥＥ→Ｅ＊Ｅ

Ｅ→（Ｅ）第47頁，課件共96頁，創(chuàng)作于2023年2月關于產(chǎn)生式可能用多個產(chǎn)生式對一個非終結(jié)符進行定義

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）定義產(chǎn)生式，可以采用遞歸的形式直接遞歸間接遞歸第48頁，課件共96頁，創(chuàng)作于2023年2月利用語法規(guī)則進行分析的方法推導——對于當前符號串中的非終結(jié)符，用對應的產(chǎn)生式的右部去替換之。構造語法樹——文法的開始符號作為根結(jié)點，每推導一步，將非終結(jié)符作為父結(jié)點，對應的產(chǎn)生式的右部作為其孩子結(jié)點。第49頁，課件共96頁，創(chuàng)作于2023年2月用文法定義語言采用推導的方法：利用產(chǎn)生式，對非終結(jié)符進行替換、展開

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）第50頁，課件共96頁，創(chuàng)作于2023年2月推導與直接推導直接推導：僅當A—>γ是一個產(chǎn)生式，有αAβαγβ該推導稱為直接推導（直接導出）推導的描述形式：

：任意次推導：至少一次推導*+第51頁，課件共96頁，創(chuàng)作于2023年2月句型與句子假定G是一個文法，S是它的開始符號。如果S(表示從S出發(fā)，經(jīng)0步或若干步可推出），則稱是一個句型。若是僅含終結(jié)符號的句型，則稱是一個句子。文法G所產(chǎn)生的句子的全體是一個語言，將它記為L(G).L(G)={|S

，∈VT*}

*+第52頁，課件共96頁，創(chuàng)作于2023年2月句型與句子例如：終結(jié)符號串（i*i+i)是文法

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

的一個句子。從開始符號E至（i*i+i)的一個推導過程如下：

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

其中：E,(E),(E*E+E)等是文法的句型。第53頁，課件共96頁，創(chuàng)作于2023年2月例2.1考慮一個文法G1:S→bAA→aA|a它定義了一個什么語言呢？從開始符S出發(fā)，我們可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫為：L(G1)={ban|n≥1}第54頁，課件共96頁，創(chuàng)作于2023年2月例2.2設有文法GS→P|aPPbP→ba|bQaQ→ab

求語言L(G).

解：

L(G)={ba,baba,abab,ababab…}第55頁，課件共96頁，創(chuàng)作于2023年2月例2.3構造一個文法G3使

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

解;S→aS|a第56頁，課件共96頁，創(chuàng)作于2023年2月例2.4構造一個文法G4使

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

解;S→aS|ab第57頁，課件共96頁，創(chuàng)作于2023年2月例2.5構造一個文法G5使

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

解;S→AB A→aA|a B→bB|b第58頁，課件共96頁，創(chuàng)作于2023年2月例2.6構造一個文法G6使

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

解;S→aSb|第59頁，課件共96頁，創(chuàng)作于2023年2月

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

G[S]:SaAbAaAb|b如果寫成

G[S]:SaSb|b

可不可以？第60頁，課件共96頁，創(chuàng)作于2023年2月例2.8：試構造生成語言L={anbnci|n0,i1}的文法解：G(Z):ZABAaAb|BcB|c第61頁，課件共96頁，創(chuàng)作于2023年2月

例2.9：已知語言L={x|x{a,b,c}*,且x的排列是對稱的（aabcbaa,aabbaa,等)寫出該語言的文法。解：G(Z)：

ZaZa|bZb|cZc|a|b|c|第62頁，課件共96頁，創(chuàng)作于2023年2月最左（右）推導最左推導或最右推導：所謂最左推導是指：任何一步都是對中的最左非終結(jié)符進行替換的。同樣，可定義最右推導。最右推導又稱為規(guī)范推導。第63頁，課件共96頁，創(chuàng)作于2023年2月例如：對于文法：

E→E+E|E*E|(E)|ｉ(2.1)符號串（i*i+i)的一個最左推導過程如下：

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

最左（右）推導第64頁，課件共96頁，創(chuàng)作于2023年2月課堂作業(yè)：第65頁，課件共96頁，創(chuàng)作于2023年2月語法分析樹：簡稱語法樹。用來表示推導過程。2.3.2語法分析樹與二義性第66頁，課件共96頁，創(chuàng)作于2023年2月語法樹示例

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

關于（i*i+i)的推導形成語法樹如圖第67頁，課件共96頁，創(chuàng)作于2023年2月語法樹的構造：語法樹的根結(jié)點由開始符號所標記。隨著推導的展開，當某個非終結(jié)符被它的某個候選式所替換時，這個非終結(jié)符的相應結(jié)點就產(chǎn)生了下一代新結(jié)點。每個新結(jié)點和其父親結(jié)點間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結(jié)點自左至右排列起來就是一個句型。2.3.2語法分析樹與二義性第68頁，課件共96頁，創(chuàng)作于2023年2月語法樹的不唯一性一個句型是否只對應唯一的一棵語法樹呢？也就是說它是否只有唯一的一個最左（最右)推導呢？

第69頁，課件共96頁，創(chuàng)作于2023年2月語法樹的不唯一性E→E+E|E*E|(E)|ｉ,

關于（i*i+i)的推導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頁，課件共96頁，創(chuàng)作于2023年2月

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

另一方面意味著，必須存在終結(jié)符串VT*,使得P+；也就是，對于P不存在永不終結(jié)的回路。第76頁，課件共96頁，創(chuàng)作于2023年2月形式語言分類

喬姆斯基把文法分為四種類型0型1型2型3型

0型強于1型，1型強于2型，2型強于3型。這幾種文法的差別在于對產(chǎn)生式施加不同的限制。第77頁，課件共96頁，創(chuàng)作于2023年2月0型文法G=(VT,VN,S,P)是一個0型文法，如果它的每個產(chǎn)生式是這樣的結(jié)構

(VN∪VT)*

且至少有一個非終結(jié)符，而(VN∪VT)*。0型文法也稱短語文法0型文法的描述能力相當于圖靈機該文法所描述的語言稱為0型語言，或者稱遞歸可枚舉語言第78頁，課件共96頁，創(chuàng)作于2023年2月1型文法特點：產(chǎn)生式的形式為 其中||<=||；但Sε除外，且S不得出現(xiàn)于任何產(chǎn)生式的右部1型文法又稱為上下文有關文法另一種定義形式:Aγ該文法所描述的語言又稱上下文有關語言第79頁，課件共96頁，創(chuàng)作于2023年2月2型文法特點：該文法的產(chǎn)生式滿足：A A為非終結(jié)符，為終結(jié)符和非終結(jié)符組成的符號串，可以是空串該文法又稱為上下文無關文法該文法所描述的語言又稱為上下文無關語言

第80頁，課件共96頁，創(chuàng)作于2023年2月3型文法特點：該文法的產(chǎn)生式滿足：AB或ABA、B為非終結(jié)符，為終結(jié)符組成的符號串，可以是空串該文法又稱為右線性文法，或左線性文法，通稱正規(guī)文法該文法所描述的語言又稱為正規(guī)語言第81頁，課件共96頁，創(chuàng)作于2023年2月四種文法的關系第82頁，課件共96頁，創(chuàng)作于2023年2月四種文法的比較產(chǎn)生式形式文法名稱定義的語言描述能力包含關系0型文法短語文法遞歸可枚舉語言最強1型文法||<=||上下文有關文法上下文有關語言次之又是0型文法2型文法A上下文無關文法上下文無關語言次之又是0，1文法3型文法ABAB正規(guī)文法正規(guī)語言最弱又是0，1，2型文法第83頁，課件共96頁，創(chuàng)作于2023年2月內(nèi)容回顧關于文法描述的幾個重要概念字母表，字符串，空串，等等字符串的連接，字符串集合的連接，字符串的冪，字符串集合的冪上下文無關文法G=(VT,VN,S,P)產(chǎn)生式的特點，產(chǎn)生式的形式推導、最左（右）推導，語法樹句型與句子文法的二義性形式語言分類第84頁，課件共96頁，創(chuàng)作于2023年2月

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

AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa

問：此文法是那種文法？他所描述的語言有何特點？第85頁，課件共96頁，創(chuàng)作于2023年2月[解]：由于A為開始符。