编译原理试题B及答案

(A) FIRST(α)∩FOLLOW(β) = Φ
(B) FIRST(α)∪FIRST(β) = Φ
(C) FIRST(α)∩FIRST(β) = Φ
(D) FIRST(α)∪FOLLOW(β) = Φ
【答案】：C。
5. 表达式 a*b-c-d$e$f-g-h*i 中，运算符的优先级由高到低依次为-、*、$，且均为右结合，
是。 (A) 属于 0 型文法，但不属于上下文有关文法 (B) 属于上下文有关文法，但不属于上下文无关文法 (C) 属于上下文无关文法，但不属于正规文法 (D) 属于正规文法 【答案】：B。
二、简述题（每小题 5 分，共 4×5＝20 分）
1. 写出表达式(a＋b/c)*(a＋b)－d 的逆波兰表示（即后缀表示）及三元式序列。
输入符号
符号
(
)
,
a
$
S
(L)
a
L
SL’
SL’
L’
ε
, S L’
3. 根据如下定义的翻译模式
D→D;D
D→T
{ L.type:=T.type }
L
T → int
{ T.type:=INT }
T → real
{ T.type:=REAL }
L→ L1 , id
L → id
{ L1.type:=L.type } { enter (, L.type)} { enter (, L.type)}
7. 对于一个有 m 个非终结符号、n 个终结符号的文法，如果可以为该文法建立一个 SLR 分
析表，则该分析表应有 列。
(A) m+n+1
(B) n+1
(C) m+n

编译原理试题与答案第1讲绪论本讲模拟练习题(不计分)1. 编译是对( )。

A. 机器语⾔的执⾏B. 汇编语⾔的翻译C. ⾼级语⾔的翻译D. ⾼级语⾔程序的解释执⾏正确答案：C你选对了2. ⽤⾼级语⾔编写的程序经编译后产⽣的程序叫( )。

A. 源程序B. ⽬标程序C. 连接程序D. 解释程序正确答案：B你选对了3. ( )不是编译程序的组成部分。

A. 词法分析程序B. 代码⽣成程序C. 设备管理程序D. 语法分析程序正确答案：C你选对了4. 源程序是句⼦的集合，( )可以较好地反映句⼦的结构。

A. 线性表B. 树C. 完全图D. 堆栈正确答案：B你选对了5. 编译程序是⼀种( )。

A. 汇编程序B. 翻译程序C. 解释程序D. ⽬标程序正确答案：B你选对了6. 按逻辑上划分，编译程序第三步⼯作是( )。

A. 语义分析B. 词法分析C. 语法分析D. 代码⽣成正确答案：A你选对了7. 编译程序中语法分析器接收以( )为单位的输⼊。

A. 单词B. 表达式C. 产⽣式D. 句⼦正确答案：A你选对了8. 编译过程中，语法分析器的任务就是( )。

A. 分析单词是怎样构成的B. 分析单词串是如何构成语句和声明的C. 分析语句和声明是如何构成程序的D. 分析程序的结构正确答案：B你选对了9. 语法分析时所依据的是( )A. 语法规则B. 词法规则C. 语义规则D. 等价变换规则正确答案：A你选对了第1讲测验（计分）把汇编语⾔程序翻译成机器可执⾏的⽬标程序的⼯作是由( )完成的。

1. 单选(1分) 把汇编语⾔程序翻译成机器可执⾏的⽬标程序的⼯作是由A. 编译器B. 解释器C. 预处理器D. 汇编器正确答案：D你选对了2. 单选(1分) ( )不是编译程序的组成部分。

A. 词法分析程序B. 语法分析程序C. 代码⽣成程序D. 设备管理程序正确答案：D你选对了3. 单选(1分) 通常⼀个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码⽣成，代码优化，⽬标代码⽣成等六个部分，还应包括( )。

西北民族大学计算机科学与信息工程学院期末考试编译原理试卷（B卷）专业:计算机科学技术课程代码: 15002171学号: 姓名:一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入题后的括号内。

每小空1分，共 10 分）1、一般程序设计语言的定义都涉及 B 三个方面。

(1)语法 (2)语义 (3)语用 (4)程序基本符号的确定供选答案：A. (1)(2)(3) B. (1)(2)(4)C. (1)(3)(4)D. (2)(3)(4)[能力层次：记忆] [难易度：B]2、程序语言一般分为（A）和（C）两大类，其中（C）通常又称为面向机器的语言。

面向机器语言指的是（B），其特点是（D），在此基础上产生了与人类自然语言比较接近的（D）（1）（2）（3）（6）Ａ. 高级语言Ｂ. 专用语言Ｃ. 低级语言Ｄ. 通用程序语言（4）Ａ. 用于解决机器硬件设计问题的语言Ｂ. 特定计算机系统所固有的语言Ｃ. 各种计算机系统都通用的语言Ｄ.只能在一台计算机上使用的语言（5） A. 程序的执行效率低，编制效率低，可读性差B. 程序的执行效率高，编制效率高，可读性强C. 程序的执行效率低，编制效率高，可读性强D. 程序的执行效率高，编制效率低，可读性差[能力层次：记忆] [难易度：C]3、高级语言编译程序常用的语法分析方法中，递归下降分析法属于 B 分析方法。

A.自左至右B.自顶向下C.自底向上D.自右向左[能力层次：记忆] [难易度：A]4、文法 G 产生的 D 的全体是该文法描述的语言。

A ．句型 B. 终结符集 C. 非终结符集 D. 句子[能力层次：记忆] [难易度：A]5、下列属于三性文法的是： CA．G1：S→AbB S→AAS A→Bab B→bB．G2: S→A ASA→abbSa bSA→ABB AS→aabbb A→baC．G3: S→aB S→aA A→bA B→bD．G4: S→Aa S→Babb A→Cc A→Bb B→Bb B→a C→D C→Bab D→d[能力层次：简单运用] [难易度：C]二、判断题（认为对的，在题后的括号内打“√”，认为错的打“×”。

编译原理复习题及答案一、选择题1．一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2．文法G[A]：A→εA→aB B→Ab B→a是(A)A 正规文法B 二型文法3．下面说法正确的是(A)A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A 必要条件B 充分必要条件5．下面说法正确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A)A 归约速度快B 对文法限制少7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B)A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A)A Lex是一个词法分析器的生成器B Yacc是一个语法分析器9．下面说法正确的是(A)A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。

东 北 大 学秦 皇 岛 分 校课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页题号 一 二 三 四 总分得分 阅卷人一、填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 理 和出错处理。

表格管2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。

3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。

4、LR （0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。

5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。

6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。

7、确定有穷自动机DFA 是 NFA 的一个特例。

8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。

二、选择题（每题2分，共20分）1、LR 语法分析栈中存放的状态是识别 B 的DFA 状态。

A 、前缀B 、可归前缀C 、项目D 、句柄 2、 D 不可能是目标代码。

A 、汇编指令代码B 、可重定位指令代码C 、绝对机器指令代码D 、中间代码 3、一个控制流程图就是具有 C 的有向图A 、唯一入口结点B 、唯一出口结点C 、唯一首结点D 、唯一尾结点 4、设有文法G[S]：S →b|bBB →bS ，则该文法所描述的语言是C 。

A 、L （G ）={b i |i ≥0}B 、L （G ）={b 2i |i ≥0}C 、L （G ）={b 2i+1|i ≥0}D 、L （G ）={b 2i+1|i ≥1}5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。

A 、编译器B 、汇编器C 、解释器D 、预处理器 6、在目标代码生成阶段，符号表用于 D 。

《编译原理》考题与答案(总16页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--[试题分类]:专升本《编译原理》_08033150[题型]:单选[分数]:21.文法所描述的语言是（）的集合。

A.文法的字汇表V中终结符号组成的符号串B.文法的字汇表V中符号组成的符号串C.由文法开始符推导的终结符号串D.由文法开始符推导的符号串答案:C2.设识别文法G[S]的LR(0)活前缀的DFA中，存在一个LR(0)项目集，其中X和A为非终结符，b为终结符，则该项目集含有（）冲突。

A.归约——归约B.移进——接受C.移进——待约D.移进——归约答案:D3.已知文法，（）是句型PaFaFbP的最左素短语。

答案:C4.已知文法（）。

A.{A，B}B.{S，A，B}C.{S}D.{S，A}答案:C5.已知字母表，下列选项中（）不是字母表∑上的正规式。

A.B.C.D.答案:B6.文法产生的语言是（）。

A.B.C.D.答案:D7.算符优先分析方法是总是对当前句型的（）进行归约的。

A.最左素短语B.句柄C.素短语D.简单短语答案:A8.设是任意符号串，则下列为恒等式的是（）。

A.B.C.D.答案:C9.局部优化指是在程序的（）范围内的优化。

A.循环体B.函数体C.基本块D.全部代码段答案:C10.语言学家Chomsky将文法和语言分为四大类，其中1型文法又称为（）。

A.上下文无关文法B.上下文有关文法C.短语文法D.正规文法答案:B11.词法分析器的输出结果是（）。

A.单词的种别编码B.单词的种别编码和自身值C.单词在符号表中的位置D.单词自身值答案:B12.编译程序的编译方式有（）种。

A. 1B. 3C. 4D. 2答案:D13.表达式：X:＝(X+Y)/ Z的四元式是（）。

A.(+，Y，X，T1），(/，Z，T1，T2), (:＝，T2，，X)B.C.D.答案:C14.已知文法，（）是该文法的句子。

《计算机编译原理》试卷B参考答案一、单项选择题（每小题1分，共25分）1、有文法G：E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约，其值为＿＿＿B＿＿＿。

A、23B、42C、30D、172、规范归约指＿＿＿B＿＿＿。

A、最左推导的逆过程B、最右推导的逆过程C、规范推导D、最左归约的逆过程3、词法分析所依据的是＿＿＿B＿＿＿。

A、语义规则B、构词规则C、语法规则D、等价变换规则4、词法分析器的输出结果是＿＿＿C＿＿＿。

A、单词的种别编码B、单词在符号表中的位置C、单词的种别编码和自身值D、单词自身值5、正规式M1和M2等价是指＿＿＿C＿＿＿。

A、M1和M2的状态数相等B、M1和M2的有向弧条数相等C、M1和M2所识别的语言集相等D、M1和M2状态数和有向弧条数相等6、下面的状态转换图接受的字集为＿＿＿D＿＿＿。

A、以0开头的二进制数组成的集合B、以0结尾的二进制数组成的集合C、含奇数个0的二进制数组成的集合D、含偶数个0的二进制数组成的集合7、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，＿＿＿B＿＿＿。

A、词法分析器应作为独立的一遍B、词法分析器作为子程序较好C、词法分析器分解为多个过程，由语法分析器选择使用D、词法分析器并不作为一个独立的阶段8、若a为终结符，则A→α·aβ为＿＿＿B＿＿＿项目A、归约B、移进C、接受D、待约9、若项目集I k含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是＿＿＿D＿＿＿。

A、LALR文法B、LR（0）文法C、LR（1）文法D、SLR（1）文法10、就文法的描述能力来说，有＿＿＿C＿＿＿。

A、SLR（1）⊂LR（0）B、LR（1）⊂LR（0）C、SLR（1）⊂LR（1）D、无二义文法⊂LR（1）11、在LR（0）的ACTION子表中，如果某一行中存在标记“r j”的栏，则＿＿＿A＿＿＿。

编译原理试题及答案一、选择题1. 下列哪个不是编译器所需的基本处理步骤？A. 词法分析B. 语法分析C. 语义分析D. 目标代码优化答案：D2. 编译器的主要功能是将高级语言程序翻译成什么形式？A. 汇编语言B. 机器语言C. 中间代码D. 高级语言答案：B3. 下列哪个不属于编译器的后端阶段？A. 代码优化B. 目标代码生成C. 词法分析D. 目标程序优化答案：C二、填空题1. 编译器的输入是源程序，输出是目标程序。

2. 目标代码生成阶段的任务是将中间代码翻译成汇编语言或机器语言。

3. 语法分析阶段的输出是抽象语法树。

三、简答题1. 请简述编译器的工作原理。

编译器的工作原理主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段。

词法分析阶段将源程序分解成单词（也称为词法单元），语法分析阶段根据语法规则将词法单元组织成一个语法树，语义分析阶段对语法树进行语义检查，中间代码生成阶段将语法树转化为中间代码，代码优化阶段对中间代码进行优化，最后目标代码生成阶段将中间代码转化为机器语言或汇编语言。

2. 请说明词法分析的作用是什么，如何实现？词法分析的作用是将源程序中的字符序列转化为单词序列，也就是将一段代码切分成不同的词法单元。

实现词法分析可以通过有限状态自动机来处理输入字符序列，并根据一系列规则将字符序列划分为词法单元。

常用的方法有手写分析器和使用词法分析生成器等。

3. 简要介绍一下代码优化的目的和方法。

代码优化的目的是通过对程序的中间代码或目标代码进行调整，以达到提高程序性能、减小程序的空间占用或减小程序的执行时间等目的。

代码优化的方法主要包括局部优化和全局优化两种。

局部优化主要针对某个代码块进行优化，如常量折叠、公共子表达式消除等。

全局优化则考虑整个程序，对程序的整体结构进行优化，如循环优化、函数内联等。

总结：编译原理试题及答案主要涵盖了选择题、填空题和简答题三个部分。

其中选择题主要考察对编译器基本处理步骤和功能的理解。

编译原理期末试题及答案一、选择题（每题2分，共20分）1. 编译器的主要功能是将（）代码转换成（）代码。

A. 高级语言，低级语言B. 高级语言，机器语言C. 汇编语言，机器语言D. 机器语言，汇编语言答案：B2. 编译过程中，词法分析的输出是（）。

A. 语法树B. 语法分析表C. 词法单元D. 抽象语法树答案：C3. 在编译原理中，语法分析通常采用（）方法。

A. 递归下降分析B. 动态规划C. 贪心算法D. 回溯算法答案：A4. 语义分析的主要任务是（）。

A. 检查语法错误B. 生成中间代码C. 检查语义错误D. 优化代码答案：C5. 编译器的优化通常发生在（）阶段。

A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D6. 编译器的前端主要负责（）。

A. 代码生成B. 代码优化C. 语法分析D. 目标代码生成答案：C7. 编译器的后端主要负责（）。

A. 代码生成B. 代码优化C. 语法分析D. 词法分析答案：A8. 编译原理中，LL(1)分析方法的特点是（）。

A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B9. 编译原理中，LR(1)分析方法的特点是（）。

A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B10. 编译原理中，语法制导翻译的主要思想是（）。

A. 根据语法树的结构进行翻译B. 根据词法单元进行翻译C. 根据语法分析表进行翻译D. 根据语义分析表进行翻译答案：A二、填空题（每题2分，共20分）1. 编译器中，用于表示语法规则的产生式通常由非终结符、产生符号和（）组成。

答案：产生式右侧2. 在编译原理中，一个文法是（）的，如果它的任何两个产生式都不会导致相同的句柄。

答案：无二义性3. 编译器的词法分析阶段通常使用（）算法来识别和分类词法单元。

答案：有限自动机4. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。

我以一名大学生的人格尊严保证，在本场考试中，自觉遵守考试纪律，服从考试管理，决不作弊或帮助别人作弊！签名：学院专业学号级班··················密···················封·····················线··················命题人签字：系主任签字：审核院长签字：共印份数：第 1 页共 4页聊城大学计算机学院13—14学年第2学期期末考试2011级《编译原理》试题（闭卷B卷）一、填空题（共10题，每空1分，共15分）1、语法分析是依据语言的规则进行的，中间代码产生是依据语言的紧密联系的。

2、规范归约是推导的逆过程。

3、表达式a+b/5*(e+f)*3的逆波兰式为。

4、自顶向下语法分析会遇到的主要问题有和。

5、对于文法G，仅含终结符号的句型称为。

6、LL(K)文法中，第一个L表示，第二个L表示，K表示。

7、若两个正规式所表示的相同，则认为二者是等价的。

8、设有文法G[S]=({b}，{S，B}，S，{S →b|bB，B→bS})，该文法所描述的语言是。

<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题1．将编译程序分成若干个“遍”是为了_b__。

a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2．构造编译程序应掌握__d__。

a.源程序b.目标语言c.编译方法d.以上三项都是3．变量应当c＿。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4．编译程序绝大多数时间花在_d___上。

a.出错处理b.词法分析c.目标代码生成d.管理表格5．词法分析器的输出结果是_c___。

a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值6．正规式MI和M2等价是指__c__。

a.MI和M2的状态数相等b.Ml和M2的有向弧条数相等。

C.M1和M2所识别的语言集相等 d.Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—c。

a．语法规则b．词法规则c．语义规则d．等价变换规则8．后缀式ab+cd+/可用表达式__b_来表示。

a．a+b/c+d b．(a+b)/(c+d)c．a+b/(c+d)d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。

a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守___d____＿原则。

a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。

2.已知文法G[E]:E→ET+|T T→TF*|F F→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b)*a(a|b)构造一个确定的有限自动机。

4．设文法G(S)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。

湖北第二师范学院2014－2015学年度第二学期《编译原理》课程考试答案(B卷) 院系：计算机学院专业班级：学生姓名：学号：考试方式：闭卷………………………………………………………………………………………………………………一、填空题（每空1分，共10分）1．从编译系统的方式看，有两种编译方式，一种是（解释）方式，另一种是（编译）。

2．编译的过程一般讲，有（词法分析），（语法分析），（语义分析），（中间代码生成），（中间代码优化）和（目标代码生成）。

3．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配）方案和（动态存储分配）方案。

二、综合题（共90分）1．（5分）构造语言｛a3n|n≥1｝的文法答案：其文法是（5分）P（A）：A→aaa|aaaA2．（5分）给出下面表达式的逆波兰表示：a*b+(c-d)/e答案：ab*cd-e/+ （5分）3．（30分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。

无论改造前还是改造后的文法，如果是LL（1）文法，则给出（i+i）*i的分析过程（要求给出详细过程，并给出LL（1）的分析表）答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归（2分）（2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是（3分）E → TE’E’→ +TE’ | εT → FT’T’→ *FT’ |εF → (E) | i证明改造后的文法是LL（1）文法的过程A.求可达ε的非终结符（1分）可达的是E’,T’B.求每个非终结符的First集合（3分）First(E)={ (,i}First(E’)={+}First(T)={ (,i}First(T’)={*}First(F)={ (,i}C.求每个产生式右部字符串的First集合（3分）First(TE’)={ (,i}First(+TE’)={+}First(FT’)={ (,i}First(*FT’)={*}First((E))={ ( }First(i)={ i }First(ε)={ ε}D.求每个非终结符的Follow集合（3分）Follow(E)={$,)}Follow(E’)= Follow(E)={$,)}Follow(T)=First(E’) ∪ Follow(E)={$,+,)}Follow(T’)= Follow(T)={$,+,)}Follow(F)= First(T’) ∪ Follow(T)={$,+, *,)}E.求每个非终结符的Select集合（5分）Select(E → TE’)=First(TE’)={ (,i }Select(E’→ +TE’)=First(+TE’)={ + }Select(E’→ε)=First(ε)-{ ε} ∪ Follow(E’)={ $,) }Select(T → FT’)=First(FT’)={ (,i }Select(T’→ *FT’)=First(*FT’)={ * }Select(T’→ε)=First(ε)-{ ε} ∪ Follow(T’)={ $,+,) }Select(F → (E))=First((E))={ ( }Select(F → i)=First(TE’)={ i }F.求有多个产生式的非终结符Select集合的交集（2分）显然有Select(E’→ +TE’) ∩Select(E’→ε)=ΦSelect(T’→ *FT’) ∩Select(T’→ε)= ΦSelect(F → (E))= ∩Select(F → i)= Φ所以改造后的文法是LL（1）文法（3）、根据E给出预测分析表（4分）符号串（i+i）*i的分析过程（4分）4．（10分）对下面的DFA进行最简化答题：第1步：确定化过程（5分）将7个状态分成两个状态集，终态集[q5,q6],非终态集[q0,q1,q2,q3,q4,q7]根据上表命名不可分割的终态集，及到达状态第2步：最小化的DFA5．（15分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是算符优先文法吗？是，则构造该文法的算符优先关系矩阵，并给出（i+i）*i的分析过程（要求给出详细过程）答案：（1）该文法是算符优先文法（1分）（2）构造该文法的算符优先矩阵A.求各非终结符的FirstVT集合（3分）FirstVT（E）=｛+，*，（，i｝FirstVT（T）=｛*，（，i｝FirstVT（F）=｛（，i｝B.求各非终结符的LasttVT集合（3分）LastVT(E)={ +，*，)，i }LastVT(T)={ *，)，i }LastVT(F)={ )，i }C.构造优先关系表（4分）6．（25分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是LR（0）文法吗？是，则构造该文法的LR（0）分析表，并给出（i+i）*i的分析过程，不是的，是SLR（1）文法吗，是，则构造该文法的SLR（1）分析表，并给出（i+i）*i的分析过程。

（2） 将所给文法消除左递归得 G’： （6 分）
S (L) | a L SL L ,SL |
5. 无左递归的文法是 LL(1)文法。
（F）
6. LR 分析法是一种规范归约分析法。
（T）
7. 文法符号的属性有两种，即继承属性和综合属性。
（T）
8. 紧跟在条件转移语句后的语句是基本块的入口语句。
（T）
9. PL0 程序具有分程序结构、过程可嵌套且支持递归调用。
（T）
10. 符号表可以辅助上下文语义正确性检查。
【解答】 （1） 最右推导为：（4 分）
S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,(L))) (L,(L,(L,S))) (L,(L,(L,a))) (L,(L,(S,a))) (L,(L,(a,a))) (L,(S,(a,a))) (L,((L),(a,a))) (L,((L,S),(a,a))) (L,((L,a),(a,a))) (L,((S,a),(a,a))) (L,((a,a),(a,a))) (S,((a,a),(a,a))) (a,((a,a),(a,a)))
A. ab0
B. a0c01
C. aaa
D. bc10
4..如果在推导过程中的任何一步 α β 都是对 α 中的最右非终结符进行替换，则称这种推导为
得__ BD__ _.
分A. 直接推导
B. 最右推导
C. 最左推导
D. 规范推导
5. 程序设计语言的单词符号一般可分为 5 种，它们是 ACD _ _及运算符和界符.
。
第1页 (共4页)
成
上海大学 09 ～ 10 学年 秋 季学期试卷(B) 绩
7. 通常程序设计语言的单词符号都能用 AC _ _描述.