‘壹’ 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所示。
求采纳为满意回答。