m1編譯器

① MDK的簡介

MDK 即RealView MDK 或MDK-ARM（Microcontroller Development kit），是 ARM 公司收購Keil公司以後，基於uVision界面推出的針對ARM7、ARM9、Cortex-M0、Cortex-M1、Cortex-M2、Cortex-M3、Cortex-R4等ARM處理器的嵌入式軟體開發工具。MDK-ARM 集成了業內最領先的技術，包括 uVision4 集成開發環境與 RealView 編譯器RVCT。支持 ARM7、ARM9 和最新的Cortex-M3/M1/M0 核處理器，自動配置啟動代碼，集成 Flash 燒寫模塊，強大的 Simulation 設備模擬，性能分析等功能，與 ARM 之前的工具包 ADS 等相比，RealView 編譯器的最新版本可將性能改善超過 20%。
Keil公司開發的ARM開發工具MDK，是用來開發基於ARM核的系列微控制器的嵌入式應用程序。它適合不同層次的開發者使用，包括專業的應用程序開發工程師和嵌入式軟體開發的入門者。MDK包含了工業標準的Keil C編譯器、宏匯編器、調試器、實時內核等組件，支持所有基於ARM的設備，能幫助工程師按照計劃完成項目。

② 用Multisim設計兩片3線-8線解碼器接成4線-16線解碼器

將其中一個E1端接一個非門在於另一個的E1端通過一個與門接在一起作為一個輸入端即變成了四線的其中之一。

設兩個3-8線解碼器分別為解碼器Y1和Y.Y1控制端分別為C1,B1,A1,Y控制端分別為C,B,A。

M3 M2 M1 M0

C1 B1 A1 C B A

0 0 0 0 0 0

0 0 0 0 0 1

0 0 1 0 0 0

O O 1 O O 1

O O 1 1 1 1

可以發現C1和B1一直是零，所以需要把這兩個控制端接地置0。

四根線分別為M3,M2, M1,M0，分別對應 A1 C B A。

(2)m1編譯器擴展閱讀：

解碼器的種類很多，但它們的工作原理和分析設計方法大同小異，其中二進制解碼器、二-十進制解碼器和顯示解碼器是三種最典型，使用十分廣泛的解碼電路。

二進制碼解碼器，也稱最小項解碼器，N中取一解碼器，最小項解碼器一般是將二進制碼譯為十進制碼；

代碼轉換解碼器，是從一種編碼轉換為另一種編碼；顯示解碼器，一般是將一種編碼譯成十進制碼或特定的編碼，並通過顯示器件將解碼器的狀態顯示出來。

③ C++繼承的構造順序

1.構造函數
先看下面的類定義
class
B1 class B2
{ {
public: public:
int
i; int i;
B1() { i = 0;
} B2() { i = 0; }
virtual void f()
{} virtual void f() {}
}
; } ;

class
M1 class M2
{ {
public: public:
int
i; int i;
M1() { i = 0;
} M2() { i = 0; }
virtual void mf()
{} virtual void mf() {}
}
; };

class C : public B1, public B2
{
public:
virtual void f() {}
M1 m1;
M2 m2;
};

（1）編譯器會不會為C生成默認構造（default ctor）
編譯器只在需要時才會為一個類生成def
ctor。「需要時」指：
a.一個類有虛函數
b.一個類有虛基類
c.一個類的基類有def ctor
d.一個類的成員類有def ctor
在這里，class C符合c,d兩個條件，編譯器會為它生成def
ctor.

（2）默認構造的內容
編譯器生成的def ctor是這樣的
C::C()
{
B1::B1()
B2::B2()
設定虛表指針指向C的虛表
m1::M1()
m2::M2()
}
a.按聲明順序構造基類
b.設定虛表指針
c.按聲明順序構造成員類

（3）對自定義構造函數的改造
對於B1，B2，M1，M2，已有構造函數，但編譯器會對其改造，加入一些代碼，完成必要的初始化工作。改造後的ctor如下：（以B1為例）
B1::B1()
{
設定虛表指針指向B1的虛表
i = 0;
}
a.設定虛表指針
b.如果用戶寫有代碼（如i=0）,則執行這些代碼

（4）綜合（2），（3），構造函數完整代碼如下
T::T()
{
按聲明順序構造基類
設定虛表指針
按聲明順序構造成員類
如果用戶寫有代碼,則執行這些代碼
}
在用戶代碼執行前，基類與成員類已構造完畢，虛指針已設定。

所以C的構造順序是：B1-〉B2-〉虛指針設定-〉m1-〉m2->C自己的代碼（如果有的話）
由（3）可知，每個類的ctor中，都會暫時將虛指針指向自己的虛表。調用B1::B1時，虛指針指向B1的虛表，然後在C::C中，虛指針被重新設定為C的虛表。
在繼承體系中，構造是由上而下的，B1或B2構造時，C還未構造。C構造時，B1和B2已構造完成。

所以在繼承體系中，一個類的構造函數執行時，該類的所有基類已構造完畢，虛指針已設定，所有成員類也已構造完畢。但該類的所有子類均未構造完成。

2.析構函數
（1）編譯器會不會為C生成析構函數（dtor）
編譯器只在需要時才會為一個類生成dtor。「需要時」指：
a.類的基類有析構
b.類的成員類有析構
與構造不同，少了兩點，因為在一個類析構時，這是一個破壞操作（destory），既然類以已經沒用了，何必再把虛指針設一下呢。

（2）析構的內容
編譯器生成的析構是這樣的
C::~C()
{
m2::M2()
m1::M1()
B2::B2()
B1::B1()
}
a.按聲明順序相反的順序析構成員類
b.按聲明順序相反的順序析構基類
這里的相反順序是C++標准規定的要求，不同編譯器都應做到，否則不符合標准（實際上編譯器或多或少都有不符標準的地方，當然不是指這里所說的順序問題）

（3）完整的析構的調用順序
對於已有析構函數的類，編譯器會對其改造，加入一些代碼，完成必要的工作。改造後的dtor如下：
T::~T()
{
設定虛表指針指向T的虛表
執行用戶代碼
按聲明順序相反的順序析構成員類
按聲明順序相反的順序析構基類
}
這是完整的析構的調用順序
在用戶代碼執行前，虛指針已重新設定，以便用戶代碼能正確執行。然後再析構成員類和基類。

所以，如果上面例子中的五個類都有析構函數的話，調用順序是：
虛指針設定-〉C自己的代碼->m2-〉m1-〉B2-〉B1
每個類的dtor中，都會暫時將虛指針指向自己的虛表。調用C::~C時，虛指針指向C的虛表，然後在B1::~B1中，虛指針被重新設定為B1的虛表。

可見，在繼承體系中，析構是由下而上的，B1或B2析構時，C已被析構。C析構時，B1和B2還未被析構。
所以在繼承體系中，一個類的析構函數執行時，該類的所有基類還未被析構，所有成員類也未被析構。但該類的所有子類均已析構完成。

3.虛函數
在構造或析構中調用虛函數，會怎樣.如：
B1：：B1（）
{
f();
}
調用的是B1：：f（）還是C：：f（）
答案是B1::f()
每個類的ctor中，都會暫時將虛指針指向自己的虛表。調用B1::B1時，虛指針指向B1的虛表
所以是B1：：f（）
如果在C的構造函數中調用f（），那就調用C：：f（）

④ 關於計算機計數系統的概念

1. 計算機系統的構成：

a. 由軟硬體兩大部分組成；

b. 硬體：是指實體部分，通常指主機（MPU、內存及其支持部件）、介面、外設這些看得見摸得著的東西；

c. 軟體：是指程序和相關附件（程序的產品說明、使用說明等），軟體不僅能充分調動硬體的功能而且能局部模仿人類思維，因此軟體也是評價系統好壞的重要標志；

d. 軟體通常分為兩大類：

i. 系統軟體：底層軟體，和相應的硬體緊密相連，通用性較差，基於硬體平台，主要有這幾類：

*1. 標准程序庫：例如開機啟動程序BIOS；

*2. 語言處理程序：特指匯編以及高級語言編譯器；

*3. 操作系統：有批處理、分時、實時等類型；

*4. 服務程序：例如連接、診斷、調試程序等；

*5. 資料庫管理程序：基於操作系統，又低於應用程序；

*6. 網路通信程序等；

ii. 應用軟體：位於最高層次，基於系統軟體，比如游戲軟體、事務管理軟體、文本編輯器等；

舉例：比如游戲里的存檔功能就是調用了操作系統提供的文件寫入功能，因此游戲軟體是基於操作系統的；

2. 計算機系統的層次結構：

a. 三級層次結構：

第三級（最高級） 虛擬機M3（高級語言機器）

實質是編譯器，將高級語言編譯成匯編語言再傳給M2執行，

從外部看上去就是一台可以直接運行高級語言的機器，將M2的功能隱藏了

第二級 虛擬機M2（匯編語言機器）

實質也是編譯器，將匯編語言編譯成機器語言再傳給M1執行，

從外部看上去就是一台可以直接運行匯編語言的機器，將M1的功能隱藏了

第一級（最底層） 實際機器M1（機器語言機器）

可以直接運行機器語言程序

b. 嚴格來講以上虛擬機都屬於翻譯程序，通常翻譯程序可以分為兩類：

i. 編譯型：就像a.中的結構，直接將源程序最終全部翻譯成可直接在M1上運行的機器語言，程序一次性執行；

ii. 解釋型：直接運行源程序，而且是一條一條執行源程序中的語句，只不過是每執行一條就將其翻譯成可直接在M1上運行的機器語言，即翻譯一次執行一次，即使下一次重復執行該語句也必須得走該流程，這種層次結構就只有兩層；

註：該過程同樣也是三層結構的，相當於M3每執行一次高級語言就將其先翻譯成匯編語言，再翻譯成機器語言最後再執行，這種模式更加貼近人的思維，就好像真的在執行高級語言一樣，並且是「一條一條執行高級語言」的；

c. 四級層次結構：就是講第一層再向下分解出一個微程序機器，又因為實際機器和微程序機器都是實際機器，因此將第一層的實際機器改稱為傳統機器以示區別

第一層 傳統機器M1

還是機器語言機器

將每一條機器指令按照不同的部分分解成更小的原子操作，即按照「指令類型+操作數1+操作數2」的形式進行分解，

分解成更小的一組微指令，再將不同類型的微指令傳給相應的M0直接運行，例如一條機器指令（為了方便，用匯編

語言描述）」MOV AL,X;「，將其分解成更小的三條微指令MOV、AL、X，分別為移動指令、尋找寄存器存儲單元的定址

指令和尋找內存存儲單元的定址指令，然後將這三個微指令交由各自相應的微程序機器運行（分別交由移動控制單元、

寄存器定址控制單元和內存定址控制單元來運行），這樣就將實際機器M1分解成了若干更小的微程序機器M0，這更加

體現了分工合作的高效性；

第零層 微程序機器M0

微指令系統

可以直接運行各自的微指令，因此由機器指令分解而來的各條微指令可以看做更小的微程序

d. 五級層次結構：即在M1和M2（即機器機和匯編機之間）還應有一層虛擬機，即操作系統，因為它具有控制並管理計算機全部硬體資源的作用，因此上層虛擬機的很多實現都必須有操作系統支持，比如malloc需要有操作系統的內存映射來支持，但從高級語言角度來看malloc沒有任何意義，操作系統不是翻譯程序，而是上層程序的運行環境；

3. 從層次結構來劃分軟硬體：

a. 以操作系統為分界線，上層虛擬機是軟體的主要研究對象，而下層的傳統機和微程序機是硬體的主要研究對象，組成原理主要的研究對象就是傳統機和微程序機；

b. 軟硬體界線並非一成不變，隨著超大規模集成電路的發展出現了固件，即將軟體永久存於只讀存儲器中；

例如，現在已經實現部分操作系統的固化（固態C盤），這樣就省去了開機時將操作系統載入進內存的時間，MPU可以直接讀操作系統中的內容，相當於一個專門存放操作系統的永久性內存；

4. 計算機系統結構和計算機組成的區別：

a. 計算機系統結構：

i. 即計算機系統的屬性，比如指令系統、數據類型、存儲技術等；

ii. 是一種概念性的結構與功能；

iii. 只在程序員層面上可見，由於計算機系統具有多級層次結構，因此站在不同層次上的程序員所看到的計算機系統結構是不同的；

iv. 例如在C程序員看來完全相同的兩種系統結構，但在匯編程序員看來可能完全不一樣；

b. 計算機組成：

i. 是對於程序員來說是透明的（隱藏的）實現系統結構的硬體細節；

ii. 例如指令系統是一種結構問題，而如何用硬體實現（用什麼電路、用那些器件進行組合）具體的指令系統就是計算機組成問題了；

c. 最為典型的例子：

廠商一般會生產同一系列不同型號的各種計算機，不同型號之間性能以及價格等會有較大的差別，但是這些型號的計算機上面開發的軟體可以相互兼容；

其中同一系列就是指這些計算機的系統結構都是相同的，因此對於程序員來說其看到的系統屬性都是相同的，因此開發的軟體相互都可以兼容（從而使用戶的軟體投資不浪費），而不同型號就是指這些計算機組成互不相同，但是這些不同的組成都實現了相同的體系結構，不同組成使得其運行速度有較大差異，一些方面的性能可能不同，這樣可以針對不同性能需求的用戶提供同一種體系結構的產品；
目錄
（一）計算機發展歷程
（二）計算機系統層次結構
1. 計算機系統的基本組成
2. 計算機硬體的基本組成
3. 計算機硬體和軟體的關系
4. 計算機的工作過程
（三）計算機性能指標
（一）計算機發展歷程
1.世界上第一台電子數字計算機是1946年問世的ENIC（Electronic Numerical Integrator And Computer）。

2.根據計算機採用的電子器件可分為四類：
（1）第一代——電子管計算機
（2）第二代——晶體管計算機
（3）第三代——小、中規模集成電路（SSI，MSI）計算機
（4）第四代——大、超大規模集成電路（LSI，VLSI）計算機

（二）計算機系統層次結構
1. 計算機系統的基本組成
1.1 一個完整的計算機系統包括硬體系統和軟體系統。

1.2 早期的馮·諾依曼機特點：

計算機硬體系統由運算器、存儲器、控制器、輸入設備和輸出設備5大部件組成。
指令和數據以同等地位存放於存儲器內，並可按地址尋訪。
指令和數據均用二進制數表示。
指令由操作碼和地址碼組成，操作碼用來表示操作的性質，地址碼用來表示操作碼在存儲器中的位置。
指令在存儲器內按順序存放。通常，指令是順序執行的，在特定條件下，可根據運算結果或根據設定的條件改變執行順序。
機器以運算器為中心，輸入輸出設備與存儲器間的數據傳送通過運算器完成。
註：現代計算機以存儲器為中心。

2. 計算機硬體的基本組成
2.1 計算機硬體的組成及作用：

運算器（ALU）：完成算術運算和邏輯運算，並將運算的中間結果暫存在運算器內。
存儲器：存放數據和程序。
控制器：控制、指揮程序和數據的輸入、運行以及處理運算結果。
輸入設備：將人們熟悉的信息形式轉換為機器能識別的信息形式，常見的有鍵盤、滑鼠等。
輸出設備：將機器運行結果轉換為人們熟悉的信息形式，如列印機輸出、顯示器輸出等。
2.2 計算機軟體的組成：

系統軟體：標准程序庫、語言處理程序、操作系統、服務性程序、資料庫管理系統、計算機網路軟體等。
應用軟體（應用程序）：科學計算程序、數據處理程序、過程式控制製程序、事務管理程序、各種APP等。
2.3 說明

中央處理器（CPU）：運算器和控制器。
I/O設備：輸入設備和輸出設備。
地址寄存器（MAR）：存放欲訪問的存儲單元地址。
數據寄存器（MDR）：暫存要從存儲器中讀或者寫的信息。
運算器：包含若干通用寄存器，如累計器（ACC）、乘商寄存器（MO）、操作數寄存器（X）、變址寄存器（IX）、基址寄存器（BR）、程序狀態寄存器（PSW）等。
控制器由程序計數器（PC）、指令寄存器（IR）、控制單元（CU）組成。
3. 計算機硬體和軟體的關系
硬體和軟體是一個完整的計算機系統互相依存的兩大部分，它們的關系主要體現在以下幾個方面。

硬體和軟體互相依存：硬體是軟體賴以工作的物質基礎，軟體的正常工作是硬體發揮作用的唯一途徑。計算機系統必須要配備完善的軟體系統才能正常工作，且充分發揮其硬體的各種功能。
硬體和軟體無嚴格界線： 隨著計算機技術的發展，在許多情況下，計算機的某些功能既可以由硬體實現，也可以由軟體來實現。因此，硬體與軟體在一定意義上說沒有絕對嚴格的界面。
硬體和軟體協同發展：計算機軟體隨硬體技術的迅速發展而發展，而軟體的不斷發展與完善又促進硬體的更新，兩者密切地交織發展，缺一不可。
4. 計算機的工作過程
計算機的工作過程可分為以下幾個過程：

把程序和數據裝入到主存儲器中。
從程序的起始地址運行程序。
用程序的首地址從存儲器中取出第一條指令，經過解碼、執行步驟等控制計算機各功能部件協同運行，完成這條指令功能，並計算下一條指令的地址。
用新得到的指令地址繼續讀出第二條指令並執行，直到程序結束為止；每一條指令都是在取指、解碼和執行的循環過程中完成的。
（三）計算機性能指標
機器字長：計算機進行一次整數運算（即定點整數運算）所能處理的二進制數據的位數。數的表示範圍越大，計算精度越高。

數據通路帶寬：數據匯流排一次所能並行傳送信息的位數。

主存容量：主存儲器所能存儲信息的最大容量，用位元組或字數×字長表示。MAR的位數反映了存儲單元的個數。
如：MAR為16位，則有216 個存儲單元（即64K內存，1K=1024），若MDR為32位，表示存儲容量為64K×32位。

運算速度：

（1）吞吐量和響應時間

吞吐量：系統在單位時間內處理請求的數量，主要取決於主存的存取周期。
響應時間：用戶向計算機發送一個請求，到系統對該請求做出響應並獲得它所需要 的 結果的等待時間。
（2）主頻和CPU時鍾周期

主頻（CPU時鍾頻率）：機器內部主時鍾的頻率，即CPU時鍾周期的倒數，常以MHz為單位，1MHz表示每秒1次。
CPU時鍾周期：通常為節拍脈沖或T周期，即主頻的倒數，是CPU中最小的時間單位。
（3）CPI：執行一條指令所需要的時鍾周期數。

（4）CUP執行時間：運行一個程序所花費的時間。
   CUP執行時間 = CPU時鍾周期數 / 主頻 = (指令條數 × CPI）/ 主頻

（5）MIPS、MFLOPS、GFLOPS和TFLOPS

MIPS：每秒執行多少百萬條指令。
MIPS = 指令條數 / (執行時間 × 106）= 主頻 / CPI

MFLOPS：每秒執行多少百萬次浮點運算。

GFLOPS：每秒執行多少十億次浮點運算。

TFLOPS：每秒執行多少萬億次浮點運算。

⑤ access創建名稱為m1的宏功能為tEmployee的表

access可以直接在宏創建名稱為m1的宏功能為tEmployee的表。
宏)是一種批量處理的稱謂。計算機科學里的宏是一種抽象(Abstraction)，它根據一系列預定義的規則替換一定的文本模式。解釋器或編譯器在遇到宏時會自動進行這一模式替換。創建宏時，意味著要錄制滑鼠點擊操作和按鍵操作。創建宏後，可進行編輯，以對其工作方式進行細微更改。
1、打開access，新建一個宏，點擊上面菜單欄的「創建」，點擊「宏」。
2、然後在彈出的界面選擇要用的宏操作，再設置好宏的相關參數。
3、最後點擊保存，在彈出的窗口中設置好宏名稱，點擊確定即可。

⑥ 編譯原理題目

習題一、單項選擇題
1、將編譯程序分成若干個「遍」是為了 。
a．提高程序的執行效率
b．使程序的結構更加清晰
c．利用有限的機器內存並提高機器的執行效率
d．利用有限的機器內存但降低了機器的執行效率
2、構造編譯程序應掌握 。
a．源程序 b．目標語言
c．編譯方法 d．以上三項都是
3、變數應當 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、編譯程序絕大多數時間花在 上。
a．出錯處理 b．詞法分析
c．目標代碼生成 d．管理表格
5、 不可能是目標代碼。
a．匯編指令代碼 b．可重定位指令代碼
c．絕對指令代碼 d．中間代碼
6、使用 可以定義一個程序的意義。
a．語義規則 b．詞法規則
c．產生規則 d．詞法規則
7、詞法分析器的輸入是 。
a．單詞符號串 b．源程序
c．語法單位 d．目標程序
8、中間代碼生成時所遵循的是- 。
a．語法規則 b．詞法規則
c．語義規則 d．等價變換規則
9、編譯程序是對 。
a．匯編程序的翻譯 b．高級語言程序的解釋執行
c．機器語言的執行 d．高級語言的翻譯
10、語法分析應遵循 。
a．語義規則 b．語法規則
c．構詞規則 d．等價變換規則
解答
1、將編譯程序分成若干個「遍」是為了使編譯程序的結構更加清晰，故選b。
2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。
3、對編譯而言，變數既持有左值又持有右值，故選c。
4、編譯程序打交道最多的就是各種表格，因此選d。
5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。
6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間代碼生成遵循的是語義規則，並且語義規則可以定義一個程序的意義。因此選a。
7、b 8、c 9、d 10、c
二、多項選擇題
1、編譯程序各階段的工作都涉及到 。
a．語法分析 b．表格管理 c．出錯處理
d．語義分析 e．詞法分析
2、編譯程序工作時，通常有 階段。
a．詞法分析 b．語法分析 c．中間代碼生成
d．語義檢查 e．目標代碼生成
解答
1．b、c 2. a、b、c、e
三、填空題
1、解釋程序和編譯程序的區別在於 。
2、編譯過程通常可分為5個階段，分別是 、語法分析 、代碼優化和目標代碼生成。 3、編譯程序工作過程中，第一段輸入是 ，最後階段的輸出為 程序。
4、編譯程序是指將 程序翻譯成 程序的程序。 解答
是否生成目標程序 2、詞法分析 中間代碼生成 3、源程序 目標代碼生成 4、源程序 目標語言
一、單項選擇題
1、文法G：S→xSx|y所識別的語言是 。
a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法G描述的語言L(G)是指 。
a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}
c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)}
3、有限狀態自動機能識別 。
a. 上下文無關文法 b. 上下文有關文法
c.正規文法 d. 短語文法
4、設G為算符優先文法，G的任意終結符對a、b有以下關系成立 。
a. 若f(a)>g(b)，則a>b b.若f(a)<g(b)，則a<b
c. a~b都不一定成立 d. a~b一定成立
5、如果文法G是無二義的，則它的任何句子α 。
a. 最左推導和最右推導對應的語法樹必定相同
b. 最左推導和最右推導對應的語法樹可能不同
c. 最左推導和最右推導必定相同
d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同
6、由文法的開始符經0步或多步推導產生的文法符號序列是 。
a. 短語 b.句柄 c. 句型 d. 句子
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
則句型P+T+i的句柄和最左素短語為 。
a.P+T和i b. P和P+T c. i和P+T+i d.P和T
8、設文法為：S→SA|A
A→a|b
則對句子aba，下面 是規范推導。
a. SÞSAÞSAAÞAAAÞaAAÞabAÞaba
b. SÞSAÞSAAÞAAAÞAAaÞAbaÞaba
c. SÞSAÞSAAÞSAaÞSbaÞAbaÞaba
d. SÞSAÞSaÞSAaÞSbaÞAbaÞaba
9、文法G：S→b|∧(T)
T→T,S|S
則FIRSTVT(T) 。
a. {b,∧,(} b. {b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}
10、產生正規語言的文法為 。
a. 0型 b. 1型 c. 2型 d. 3型
11、採用自上而下分析，必須 。
a. 消除左遞歸 b. 消除右遞歸 c. 消除回溯 d. 提取公共左因子
12、在規范歸約中，用 來刻畫可歸約串。
a. 直接短語 b. 句柄 c. 最左素短語 d. 素短語
13、有文法G：E→E*T|T
T→T+i|i
句子1+2*8+6按該文法G歸約，其值為 。
a. 23 B. 42 c. 30 d. 17
14、規范歸約指 。
a. 最左推導的逆過程 b. 最右推導的逆過程
c. 規范推導 d. 最左歸約的逆過程
[解答]
1、選c。
2、選a。
3、選c。
4、雖然a與b沒有優先關系，但構造優先函數後，a與b就一定存在優先關系了。所以，由f(a)>g)(b)或f(a)<g(b)並不能判定原來的a與b之間是否存在優先關系：故選c。
5、如果文法G無二義性，則最左推導是先生長右邊的枝葉：對於d，如果有兩個不同的是了左推導，則必然有二義性。故選a。
6、選c。
7、由圖2-8-1的語法樹和優先關系可以看出應選b。

8、規范推導是最左推導，故選d。
9、由T→T,…和T→(… 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}； 因此選c。
10、d 11、c 12、b 13、b 14、b
二、多項選擇題
1、下面哪些說法是錯誤的 。
a. 有向圖是一個狀態轉換圖 b. 狀態轉換圖是一個有向圖
c.有向圖是一個DFA d.DFA可以用狀態轉換圖表示
2、對無二義性文法來說，一棵語法樹往往代表了 。
a. 多種推導過程 b. 多種最左推導過程 c.一種最左推導過程
d.僅一種推導過程 e.一種最左推導過程
3、如果文法G存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。
a. 該句子的最左推導與最右推導相同
b. 該句子有兩個不同的最左推導
c. 該句子有兩棵不同的最右推導
d. 該句子有兩棵不同的語法樹
e.該句子的語法樹只有一個
4、有一文法G：S→AB
A→aAb|ε
B→cBd|ε
它不產生下面 集合。
a. {anbmcndm|n,m≥0} b. {anbncmdm|n,m>0}
c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0}
e. {anbncndn|n≥0}
5、自下而上的語法分析中，應從 開始分析。
a. 句型 b. 句子 c. 以單詞為單位的程序
d. 文法的開始符 e. 句柄
6、對正規文法描述的語言，以下 有能力描述它。
a.0型文法 b.1型文法 c.上下文無關文法 d.右線性文法 e.左線性文法
解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e
三、填空題
1、文法中的終結符和非終結符的交集是 。詞法分析器交給語法分析器的文法符號一定是 ，它一定只出現在產生式的 部。
2、最左推導是指每次都對句型中的 非終結符進行擴展。
3、在語法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。
4、採用 語法分析時，必須消除文法的左遞歸。
5、 樹代表推導過程， 樹代表歸約過程。
6、自下而上分析法採用 、歸約、錯誤處理、 等四種操作。
7、Chomsky把文法分為 種類型，編譯器構造中採用 和 文法，它們分別產生 和 語言，並分別用 和 自動機識別所產生的語言。
解答 1、空集 終結符 右
2、最左
3、自上而上 自下而上
4、自上而上
5、語法 分析
6、移進 接受
7、4 2 型 3型 上下文無關語言 正規語言 下推自動機 有限
四、判斷題
1、文法 S→aS|bR|ε描述的語言是(a|bc)* ( )
R→cS
2、在自下而上的語法分析中，語法樹與分析樹一定相同。 （ ）
3、二義文法不是上下文無關文法。 （ ）
4、語法分析時必須先消除文法中的左遞歸。 （ ）
5、規范歸約和規范推導是互逆的兩個過程。 （ ）
6、一個文法所有句型的集合形成該文法所能接受的語言。 （ ）
解答 1、對 2、錯 3、錯 4、錯 5、錯 6、錯
五、簡答題
1、句柄 2、素短語 3、語法樹 4、歸約 5、推導
[解答]
1、句柄：一個句型的最左直接短語稱為該句型的句柄。
2、素短語：至少含有一個終結符的素短語，並且除它自身之外不再含任何更小的素短語。
3、語法樹：滿足下面4個條件的樹稱之為文法G[S]的一棵語法樹。
①每一終結均有一標記，此標記為VN∪VT中的一個符號；
②樹的根結點以文法G[S]的開始符S標記；
③若一結點至少有一個直接後繼，則此結點上的標記為VN中的一個符號；
④若一個以A為標記的結點有K個直接後繼，且按從左至右的順序，這些結點的標記分別為X1,X2,…,XK，則A→X1,X2,…,XK，必然是G的一個產生式。
4、歸約：我們稱αγβ直接歸約出αAβ，僅當A→γ 是一個產生式，且α、β∈(VN∪VT)*。歸約過程就是從輸入串開始，反復用產生式右部的符號替換成產生式左部符號，直至文法開始符。
5、推導：我們稱αAβ直接推出αγβ，即αAβÞαγβ，僅當A→ γ 是一個產生式，且α、β∈(VN∪VT)*。如果α1Þα2Þ…Þαn，則我們稱這個序列是從α1至α2的一個推導。若存在一個從α1αn的推導，則稱α1可推導出αn。推導是歸約的逆過程。
六、問答題
1、給出上下文無關文法的定義。
[解答]
一個上下文無關文法G是一個四元式（VT,VN,S, P），其中：
●VT是一個非空有限集，它的每個元素稱為終結符號；
●VN是一個非空有限集，它的每個元素稱為非終結符號，VT∩VN=Φ；
●S是一個非終結符號，稱為開始符號；
●P是一個產生式集合（有限），每個產生式的形式是P→α，其中，P∈VN，
α∈(VT∪VN)*。開始符號S至少必須在某個產生式的左部出現一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的語言是什麼？
[解答]
（1）由於產生式左部存在終結符號，且所有產生式左部符號的長度均小於等於產生式右部的符號長度，所以文法G[S]是Chomsky1型文法，即上下文有關文法。
（2）按產生式出現的順序規定優先順序由高到低（否則無法推出句子），我們可以得到：
SÞabQÞabc
SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc
SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞ
aaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc
……
於是得到文法G[S]生成的語言L={anbncn|n≥1}
3、按指定類型，給出語言的文法。
L={aibj|j＞i≥1}的上下文無關文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求該語言對應的上下文無關文法首先應有S→aSb型產生式，以保證b的個數不少於a的個數；其次，還需有S→Sb或S→bS型的產生式，用以保證b的個數多於a的個數；也即所求上下文無關文法G[S]為：
G[S]：S→aSb|Sb|b
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）寫出句子acabcbbdcc的最左推導過程。
【解答】（1）分別畫出對應兩句型的語法樹，如圖2-8-2所示
句柄:AaB Bd

圖2-8-2 語法樹
（2）句子acabcbbdcc的最左推導如下：
SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA
ÞacabcbbdcAÞacabcbbdcc
5、對於文法G[S]：
S→（L）|aS|a L→L, S|S
（1）畫出句型（S,（a））的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。
【解答】
（1）句型（S,（a））的語法樹如圖2-8-3所示

（2）由圖2-8-3可知：
①短語：S、a、(a)、S,(a)、(S,(a))；
②直接短語：a、S；
③句柄：S；
④素短語：素短語可由圖2-8-3中相鄰終結符之間的優先關系求得，即；

因此素短語為a。
6、考慮文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
證明T*P↑（T*F）是該文法的一個句型，並指出直接短語和句柄。
【解答】
首先構造T*P↑（T*F）的語法樹如圖2-8-4所示。

由圖2-8-4可知，T*P↑（T*F）是文法G[T]的一個句型。
直接短語有兩個，即P和T*F；句柄為P。

一、單項選擇題
1、詞法分析所依據的是 。
a. 語義規則 b. 構詞規則 c. 語法規則 d. 等價變換規則
2、詞法分析器的輸出結果是 。
a. 單詞的種別編碼 b. 單詞在符號表中的位置
c. 單詞的種別編碼和自身值 d. 單詞自身值
3、正規式M1和M2等價是指 。
a. M1和M2的狀態數相等 b. M1和M2的有向弧條數相等
c. M1和M2所識別的語言集相等 d. M1和M2狀態數和有向弧條數相等
4、狀態轉換圖（見圖3-6-1）接受的字集為 。

a. 以 0開頭的二進制數組成的集合 b. 以0結尾的二進制數組成的集合
c. 含奇數個0的二進制數組成的集合 d. 含偶數個0的二進制數組成的集合
5、詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確，因此， 。
a. 詞法分析器應作為獨立的一遍 b. 詞法分析器作為子程序較好
c. 詞法分析器分解為多個過程，由語法分析器選擇使用 d. 詞法分析器並不作為一個獨立的階段
解答 1、b 2、c 3、c 4、d 5、b
二、多項選擇題
1、在詞法分析中，能識別出 。
a. 基本字 b. 四元式 c. 運算符
d. 逆波蘭式 e. 常數
2、令∑={a,b}，則∑上所有以b開頭，後跟若干個ab的字的全體對應的正規式為 。
a. b(ab)* b. b(ab)+ c.(ba)*b
d. (ba)+b e. b(a|b)
解答 1、a、c、e 2、a、b、d
三、填空題
1、確定有限自動機DFA是 的一個特例。
2、若二個正規式所表示的 相同，則認為二者是等價的。
3、一個字集是正規的，當且僅當它可由 所 。
解答 1、NFA 2、正規集 3、DFA（NFA）所識別
四、判斷題
1、一個有限狀態自動機中，有且僅有一個唯一終態。 （ ）
2、設r和s分別是正規式，則有L（r|s）=L(r)|L(s)。 （ ）
3、自動機M和M′的狀態數不同，則二者必不等價。 （ ）
4、確定的自動機以及不確定的自動機都能正確地識別正規集。 （ ）
5、對任意一個右線性文法G，都存在一個NFA M，滿足L(G)=L(M)。 （ ）
6、對任意一個右線性文法G，都存在一個DFA M，滿足L(G)=L(M)。 （ ）
7、對任何正規表達式e，都存在一個NFA M，滿足L(G)=L(e)。 （ ）
8、對任何正規表達式e，都存在一個DFA M，滿足L(G)=L(e)。 （ ）
解答 1 、2、3、錯 4、5、6、7、8、正確
五、基本題
1、設M＝（{x,y}, {a,b}, f,x,{y}）為一非確定的有限自動機，其中f定義如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
試構造相應的確定有限自動機M′。
解答：對照自動機的定義M=(S,Σ,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數，所以是一非確定有限自動機，先畫出NFA M相應的狀態圖，如圖3-6-2所示。

用子集法構造狀態轉換矩陣表3-6-3所示。
I Ia Ib
{x} {x,y} {y}
{y} — {x,y}
{x,y} {x,y} {x,y}
將轉換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態轉換矩陣。
表3-6-4 狀態轉換矩陣
a b
0 2 1
1 — 2
2 2 2
即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其狀態轉換圖如圖3-6-5所示。

將圖3-6-5的DFA M′最小化。首先，將M′的狀態分成終態組{1，2}與非終態組{0}；其次，考察{1,2}。由於{1,2}a={1,2}b={2}⊂{1,2}，所以不再將其劃分了，也即整個劃分只有兩組{0}，{1,2}：令狀態1代表{1,2}，即把原來到達2的弧都導向1，並刪除狀態2。最後，得到如圖3-6-6所示化簡DFA M′。

2、對給定正規式b*（d|ad）（b|ab）+，構造其NFA M；
解答：首先用A+=AA*改造正規式得：b*(d|ad)(b|ab)(b|ab)*；其次，構造該正規式的NFA M，如圖3-6-7所示。
求採納為滿意回答。

⑦ C++運行問題

有兩個錯誤：
#include<iostream.h>
typedef unsigned short USHORT;
typedef unsigned short ULONG;
//ULONG GrtPower(USHORT n,USHORT power); //錯誤1.GrtPower拼寫錯誤
ULONG GetPower(USHORT n,USHORT power);
int main()
{
USHORT number,power;
ULONG answer;
cout<<"Enter a number:";
cin>>number;
cout<<"To what power?";
cin>>power;
answer=GetPower(number,power);
cout<<number<<"to the"<<power<<"th power is"<<
answer<<endl;
return 0;
}
//ULONG GetPower(USHORT n,USHORT power);//錯誤2.後面的;去掉
ULONG GetPower(USHORT n,USHORT power)
{
if(power==1)
return n;
else
return(n*GetPower(n,power-1));
}