编译原理 样题
一 选择题
【 D 】1．____ 型文法也称为正规文法。
[A] 0 [B] 1 [C] 2 [D] 3
【 D 】2．____ 文法不是 LL(1) 的。
[A] 递归 [B] 右递归 [C] 2 型 [D] 含有公共左因子的
【 B 】3． 文法 E→E+E|E*E|i 的句子 i*i+i*i 的不同语法分析树的总数为 ______ 。
[A]1 [B]3 [C]5 [D]7
【 A 】4 ．四元式之间的联系是通过 实现。
[A] 临时变量 [B] 指示器 [C] 符号表 [D] 程序变量
【 C 】5．同心集合并可能会产生的新冲突为 。
[A] 二义 [B] 移进/ 移进 [C] 移进 / 归约 [D] 归约 / 归约
【 C 】6．代码优化时所依据的是 。
[A] 语法规则 [B] 词法规则 [C] 等价变换规则 [D] 语义规则
【 B 】7．表达式 a-(-b)*c 的逆波兰表示为 。
[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* （注：@为单目减运算符）
【 B 】8．过程的 DISPLAY 表记录了 。
[A] 过程的连接数据 [B] 过程的嵌套层次
[C] 过程的返回地址 [D] 过程的入口地址
二 填空题
1．编译过程的六个阶段为：词法分析、 语法分析 、语义分析、 中间代码生成
代码优化和目标代码生成。
2．词法分析阶段的任务式从左到右扫描 字符串形式的源程序 ，从而逐个识别 单
词 。
3．对于文法 G1 和 G2，若有 L(G1)=L(G2) ，则称文法 G1 和 G2 是等价的。
4．对于文法 G[E] ：E→T|E+T T→F|T*F F →P^ F|P P→(E)|i ，句型 T+T*F+i 的句柄是
T ，最左素短语是 T*F 。
5．最右推导的逆过程称为 最左规约 ，也称为 规范规约 。
6．规范规约中的可规约串是 句柄 ，算符优先分析中的可规约串是 最左素短
扫描器设计
姓 名: 库尔班江.阿瓦克日
学 号: 5011212524
学 院: 信息工程学院
专 业: 计算机科学与技术
班 级: 计算机17-1班
塔里木大学教务处制
2017届课程设计
实验一 词法扫描器设计
一 实验目的
通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。
二 实验内容
设计一个简单的类C语言的词法扫描器。
三 实验要求
（一） 程序设计要求
（1） 根据附录给定的文法，从输入的类C语言源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、分隔符五大类；文法见最后附录。
（2） 提供源程序输入界面；
（3） 词法分析后可查看符号表和TOKEN串表；
（4） 保存符号表和TOKEN串表（如：文本文件）；
（5） 遇到错误时可显示提示信息，然后跳过错误部分继续进行分析。
（二）实验报告撰写要求
（1） 系统功能（包括各个子功能模块的功能说明）；
（2） 开发平台（操作系统、设计语言）；
（3） 设计方案；
1） 主数据流图；
2） 主要子程序的流程框图（若有必要）；
3） 模块结构图；
4） 主要数据结构：符号表、TOKEN串表等。
（4） 具体设计过程（包括主控程序、各个功能模块的具体实现）。
四 实验总结
附录：类C语言的词法文法
id Letter
int10 Num int10 | Num
OP +| - |* |/ |>| < | = | ( | ) | ; | ‘ | == | >= |<= | !=
Keywordif | then | else | while | do
Lettera|b|c|d|e|f|g|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
设计任务为开发一个小型编译器，主要包括4个部件：词法分析器、语法分析器、语义分析器、目标代码生成器。
一、课程设计的目的与要求
1.通过设计、编写和调试词法分析程序，了解词法扫描器的组成结构、不同种类单词的识别方法，掌握由单词的词法规则出发，通过识别单词的状态转换图、利用程序实现词法扫描器的方法。
1.1扫描器设计
该扫描器是一个子程序，其输入是源程序字符串，每调用一次输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设程序设计语言中，基本字不能用作一般标识符，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。
2.通过设计、编写和调试语法分析程序，了解语法分析器的组成结构以及对文法的要求，掌握基于LL(1)文法或算符优先文法的语法分析程序的实现方法。
2.1语法分析器设计
以算法优先分析方法为例，设计一个算符优先语法分析程序。算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“#”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。当然，也可采用预测分析等方法设计语法分析器，具体方法自定。
3.通过设计、编写和调试语法制导翻译程序，掌握从语句的语法出发，构造相应的语义子程序，实现自定义语言的语法制导翻译。 3.1语法制导翻译程序设计
采用语法制导翻译方法，实现算术表达式、赋值语句和基本控制语句等的翻译。本语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“#”结尾），如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列。
4.目标代码生成器设计，将程序设计语言的中间代码程序翻译为目标代码程序，其输入是四元式序列，输出是一个汇编代码文件。
二、设计（实验）正文
1. 词法分析器设计
1.1 单词符号表
1.2 可实现的功能
1） 输入:字符串(待进行词法分析的源程序)；
输出:一个单词序列文件（即：token文件）和一个符号表文件，并输出错误信息。
第一章
编译程序基本任务：将源语言程序翻译成等价的目标语言程序。
编译过程
词法分析：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描 和分解，从而识别出一个个单词。
语法分析：在词法分析的基础上将单词序列分解成各类语法短语。
语义分析：审查源程序有无语义错误，为代码生成阶段收集类型信息。
中间代码生成：将源程序变成一种内部表示形式（中间代码）。
代码优化：对中间代码进行变换或进行改造，目的是使生成的目标代码更为高效。
目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或 汇编指令代码。
编译和解释程序的区别：
编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序在机器上运行得出结果，其中编译和运行是两个独立分开的阶段。
解释程序接受某个语言的程序并立即运行，不需要在运行前把源程序翻译成目标代码，也可以让我们实现在某台机器上运行程序并生成结果。
构造一个编译程序的三要素：源程序、目标程序、编译方法
第三章
静态语义是一系列限定规则，并确定哪些呵护语法的程序是合适的；
动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。
句型，句子
文法描述的语言是该文法一切句子的集合
等价文法：语言相同
文法类型
0型：A推出B
1型：B长度大于等于A（上下文有关）
2型：A为非终结符，（上下文无关）
3型：A推出bC（正规文法）
最左推导：最左非终结符替换
最右推导：规范推导，规范句型
二义文法：有两个不同的最左/最右推导
句型分析：
分析程序：完成句型分析的程序
自上而下：从开始符号出发，寻找匹配于输入符号串的推导
自下而上：从输入符号串开始，逐步进行归约，直至规约到文法的开始符号
短语，直接短语，句柄（最左直接短语）
不可到达：不在任何规则右部出现；不可终止：不能推出终结符号串。
第四章：
