程序設計語言基礎ppt課件

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

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

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

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

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

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

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

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

9、S1，從S推導出的符號串可用 (n0)描畫。 A(010)n B0n10n C1n D01n0 例2019年下半年上午第50：設某上下文無關文法如下：S11 | 1001 | S0 |SS，那么該文法所產(chǎ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ā)能推導出的終結(jié)符號的集合(S是文法的起始符號，為非終結(jié)符)。對于文法GS： SL|a LL，S|S 其中，GS包含的4個終結(jié)符號分別為： a ， 那么FIRST(S)的

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

11、程序就轉(zhuǎn)換為單詞串。 例軟設2019年11月上午試題27：編譯程序進展詞法分析時不能_. A.過濾源程序中的注釋 B.掃描源程序并識別句號 C.指出出錯的行號 D.查出拼錯的保管字考點考點2：正規(guī)式和正規(guī)集：正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集正規(guī)式：用正規(guī)表達式簡稱正規(guī)式可正規(guī)式：用正規(guī)表達式簡稱正規(guī)式可表示程序文語的單詞表示程序文語的單詞正規(guī)集：正規(guī)式表示的集合稱為正規(guī)集正規(guī)集：正規(guī)式表示的集合稱為正規(guī)集 例：令=a，b,上的正規(guī)式和相應的正規(guī)集的例子有： 正規(guī)式正規(guī)集 a a a|b a,b ab ab a* ,a,aa,.恣意個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：正那么表達式1*(0|01)*表示的集合元素的特點是_. A.長度為奇數(shù)的0、1串 B.開場和結(jié)尾字符必需為1的0、1串 C.串的長度為偶數(shù)的0、1串 D.不包含字串011的0、1串 例2021年上半年上午第49：由a、b構(gòu)造且僅包含偶數(shù)個a的串的集合用正規(guī)式表示為_。 A. (a*a)*b* B. (b* (ab*a)*)* C. (a*

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

14、kj屬于K表示當前形狀為ki,輸入字符在a時，將轉(zhuǎn)換為下一個形狀kj；4S屬于K，S是獨一的一個初態(tài)；5Z包含與K，Z是一個終態(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 請畫出該DFA的形狀轉(zhuǎn)換圖。補充： 對于*中的任何一個串t，假設存在一條從某一初態(tài)結(jié)點到某一個終態(tài)結(jié)點的道路，且這條道路上一切弧的標志符依序銜接成的串等于t，那么稱t可為DFA M所識別讀出或接受。 假設M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，那么空字可為M所識別接

15、受。2不確定的有窮自動機NFA一個不確定的有窮自動機NFAM是一個五元組：M=K，f，S，Z其中1K是一個有窮集，它的每個元素稱為一個形狀；2是一個有窮字母表，它的每個元素稱為一個輸入字符；3f是轉(zhuǎn)換函數(shù)，是從K*K上子集的映像； 4S屬于K，S是一個非空的初態(tài)集；5Z包含與K，Z是一個終態(tài)集。 例2：一個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 請畫出該NFA的形狀轉(zhuǎn)換圖。補充： 對于*中的任何一個串t，假設存在一條從某一初態(tài)結(jié)點到某一個終態(tài)結(jié)點

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

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

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