编译原理 样题
一 选择题
【 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
《编译原理》课程
实验报告（临时）
题目
专业
班级
学号
姓名
指导教师
华东理工大学软件与管理信息学院
2006年9月22日
一.实验题目
二.实验成员
组长名字写在第一个，每个同学完成的基本任务是什么。
三.实验内容
本学期的编译实验内容是使用编译构造工具实现一个扩充PL0语言的编译器。
扩充PL0语言是在PL0语言的基础上增加对整型一维数组的支持、扩充IF-THEN-ELSE条件语句、增加REPEAT语句、支持带参数的过程和增加注释，如下所示：
（1）整型一维数组，数组的定义格式为：
VAR (:)
其中上界和下界可以是整数或者常量标识名。
访问数组元素的时候，数组下标是整型的表达式，包括整数、常量或者变量和它们的组合。例如，假设a是常量，b是整型变量，c是数组，这些访问方式都应该可以使用：c(1)，c(a)，c(b)，c(b+c(1))。
（2）扩充条件语句，格式为：
::= IF THEN [ELSE ]
（3）增加REPEAT语句，格式为：
::= REPEAT UNTIL
(4) 支持带参数（传值参数）的过程，定义和调用形式如下:
::= PROCEDURE [‘(’{, }‘)’] ;
::= CALL [‘(’ {, }‘)’] (5) 注释
单行注释以 { 开始，以 } 结束，注释内容不包括 {和 }.
完整的扩充PL0语言的EBNF范式见实验提供的文档所示。下文所说的PL0语言，如果不加说明，就是特指扩充PL0语言。
本实验实现的PL0语言编译器，输入是PL0源语言程序，输出是一个栈式机的汇编语言(PCODE)程序，然后解释执行。如图1所示。
1. 编译过程概述：
编译过程划分为词法分析，语法分析，语义分析，中间代码生成，代码优化和目标代码生成；
1) 词法分析：是从左到右一个字符一个字符读入源程序，对构成源程序的字符流进行扫描和分析，从而识别出一个个单词；
2) 语法分析：是在词法分析的基础上将单词序列分解成各类语法短语；
3) 语义分析：审查源程序有无语义错误；为代码生成阶段收集信息；
4) 中间代码生成：将程序变成一种内部表示形式；
5) 代码优化：对中间代码进行变换或进行改造；
6) 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或汇编指令代码；
2. 编译过程是一个语言处理程序；它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序。
3. 一个程序设计语言的完整定义应包括语法和语义两个方面；
4. 符号串： 有字母表的符号组成的任何有穷序列；
5. 符号串的方幂：设X是符号串，把X自身连接N次得到的符号串Z。Z为X的方幂。
6. 符号串集合 ， 闭包 ，正闭包。
7. 若一个文法存在某个句子对应两棵不同的语法树；则说这个文法是二义的。
8. 语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子；目前语法分析常用的方法：：自顶向下分析；自底向上分析。
9. 预测分析方法是自顶向下分析：一个预测分析器由三个部分组成
1) 预测分析程序
2) 先进后出栈
3) 预测分析表
10. 确定的有穷自动机（DFA）与不确定的有穷自动机的异同点；
相同点：其中K都是一个有穷集，它的每个元素称为一个状态；
E都是一个有穷字母表；它的每个元素称为一个输入字符；
是一个终态集；
不同点：DFA：f是转换函数，是K*E→K上的映像；
NFA：f是一个从K*E→K的子集的映像；
其实DFA是NFA的特例，对于每个NFA M，存在一个DFA M’使得L(M)=L(M‘)。
