一、填空题（每空1分，共24分）
1、文法G定义为四元组VNVTPS，其中VN是非终结符集合，VT是终结符集合，P是规则的集合，S是起始符或识别符。，1型或上下文有关。，LR0。
A、标识符C、四元式
B、运算符D、常数
4、自上而下语法分析的主要动作是（D）不严格，加算法动作匹配，否则是推导A、移进C、规约B、推导D、匹配
2、乔姆斯基形式文法共有4种，分别是0型或短语文法文法，2型或上下文无关文法，
3型或正规文法简单优先，算符优先
3、列举4种以上的自底向上语法分析方法SLR1LR1LALR1，
5、文法S为S→ABbC，A→εb，B→εaD，C→ADb，D→aSc，FOLLOWA为（C）A、ac6、设有文法GSA、pq
i
B、c
C．、a
D、）
4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。
LEX。
S→ApBq，A→acA，B→bdB，则FIRSTAp为（CB、bdC、ac
2i
D、其他
C）
7、设有文法GS：S→bbB5、你所知道的词法分析程序自动构造工具有6、编译方式与解释方式的根本区别在于译边执行。句柄，算符优先分析法归约的对象是最左A、L（G）bi≥0C、L（G）b
2i1
B→bS，则该文法所描述的语言是（B、L（G）bi≥0D、L（G）b2i1i≥1
编译方式先翻译后执行，解释方式则是边翻
i≥0
8、设有文法GSS→ApBq，A→acA，B→bdB，则FIRSTAp为（CA、pqB、bdC、acD、其他
）
7、简单优先分析法归约的对象是素短语。
8、编译程序分为6个阶段分别是：生成、代码优化、目标代码生成。
词法分析、语法分析、语义分析、中间代码
三、综合题（共55分）1、构造正规式rb（（ab）bb）ab的DFA并化简。（10分）
NFA
二、选择题（每题2分，共16分）1、哪个不是DFA的构成成分（C）A、有穷字母表C、终止状态集合B、初始状态集合D、有限状态集合
2、词法分析器的输入是（B）A、单词符号串C、语法单位B、源程序D、目标程序
确定化
3、在词法分析阶段不能识别的是（C）
1
f2判断文法GS：S→MHa
H→LSoε
K→dMLε
L→eHf
M→KbLM是否是LL
（1）文法，如果是，构造其LL（1）预测分析表（10分）
重命名
所以是LL（1）预测分析表如下
DFA
3文法GS（10分）1S→aAcBe2A→b3A→Ab4B→d1构造文法的LR0分析表；（5分）2给出分析输入串abbcde是否为句子的LR0分析过程。（5分）
2
f2求LR0分析表（4分）
E’→EE→ET
r0r1r2r3r4r5r6
2E→T3T→TF
1
3分析r