軟件開發(fā)過程與項目管理綜述ppt課件

1、Part2高級言語及其語法描畫授課：胡靜內(nèi)容提要程序文語的定義 程序文語的語法定義程序文語的語義定義高級言語的普通特性高級言語的程序構(gòu)造數(shù)據(jù)類型和操作語句與控制構(gòu)造程序文語的文法關(guān)于文法的定義文法的類型上下文無關(guān)文法及其語法樹有關(guān)文法適用中的一些闡明程序文語的定義程序文語的語法定義任何言語程序都可以看成是一定字符集稱為字母表上的一字符串有限序列。所謂一個言語的語法是指這樣一組規(guī)那么，用它可以構(gòu)成和產(chǎn)生一個合式的程序。這些規(guī)那么一部分稱為詞法規(guī)那么那么，另一部分稱為語法規(guī)那么或產(chǎn)生規(guī)那么詞法規(guī)那么：詞法規(guī)那么規(guī)定了字母表中哪樣的字符串是一個單詞符號，是單詞符號的構(gòu)成規(guī)那么 語法規(guī)那么：言語的語法

2、規(guī)那么規(guī)定了如何從單詞符號構(gòu)成更大的構(gòu)造即語法單位，換言之，語法規(guī)那么是語法單位的構(gòu)成規(guī)那么程序文語的定義程序文語的語義定義所謂一個言語的語義是指這樣的一組規(guī)那么，運用它可以定義一個程序的意義。這些規(guī)那么稱為語義。 我們將要引見的是目前大多數(shù)編譯程序普遍采用的一種方法，即基于屬性文法的語法制導(dǎo)翻譯方法，雖然還不是方式系統(tǒng)，但是比較接近方式化的。 高級言語的普通特征 高級言語的程序構(gòu)造 程序子程序或分程序語句表達式數(shù)據(jù)援用算符函數(shù)調(diào)用數(shù)據(jù)類型和操作 數(shù)據(jù)類型的要素：用于區(qū)別這種類型的數(shù)據(jù)對象的屬性；這種類型的數(shù)據(jù)對象可以具有的值；可以作用于這種類型的數(shù)據(jù)對象的操作； 數(shù)據(jù)類型分類：初等數(shù)據(jù)類型：

3、數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)、指針類型數(shù)據(jù)構(gòu)造：數(shù)組、記錄、字符串、表格、棧、隊列和籠統(tǒng)數(shù)據(jù)類型Ada經(jīng)過程序包package提供，其他經(jīng)過類class提供語句與控制構(gòu)造 表達式：一個表達式是由運算量操作數(shù)，即數(shù)據(jù)援用或函數(shù)調(diào)用和算符組成的。語句：不同程序文語含有不同方式和功能的各種語句執(zhí)行語句：描畫程序的動作，分為賦值語句、控制語句、輸入/輸出語句；闡明性語句：定義各種不同數(shù)據(jù)類型的變量或運算從方式上分，語句可以分為簡單句、復(fù)合句和分程序等。 程序文語的文法相關(guān)定義 字母表：字母表是元素的非空有窮集合，我們把字母表中的元素稱為符號，因此，字母表也稱為符號集，記做字符串：由符號表中的符號組成的

4、任何有窮序列稱為符號串，不包含任何符號的序列稱為空串，記為，表示不含任何元素的空集。*符號串的長度：假設(shè)某符號串x中有m個符號，那么稱其長度為m，表示為|x|=m，即|=0。符號串的銜接：設(shè)x和y是符號串，它們的銜接xy是把y的符號寫在x的符號之后得到的符號串。符號串的方冪：設(shè)x是符號串，把x本身銜接n次得到的符號串z稱為符號串x的方冪，寫成z=xn。程序文語的文法相關(guān)定義續(xù) 符號串集合：假設(shè)集合A中的一切元素都是某字母表上的符號串，那么稱A為該字母表上的符號串集合。用*表示上的一切有窮長的串的集合，空串也包含在內(nèi)。*的子集U和V的銜接積定義為：UV = | U & V，普通而言，UVVUV的

5、n次銜接積記為Vn，規(guī)定V0=V*稱為V的閉包，V+ = V V*，是V的正那么閉包更多的概念和一些商定A, B, C, 用來表示非終結(jié)符a, b, c, 表示終結(jié)符, X, Y, Z 可以用來表示終結(jié)符或者非終結(jié)符, w, x, y, z 表示終結(jié)符號串, , , , 表示由終結(jié)符或非終結(jié)符構(gòu)成的符號串在產(chǎn)生式A中，A 是產(chǎn)生式的左邊(lefthand side,LHS)是產(chǎn)生式的右邊( righthand side, RHS)A1|n 表示產(chǎn)生式 A 1 , A n文法的直觀概念EBNF(擴展的巴科斯瑙爾范式)表示的句子的構(gòu)成規(guī)那么句子：=主語謂語主語：=代詞|名詞代詞：= 我|他|他名詞

6、：= 王明|大學(xué)生|工人|英語謂語：=動詞直接賓語動詞：= 是|學(xué)習(xí)直接賓語：= 代詞|名詞“我是大學(xué)生的推導(dǎo)過程句子主語謂語 代詞謂語我謂語我 動詞直接賓語我是直接賓語我是名詞我是大學(xué)生關(guān)于文法的定義定義3.1文法G定義為四元組VN, VT, P, S。其中VN為非終結(jié)符號或語法實體，或變量集；VT為終結(jié)符號集；P為產(chǎn)生式也稱規(guī)那么的集合；VN, VT和P是非空有窮集。S稱做識別符號或開場符號，它是一個非終結(jié)符，至少要在一條規(guī)那么中作為左部出現(xiàn)。VN和VT不含公共元素，即VNVT=。通常V表示VNVT，V稱為文法G的字母表或字匯表。例3.1 文法G=VN，VT，P，SVN = S , VT

7、= 0, 1 P= S0S1, S01 S為開場符號關(guān)于文法的定義續(xù)定義3.2如是文法G=(VN, VT, P, S)的規(guī)那么(或說是P中第一個產(chǎn)生式)，和是V*中的恣意符號，假設(shè)有符號串v，w滿足：v=，w=，那么說v運用規(guī)那么直接產(chǎn)生w，或說w是v的直接推導(dǎo)。例：G： S0S1， S01 S 0S1 00S11 000S111 00001111關(guān)于文法的定義續(xù)定義3.3假設(shè)存在直接推導(dǎo)的序列：v=w0=w1=w2=wn=w，(n0)，那么稱v推導(dǎo)出產(chǎn)生w推導(dǎo)長度為n。記做v=+w。定義3.4假設(shè)有v=+w，或v=w，那么記做v=*w。關(guān)于文法的定義續(xù)定義3.5設(shè)GS是一文法，假設(shè)符號串x是

8、從識別符號推導(dǎo)出來的，即有S=*x，那么稱x是文法GS的句型。假設(shè)x只由終結(jié)符號組成，那么稱x為GS的句子。定義3.6文法G所產(chǎn)生的言語定義為集合x | S=*x，其中S為文法的開場符號，且xVT *?？捎肔(G)表示該集合。例：G： S0S1， S01S 0S1 00S11 000S111 00001111L(G) = 0n1n | n1關(guān)于文法的定義續(xù)定義3.7假設(shè)L(G1) = L(G2)，那么稱文法G1和G2是等價的。例1：如文法G1A：A0R 與G2S：S0S1 等價 A01 S01 RA1例2：G1E: E i 與 G2E：E T|E+T等價 E E+E T F|T*F E E*E

9、 F E|i E (E)文法的類型 Chomsky將文法分為四種類型：0型文法：對任一產(chǎn)生式，都有(VNVT)+， (VNVT)*1型文法：對任一產(chǎn)生式，都有|， 僅僅 S除外2型文法：對任一產(chǎn)生式，都有VN ， (VNVT)*3型文法：任一產(chǎn)生式的方式都為AaB或Aa，其中AVN ，BVN ，aVT。上述叫做右線性文法，另有左線性文法，二者等價。文法的類型舉例1型上下文有關(guān)文法 文法GS： SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*文法的類型舉例2型上下文無關(guān)文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文

10、法GS：S0A|1B|0A0A|1B|0SB1B|1|0文法的類型舉例定義標識符的3型正規(guī)文法 文法GI：I lTI lT lTT dTT lT d文法和言語0型文法0型文法短語文法的才干相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何0型言語都是遞歸可枚舉的1型文法上下文有關(guān)文法產(chǎn)生式的方式為1A212，即只需A出如今1和2的上下文中時，才允許取代A。其識別系統(tǒng)是線性界限自動機。2型文法上下文無關(guān)文法產(chǎn)生式的方式為A，取代A時與A的上下文無關(guān)。其識別系統(tǒng)是不確定的下推自動機。3型文法正那么文法產(chǎn)生的言語是有窮自動機FA所接受的集合上下文無關(guān)文法上下文無關(guān)文法有足夠的才干描畫現(xiàn)今程序設(shè)計言語的

11、語法構(gòu)造算術(shù)表達式語句賦值語句條件語句讀語句文法G=(E, +,*,I,(,), P, E ifthen P:E i | ifthenelse E E+EE E*EE (E)上下文無關(guān)文法的語法樹用于描畫上下文無關(guān)文法的句型推導(dǎo)的直觀方法 例: GS:SaASASbAASSSaAba S a A S S b A b a句型aabbaa的語法樹推導(dǎo)樹葉子結(jié)點：樹中沒有子孫的結(jié)點。從左到右讀出推導(dǎo)樹的葉子標志，所得的句型為推導(dǎo)樹的結(jié)果。也把該推導(dǎo)樹稱為該句型的語法樹。aa上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:SaASASbAASSSaAba S a A S S b A a

12、a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa文法的二義性最左最右推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對中的最左右非終結(jié)符進展交換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型文法的二義性例：GE:E iE E+EE E*EE (E) E E + E E * E i i i E E * E i E + E i i句型 i*i+i 的兩個不同的最左推導(dǎo)：推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i文法的二義性假設(shè)一個文法