『壹』 C語言考試我把選擇題的程序抄進編譯器里做太慢了，那麼應該怎麼做
計算機等級考試二級的考試時間是120分鍾，不清楚你的基礎怎麼樣，首先分析一下題目類型，二級c裡面有40道選擇題，其中有10道公共基礎題.公共基礎知識部分10題，共計10分，C語言部分30題，30分。操作題60分，仍是程序填空、程序改錯和編程3個題，分值分別為18、18和24分。
如果你基礎可以，建議選擇題在50分鍾以內完成，留給盡量多的時間給後面的填空，改錯和編程。
如果你C語言可以，但是公共基礎不行，建議也在50分鍾內完成，因為公共基礎如果你沒有專門復習過，那麼肯定不會，所以公共基礎迅速做，留時間給其餘的C選擇題，確保正確率。
如果你基礎不太好，建議在60分鍾內完成，然後做後面的大題。
個人體會，前面選擇終究是一個小門檻，後面的大題才是重頭，祝你考試通過！
『貳』 c語言和java哪個更好學
C與Java從編程思想上來說完全不同.
Java是純面向對象語言,用虛擬機解釋執行,速度非常慢,大約是同等C語言程序速度的1/60。好處是程序執行和
操作系統
無關。非常適合在網路上使用。
C是面向過程的語言，編譯出的程序和硬體，操作系統相關。程序運行效率非常高。好的C程序最多比同樣的匯編程序慢10%.
兩種語言入門都很簡單。要想用好還是很費功夫的。
Java程序員都是做網路工作的，年薪可到10萬美金以上。
C程序員一般是做硬體程序的，比如：PDA,手機,MP3等電子產品的開發。收入也不錯。
最好兩種語言都學。因為他們完全不同，不會互相干擾。
學C容易上手，最要是開發工具比較好用，便於實踐。
學Java缺少良好的開發工具，熟悉，配置開發環境要花很長時間。如果是沒全面學過編程的人，上手還是很困難的。
C++屬於混合型的編程語言。有Java的特點，也有C的特點。最靈活，功能也最強。要學好花的功夫也越多。
C#和Java一樣，是純面向對象的語言。但不是解釋執行的。
c語言與java的區別與各自的優勢：（c是面向過程的，java是面向對象的）
1.語言背景：
C語言是在單機時代應用非常廣泛，它融合了高級語言的簡單易用和匯編語言的執行效率。而Java是在研究電子消費產品開發平台和互聯網應用的基礎上實現的，它的許多語言特性也是從c語言那裡沿用和發展，並且使面向對象更加自然和完善（如安全性和代碼的移動性）。
2.語言跨平台：
C語言不可以跨平台，JAVA 是不怕這一點的，因為Java可以跨平台，在windows 和 unix 等系統上都可以很好的運行。
3.指針管理：
指針是c語言最大的優點，它可以使用戶幾乎可以訪問計算機的所有內存資源和其他部分資源（就是指那裡打那裡）。同時也是c語言程序最難掌握和調試的問題，並且給系統的安全性和穩定性帶來很大的困難。 而java中沒有指針的概念，盡管也有數組和對象的引用的概念，但它的管理全部交給系統管理，這樣限制了用戶的資源的訪問，但是也給java系統帶來安全性和穩定性。JAVA語言讓編程者無法找到指針來直接訪問內存無指針，並且增添了自動的內存管理功能，從而有效地防止了c語言中指針操作失誤，如野指針所造成的系統崩潰。但也不是說JAVA沒有指針，虛擬機內部還是使用了指針，只是外人不得使用而已。這有利於Java程序的安全
4.封裝
在java中引入了package的概念，使面向對象和面向組件開發更加方便，而在c語言中沒有package概念，需要其他方式來實現。Java都能夠實現面向對象思想（封裝，繼乘，多態）。而由於c語言為了照顧大量的C語言使用者，而兼容了C，使得自身僅僅成為了帶類的C語言，多多少少影響了其面向對象的徹底性！JAVA則是完全的面向對象語言，它句法更清晰，規模更小，更易學。它是在對多種程序設計語言進行了深入細致研究的基礎上，據棄了其他語言的不足之處，從根本上解決了c語言的固有缺陷。
5．數據類型及類
Java是完全面向對象的語言，所有函數和變數部必須是類的一部分。除了基本數據類型之外，其餘的都作為類對象，包括數組。對象將數據和方法結合起來，把它們封裝在類中，這樣每個對象都可實現自己的特點和行為。而c語言允許將函數和變數定義為全局的。
6．自動內存管理
Java程序中所有的對象都是用new操作符建立在內存堆棧上， Java自動進行無需內存回收操作，不需要程序員進行刪除。而c語言中必須由程序貝釋放內存資源，增加了程序設計者的負扔。Java中當一個對象不被再用到時，無用內存回收器將給它加上標簽以示刪除。JAVA里無用內存回收程序是以線程方式在後台運行的，利用空閑時間工作。
7. 字元串：
C語言不支持字元串變數，在c語言程序中使用Null終止符代表字元串的結束，在Java中字元串是用類對象(strinR和stringBuffer)來實現的，這些類對象是Java語言的核心！
Java沒有函數，作為一個比c語言更純的面向對象的語言，Java強迫開發人員把所有例行程序包括在類中，事實上，用方法實現例行程序可激勵開發人員更好地組織編碼。
『叄』 對C語言進行調試的最好方法是什麼
要了解調試程序的最好方法，首先要分析一下調試過程的三個要素：
應該用什麼工具調試一個程序?
用什麼辦法才能找出程序中的錯誤?
怎樣才能從一開始就避免錯誤?
應該用什麼工具調試一個程序?
有經驗的程序員會使用許多工具來幫助調試程序，包括一組調試程序和一些"lint」程序，當然，編譯程序本身也是一種調試工具。
在檢查程序中的邏輯錯誤時，調試程序是特別有用的，因此許多程序員都把調試程序作為基本的調試工具。一般來說，調試程序能幫助程序員完成以下工作：
(1)觀察程序的運行情況
僅這項功能就使一個典型的調試程序具備了不可估量的價值。即使你花了幾個月的時間精心編寫了一個程序，你也不一定完全清楚這個程序每一步的運行情況。如果程序員忘記了某些if語句、函數調用或分支程序，可能會導致某些程序段被跳過或執行，而這種結果並不是程序員所期望的。不管怎樣，在程序的執行過程中，尤其是當程序有異常表現時，如果程序員能隨時查看當前被執行的是那幾行代碼，那麼他就能很好地了解程序正在做什麼以及錯誤發生在什麼地方。
(2)設置斷點
通過設置斷點可以使程序在執行到某一點時暫時停住。當你知道錯誤發生在程序的哪一部分時，這種方法是特別有用的。你可以把斷點設置在有問題的程序段的前面、中間或後面。當程序執行到斷點時，就會暫時停住，此時你可以檢查所有局部變數、參數和全局變數的值。如果一切正常，可以繼續執行程序，直到遇到另一個斷點，或者直到引起問題的原因暴露出來。
(3)設置監視
程序員可以通過調試程序監視一個變數，即連續地監視一個變數的值或內容。如果你清楚一個變數的取值范圍或有效內容，那麼通過這種方法就能很快地找出錯誤的原因。此外，你可以讓調試程序替你監視變數，並且在某個變數超出預先定義的取值范圍或某個條件滿足時使程序暫停執行。如果你知道變數的所有行為，那麼這么做是很方便的。
好的調試程序通常還提供一些其它功能來簡化調試工作。然而，調試程序並不是唯一的調試工具，lint程序和編譯程序本身也能提供很有價值的手段來分析程序的運行情況。
注意：lint程序能分辨數百種常見的編程錯誤，並且能報告這些錯誤發生在程序的哪一部分。盡管其中有一些並不是真正的錯誤，但大部分還是有價值的。
lint程序和編譯程序所提供的一種典型功能是編譯時檢查(compile—time checks)，這種功能是調試程序所不具備的。當用這些工具編譯你的程序時，它們會找出程序中有問題的程序段，可能產生意想不到的效果的程序段，以及常見的錯誤。下面將分析幾個這種檢查方式的應用例子，相信對你會有所幫助。
等於運算符的誤用
編譯時檢查有助於發現等於運算符的誤用。請看下述程序段：
void foo(int a，int b)
{
if ( a = b )
{
/ * some code here * /
}
}
這種類型的錯誤一般很難發現!程序並沒有比較兩個變數，而是把b的值賦給了a，並且在b不為零的條件下執行if體。一般來說，這並不是程序員所希望的(盡管有可能)。這樣一來，不僅有關的程序段將被執行錯誤的次數，並且在以後用到變數a時其值也是錯誤的。
未初始化的變數
編譯時檢查有助於發現未初始化的變數。請看下面的函數：
void average ( float ar[], int size )
{
float total;
int a;
for( a = 0;a<size; ++a)
{
total+=ar[a];
}
printf(" %f\n", total / (float) size );
}
這里的問題是變數total沒有被初始化，因此它很可能是一個隨機的無用的數。數組所有元素的值的和將與這個隨機數的值相加(這部分程序是正確的)，然後輸出包括這個隨機數在內的一組數的平均值。
變數的隱式類型轉換
在有些情況下，C語言會自動將一種類型的變數轉換為另一種類型。這可能是一件好事(程序員不用再做這項工作)，但是也可能會產生意想不到的效果。把指針類型隱式轉換成整型恐怕是最糟糕的隱式類型轉換。
void sort( int ar[],int size )
{
/* code to sort goes here * /
}
int main()
{
int arrgy[10];
sort( 10, array );
}
上述程序顯然不是程序員所期望的，雖然它的實際運行結果難以預測，但無疑是災難性的。
用什麼辦法才能找出程序中的錯誤?
在調試程序的過程中，程序員應該記住以下幾種技巧：
先調試程序中較小的組成部分，然後調試較大的組成部分
如果你的程序編寫得很好，那麼它將包含一些較小的組成部分，最好先證實程序的這些部分是正確的。盡管程序中的錯誤並不一定發生在這些部分中，但是先調試它們有助於你理解程序的總體結構，並且證實程序的哪些部分不存在錯誤。進一步地，當你調試程序中較大的組成部分時，你就可以確信那些較小的組成部分是正常工作的。
徹底調試好程序的一個組成部分後，再調試下一個組成部分
這一點非常重要。如果證實了程序的一個組成部分是正確的，不僅能縮小可能存在錯誤的范圍，而且程序的其它組成部分就能安全地使用這部分程序了。這里應用了一種很好的經驗性原則，簡單地說就是調試一段代碼的難度與這段代碼長度的平方成正比，因此，調試一段20行的代碼比調試一段10行的代碼要難4倍。因此，在調試過程中每次只把精力集中在一小段代碼上是很有幫助的。當然，這僅僅是一個總的原則，具體使用時還要視具體情況而定。
連續地觀察程序流(flow)和數據的變化
這一點也很重要!如果你小心仔細地設計和編寫程序，那麼通過監視程序的輸出你就能准確地知道正在執行的是哪部分代碼以及各個變數的內容都是什麼。當然，如果程序表現不正常，你就無法做到這一點。為了做到這一點，通常只能藉助於調試程序或者在程序中加入大量的print語句來觀察控制流和重要變數的內容。
始終打開編譯程序警告選項 並試圖消除所有警告
在開發程序的過程中，你自始至終都要做到這一點，否則，你就會面臨一項十分繁重的工作。盡管許多程序員認為消除編譯程序警告是一項繁瑣的工作，但它是很有價值的。編譯程序給出警告的大部分代碼至少都是有問題的，因此用一些時間把它們變成正確的代碼是值得的；而且，通過消除這些警告，你往往會找到程序中真正發生錯誤的地方。
准確地縮小存在錯誤的范圍
如果你能一下子確定存在錯誤的那部分程序並在其中找到錯誤，那就會節省許多調試時間，並且你能成為一個收入相當高的專業調試員。但事實上，我們並不能總是一下子就命中要害，因此，通常的做法是逐步縮小可能存在錯誤的程序范圍，並通過這種過程找出真正存在錯誤的那部分程序。不管錯誤是多麼難於發現，這種做法總是有效的。當你找到這部分程序後，就可以把所有的調試工作集中到這部分程序上了。不言而喻，准確地縮小范圍是很重要的，否則，最終集中精力調試的那部分程序很可能是完全正確的。
如何從一開始就避免錯誤?
有這樣一句諺語——「防患於未然」，它的意思是避免問題的出現比出現問題後再想辦法彌補要好得多。這在計算機編程中也是千真萬確的!在編寫程序時，一個經驗豐富的程序員所花的時間和精力要比一個缺乏經驗的程序員多得，但正是這種耐心和嚴謹的編程風格使經驗豐富的程序員往往只需花很少的時間來調試程序，而且，如果此後程序要解決某個問題或做某種改動，他便能很快地修正錯誤並加入相應的代碼。相反，對於一個粗製濫造的程序，即使它總的來說還算正確，那麼改動它或者修正其中一個很快就暴露出來的錯誤，都會是一場惡夢。
一般來說，按結構化程序設計原則編寫的程序是易於調試和修改的，下面將介紹其中的一些原則。
程序中應有足夠的注釋
有些程序員認為注釋程序是一項繁瑣的工作，但即使你從來沒想過讓別人來讀你的程序，你也應該在程序中加入足夠的注釋，因為即使你現在認為清楚明了的語句，在幾個月以後往往也會變得晦澀難懂。這並不是說注釋越多越好，過多的注釋有時反而會混淆代碼的原意。但是，在每個函數中以及在執行重要功能或並非一目瞭然的代碼前加上幾行注釋是必要的。下面就是一段注釋得較好的代碼：
/*
* Compute an integer factorial value using recursion.
* Input an integer number.
* Output : another integer
* Side effects : may blow up stack if input value is * Huge *
*/
int factorial ( int number)
{
if ( number < = 1)
return 1; /* The factorial of one is one; QED * /
else
return n * factorial( n - 1 );
/ * The magic! This is possible because the factorial of a
number is the number itself times the factorial of the
number minus one. Neat! * /
}
函數應當簡潔
按照前文中曾提到的這樣一條原則——調試一段代碼的難度和這段代碼長度的平方成正比——函數編寫得簡潔無疑是有益的。但是，需要補充的是，如果一個函數很簡潔，你就應該多花一點時間去仔細地分析和檢查它，以確保它准確無誤。此後你可以繼續編寫程序的其餘部分，並且可以對剛才編寫的函數的正確性充滿信心，你再也不需要檢查它了。對於一段又長又復雜的常式，你往往是不會有這樣的信心的。
編寫短小簡潔的函數的另一個好處是，在編寫了一個短小的函數之後，在程序的其它部分就可以使用這個函數了。例如，如果你在編寫一個財務處理程序，那麼你在程序的不同部分可能都需要按季、按月、按周或者按一月中的某一天等方式來計算利息。如果按非結構化原則編寫程序，那麼在計算利息的每一處都需要一段獨立的代碼，這些重復的代碼將使程序變得冗長而難讀。然而，你可以把這些任務的實現簡化為下面這樣的一個函數：
/*
* ComDllte what the "real" rate of interest would be
* for a given flat interest rate, divided into N segments
*/
double Compute Interest( double Rate, int Segments )
{
int a;
double Result = 1.0;
Rate /= (double) Segments;
for( a = 0; a< Segments ; ++a )
Result * =Rate;
return Result;
}
在編寫了上述函數之後，你就可以在計算利息的每一處調用這個函數了。這樣一來，你不僅能有效地消除每一段復制的代碼中的錯誤，而且大大縮短了程序的長度，簡化了程序的結構。這種技術往往還會使程序中的其它錯誤更容易被發現。
當你習慣了用這種方法把程序分解為可控制的模塊後，你就會發現它還有更多的妙用。
程序流應該清晰，避免使用goto語句和其它跳轉語句
這條原則在計算機技術領域內已被廣泛接受，但在某些圈子中對此還很有爭議。然而，人們也一致認為那些通過少數語句使程序流無條件地跳過部分代碼的程序調試起來要容易得多，因為這樣的程序通常更加清晰易懂。許多程序員不知道如何用結構化的程序結構來代替那些「非結構化的跳轉」，下面的一些例子說明了應該如何完成這項工作：
for( a = 0; a<100s ++a)
{
Func1( a );
if (a = = 2 ) continue;
Func2( a );
}
當a等於2時，這段程序就通過continue語句跳過循環中的某余部分。它可以被改寫成如下的形式：
for( a = 0; a<100; ++a)
{
Func1 (a);
if (a !=2 )
Func2(a) ;
}
這段程序更易於調試，因為花括弧內的代碼清楚地顯示了應該執行和不應該執行什麼。那麼，它是怎樣使你的代碼更易於修改和調試的呢?假設現在要加入一些在每次循環的最後都要被執行的代碼，在第一個例子中，如果你注意到了continue語句，你就不得不對這段程序做復雜的修改(不妨試一下，因為這並非是顯而易見的!)；如果你沒有注意到continue語句，那麼你恐怕就要犯一個難以發現的錯誤了。在第二個例子中，要做的修改很簡單，你只需把新的代碼加到循環體的末尾。
當你使用break語句時，可能會發生另外一種錯誤。假設你編寫了下面這樣一段程序：
for (a =0) a<100; ++a)
{
if (Func1 (a) ==2 )
break;
Func2 (a) ;
}
假設函數Funcl()的返回值永遠不會等於2，上述循環就會從1進行到100；反之，循環在到達100以前就會結束。如果你要在循環體中加入代碼，看到這樣的循環體，你很可能就會認為它確實能從0循環到99，而這種假設很可能會使你犯一個危險的錯誤。另一種危險可能來自對a值的使用，因為當循環結束後，a的值並不一定就是100。
c語言能幫助你解決這樣的問題，你可以按如下形式編寫這個for循環：
for(a=O；a<100&&Func1(a)!=2；++a)
上述循環清楚地告訴程序員：「從0循環到99，但一旦Func1()等於2就停止循環」。因為整個退出條件非常清楚，所以程序員此後就很難犯前面提到的那些錯誤了。
函數名和變數名應具有描述性
使用具有描述性的函數和變數名能更清楚地表達代碼的意思——並且在某種程度上這本身就是一種注釋。以下幾個例子就是最好的說明：
y=p+i-c；
和
YearlySum=Principal+Interest-Charges：
哪一個更清楚呢?
p=*(l+o)；
和
page=&List[offset]；
哪一個更清楚呢?
『肆』 編譯原理題目
習題一、單項選擇題
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所示。
求採納為滿意回答。