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

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

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

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

4、1 集合U與V的乘積乘積 ：UV = | U & V 即: 集合UV是由U中的任一符號(hào)串與V中的任一符號(hào)串連接而成的符號(hào)串集合。 例：設(shè)U = aa,bb ，V=00,11 則UV=?UV VU 集合V的n次方冪方冪：V自身的n次乘積 Vn =VVVV . V 規(guī)定V0 = 例：設(shè)V=ab,x,y, 則V2=VV=ab,x,yab,x,y=abab,abx,aby,xab,xx,xy,yab,yx,yy例：例：=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,

5、=a,b,aa,ab,ba,bb,aaa,aab, 的閉包、正閉包閉包、正閉包的閉包的閉包 *: 表示上的所有符號(hào)串（包括）組成的集合。 包括長(zhǎng)度為0，1，2， 的正閉包的正閉包 + ：表示 上的除外的所有符號(hào)串組成的集合。.32=+V=0,1 V* = ? V+ = ?.32= *形式語(yǔ)言的概念*中的任意一個(gè)按一定規(guī)則構(gòu)成的子集稱(chēng)為上的一個(gè)（形式）語(yǔ)言（形式）語(yǔ)言，屬于該語(yǔ)言的符號(hào)串稱(chēng)為該語(yǔ)言的句子句子。例：令LA, B, , Z, a, b, , z，D0, 1, , 9，。由于單個(gè)符號(hào)可以看成是長(zhǎng)度為1的符號(hào)串，L和D可以分別看成是有窮的語(yǔ)言集。用集合的運(yùn)算作用于L和D所得到6種新語(yǔ)言：

6、（1）LD是字母和數(shù)字的集合；（2）LD是所有一個(gè)字母后隨一個(gè)數(shù)字的符號(hào)串的集合；（3）L6是由6個(gè)字母構(gòu)成的符號(hào)串的集合；（4）L*是所有字母串（包括）的集合；（5）L(LD )*是以字母開(kāi)頭的所有字母數(shù)字串的集合； （6）D+是不含空串的數(shù)字串的集合。 語(yǔ)言的有窮表示 語(yǔ)言的有窮表示有兩種方法： 用產(chǎn)生的觀點(diǎn)來(lái)表示語(yǔ)言。方法：為語(yǔ)言定義一組規(guī)則，利用規(guī)則產(chǎn)生語(yǔ)言中的每個(gè)句子。 用識(shí)別的觀點(diǎn)表示語(yǔ)言。方法：利用一個(gè)算法（有限自動(dòng)機(jī)）來(lái)判斷某個(gè)給定的符號(hào)串（句子）是否在某語(yǔ)言中。本章先從“產(chǎn)生的觀點(diǎn)”來(lái)描述語(yǔ)言文法。2.2 文法與語(yǔ)言文法與語(yǔ)言 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式化描述稱(chēng)為文法（Gr

7、ammar）。 文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（即語(yǔ)法規(guī)則）。 文法是從產(chǎn)生語(yǔ)言中的句子的觀點(diǎn)來(lái)描述語(yǔ)言的，即語(yǔ)言中的每個(gè)句子都可以用嚴(yán)格定義的規(guī)則來(lái)產(chǎn)生。 文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。引引 例例例2.2：有如下規(guī)則 (表示由組成)| （|表示“或”）我大學(xué)生是| 根據(jù)如上9條規(guī)則可以得出句子：我是大學(xué)生。分析過(guò)程是： = = =我 =我 =我是 =我是 =我是大學(xué)生說(shuō)明這是語(yǔ)法上正確的句子！文法的形式化定義文法的形式化定義 文法G由四部分組成：終結(jié)符號(hào)：出現(xiàn)在句子中的符號(hào)，是一個(gè)語(yǔ)言不可再分的基本單位,如保留字、標(biāo)識(shí)符等。用VT表示終結(jié)符的集合。非終結(jié)符號(hào)：規(guī)則中用尖括號(hào)括起來(lái)的

8、符號(hào)，表示一些語(yǔ)法成分，可以推導(dǎo)出其他的語(yǔ)法成分,表示一定符號(hào)串的集合，如表達(dá)式。用VN表示非終結(jié)符的集合。開(kāi)始符號(hào)：規(guī)則中的一個(gè)特殊的非終結(jié)符號(hào)，語(yǔ)言中的句子都從它開(kāi)始推導(dǎo),如程序、句子產(chǎn)生式：定義語(yǔ)法成分的規(guī)則，上例中有9個(gè)產(chǎn)生式。用P表示產(chǎn)生式的集合。|我大學(xué)生是|文法的形式化定義文法的形式化定義( (續(xù)續(xù)) ) 一個(gè)文法文法G抽象地表示為一個(gè)四元組 G=（VN，VT，P，S） 其中VN表示非終結(jié)符號(hào)集VT表示終結(jié)符號(hào)集，VNVT=(字母表)，VNVT=S是開(kāi)始符號(hào)P是產(chǎn)生式集合 上例中： G=（VN,VT,P,） VN=（，） VT= (我，是，大學(xué)生) P = | 我 大學(xué)生 是 |

9、例2.3：某語(yǔ)言中標(biāo)識(shí)符定義的文法G=（VN，VT，P，S）其中：VN=標(biāo)識(shí)符，字母，數(shù)字 VT=a,b,c,y,z,0,1,9 S = P= abz09 產(chǎn)生式的形式為：A 左部符號(hào)，非終結(jié)符右部，可以含有非終結(jié)符和終結(jié)符又稱(chēng)為一條規(guī)則。l注：有時(shí)不用將文法G的四元組顯式地表示出來(lái)，而只將產(chǎn)生式寫(xiě)出。l書(shū)寫(xiě)產(chǎn)生式的約定： 第一條產(chǎn)生式的左部是開(kāi)始符號(hào)； 用大寫(xiě)字母表示非終結(jié)符，小寫(xiě)字母表示終結(jié)符； 用小寫(xiě)希臘字母（如、和）代表文法的符號(hào)串； 如果S是文法G的開(kāi)始符號(hào)，也可將文法G寫(xiě)成GS。 有時(shí)為書(shū)寫(xiě)簡(jiǎn)潔，常把相同左部的產(chǎn)生式進(jìn)行縮寫(xiě)。如： 其中，每個(gè)i是A的一個(gè)候選式。A1A2An縮寫(xiě)為A

10、1|2|n例2.4：下面是一個(gè)文法的幾種等價(jià)寫(xiě)法。 （1）G=(S,A,a,b,P,S) 其中 P：SaAb Aab AaAb A（2）G：SaAb Aab AaAb A（3）GS：SaAb Aab AaAb A（4）GS：SaAb Aab|aAb|例例2.5 2.5 某語(yǔ)言算術(shù)表達(dá)式的文法定義某語(yǔ)言算術(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若用E表示表達(dá)式，i表示變量，則表達(dá)式的文法可以表示為：簡(jiǎn)寫(xiě)為2.2.2 文法產(chǎn)生的語(yǔ)

11、言推導(dǎo)和規(guī)約 推導(dǎo):從文法的開(kāi)始符號(hào)出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對(duì)左邊的非終結(jié)符進(jìn)行替換和展開(kāi)，直到全部為終結(jié)符為止。這個(gè)過(guò)程就是推導(dǎo)。用=表示。 例：利用例2.5的算術(shù)表達(dá)式文法，推導(dǎo)表達(dá)式（i+i）。過(guò)程是：E E + E E E * E E ( E ) E iE=( E ) =( E+E ) =( i+E ) =( i + i )推導(dǎo)和規(guī)約推導(dǎo)和規(guī)約 直接推導(dǎo)直接推導(dǎo)：又稱(chēng)一步推導(dǎo)(用 符號(hào)=表示),就是用某條規(guī)則的右部去替換該規(guī)則的左部。 歸約：歸約：推導(dǎo)的逆過(guò)程稱(chēng)為歸約歸約（Reduction）。 直接歸約：直接歸約：直接推導(dǎo)的逆過(guò)程。 推導(dǎo)和規(guī)約推導(dǎo)和規(guī)約*+ 如果存在v=w0=w1

12、=w2.=Wn=w(n0)，則稱(chēng)v推導(dǎo)出w（長(zhǎng)度為n），記作v=w(至少一步) 若有=w或v=w，則記作v=w(0步或若干步) 最左推導(dǎo)：整個(gè)推導(dǎo)過(guò)程中，每一步都是替換句型中最左邊的非終結(jié)符。 最右推導(dǎo)： 例2.6 : G = (E, i, +, *, (, ) , P , E) P： E E+E | E*E | (E) | i 寫(xiě)出表達(dá)式(i+i)*i的最左推導(dǎo)和最右推導(dǎo)。最左推導(dǎo)：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i最右推導(dǎo)：E E*E E*i (E + E)*i (E+i)*i (i + i)*i 句型句型：設(shè)(s)是一文

13、法，如果符號(hào)串x是從開(kāi)始符號(hào)推導(dǎo)出來(lái)的，即有s=x,則稱(chēng)x是文法G(s)的一個(gè)句型。 即: 任何由開(kāi)始符推導(dǎo)出來(lái)的符號(hào)串都是句型。 句子句子：若x僅由終結(jié)符號(hào)組成，則稱(chēng)x為G(S)的句子* 練習(xí)練習(xí) 文法文法G：SaAcB | Bd AAaB | c BbScA | b 寫(xiě)出寫(xiě)出句型句型aAcbBdcc和和句句子子acabcbbdcc的的推導(dǎo)推導(dǎo)過(guò)程。過(guò)程。 文法文法G所產(chǎn)生的語(yǔ)言所產(chǎn)生的語(yǔ)言定義為： 文法G產(chǎn)生的所有句子的集合稱(chēng)為G產(chǎn)生的語(yǔ)言，記為L(zhǎng)(G)，表示為： L(G)=X|S=X,XVT* 。* 例：考慮文法G: 它定義了什么語(yǔ)言。S bAA aA|a推導(dǎo)過(guò)程 ：S=bA =ba S

14、=bA =baA=baa . S=bA =baA= =baa歸納得： L(G1) = ban | n1 練習(xí)：文法(A,B,S,a,b,c,P,S) S Ac|aB A ab B bc寫(xiě)出(G)的全部元素 L(G) = abc 例：考慮文法G2: 它定義的語(yǔ)言是：S ABA aA|aB bB|bL(G2) = ambn |m,n1 例2.8：構(gòu)造一個(gè)文法G使得：L(G) = anbn |n1 S aSbS ab a,b的個(gè)數(shù)相同,則文法G為： 文法等價(jià)：文法等價(jià)： 若文法G1和文法G2所產(chǎn)生的語(yǔ)言相同，即L(G1) = L(G2)，則稱(chēng)文法G1和文法G2等價(jià)等價(jià)。例：有如下兩個(gè)文法，判斷它們是

15、否等價(jià)？ G1=（S，0，S0S，S0，S） G2=（S，0，SS0，S0，S）S0S0S00S0S 00S 0000 L(G1) = 0n | n1 對(duì)于對(duì)于G2： 對(duì)于對(duì)于G1 ：SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)，文法G1和G2等價(jià) 例 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (i+i)*i的推導(dǎo)過(guò)程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E

16、 E*i (E)* i (E + E)*i (E+ i)*i (i + i)*il 對(duì)給定的文法，定義的語(yǔ)言是由利用所有的產(chǎn)生式經(jīng)過(guò)各種方式推導(dǎo)出所有可能的句子構(gòu)成的，并沒(méi)有規(guī)定推導(dǎo)使用產(chǎn)生式的順序。l 因此從一個(gè)句型到另一個(gè)句型(句子)的推導(dǎo)過(guò)程不是唯一的。文法的二義性文法的二義性 語(yǔ)法樹(shù)語(yǔ)法樹(shù)（分析樹(shù)）（分析樹(shù)）：推導(dǎo)的形式化表示推導(dǎo)的形式化表示，有助于理解句子語(yǔ)法結(jié)構(gòu)的層次 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，該標(biāo)記屬字母集中的一個(gè)符號(hào)，根由開(kāi)始符號(hào)標(biāo)記。 隨著推導(dǎo)，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，就產(chǎn)生相應(yīng)的下一層的結(jié)點(diǎn)，候選式中自左至右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新的結(jié)點(diǎn)，并標(biāo)記它，畫(huà)出其與父結(jié)點(diǎn)之

17、間的連線。 末結(jié)點(diǎn)從左到右排列起來(lái)構(gòu)成一個(gè)句型。 如果自左至右端末結(jié)點(diǎn)排列起來(lái)都是終結(jié)符，則這顆樹(shù)表示了一個(gè)句子的推導(dǎo)過(guò)程。例：對(duì)文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的最左推導(dǎo)的語(yǔ)法樹(shù)是？ 在語(yǔ)法樹(shù)的推導(dǎo)過(guò)程中的任何時(shí)刻，沒(méi)有后代的端末結(jié)點(diǎn)自左至右排列起來(lái)就是一個(gè)句型 一棵語(yǔ)法樹(shù)表示了一個(gè)句型很多可能的不同推導(dǎo)過(guò)程。(包括最左推導(dǎo)和最右推導(dǎo))例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 i *

18、 i + i的語(yǔ)法樹(shù)： (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è)句型就唯一地對(duì)應(yīng)一棵語(yǔ)法樹(shù)。正常優(yōu)先級(jí)+優(yōu)先 定義定義：如果一個(gè)文法存在某個(gè)句型對(duì)應(yīng)兩棵或兩顆以上的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義二義文法文法。 對(duì)二義文法中的某個(gè)句子的分析（最左或最右推導(dǎo)）不是唯一的，因此有些程序設(shè)計(jì)語(yǔ)言的分析器要求文法是無(wú)二義的。例2.9 證明下述文法是二義文法。 設(shè)if語(yǔ)句S的文法G=(E，S，if，then，else，a，e，P，S)，其中P為： Sif E then S （1）Sif E th

19、en 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文法的分類(lèi)文法的分類(lèi) 文法有四種，不同類(lèi)型的文法只是對(duì)產(chǎn)生式的要求不同。 設(shè)G=(VN,VT,P,S)，其中,(VNVT)*型文法型文法(短文文法)： 對(duì)產(chǎn)生式只要求中至少含有一個(gè)非終結(jié)符。（對(duì)每個(gè)產(chǎn)生式不加任何限制）型文法型文法(上下文有關(guān)文法)：每個(gè)產(chǎn)生式限制為形如1A212, 其中1,2,(VNVT)*,AVN,型文法型文法(上下文

20、無(wú)關(guān)文法)：每個(gè)產(chǎn)生式限制為形如 A, 其中AVN，(VNVT)*型文法型文法(正規(guī)文法)：G的每個(gè)產(chǎn)生式的形式都是：AB或A，其中A,BVN，VT*。(右線性文法）文法的分類(lèi) 例2.10 例2.11 4類(lèi)文法總結(jié)： 4類(lèi)文法的定義是對(duì)產(chǎn)生式逐漸加限制的，對(duì)應(yīng)的語(yǔ)言描述能力越來(lái)越弱。 每種正規(guī)文法也都是上下文無(wú)關(guān)文法，每種上下文無(wú)關(guān)文法也都是上下文有關(guān)文法，而每種上下文有關(guān)文法也都是0型文法。 4類(lèi)文法應(yīng)用 在編譯技術(shù)中通常使用正規(guī)文法（3型文法）描述高級(jí)程序設(shè)計(jì)語(yǔ)言的詞法部分，用有限自動(dòng)機(jī)來(lái)識(shí)別單詞。 使用上下文無(wú)關(guān)文法（2型文法）描述高級(jí)程序語(yǔ)言的語(yǔ)法結(jié)構(gòu)，用下推自動(dòng)機(jī)識(shí)別語(yǔ)法成分。語(yǔ)言的

21、層次語(yǔ)言的層次 這四種語(yǔ)言可被4種自動(dòng)機(jī)識(shí)別： 0型圖靈機(jī) 1型線性界限自動(dòng)機(jī) 2型下推自動(dòng)機(jī) 3型有窮自動(dòng)機(jī) 從外到內(nèi)，四種文法對(duì)產(chǎn)生式的限制越來(lái)越多，語(yǔ)言的描述能力越來(lái)越弱2.3 高級(jí)語(yǔ)言的設(shè)計(jì)高級(jí)語(yǔ)言的設(shè)計(jì) 語(yǔ)言涉及它的設(shè)計(jì)者、實(shí)現(xiàn)者和使用者 本書(shū)主要介紹語(yǔ)言的實(shí)現(xiàn)，但實(shí)現(xiàn)之前必須了解所實(shí)現(xiàn)的語(yǔ)言的特征、結(jié)構(gòu)和功能。 本節(jié)從宏觀上介紹高級(jí)語(yǔ)言的基本結(jié)構(gòu)和共同特征，讓讀者對(duì)高級(jí)語(yǔ)言的認(rèn)識(shí)達(dá)到新的高度，從語(yǔ)言使用者逐步向語(yǔ)言的實(shí)現(xiàn)者、設(shè)計(jì)者過(guò)渡。 例子 程序語(yǔ)言的定義 程序設(shè)計(jì)語(yǔ)言的定義包括三部分： 語(yǔ)法是定義程序的一組形式規(guī)則，用它可以形成和產(chǎn)生一個(gè)形式上正確的程序； 語(yǔ)義也是一組規(guī)則的集

22、合，用以定義語(yǔ)法正確的單詞符號(hào)和語(yǔ)法單位的含義； 語(yǔ)用主要是有關(guān)程序設(shè)計(jì)技術(shù)和語(yǔ)言成分的使用方法，它使語(yǔ)言的基本概念與語(yǔ)言的外界（如數(shù)學(xué)概念或計(jì)算機(jī)的對(duì)象和操作）聯(lián)系起來(lái)。 程序的本質(zhì)程序的本質(zhì) 程序是在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)的基礎(chǔ)上對(duì)抽象算法的具體描述。 沃斯（N.wirth）以“算法+數(shù)據(jù)結(jié)構(gòu)=程序” 來(lái)描述程序 程序設(shè)計(jì)語(yǔ)言必須以描述算法和數(shù)據(jù)結(jié)構(gòu)作為他自身的主要結(jié)構(gòu)。 各種高級(jí)語(yǔ)言均以數(shù)據(jù)類(lèi)型來(lái)描述數(shù)據(jù)結(jié)構(gòu)，以控制結(jié)構(gòu)來(lái)描述算法。 馮.諾依曼體系結(jié)構(gòu)與高級(jí)語(yǔ)言 馮.諾依曼機(jī)的思想：一個(gè)存儲(chǔ)器（用來(lái)存放指令和數(shù)據(jù)），一個(gè)控制器和一個(gè)運(yùn)算器（控制器負(fù)責(zé)從存儲(chǔ)器中逐條取出指令，運(yùn)算器

23、通過(guò)算術(shù)或邏輯操作來(lái)處理數(shù)據(jù)），最后的處理結(jié)果必須送回存儲(chǔ)器中。 特點(diǎn)： （1）數(shù)據(jù)和指令均以二進(jìn)制形式存儲(chǔ)（它們?cè)谕庑紊蠜](méi)有什么區(qū)別，但每位二進(jìn)制數(shù)有不同的含義）； （2）程序以“存儲(chǔ)程序”的方式工作（即事先編寫(xiě)好程序，執(zhí)行之前先將程序存放到存儲(chǔ)器某個(gè)可知的地方）； （3）程序順序執(zhí)行（但可強(qiáng)制改變執(zhí)行順序）； （4）存儲(chǔ)器的內(nèi)容可以被修改（一旦放入新的數(shù)據(jù)，則該單元原來(lái)的數(shù)據(jù)立即消失，且被新數(shù)據(jù)代替）。 高級(jí)語(yǔ)言的特性： （1）變量：存儲(chǔ)器由大量存儲(chǔ)單元組成，數(shù)據(jù)就存放在這些單元中，匯編語(yǔ)言通過(guò)對(duì)存儲(chǔ)單元的命名來(lái)訪問(wèn)數(shù)據(jù)。在高級(jí)語(yǔ)言中，存儲(chǔ)單元及其名稱(chēng)由變量的概念來(lái)代替，變量代表一個(gè)（或一

24、組）已命名的存儲(chǔ)單元，存儲(chǔ)單元可存放變量的值。 （2）賦值：使用存儲(chǔ)單元概念的另一個(gè)結(jié)果是每個(gè)計(jì)算結(jié)果都必須存儲(chǔ)，即將其賦值到某個(gè)存儲(chǔ)單元，從而改變?cè)搯卧闹怠?（3）重復(fù)：指令存儲(chǔ)在有限的存儲(chǔ)器中，按順序執(zhí)行。若要完成復(fù)雜的計(jì)算，有效的方式就是重復(fù)執(zhí)行某些指令序列。 一個(gè)程序往往要涉及若干實(shí)體，如變量、語(yǔ)句和子程序等。實(shí)體具有某些特性，這些特性稱(chēng)為實(shí)體的屬性。 變量的屬性有名字、類(lèi)型和保留其值的存儲(chǔ)區(qū)等 語(yǔ)句的屬性是與之相關(guān)的一系列動(dòng)作 子程序的屬性有名字、形參個(gè)數(shù)和類(lèi)型、參數(shù)傳遞方式的約定等。 在處理實(shí)體之前，必須將實(shí)體與相關(guān)的屬性聯(lián)系起來(lái)，這個(gè)聯(lián)系的過(guò)程稱(chēng)為綁定綁定（Binding），每

25、個(gè)實(shí)體的綁定信息存儲(chǔ)在特定的表格中。 把實(shí)體與它的某個(gè)屬性聯(lián)系起來(lái)的時(shí)刻稱(chēng)為綁定時(shí)間。 一旦綁定，這種關(guān)系就一直存在，直到對(duì)這一實(shí)體的另一次綁定。 若一個(gè)綁定在運(yùn)行之前（即編譯時(shí)）完成，且在運(yùn)行時(shí)不會(huì)改變，則稱(chēng)為靜態(tài)綁定靜態(tài)綁定（Static Binding）。 如一個(gè)綁定在運(yùn)行時(shí)完成（此后可能在運(yùn)行過(guò)程中被改變），則稱(chēng)為動(dòng)態(tài)綁定動(dòng)態(tài)綁定（dynamic Binding）。 抽象 變量是高級(jí)語(yǔ)言中最重要的概念之一，它是一個(gè)抽象概念，是對(duì)存儲(chǔ)單元的抽象。馮.諾依曼機(jī)基于存儲(chǔ)單元組成的主存儲(chǔ)器概念，每個(gè)存儲(chǔ)單元用地址來(lái)標(biāo)識(shí)，可以對(duì)它進(jìn)行讀或?qū)懖僮?，?xiě)操作就是指修改存儲(chǔ)單元的值。賦值語(yǔ)句就是對(duì)修改存

26、儲(chǔ)單元內(nèi)容的抽象。 數(shù)據(jù)類(lèi)型 內(nèi)部類(lèi)型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)和指針類(lèi)型數(shù)據(jù)。內(nèi)部類(lèi)型是對(duì)二進(jìn)制位串的抽象，其基本形式對(duì)程序員是不可見(jiàn)的，即程序員不能直接訪問(wèn)表示一個(gè)整數(shù)的位串的某個(gè)特定位。 用戶定義類(lèi)型：數(shù)組、記錄、聯(lián)合、字符串、表格、棧、隊(duì)列、鏈表和樹(shù)等，基本表示形式對(duì)程序員是可見(jiàn)的 抽象數(shù)據(jù)類(lèi)型：數(shù)據(jù)對(duì)象的一個(gè)集合，作用于這些數(shù)據(jù)對(duì)象的抽象運(yùn)算的集合，以及這些類(lèi)型對(duì)象的封裝，C+中的類(lèi)?；颈硎緦?duì)程序員是不可見(jiàn)的 語(yǔ)句和控制結(jié)構(gòu) 程序結(jié)構(gòu)表達(dá)式表達(dá)式 表達(dá)式由運(yùn)算對(duì)象（數(shù)據(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á)式|變量|()| + |-| *|/|()|語(yǔ)句語(yǔ)句 語(yǔ)句 說(shuō)明性語(yǔ)句 可執(zhí)行語(yǔ)句 說(shuō)明性語(yǔ)句旨在定義各種不同數(shù)據(jù)類(lèi)型的變量或運(yùn)算，不需要由編譯程序生成目標(biāo)代碼，主要用來(lái)告訴編譯程序一些實(shí)體的屬性，供編譯程序生成目標(biāo)代碼時(shí)使用。 可執(zhí)行語(yǔ)句旨在描述程序的動(dòng)作，需要由編譯程序生成目標(biāo)代碼來(lái)實(shí)現(xiàn)它的語(yǔ)義。 說(shuō)明語(yǔ)句說(shuō)明語(yǔ)句 | const 標(biāo)識(shí)符 = var : |, integer|real|char|boolean執(zhí)行語(yǔ)句 | | read () writ