《編譯原理實(shí)踐及應(yīng)用》第2章高級語言設(shè)計(jì)基礎(chǔ)

1、高級語言設(shè)計(jì)基礎(chǔ)高級語言設(shè)計(jì)基礎(chǔ)第二章第二章 本章要求本章要求 主要內(nèi)容主要內(nèi)容：符號串，文法和語言的概：符號串，文法和語言的概念及分類，高級語言的定義過程念及分類，高級語言的定義過程 重點(diǎn)掌握重點(diǎn)掌握：符號串及其運(yùn)算，上下文：符號串及其運(yùn)算，上下文無關(guān)文法、推導(dǎo)、句型、句子、語言，無關(guān)文法、推導(dǎo)、句型、句子、語言，語法樹、二義文法、文法的語言生成語法樹、二義文法、文法的語言生成過程，高級語言的設(shè)計(jì)過程過程，高級語言的設(shè)計(jì)過程 以C和PASCAL為例復(fù)習(xí)高級語言 1 語言的基本字符集的定義(字母, 數(shù)字, 符號) 2 單詞的定義 3 數(shù)據(jù)類型的定義 4 各種表達(dá)式的定義 5 各種語句的定義 6

2、 程序定義 PASCAL和C的主要區(qū)別2.1 符號和符號串符號和符號串 1. 字母表字母表：高級語言程序能夠使用的全體字符構(gòu)成的集合，是元素的有窮非空集合 2. 符號符號：字母表中的每個(gè)元素，因此字母表也稱為符號集。 不同的語言可以有不同的字母表，例如英文的字母表中26個(gè)字母、數(shù)字及標(biāo)點(diǎn)符號等。 C語言的字母表是由字母、數(shù)字、若干專用符號組成。 符號是某語言能識別的字符，字母表是該語言能符號是某語言能識別的字符，字母表是該語言能識別的所有符號的全體（字符集）識別的所有符號的全體（字符集）?；靖拍罨靖拍? (續(xù)續(xù)) ) 3. 符號串符號串: 由字母表中的符號組成的任何有窮序列稱為符號串，例如

3、00 11 10 是字母表 =0，1上的符號串 字母表A=a,b,c上的一些符號串有：a,b,c,ab,aaca等。 在符號串中，符號的順序是很重要的，符號串a(chǎn)b就不同于ba，abca和aabc也不同。 符號串STR表示“由符號S、T和R，并按此順序組成基本概念(續(xù)) 4. 符號串的運(yùn)算符號串的運(yùn)算 符號串的長度符號串的長度 :符號串中符號的個(gè)數(shù) 如：某符號串中有m個(gè)符號,則稱其長度為m，表示為|x|=m，如001110的長度是6。 空符號串空符號串: 即不包含任何符號的符號串，用表示，其長度為0， 即|=0。 符號串的連接連接：字符串稱為字符串和的連接 如：=01，=110，則=01110，

4、=11001 集合U、V的乘積乘積 ：UV = | U & V 長度相加即: 集合UV中的符號串是由U和V的符號串連接而成。 U = aa,bb V=00,11 則UV=?UV VU 集合的方冪方冪：n個(gè)相同集合的乘積 Vn =VVVV . V 規(guī)定V0 = 例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab, 集合的閉包、正閉包閉包、正閉包的閉包的閉包 * 表示上的所有符號串（包括）組成的集合。 包括長

5、度為0，1，2， 的正閉包的正閉包 + 表示 *上的除外的所有符號串組成的集合。.32=+V=0,1 V* = ? V+ = ?.32= *形式語言的概念*中的任意一個(gè)按一定規(guī)則構(gòu)成的子集稱為上的一個(gè)（形式）語言（形式）語言，屬于該語言的符號串稱為該語言的句子句子。例：令LA, B, , Z, a, b, , z，D0, 1, , 9，。由于單個(gè)符號可以看成是長度為1的符號串，L和D可以分別看成是有窮的語言集。用集合的運(yùn)算作用于L和D所得到新語言：（1）LD是字母和數(shù)字的集合；（2）LD是所有一個(gè)字母后隨一個(gè)數(shù)字的符號串的集合；（3）L*是所有字母串（包括）的集合；（4）L(LD )*是以字母

6、開頭的所有字母數(shù)字串的集合 2.2 文法與語言文法與語言 程序設(shè)計(jì)語言的語法結(jié)構(gòu)的形式化描述稱為文法。是一種工具，用于嚴(yán)格定義句子的結(jié)構(gòu)；用有窮的規(guī)則刻劃無窮的集合 文法是被用來精確而無歧義地描述語言的句子的構(gòu)成方式. 文法描述語言的時(shí)候不考慮語言的含義。引引 例例例1：有如下規(guī)則 (表示由組成)|我大學(xué)生是| 現(xiàn)要求根據(jù)如上規(guī)則得出句子：我是大學(xué)生 = = = =我是大學(xué)生句子“我是大學(xué)生”也可以如下圖示分析 在有規(guī)則的情況下，每一次用上述規(guī)則的右邊去替換左邊，得到“我是大學(xué)生”是符合上述規(guī)則的句子大學(xué)生大學(xué)生我我是是上下文無關(guān)文法的形式定義上下文無關(guān)文法的形式定義 由四部分組成：終結(jié)符號：

7、是組成該語言的最基本的符號，是不可再分的基本符號,如保留字、標(biāo)識符等。非終結(jié)符號：規(guī)則中用尖括號括起來的符號，表示一些語法成分，可以推導(dǎo)出其他的語法成分,表示一定符號串的集合，是一個(gè)類，如表達(dá)式。開始符號：規(guī)則中的一個(gè)特殊的非終結(jié)符號，語言中的句子都從它開始推導(dǎo),如程序、句子產(chǎn)生式：定義語法成分的規(guī)則，上例中的產(chǎn)生式為所有規(guī)則|我大學(xué)生是|文法的形式定義文法的形式定義( (續(xù)續(xù)) ) 一個(gè)文法文法G抽象地表示為四元組 G=（Vn,Vt,P,S） 其中Vn表示非終結(jié)符號Vt表示終結(jié)符號，VnVt=(字母表)，VnVt=S是開始符號，P是產(chǎn)生式，形如：(V+且至少含有一個(gè)非終結(jié)符號，V*) 上例中

8、： G=（Vn,Vt,P,） Vn=（，） Vt= (我，是，大學(xué)生) P = | 我 大學(xué)生 是 |例：某語言中標(biāo)識符定義的文法G=（VN，VT，P，S）其中：VN=標(biāo)識符，字母，數(shù)字 VT=a,b,c,y,z,0,1,9 S = P= abz09 產(chǎn)生式的形式為：A 左部符號，非終結(jié)符右部，可以含有非終結(jié)符和終結(jié)符又稱為一條規(guī)則有時(shí)一個(gè)產(chǎn)生式不足以描述該語法范疇，就用多個(gè)產(chǎn)生式，如算術(shù)表達(dá)式的描述為：(遞歸定義) E E + E E E * E E i E E+E | E*E | i相同左部的一個(gè)右部又稱一個(gè)候選式上下文無關(guān)上下文無關(guān)文法所定義的語法成分獨(dú)立于它可能出現(xiàn)的環(huán)境，即不考慮上下

9、文。算術(shù)表達(dá)式的文法定義算術(shù)表達(dá)式的文法定義 變量是表達(dá)式 表達(dá)式 + 表達(dá)式是表達(dá)式 表達(dá)式 * 表達(dá)式是表達(dá)式 (表達(dá)式) 是 表達(dá)式E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i 從上下文無關(guān)文法得到某個(gè)符號串的方法從上下文無關(guān)文法得到某個(gè)符號串的方法:從文法的開始符號出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對左邊的非終結(jié)符進(jìn)行替換和展開，直到全部為終結(jié)符為止。 例：表達(dá)式定義規(guī)則E E + E E E * E E ( E ) E i( i+i )E=( E ) =( E+E ) =( i+E ) =( i + i ) 推導(dǎo)推導(dǎo): 連續(xù)使用產(chǎn)生式右部

10、去替換左部某個(gè)非終結(jié)符的過程,得到的連續(xù)序列稱為一個(gè)推導(dǎo)。 直接推導(dǎo)直接推導(dǎo)：又稱一步推導(dǎo)(用 符號=表示),就是用某條規(guī)則的右部去替換該規(guī)則的左部。 歸約：歸約：推導(dǎo)的逆過程稱為歸約歸約（Reduction）。 直接歸約：直接歸約：直接推導(dǎo)的逆過程。 幾個(gè)概念的形式定義幾個(gè)概念的形式定義 直接推導(dǎo): 如果是文法 G=（Vn,Vt,P,S）的產(chǎn)生式，和是*中的任意符號，若有符號串v,w滿足：v=,w=,則說v直接產(chǎn)生w，(w是v的直接推導(dǎo))記作：v=w*+例：S01, 0S0=0010(直接推導(dǎo),) 如果存在v=w0=w1=w2.=Wn=w(n0)，則稱v推導(dǎo)出w（長度為n），記作v=w(至少

11、一步) 若有=w或v=w，則記作v=w(0步或若干步) 例3 : G = (E, i, +, *, (, ) , P , E) P： E E+E | E*E | (E) | i 表達(dá)式(i)和(i+i)*i的推導(dǎo)：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i E E 0步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (E) 直接推導(dǎo) 句型句型：設(shè)(s)是一文法，如果符號串x是從開始符號推導(dǎo)出來的，即有s=x,則稱x是文法G(s)的一個(gè)句型。 即: 任何由開始符推導(dǎo)出來的符號串都是句型。

12、句子句子：若x僅由終結(jié)符號組成，則稱x為G(S)的句子* 練習(xí)練習(xí) 文法文法G：SaAcB | Bd AAaB | c BbScA | b 寫出句型寫出句型aAcbBdcc和句子和句子acabcbbdcc的的推導(dǎo)推導(dǎo)過程。過程。 文法文法G所產(chǎn)生的語言所產(chǎn)生的語言定義為： L(G)=x|S=x,其中S為文法的開始符號，xVt* 。即: 一個(gè)文法G可以推導(dǎo)出的所有句子構(gòu)成的一個(gè)集合, 就確定了一個(gè)語言。* 例：考慮文法G: 它定義了什么語言。S bAA aA|a推導(dǎo)過程 ：S=bA =ba S=bA =baA=baa . S=bA =baA= =baa歸納得： L(G1) = ban | n1

13、練習(xí)：文法(A,B,S,a,b,c,P,S) S Ac|aB A ab B bc寫出(G)的全部元素 L(G) = abc 例：考慮文法G2: 它定義的語言是：S ABA aA|aB bB|bL(G2) = ambn |m,n1 思考：構(gòu)造一個(gè)文法G3使得：L(G3) = anbn |n1 S aSbS ab a,b的個(gè)數(shù)相同,則文法G3為： 文法等價(jià)：文法等價(jià)： 若文法G1和文法G2所產(chǎn)生的語言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價(jià)等價(jià)。例：有如下兩個(gè)文法，判斷它們是否等價(jià)？ G1=（S，0，S，S0S，S0） G2=（S，0，S，SS0，S0）S0S0S00S0S

14、00S 0000 L(G1) = 0n | n1 對于對于G2： 對于對于G1 ：SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)，文法G1和G2等價(jià) 例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (i+i)*i的推導(dǎo)過程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*il 對給定的文法，定

15、義的語言是由利用所有的產(chǎn)生式經(jīng)過各種方式推導(dǎo)出所有可能的句子構(gòu)成的，并沒有規(guī)定推導(dǎo)使用產(chǎn)生式的順序。l 因此從一個(gè)句型到另一個(gè)句型(句子)的推導(dǎo)過程不是唯一的。 最左推導(dǎo)最左推導(dǎo): 在整個(gè)推導(dǎo)過程中,任何一步推導(dǎo)=都是對中最左邊的非終結(jié)符進(jìn)行替換。 最右推導(dǎo)最右推導(dǎo): 在推導(dǎo)之前確定推導(dǎo)的順序，是對句子進(jìn)行確定性分析所必須的例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推導(dǎo)過程： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i最右推導(dǎo)

16、過程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i文法的二義性文法的二義性 語法樹語法樹：推導(dǎo)的形式化表示推導(dǎo)的形式化表示，有助于理解句子語法結(jié)構(gòu)的層次 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，該標(biāo)記屬字母集中的一個(gè)符號，根由開始符號標(biāo)記。 當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，就產(chǎn)生相應(yīng)的下一層的結(jié)點(diǎn)，候選式中自左至右的每個(gè)符號對應(yīng)一個(gè)新的結(jié)點(diǎn)，并標(biāo)記它，畫出其與父結(jié)點(diǎn)之間的連線。例：對文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的語法樹： 在語法樹的推導(dǎo)過程中的任何時(shí)刻

17、，沒有后代的端末結(jié)點(diǎn)自左至右排列起來就是一個(gè)句型 一棵語法樹表示了一個(gè)句型很多可能的不同推導(dǎo)過程。(包括最左推導(dǎo)和最右推導(dǎo))例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的語法樹： (1) E E+E E*E+E i*E+E i*i+E i*i+i (2) E E*E i*E i*E+E i*i+E i*i+i 并不是任何情況下一個(gè)句型就唯一地對應(yīng)一棵語法樹。 定義定義：如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則說這個(gè)文法是二二義義的 對二義文法中的某個(gè)句子的分析不是唯一的

18、，因此總是希望文法是無二義的。 但是二義文法有時(shí)也是有用的。證明下述文法是二義文法。 例：設(shè)if語句S的文法G=(E，S，if，then，else，a，e，P，S)，其中P為： Sif E then S （1）Sif E then S else S （2）Sa （3）Ee （4）推導(dǎo)(1)：S if E then S if E then if E then S else S推導(dǎo)(2)：S if E then S else S if E then if E then S else S文法的分類文法的分類 文法有四種:設(shè)有G=(Vn,Vt,P,S),不同類型的文法只是對產(chǎn)生式的要求不同： 型文法型

19、文法(短文文法)： G的每個(gè)產(chǎn)生式滿足：V+且中至少含有一個(gè)非終結(jié)符,V*型文法型文法(上下文有關(guān)文法)：如果G的每個(gè)產(chǎn)生式 均滿足|=|,僅當(dāng)除外，但S不得出現(xiàn)在任何產(chǎn)生式的右部型文法型文法(上下文無關(guān)文法)：G的每個(gè)產(chǎn)生式為A, A是一非終結(jié)符，V*型文法型文法(正規(guī)文法)：G的每個(gè)產(chǎn)生式的形式都是：AB或A，其中A,B是非終結(jié)符，是終結(jié)符串。(右線性文法)語言的層次語言的層次 這四種語言可被4種自動機(jī)識別： 0型圖靈機(jī) 1型線性界限自動機(jī) 2型下推自動機(jī) 3型有窮自動機(jī) 從外到內(nèi)，四種文法對產(chǎn)生式的限制越來越多，語言的描述能力越來越弱 正規(guī)文法的描述能力比上下文無關(guān)文法的描述能力弱 正規(guī)

20、文法只能用于描述單詞的構(gòu)成 上下文無關(guān)文法有足夠的能力描述現(xiàn)今大多數(shù)程序設(shè)計(jì)語言的語法結(jié)構(gòu)例.3: L(G3) = anbn |n1 a,b的個(gè)數(shù)相同, 不能由任何正規(guī)文法產(chǎn)生，可以由下述上下文無關(guān)文法產(chǎn)生。S aSbS ab 同樣，上下文無關(guān)語言的描述能力比上下文有關(guān)語言的描述能力弱。2.3 高級語言的設(shè)計(jì)高級語言的設(shè)計(jì) 語言涉及它的設(shè)計(jì)者、實(shí)現(xiàn)者和使用者 本書主要介紹語言的實(shí)現(xiàn)，但實(shí)現(xiàn)之前必須了解所實(shí)現(xiàn)的語言的特征、結(jié)構(gòu)和功能。 本節(jié)從宏觀上介紹高級語言的基本結(jié)構(gòu)和共同特征，讓讀者對高級語言的認(rèn)識達(dá)到新的高度，從語言使用者逐步向語言的實(shí)現(xiàn)者、設(shè)計(jì)者過渡。 例子 程序語言的定義 程序設(shè)計(jì)語言

21、的定義包括三部分： 語法是定義程序的一組形式規(guī)則，用它可以形成和產(chǎn)生一個(gè)形式上正確的程序； 語義也是一組規(guī)則的集合，用以定義語法正確的單詞符號和語法單位的含義； 語用主要是有關(guān)程序設(shè)計(jì)技術(shù)和語言成分的使用方法，它使語言的基本概念與語言的外界（如數(shù)學(xué)概念或計(jì)算機(jī)的對象和操作）聯(lián)系起來。 程序的本質(zhì)程序的本質(zhì) 程序是在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)的基礎(chǔ)上對抽象算法的具體描述。 沃斯（N.wirth）以“算法+數(shù)據(jù)結(jié)構(gòu)=程序” 來描述程序 程序設(shè)計(jì)語言必須以描述算法和數(shù)據(jù)結(jié)構(gòu)作為他自身的主要結(jié)構(gòu)。 各種高級語言均以數(shù)據(jù)類型來描述數(shù)據(jù)結(jié)構(gòu)，以控制結(jié)構(gòu)來描述算法。 馮.諾依曼體系結(jié)構(gòu)與高級語言 馮.諾

22、依曼機(jī)的思想：一個(gè)存儲器（用來存放指令和數(shù)據(jù)），一個(gè)控制器和一個(gè)運(yùn)算器（控制器負(fù)責(zé)從存儲器中逐條取出指令，運(yùn)算器通過算術(shù)或邏輯操作來處理數(shù)據(jù)），最后的處理結(jié)果必須送回存儲器中。 特點(diǎn)： （1）數(shù)據(jù)和指令均以二進(jìn)制形式存儲（它們在外形上沒有什么區(qū)別，但每位二進(jìn)制數(shù)有不同的含義）； （2）程序以“存儲程序”的方式工作（即事先編寫好程序，執(zhí)行之前先將程序存放到存儲器某個(gè)可知的地方）； （3）程序順序執(zhí)行（但可強(qiáng)制改變執(zhí)行順序）； （4）存儲器的內(nèi)容可以被修改（一旦放入新的數(shù)據(jù)，則該單元原來的數(shù)據(jù)立即消失，且被新數(shù)據(jù)代替）。 高級語言的特性： （1）變量：存儲器由大量存儲單元組成，數(shù)據(jù)就存放在這些單元

23、中，匯編語言通過對存儲單元的命名來訪問數(shù)據(jù)。在高級語言中，存儲單元及其名稱由變量的概念來代替，變量代表一個(gè)（或一組）已命名的存儲單元，存儲單元可存放變量的值。 （2）賦值：使用存儲單元概念的另一個(gè)結(jié)果是每個(gè)計(jì)算結(jié)果都必須存儲，即將其賦值到某個(gè)存儲單元，從而改變該單元的值。 （3）重復(fù)：指令存儲在有限的存儲器中，按順序執(zhí)行。若要完成復(fù)雜的計(jì)算，有效的方式就是重復(fù)執(zhí)行某些指令序列。 一個(gè)程序往往要涉及若干實(shí)體，如變量、語句和子程序等。實(shí)體具有某些特性，這些特性稱為實(shí)體的屬性。 變量的屬性有名字、類型和保留其值的存儲區(qū)等 語句的屬性是與之相關(guān)的一系列動作 子程序的屬性有名字、形參個(gè)數(shù)和類型、參數(shù)傳遞

24、方式的約定等。 在處理實(shí)體之前，必須將實(shí)體與相關(guān)的屬性聯(lián)系起來，這個(gè)聯(lián)系的過程稱為綁定綁定（Binding），每個(gè)實(shí)體的綁定信息存儲在特定的表格中。 把實(shí)體與它的某個(gè)屬性聯(lián)系起來的時(shí)刻稱為綁定時(shí)間。 一旦綁定，這種關(guān)系就一直存在，直到對這一實(shí)體的另一次綁定。 若一個(gè)綁定在運(yùn)行之前（即編譯時(shí)）完成，且在運(yùn)行時(shí)不會改變，則稱為靜態(tài)綁定靜態(tài)綁定（Static Binding）。 如一個(gè)綁定在運(yùn)行時(shí)完成（此后可能在運(yùn)行過程中被改變），則稱為動態(tài)綁定動態(tài)綁定（dynamic Binding）。 抽象 變量是高級語言中最重要的概念之一，它是一個(gè)抽象概念，是對存儲單元的抽象。馮.諾依曼機(jī)基于存儲單元組成的主

25、存儲器概念，每個(gè)存儲單元用地址來標(biāo)識，可以對它進(jìn)行讀或?qū)懖僮?，寫操作就是指修改存儲單元的值。賦值語句就是對修改存儲單元內(nèi)容的抽象。 數(shù)據(jù)類型 內(nèi)部類型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)和指針類型數(shù)據(jù)。內(nèi)部類型是對二進(jìn)制位串的抽象，其基本形式對程序員是不可見的，即程序員不能直接訪問表示一個(gè)整數(shù)的位串的某個(gè)特定位。 用戶定義類型：數(shù)組、記錄、聯(lián)合、字符串、表格、棧、隊(duì)列、鏈表和樹等，基本表示形式對程序員是可見的 抽象數(shù)據(jù)類型：數(shù)據(jù)對象的一個(gè)集合，作用于這些數(shù)據(jù)對象的抽象運(yùn)算的集合，以及這些類型對象的封裝，C+中的類?；颈硎緦Τ绦騿T是不可見的 語句和控制結(jié)構(gòu) 程序結(jié)構(gòu)表達(dá)式表達(dá)式 表達(dá)式由運(yùn)算對象（數(shù)

26、據(jù)引用或函數(shù)調(diào)用）和運(yùn)算符組成。 分為邏輯表達(dá)式、關(guān)系表達(dá)式和算術(shù)表達(dá)式 運(yùn)算符之間的優(yōu)先關(guān)系和結(jié)合性規(guī)定了表達(dá)式的計(jì)算次序。 邏輯表達(dá)式 | |() | not | and | or 關(guān)系表達(dá)式 |=| =算術(shù)表達(dá)式|變量|()| + |-| *|/|()|語句語句 語句 說明性語句 可執(zhí)行語句 說明性語句旨在定義各種不同數(shù)據(jù)類型的變量或運(yùn)算，不需要由編譯程序生成目標(biāo)代碼，主要用來告訴編譯程序一些實(shí)體的屬性，供編譯程序生成目標(biāo)代碼時(shí)使用。 可執(zhí)行語句旨在描述程序的動作，需要由編譯程序生成目標(biāo)代碼來實(shí)現(xiàn)它的語義。 說明語句說明語句 | const 標(biāo)識符 = var : |, integer|real|char|boolean執(zhí)行語句 | | read () write ()= | | begin end程序和子程