2011春课程情况（1）考试题目来自教材的例题和习题、教材的辅助程序、实验内容几个方面；（2）题型：填空（20%）、简单作答（10%），文法题（10%）、词法分析（20%）、语法分析（20%）、代码优化10%、Lex/yacc程序10%。
（3）重点在计算题上，即形式语言、词法分析、语法分析和代码优化，将占60-70%。
主要有形式语言（根据语言描述写上下文无关文法）（10分），词法分析（自动机、正则式、正则文法之间相互转化，自动机应用）（20分）；语法分析部分是给出文法和待分析的串，按照某个分析方法构建分析表列分析过程（20分），可能出现的分析方法有LL（1）、算符优先分析、LR（0）分析左递归的消除、公共因子提取对文法进行改造代码优化（10分）。
给定一段程序（可能是中间代码形式的），进行优化或找出循环之类的题目。
Lex或Yacc程序简单设计（10）(4)共有题目7道，时间100min；（5）具体考试时间、地点待后通知。
1、给出如图所示NFA(非确定自动机)等价的DFA2、构造正规式1(1|0)*101相应的DFA.3、为正规式（ab）*a(a|b)构造NFA、DFA。
4、（1）考虑正规表达式1（1|0）*101，构造可以生成语言L(r)的一个正规文法。
（2）考虑如图所示的NFA N,构造可以生成语言L(N)的一个正规文法.5、考虑如下文法G：S-->1S|0S|1AA-->0B|1BB-->e (空串)(1) 试构造语言为L(G)的一个正规表达式。
(2) 试构造语言为L(G)的一个有限自动机。
6、构造产生如下语言的上下文无关文法：（1）{a n b n|n>0}（2）{wcw R|w由a,b组成的任意串}（3）{ww R|w由a,b组成的任意串}（4）{w|w由a,b组成的任意串且w与其逆串相等}(5) {w|w由a,b组成的任意串且w中a的个数是b个数的2倍}7、考虑下面的文法：S-->aS|aSbS|e e是空串的意思这个文法是二义的，试给出串a a b的两个不同的：（1）分析树。
（2）最左推导。
（3）最右推导。
8、已知文法G[S]:S-->MH|aH-->LS|e e是空串的意思M-->K|MBLK-->dMLL-->bHf判断G是否是LL(1)文法，如果是，构造LL(1)分析表。
9、已知文法G[S]:S-->MBfM-->BbS|aB-->dMg|e e是空串的意思判断G是否是LL(1)文法，如果是，构造LL(1)分析表。
10、对于文法G[V]:V-->N|N[E]E-->V|V+EN-->i(1) 构造G[V]的优先关系表，判断G[V]是否为算符优先文法。
(2) 分析输入串i[i+i+i]是否是G[V]的句子。
11、某语言的文法G(E)为：E-->aTd|e e是空串的意思T-->Eb|ac|e（1）请证明G（E）不是LR(0)文法而是SLR(1)文法，请给出该文法的分析表。
（2）给出输入串aabdbd#的分析过程，并说明是否是G(E)的句子。
12、对于文法G[S]:S-->a|^|(T)T-->T,S| S构造文法G[S]的算法优先关系矩阵，并判断该文法是否是算符优先文法。
13、划分下列程序的所有基本块，画出程序的流图。
（1） read x（2） read y（3） r:=x mod y（4） if r=0 goto (8)（5） x:=y（6） y:=r（7） goto (3)（8） write y（9） halt14、已知四元式的代码序列如下：（1） read a（2） read b（3） h：=1（4） f：=1（5） if f>3 goto (18)（6） g：:=1（7） c：=a（8） d：=b（9） if g>2 goto (14)（10） c：=c*c（11） d：=d*d（12） g:：=g+1（13） goto (9)（14） f：=f+1（15） e：=c+d（16） h：=h*e（17） goto (5)（18） write h（19） halt完成一下任务：（1）划分为基本块并画出其流程图。
（2）求每个每个结点的必经结点集。
（3）求流图的回边。
（4）找出流图中的循环。
15、已知四元式的代码序列如下:(1) j：=1(2) write j(3) writeln(4) R[j]：=1(5) i：=1(6) if i>12 goto (22)(7) i：=i+1(8) k：=1(9) if k>4 goto (18)(10)k：=k+1(11)j：=j+1(12)if j14 goto (14)(13)j：=j+1(14)if R[j] 1 goto (9)(15)j：=j+1(16)if j14 goto (14)(17)goto (13)(18)write j(19)writeln(20)R[j]：=1(21)Goto (6)(22)Halt1、划分的基本块并画出其流图；2、求每个结点的必经结点集；3、求流图中的回边；4、找出流图中的所有循环。
16、根据定义计算下列表达式文法的算符优先关系表。
（1）E-->E+T|T(2) T-->T*F|F(3) F-->P^F|P(4) P-->(E)|i17、给出文法：（1）求出该文法对应的全部LR(0)的项目；（2）构造识别该文法所有活前缀的DFA;（3）该文法是否是LR(0)的，若是，构造LR(0)分析表。
18：对于下面的基本块，构造它的DAG表示。
（1）T0=3.14（2）T1=2*T0（3）T0=R+r(4) A=T1*T2(5)B=A(6) T4=R+r（7）T5=T3*T4(8) T6=R-r（9）B=T5*T619、求如图所示的回边。
寻找图中的流图中的循环。
21、说明LEX程序的结构。
并编写一个LEX程序，其功能将文本中的十进制转换成十六进制。
（也会是2-16,2-8之类的转换）术语解释：推导直接推导最左推导最右推导规范推导句型句子语言非确定有限自动机确定有限自动机LL（1）分析短语直接短语句柄素短语算符优先文法LR(0)项目规约项目接受项目移进项目待约项目写出下列术语的英文含义机器语言Machine Language汇编语言AssemblyLanguage高级语言high-level language源语言source language源语言是外语翻译专业术语，和目标语相对。
目标语言用另一种计算机语言写成的文件将被翻译成的计算机语言，常为一种机器语言也作object language翻译程序编译程序交叉编译程序预处理程序解释程序中间代码词法分析器语法分析器前端后端遍文法正规文法正规式有穷自动机LexLR分析SLRLALRYacc语法训练一、已知以下文法G[E],试用算符优先文法分析回答以下几个问题。
G[E]：E->E+T|TT->T*F|FF->P-F|PP->(E)|i1、分别求取FirstVt(E),FirstVt(T),FirstVt(F),FirstVt(P).2、分别求取LasttVt(E),LastVt(T),LastVt(F),LastVt(P).3、构造该文法的算符优先文法分析的分析表。
4、分析i+i*i是否为该文法的句子，并写出分析过程。
二、文法G[S]:S→AB; A→aBa|ε;B→bAb|ε.（20分）1. 引入产生式S’→S,对文法改造为G[S’],计算G[S’]的First和Follow集；2. 构造G[S’]的LR(0)项目集族和识别活前缀的DFA，说明该文法是SLR(1)文法?3. 请构造SLR(1)文法分析的分析表；4. 给出输入baab#的SLR（1）分析过程。
三、已知文法G[S]: S→a H; H→a M d|d; M→A b|ε; A→a M|e.1 求每个非终结符号的FIRST集和FOLLOW集；2 判定该文法是否为LL(1)文法，如是，构造LL(1)预测分析表；3 若是LL(1)文法，请给出输入串aaabd＃的预测分析过程，并说明该输入是G[S]的句子四、已知以下文法G[E],试用算符优先文法分析回答以下几个问题。
G[E]：E->E+T|TT->T*F|FF->P-F|PP->(E)|i1、分别求取FirstVt(E),FirstVt(T),FirstVt(F),FirstVt(P).2、分别求取LasttVt(E),LastVt(T),LastVt(F),LastVt(P).3、构造该文法的算符优先文法分析的分析表。
4、分析i+i*i是否为该文法的句子，并写出分析过程。