程序設(shè)計(jì)語言基礎(chǔ)ppt課件

1、第2章 程序文語根底知識(shí)2.1 程序設(shè)計(jì)言語根底知識(shí)2.2 編譯系統(tǒng)根本原理 2.2.1 文法 2.2.2 文法分析 2.2.3 詞法分析2.3 C言語根底2.1 程序設(shè)計(jì)言語概述 低級(jí)言語(面向機(jī)器的言語) 面向?qū)ο蟪绦蛟O(shè)計(jì)言語 (C+，Java， Smalltalk)程序設(shè)計(jì)言語 邏輯程序設(shè)計(jì)言語 Prolog 高級(jí)言語 函數(shù)式的言語Lisp 命令式程序設(shè)計(jì)言語(C，Pascal) 科學(xué)計(jì)算言語Fortran 邏輯式言語 是一類以方式邏輯為根底的言語，其代表就是建立關(guān)系實(shí)際和一階謂詞實(shí)際根底上的Prolog 。邏輯式言語有很強(qiáng)的推理才干。用于開發(fā)專家系統(tǒng)、自然言語了解等。函數(shù)式言語 是一類

2、以演算為根底的言語，其根本概念來自為人工智能而設(shè)計(jì)的Lisp言語。這里所謂的函數(shù)跟數(shù)學(xué)中的函數(shù)概念是類似的。命令式言語 命令式言語又稱過程式言語，它是一種基于動(dòng)作的言語，一切的計(jì)算被看成任務(wù)序列。 例：_言語不是面向?qū)ο蟮某绦蛟O(shè)計(jì)言語。A.JavaB.C+C.SmalltalkD.Fortran2.2 編譯系統(tǒng)根本原理2.2.1 編譯原理根本知識(shí) 言語處置程序分為兩個(gè)大類：翻譯程序和解釋程序。翻譯程序：把用某種程序設(shè)計(jì)言語書寫的程序翻譯成等價(jià)的機(jī)器言語。 ?？键c(diǎn)?？键c(diǎn)1：程序編譯過程：程序編譯過程普通情況，編譯程序的流程如以下圖所示：普通情況，編譯程序的流程如以下圖所示：源程序源程序詞法分析詞

3、法分析語法分析語法分析語義分析語義分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目的代碼生成目的代碼生成目的程序目的程序 留意： 并非一切的編譯程序都分成這幾個(gè)處置階段，有些編譯程序并不需求生成中間代碼，有些編譯程序不進(jìn)展代碼優(yōu)化，有些最簡單的編譯程序在語法分析的同時(shí)產(chǎn)生目的指令代碼。 例軟設(shè)2019年5月上午試題20：編譯器對(duì)高級(jí)言語源程序的處置過程可以劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目的代碼生成等幾個(gè)階段，其中， 并不是每種編譯器都必需的。 A詞法分析和語法分析 B語義分析和中間代碼生成 C中間代碼生成和代碼優(yōu)化 D代碼優(yōu)化和目的代碼生成2.2 編譯系統(tǒng)根本原理2

4、.2.2 文法1文法定義 文法G定義為四元組VN，VT，P，S，其中：1VN為非終結(jié)符號(hào)或語法實(shí)體，或變量集；2VT為終結(jié)符號(hào)集；3P為產(chǎn)生式也稱規(guī)那么的集合；4S稱為識(shí)別符號(hào)或開場符號(hào)，它是一個(gè)非終結(jié)符。普通商定，第一條產(chǎn)生式的左部是開場符號(hào)識(shí)別符號(hào)。普通情況，大寫字母表示非終結(jié)符； 小寫字母表示終結(jié)符。 例：文法G=VN，VT，P，S，其中VN=S，VT=0，1，P=S0S1，S01. 總結(jié)： 一個(gè)文法定義的言語是終結(jié)符號(hào)串的集合，這些終結(jié)符號(hào)串應(yīng)能從文法的起始符號(hào)出發(fā)推導(dǎo)出來。2*：*稱為集合的閉包。*=012n. 其中，n表示 的方冪。假設(shè)是個(gè)符號(hào)串，n表示把本身銜接n次得到的符號(hào)串。

5、例如=AB，求*。 *=012n. 其中： 0= ，表示不包含任何符號(hào)的符號(hào)串，即空 符號(hào)串，其長度為0。 1=AB 2=ABAB 定義：設(shè)GS是一文法，假設(shè)符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來的，即有S=x，那么稱x是文法GS的句型。假設(shè)x僅有終結(jié)符號(hào)組成，即S=x，x屬于VT*，那么稱x為GS的句子。2.2.3 文法分析文法分析1.文法的類型文法的類型10型文法型文法21型文法或上下文有關(guān)文法型文法或上下文有關(guān)文法32型文法或上下文無關(guān)文法型文法或上下文無關(guān)文法10型文法定義：設(shè)G=VN，VT，P，S為一文法，假設(shè)它的每個(gè)產(chǎn)生式ab是這樣一種構(gòu)造：a屬于VNVT*且至少含有一個(gè)非終結(jié)符，而b屬于V

6、NVT*，那么G是一個(gè)0型文法。 對(duì)0型文法產(chǎn)生式的方式作某些限制，就是1型、2型、3型文法。21型文法或上下文有關(guān)文法定義：設(shè)G=VN，VT，P，S為一文法，假設(shè)P中的每一個(gè)產(chǎn)生式ab均滿足|b|a|,僅僅S除外，那么G是1型文法或上下文有關(guān)文法。32型文法或上下文無關(guān)文法定義：設(shè)G=VN，VT，P，S為一文法，假設(shè)P中的每一個(gè)產(chǎn)生式ab滿足：a是一非終結(jié)符，b屬于VNVT*，那么此文法為2型文法或上下文無關(guān)文法。例：文法G=E，+，*，i，(，)，P，E其中P為： Ei EE+E EE*E E(E)今后，對(duì)“文法一詞假設(shè)無特別闡明，那么均指上下文無關(guān)文法。 例2019年下半年上午第50：程

7、序文語的大多數(shù)語法景象可用上下文無關(guān)文法描畫。對(duì)于一個(gè)上下文無關(guān)文法 G=(N，T，P，S)，其中N是非終結(jié)符號(hào)的集合，T是終結(jié)符號(hào)的集合，P是產(chǎn)生式集合，S是開場符號(hào)。令集合V=NT，那么G所描畫的言語是 的集合。 A從S出發(fā)推導(dǎo)出的包含V中一切符號(hào)的串 B從S出發(fā)推導(dǎo)出的僅包含T中符號(hào)的串 CN中一切符號(hào)組成的串 DT中一切符號(hào)組成的串 例2021年上半年上午第50：設(shè)某言語的語法規(guī)那么用上下文無關(guān)文法G=(N,T,P,S)表示，其中N是非終結(jié)符號(hào)的集合，T是終結(jié)符號(hào)的集合，P 是產(chǎn)生式集合，S是開場符號(hào)，令V=NT，那么符合該言語的句子是_。 A. 從S 出發(fā)推導(dǎo)的、僅包含T 中符號(hào)的符

8、號(hào)串 B. 從N 中符號(hào)出發(fā)推導(dǎo)的、僅包含T 中符號(hào)的符號(hào)串 C. 從S 出發(fā)推導(dǎo)的、包含V 中符號(hào)的符號(hào)串 D. 從N 中符號(hào)出發(fā)推導(dǎo)的、包含V 中符號(hào)的符號(hào)串 2.上下文無關(guān)文法及其語法樹推導(dǎo)樹語法樹或推導(dǎo)樹：是一種描畫上下文無關(guān)文法的句型推導(dǎo)的直觀方法。經(jīng)過語法樹，可以得到文法G的句型。 從下面的例子闡明語法樹的構(gòu)造。 例：G=S，A，a，b，P，S，其中P為： 1SaAS 2ASbA 3ASS 4Sa 5Aba 構(gòu)造G的語法樹。 留意：假設(shè)在推導(dǎo)的任何一步, 都是對(duì)其中的最左最右非終結(jié)符進(jìn)展交換，那么稱這種推導(dǎo)為最左最右推導(dǎo)。 例軟設(shè)2019年5月上午試題21：知某文法GS：S0S0

9、S1，從S推導(dǎo)出的符號(hào)串可用 (n0)描畫。 A(010)n B0n10n C1n D01n0 例2019年下半年上午第50：設(shè)某上下文無關(guān)文法如下：S11 | 1001 | S0 |SS，那么該文法所產(chǎn)生的一切二進(jìn)制字符串都具有的特點(diǎn)是_。 A. 能被3整除 B. 0、1出現(xiàn)的次數(shù)相等 C. 0和1的出現(xiàn)次數(shù)都為偶數(shù) D. 能被2整除 例2019年下半年上午第48：.給定文法GS及其非終結(jié)符A，F(xiàn)IRST(A)定義為：從A出發(fā)能推導(dǎo)出的終結(jié)符號(hào)的集合(S是文法的起始符號(hào)，為非終結(jié)符)。對(duì)于文法GS： SL|a LL，S|S 其中，GS包含的4個(gè)終結(jié)符號(hào)分別為： a ， 那么FIRST(S)的

10、成員包括 (48) 。 Aa Ba、 Ca、和 Da、和，2.2.4 詞法分析詞法分析考點(diǎn)考點(diǎn)1：詞法分析的功能：詞法分析的功能詞法分析階段的主要功能如下：詞法分析階段的主要功能如下：1識(shí)別出源程序中意義獨(dú)立的最小詞法識(shí)別出源程序中意義獨(dú)立的最小詞法單位單位單詞，并且確定其類型例如表單詞，并且確定其類型例如表示符、關(guān)鍵字、操作符還是數(shù)字等。示符、關(guān)鍵字、操作符還是數(shù)字等。2刪除無用的空格、回車和其它與輸入刪除無用的空格、回車和其它與輸入介質(zhì)有關(guān)的無用符號(hào)以及程序注釋。介質(zhì)有關(guān)的無用符號(hào)以及程序注釋。3報(bào)告分析時(shí)的錯(cuò)誤。報(bào)告分析時(shí)的錯(cuò)誤。 經(jīng)過詞法分析后，源程序就轉(zhuǎn)換為單詞串。經(jīng)過詞法分析后，源

11、程序就轉(zhuǎn)換為單詞串。 例軟設(shè)2019年11月上午試題27：編譯程序進(jìn)展詞法分析時(shí)不能_. A.過濾源程序中的注釋 B.掃描源程序并識(shí)別句號(hào) C.指出出錯(cuò)的行號(hào) D.查出拼錯(cuò)的保管字考點(diǎn)考點(diǎn)2：正規(guī)式和正規(guī)集：正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集正規(guī)式：用正規(guī)表達(dá)式簡稱正規(guī)式可正規(guī)式：用正規(guī)表達(dá)式簡稱正規(guī)式可表示程序文語的單詞表示程序文語的單詞正規(guī)集：正規(guī)式表示的集合稱為正規(guī)集正規(guī)集：正規(guī)式表示的集合稱為正規(guī)集 例：令=a，b,上的正規(guī)式和相應(yīng)的正規(guī)集的例子有： 正規(guī)式正規(guī)集 a a a|b a,b ab ab a* ,a,aa,.恣意個(gè)a的串 (a|b)(a|b) aa,ab,ba,bb

12、.一切a,b組成的串 (a|b)* ,a,b,aa,bb,. 正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)那么 文法產(chǎn)生式 正規(guī)式 規(guī)則一AxB ByA=xy規(guī)則二AxA|yA=x*y規(guī)則三Ax AyA=x|y 表 正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)那么 例2019年下半年上午第48：正那么表達(dá)式1*(0|01)*表示的集合元素的特點(diǎn)是_. A.長度為奇數(shù)的0、1串 B.開場和結(jié)尾字符必需為1的0、1串 C.串的長度為偶數(shù)的0、1串 D.不包含字串011的0、1串 例2021年上半年上午第49：由a、b構(gòu)造且僅包含偶數(shù)個(gè)a的串的集合用正規(guī)式表示為_。 A. (a*a)*b* B. (b* (ab*a)*)* C. (a*

13、(ba*)*b)* D. (a|b)* (aa)*考點(diǎn)考點(diǎn)3：自動(dòng)機(jī)：自動(dòng)機(jī)有窮自動(dòng)機(jī)分為兩類：有窮自動(dòng)機(jī)分為兩類：1.確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)Deterministic Finite Automata2.不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)Nondeterministic Finite Automata。1.確定的有窮自動(dòng)機(jī)DFA一個(gè)確定的有窮自動(dòng)機(jī)DFAM是一個(gè)五元組：M=K，f，S，Z 其中1K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)形狀；2是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符，所以也稱為輸入符號(hào)字母表；3f是轉(zhuǎn)換函數(shù)，是在KK上的映像，即，如f(ki，a)=kjki屬于K，

14、kj屬于K表示當(dāng)前形狀為ki,輸入字符在a時(shí)，將轉(zhuǎn)換為下一個(gè)形狀kj；4S屬于K，S是獨(dú)一的一個(gè)初態(tài)；5Z包含與K，Z是一個(gè)終態(tài)集，終態(tài)也稱為可接受形狀或終了形狀。 例：DFA M=S，U，V，Q，a，b，f，S，Q其中f定義為： fS，a=U fV，a=U fS，b=V fV，b=Q fU，a=Q fQ，a=Q fU，b=V fQ，b=Q 請(qǐng)畫出該DFA的形狀轉(zhuǎn)換圖。補(bǔ)充： 對(duì)于*中的任何一個(gè)串t，假設(shè)存在一條從某一初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的道路，且這條道路上一切弧的標(biāo)志符依序銜接成的串等于t，那么稱t可為DFA M所識(shí)別讀出或接受。 假設(shè)M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，那么空字可為M所識(shí)別接

15、受。2不確定的有窮自動(dòng)機(jī)NFA一個(gè)不確定的有窮自動(dòng)機(jī)NFAM是一個(gè)五元組：M=K，f，S，Z其中1K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)形狀；2是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；3f是轉(zhuǎn)換函數(shù)，是從K*K上子集的映像； 4S屬于K，S是一個(gè)非空的初態(tài)集；5Z包含與K，Z是一個(gè)終態(tài)集。 例2：一個(gè)NFA M=0，1，2，3，4，a，b，f，0，2，4其中f定義為： f0，a=0，3 f2，b=2 f0，b=0，1 f3，a=4 f1，b=2 f4，a=4 f2，a=2 f4，b=4 請(qǐng)畫出該NFA的形狀轉(zhuǎn)換圖。補(bǔ)充： 對(duì)于*中的任何一個(gè)串t，假設(shè)存在一條從某一初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)

16、的道路，且這條道路上一切弧的標(biāo)志符依序銜接成的串等于t，那么稱t可為NFA M所識(shí)別讀出或接受。 例2中的NFA M所能識(shí)別的是那些含有相繼兩個(gè)a或相繼兩個(gè)b的串。 自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換過程如下圖: 對(duì)于 代之 對(duì)于 代之 對(duì)于 代之123R1R213R1 R2121231213R1| R2R 1 R 2 * R3R1R2R1R3R2 例2019年下半年上午第45-46：以下圖是一有限自動(dòng)機(jī)的形狀轉(zhuǎn)換圖，該自動(dòng)機(jī)所識(shí)別言語的特點(diǎn)是 1 ，等價(jià)的正規(guī)式為 2 。 1A由符號(hào)a、b構(gòu)成且包含偶數(shù)個(gè)a的串 B由符號(hào)a、b構(gòu)成且開頭和結(jié)尾符號(hào)都為a的串 C由符號(hào)a、b構(gòu)成的恣意串 D由符號(hào)a、b構(gòu)成且

17、b的前后必需為a的串 2A(a|b)*(aa)* Ba(a|b)*a C(a|b)* Da(ba)*a 例2021年上半年上午第48：以下圖所示有限自動(dòng)機(jī)的特點(diǎn)是_ 。 A. 識(shí)別的0、1串是以0開頭且以1結(jié)尾 B. 識(shí)別的0、1串中1的數(shù)目為偶數(shù) C. 識(shí)別的0、1串中0后面必需是1 D. 識(shí)別的0、1串中1不能延續(xù)出現(xiàn) 例2019年上半年上午第50：某確定性有限自動(dòng)機(jī)(DFA)的形狀轉(zhuǎn)換圖如以下圖所示，令d=0129，那么以下字符串中，能被該DFA接受的是_。 A3857 B1.2E+5 C-123.67 D0.576E10 例2019年上半年上午第48：有限自動(dòng)機(jī)(FA)可用于識(shí)別高級(jí)言

18、語源程序中的記號(hào)(單詞)，F(xiàn)A可分為確定的有限自動(dòng)機(jī)(DFA)和不確定的有限自動(dòng)機(jī)(NFA)。假設(shè)某DFA D與某NFA M等價(jià)，那么_。 ADFA D與NFA M的形狀數(shù)一定相等 BDFA D與NFA M可識(shí)別的記號(hào)一樣 CNFA M能識(shí)別的正規(guī)集是DFA D所識(shí)別正規(guī)集的真子集 DDFA D能識(shí)別的正規(guī)集是NFA M所識(shí)別正規(guī)集的真子集2.3 C言語根底?？键c(diǎn)：參數(shù)傳送方式參數(shù)傳送有兩種方式：傳值方式和傳援用方式。 傳值調(diào)用： 以傳值調(diào)用方式進(jìn)展參數(shù)傳送時(shí)，是將實(shí)參的值傳送給形參，然后執(zhí)行被調(diào)用的函數(shù)，被調(diào)用的函數(shù)執(zhí)行時(shí)對(duì)形參的修正不影響實(shí)參的值。 援用調(diào)用： 以援用調(diào)用方式進(jìn)展參數(shù)傳送時(shí)，是將實(shí)參的地址傳送給形參，然后執(zhí)行被調(diào)用的函數(shù)，被調(diào)用的函數(shù)執(zhí)行時(shí)對(duì)形參的修正將反映在對(duì)應(yīng)實(shí)參變量中。 例：函數(shù)f()、g()的定義如下所示，調(diào)用函數(shù)f時(shí)傳送給形參a的值為1。假設(shè)采用傳值call by value的方式調(diào)用g(c)，那么函數(shù)f的前往值為_(1)_；假設(shè)采用傳援用call by reference