第一章 2010

以下对编译器(compiler)描述错误的是（ ）。



A. 编译器是将一种语言翻译成另一种语言的计算机 部件，包括软件部分和硬件部分； B. 输入编译器的源语言通常是高级语言，如C语言； 输出编译器的目标语言通常是低级语言，如01代码； C. 词法分析是编译器的一个处理阶段； D. 编译器和编辑器以及其它程序经常被捆绑成一 个与用户交互的开发环境(IDE)中。

※编译器的翻译过程
第一章 2009

编译器各处理阶段的正确顺序是（ ）

A．词法分析、语法分析、语义分析、代码生成； B．语法分析、词法分析、语义分析、代码生成； C．语义分析，语法分析、词法分析，代码生成； D．以上都不对。 A．字符串、记号串 C．记号串、语法树 B．记号串、注释树 D．语法树、注释树
第一章 2010

汇编语言与机器语言相比，其主要优点在于 （ ）。


A．汇编语言机器依赖性强； B．汇编程序的可执行程序的长度可以大幅下降； C．汇编语言的符号形式更易理解，也提高了编写 程序的准确性； D．以上都不对。
第一章 2010

一般的编译器中，语法分析的结果是生成源程 序的（ ）。


分析程序的功能及其输入输出。 常见的高级语言的文法（上下文无关文法）、 表示方式（BNF）以及其特点（包含递归）。 推导 分析给定文法的：终结符、非终结符、生成的 语言、对某个串的推导。 二义性文法

概念及消除二义性的方法（1、2） 常见产生原因及消除的方法
第三章 2010

判断：

一个文法所描述的语言是不唯一的；描述一个语言 的文法是唯一的。（ ）

编译过程中，语法分析器的任务是_______。
①分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的 ③分析语句和说明是如何构成程序的 ④分析程序的结构 A、②和③ B、④ C、②③④ D、①②③④

第三章

2008
已知文法G[S]： S::=a | (T) T::=T，S | S 给出句子（a，（a，a））的最左推导并画出 语法树。

编译器中语法分析的输入和输出分别是（ ）


什么是编译器？请简述编译器的功能及其输入输出。
第一章 2008

以下对编译器(compiler)描述错误的是（ ）。
编译器的输入是由源语言编写的源程序，输出是由目标语 言编写的目标程序。 B 编译器是一个执行程序而不是一个转换程序。 C 编译器和编辑器以及其它程序经常被捆绑成一个与用户交 互的开发环境(IDE)中。 D 按照编译器扫描的遍数，可把编译器分为一遍扫描和多遍 扫描的编译器。
第二章 2009

表示“由a或b组成的含有偶数个b的字符串” 的正则表达式是（ ）

A．a*ba*ba* C．(abab)*
B. (a*ba*ba*)* D. 以上都不对

请写出下面各个字符串的正则表达式

所有整数的数字串（包括负数） 字符串中至多含有一个A的大写字母串

请简述有限自动机的组成元素并解释DFA和 NFA的区别。
第四章 2009

设有文法G[S]：
S→ X S | ε X→ a S b | { S } | c 计算文法G[S]非终结符的FIRST集合和FOLLOW集 合； 若采用自顶向下分析方法，对此文法来说，在分析 过程中能否避免二义性？为什么？ 分析符号串aababb是否为此文法的句子。



第四章 2009
第三章 2009

在文法中可能引起二义性的原因有：（ ）

A．运算的优先级 C．else的悬挂问题
B. 运算的结合性 D. 以上都有可能
第三章 2008

以下对于语法二义性的描述正确的是（）。
A如果文法G的某个句子存在两棵或者两棵以上的语法树（或 分析树），则称该文法是存在二义性的； B如果文法G的某个文法存在两个或者两个以上的句子符合该 文法规则，则称该文法是存在二义性的； C消除文法二义性只能对文法进行修改，别无他法； D能够通过算法判别文法是否存在二义性 。
第二章 2009

以下不是有限自动机的组成元素的是（）

A．开始状态 C．正则表达式
B．结束状态 D．状态转换函数

已知正则表达式(ab)*(a|b)


1．构造该正则表达式所对应的NFA； 2．由NFA构造DFA； 3．对DFA进行最小化。
第二章 2008


以下对有穷自动机的图形表示描述错误的是（）。
第六章 要点

属性文法 概念：


联编 联编时间 静态语义和动态语义

常见的静态语义 符号表的作用、内容 符号表存储的属性
第六章 2008-2010

下面不属于语义属性的是（
A. 变量的数据类型 C. 变量对应的内存地址
）
B. 表达式的值 D. 源程序文件名
3
第二章 2010

请写出下面各个字符串的正规表达式(regular expression)

a．十六进制的数字串； b．含有偶数个2的数字串； c．不以AA开头的大写字母串。
第二章 2010

（15分）已知正则表达式(a|b)*a(b|ε)


1. 利用Thompson构造法(Thompson’s construction)将该正规表达式(regular expression) 转化为NFA； 2. 将1中得到的NFA转化为DFA； 3. 将2中得到的DFA进行化简，以得到状态数最少 的DFA。



第四章 2008


高级语言编译程序常用的语法分析方法中， 递归下降分析法属于______分析方法。
A、自左至右 C、自底向上 B．自顶向下 D．自右向左

LL(1)分析方法是这样得名的：第一个“L”指 的是___，第二个“L”指的是___，括号中的 数字1指的是___。
第四章 2008
RE =>NFA Thompson’s construction NFA=>DFA 子集构造法 DFA的化简 DFA=>程序 三种方式+Lex
第二章 2010

下面的DFA中，（ ）可以合并。

A．状态1和状态2； B．状态2和状态3； C．状态1和状态3； D．以上都不对。
1
b
a
2
b b

分析器(parser)的主要功能是进行__________， 分析器的输入是________，输出是________。
第三章 2010


请写出下面文法对于表达式（（））（）进行 的最左推导过程，并画出其分析树或语法树。 A →（A）A | ε 试描述由下列文法所产生的语言。 S → aSS | a
编译原理总复习
第一章要点

编译器的概念。其输入和输出。 机器语言->汇编语言->高级语言。 乔姆斯基分层结构。



0型-无限制文法 1型-上下文相关文法 2型-上下文无关文法 3型-正则文法
第一章要点

相关程序和概念




解释器 编辑器 交互式开发环境（IDE） 调试程序 分析和综合 前端和后端 遍

(1) 通过消除左递归和提取左因子（回溯），给出与G[A]等价的文法G’[A]； (2) 计算文法G’[A]非终结符的FIRST集合和FOLLOW集合； (3) 判断文法G’[A]是否为LL(1)文法； (4) 如果文法G’[A]是LL(1)文法，构造G’[A]的分析表； (5) 给出输入串aade的分析过程。
A

把汇编语言程序翻译成机器可执行的目标程序的工作 是由______完成的。
A、编译器 C、汇编器
B、解释器 D、预处理器
第一章 2008





编译器的工作可分为多个阶段，词法分析、语法分析、语义分析 阶段的结果分别是（）。 A 分析树、语法树、语义树； B 分析树、语法树、注释树； C 记号序列、语法树、语义树； D 记号序列、分析树、注释树。 文法根据限定条件分为四种文法：0型文法、1型文法、2型文法、 3型文法。其中2型文法又有两种执行方式，即____和____。 什么是编译器？ 什么是遍。 什么是扫描器？扫描器的功能是什么？
第四章 要点

语法分析的分类：自顶向下，自底向上 自顶向下分析方法：递归下降，LL(1)分析 LL(1)


基本方法，三种动作（生成、匹配、接受） 判断文法是否是LL(1)文法

First集和Follow集 左递归和左因子的消除 构造分析表
第四章 2010

对于文法G[S]：
S→Q*S|Q|S Q → a | (S) | ε

A．记号序列； C．语法树；
B．分析树； D．注释树。

编译程序和解释程序有哪些区别？
第二章要点


扫描程序的功能及其输入输出。 正则表达式

什么是由r生成的语言，字母表，元符号 三种基本操作

有限自动机

定义 DFA NFA
第二章要点

※正则表达式=>NFA=>DFA=>程序

S为开始符号，请计算S和Q的FIRST集合和 FOLLOW集合。
第四章 2010

已知文法G[A]为