AbaAbεBbBbBaBbb
与abcd等价（即有相同符号串集）B、acdcdD、abcabd
20、设有有穷自动机的状态图如图所示，其中，状态①为开始状态，状态③为终止状态。下述正规表达式中A、0100B、110111
1001402101531
可被该有穷自动机接受。
16、设有文法Gs（b，SB，S，SbbB，BbS），该文法所描述的语言是。BDLGsb2ii≥0LGsb2i1i≥1
ALGsbii≥0CLGsb2i1i≥0
C、110100D、10100
17、已知文法G定义为G（SWXYZ，x，y，z，P，S）其中，P为SWZWXYXxxXYyyY
二、填空题（每空1分，共10分）
1、编译程序首先要识别出源程序中每个并翻译其意义。和
，然后再分析每个
2、编译器常用的语法分析方法有3、对编译程序而言，输入数据是
两种。。
，输出结果是
4、翻译程序是把高级语言翻译成机器语言的程序，它有两种方式分别为（）和（），其根本区别在于（）。
第3页（共8页）
第4页（共8页）
f5、语言集合LGa
≥0相应的正规表达式为（
）。
三、判断（每小题1分，共5分）
1、解释程序是用来逐句分析、执行源程序语句的计算机程序。2、任何LL（1）文法肯定不含左递归。3、任何左线性文法都是无二义性文法。（（（）））2、有正规式abaabbab，求对应的NFA并使其确定化。
4、一种语言可由不同的文法产生，但一个文法描述的语言却是唯一的。（5、每一个NFA都对应一个唯一的一个最小化的DFA。（））
四、简答题（共5分）
编译程序的工作分为那几个阶段
五、综合题（每小题10分，共40分）
1、求生成字符串集合ssssss…的上下文无关文法，并为符号串sss给出一个推导和语法树。
第7页（共8页）
第8页（共8页）
f4、考虑产生文法G1：3、给定右线性文法G：S0S1S1A0BA1C1B0C0C0C1C01求出一个与G相等的左线性文法。SaTTTSS（1）消去G1的左递归（2）经改写后的文法是否是LL1文法？给出它的预测分析表。
第7页（共8页）
第8页（共8页）
fr