一、选择题
1. 词法分析器的输入（）
A．单词符号B．源程序
C．语法单位D．目标程序
2.构造编译程序应该掌握( )。
A. 源程序
B.目标语言
C.目标代码生成
D.以上三者都要
3. 编译程序绝大多数时间花在（）。
A.出错处理
B.词法分析
C.目标代码生成
D.表格管理
4. 编译程序的各阶段都涉及到（）。
A.词法分析
B.表格管理
C. 语法分析
D. 语义分析
5. 解释程序和编译程序的区别是（）之间的转换。
A.是否生成中间代码
B.加工的对象不同
C. 使用的实现技术不同
D.是否生成目标代码
6. 一个上下文无关文法G包含四个组成部分，依次为：一组（G），一组（H），一个（E）和一组（C）。
A．字符串 B. 字母数字串 C.产生式 D.结束符号E.开始符号 F.文法 G.非终结符 H.终结符
7. 一个语言的文法是（）。
A．唯一的 B. 不唯一的 C.数量有限的
8. 编译程序中的语法分析器接受以（）为单位的输入，并产生有关信息供以后各阶段使用。
A.表达式
B.产生式
C.单词
D.语句
9. 文法的二义性和语法的二义性是两个（）的概念。
A.不同
B.相同
C.无法判断
10、如果L(M)=L(M'），则M与M'（）
A．等价B．M与M'都是二义的
C．M与M'都是无二义的D．他们的状态数相等
11、如果文法G是无二义的，则它的任何句子α（）
A．最左推导和最右推导对应的语法树必定相同
B．最左推导和最右推导对应的语法树可能不同
C．最左推导和最右推导必定相同
D．可能存在两个不同的最左推导，但它们对应的语法树相同
12、给定文法, A-> bA | cc, 下面哪些符号串可由其推导出（）。
{ = 1 \* GB3 |①cc b*cc b*cbcc bccbcc bbbcc
可选项有：
a. b. c. d. e.
13. 若一个文法是递归的，则它所产生语言的句子个数（）。
a.必定是无穷的
b.是有限个的
c.根据具体情况而定
14. Chmosky的3型语言是这样一种语言，其产生式限制为____。
a.A-> π
b. A->a A->aB
c.α->β
d. αAβ->απβ
15. 词法分析器的输出结果是（）。
A、单词自身值
B、单词在符号表中的位置
C、单词的种别编码
D、单词的种别编码和自身值
16、文法：G：S→xSx | y所识别的语言是（）。
A、xyx
B、（xyx）*
C、x+yx+
D、{x n yx n |（n≥0）}
二、判断题
设有文法G[I]:
I->I1/I0/Ia/Ic/a/b/c
判断下面符号串中哪些是该文法的句子.
(1) ab0
(2)a0c01
(3)aaa
(4)bc10
(5)aabc
(6)bbca
答：(1)错误
(2)正确
(3)正确
(4)正确
(5)错误
(6)错误
三、问答题
1. 什么是正规式，正规式的递归定义是什么？
答：正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。
下面是正规式和它所表示的正规集的递归定义。
设字母表为∑，辅助字母表为∑'={Ф，ε，|，·，*，(，)}
(1). ε和Ф都是∑上的正规式，它们所表示的正规集分别为{ε}和Ф
(2). 任意a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}
(3). 若e1，e2都是∑上的一个正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么e1|e2，e1·e2和，( e1)也都是正规式, 它们所表示的正规集分别为L(e1)∪L(e2), L(e1) ·L(e2)和，L(e1)
(4). 仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上正规集。
2. 何谓二义性文法？试举一例说明。
答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。
3. 什么是有穷自动机？什么是确定的有穷自动机？
答：有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。
确定的有穷自动机（DFA）
一个确定的有穷自动机（DFA）是一个五元组：M=（K，∑，f，S，Z），其中
(1) K是一个有穷集，它的每个元素称为一个状态；
(2) ∑是一个有穷字母表，它的每个元素称为一个输入字符，所以也称∑为输入符号字母表；
(3) f是转换函数，是在K×∑→K上映像，即，如f（，a）=（∈K，∈K），就意味着，当前状态为，输入字符为a时，将转换到下一状态，我们把称作的一个后继状态；
(4) S∈K是唯一的一个初态；
(5) ，是终态集，终态也称可接受状态或结束状态。
1. 对于文法G(E):
E→T|E+T
T→F|T*F
F→(E)|i
1. 写出句型(T*F+i)的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语、句柄。
答：
1.
E?T?F?(E) ?(E+T) ?(E+F)
?(E+i) ?(T+i) ?(T*F+i)
2.
短语：(T*F+i), T*F+i, T*F, i
直接短语：T*F, i
句柄：T*F
2. 设∑={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
答：
构造相应的正规式：(0|1)*1(0|1)
NFA:
3. 设为一非确定的有限自动机，其中定义如下：
试构造相应的确定有限自动机M'。
解答：
根据子集构造法可以得出以下表格：
根据该表可以得到以下的DFA
东南大学考试卷 考试科目微机系统与接口考试形式闭卷试卷类型 B卷 考试时间长度120分钟共 5 页得分 一、填空或选择填空（35分） 1. 8086/8088段寄存器的功能是_____________, 某一时刻程序最多可以指定访问________个存储段。 A1.用于计算有效地址B1. 用于存放段起始地址及计算物理地址 C1.分段兼容8080/8085指令D1. 方便分段执行各种数据传送操作 A2. 3 B2. 4 C2. 6D2. 64K E2.初始化时程序指定 2．8086/8088系统中复位信号RESET的作用是使_______ A. 处理器总线休眠 B.处理器总线清零 C. 处理器和协处理器工作同步 D. MPU恢复到机器的起始状态并重新启动 3. 在默认情况下, ADD [DI+100], DI指令中目标操作数存放在______寄存器指定的存储段中，指令执行时将完成______ 个总线操作周期。 A1. CS B1. DS C1. ES D1. SS A2. 0 B2. 1 C2. 2 D2. 3 4. 8086/8088CPU用指令ADD对两个8位二进制数进行加法运算后，结果为14H，且标志位CF＝1，OF＝1，SF=0，此结果对应的十进制无符号数应为_____ A. 20 B. –20 C. –236 D.276 5．堆栈是内存中的一个专用区域，其一般存取规则是_________ A.先入先出(FIFO) B.先入后出（FILO） C.按字节顺序访问 D.只能利用PUSH/POP指令读写 6. 在下列指令中，使堆栈指针变化8字节的指令是_____. A. PUSHA B. CALL 4000：0008H C. RET 8 D.SUB SP,8
东南大学一九九三年攻读硕士学位研究生入学考试试题 试题编号:553 试题名称:编译原理 一:(15分)判断下列命题的真假,并简述理由: 1.文法G的一个句子对应于多个推导,则G是二义的. 2.LL(1)分析必须对原有文法提取左因子和消除左递归. 3.算符优先分析法采用"移近-归约"技术,其归约过程是规范的. 4.文法S→aA;A→Ab;A→b是LR(0)文法(S为文法的开始符号). 5.一个BASIC解释程序和编译程序的不同在于,解释程序由语法制导翻译成目标代码并立即执行之,而编译程序需产生中间代码及优化. 二:(15分)设计一个最小状态有穷自动机,识别由下列子串组成的任意字符串. GO,GOTO,TOO,ON 例如:GOTOONGOTOOGOON是合法字符串. 三:(15分)构造一个LL(1)文法G,识别语言L: L={ω|ω为{0,1}上不包括两个相邻的1的非空串} 并证明你的结论. 四:(20分)设有一台单累加器计算机,并汇编语言含有通常的汇编指令LOAD,STORE,ADD和MUL. 1.写一个递归下降分析程序,将如下文法所定义的赋值语句翻译成汇编语言: A→i:=E E→E+E|E*E|(E)|i 2.利用加,乘法满足交换率这一性质,改进你的分析程序,以期产生比较高效的目标代码. 五:(15分)C为大家熟知的程序语言. 1.C的参数传递采用传值的方式,而且允许函数定义和调用时的参数个数不一致(如printf).请指出其函数调用语句: f(arg1,arg2,...,argn) 翻译成的中间代码序列,并简述其含义. 2.C语言中的变量具有不同的作用范围,试述C应采用的存储分配策略. 六:(20分)设有一个子程序的四元式序列为: (1) I:=1 (2) if I>20 GOTO (16) (3) T1:=2*J (4) T2:=20*I (5) T3:=T1+T2 (6) T4:=addr(A)-22 (7) T5:=2*I (8) T6:=T5*20 (9) T7:=2*J (10) T8:=T6+T7 (11) T9:=addr(A)-22 (12) T10:=T9[T8] (13) T4[T3]:=T10+J
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
东 南 大 学 考 试 卷（A 、B 卷） （答案附后） 课程名称 信号与线性系统 考试学期 03-04-3 得分 适用专业 四系，十一系 考试形式 闭卷 考试时间长度 120分钟 一、简单计算题（每题8分）： 1、 已知某连续信号()f t 的傅里叶变换为 21 ()23F j j ωωω= -+，按照取 样间隔1T =对其进行取样得到离散时间序列()f k ，序列()f k 的Z 变换。 2、 求序列{} 10()1,2,1 k f k ==和2()1cos ()2f k k k πε????=+ ???????的卷积和。 3、 已知某双边序列的Z 变换为 21 ()1092F z z z = ++，求该序列的时域表 达式()f k 。
4、 已知某连续系统的特征多项式为： 269111063)(234567+++++++=s s s s s s s s D 试判断该系统的稳定情况，并指出系统含有负实部、零实部和正实部的根各有几个？ 5、 已知某连续时间系统的系统函数为： 323 2642 ()21s s s H s s s s +++=+++。试给出该系统的状态方程。 6、 求出下面框图所示离散时间系统的系统函数。 ) (k
二、（12分）已知系统框图如图（a ），输入信号e(t)的时域波形如图（b ），子系统h(t)的冲激响应波形如图(c)所示，信号()f t 的频谱为 ()jn n F j e πω ω+∞ =-∞ = ∑ 。 图(a) y(t) ) (t f e(t)图(b) h(t)图(c) 试：1） 分别画出)(t f 的频谱图和时域波形； 2） 求输出响应y(t)并画出时域波形。 3） 子系统h(t)是否是物理可实现的？为什么？请叙述理由；
词法分析设计 1. 实验目的 通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。 2. 实验内容 用C++语言实现对C++语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。 3. 实验原理 本次实验采用NFA->DFA->DFA0的过程: 对待分析的简单的词法（关键词/id/num/运算符/空白符等）先分别建立自己的FA，然后将他们用产生式连接起来并设置一个唯一的开始符，终结符不合并。 待分析的简单的词法 （1）关键字： "asm","auto","bool","break","case","catch","char","class","
const","const_cast"等 （2）界符（查表） ";",",","(",")","[","]","{","}" （3）运算符 "*","/","%","+","-","<<","=",">>","&","^","|","++","--"," +=","-=","*=","/=","%=","&=","^=","|=" relop： （4）其他单词是标识符（ID）和整型常数（SUM），通过正规式定义。 id/keywords: digit: （5）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。
编译原理综合实验指导书 一、实验任务 设计、编制并调试一个中缀表达转换为后缀表达的实验程序，加深对词法分析、语法分析、语义分析及代码生成的理解。 二、实验内容 1、词法 输入：扩展ASCII码字符集字符。除大小写26英文字母（letter）和数字0-9（digit）以及+ - * / ^ = ; , ( )以外，所有其他字符一律按等同于空格处理，一般用来分隔单词。 输出：识别单词，单词包括关键字、运算符、界符、标识符和整型常数。 （1）关键字：var （2）运算符和界符：+ - * / ^ = ; , ( ) 其中：乘除运算符（*， /）返回具有不同属性值的单词mulop， 加减运算符（+， -）返回具有不同属性值的单词addop。 （3）标识符（id）和整型常数（num）： 标识符（id）和整型常数（num）最大长度为8个字符，定义如下。 id = letter (letter | digit)* num = digit digit* 2、语法 根据输入的单词序列，分析是否符合语法规则，如果不符合，应指明位置与理由；如果符合，则执行相应的语义子程序完成语义分析及中缀表达转换为后缀表达的过程。需注意的是，这里给出的是二义文法，从语义上考虑，表达式的计算按先幂次运算（^），再乘除运算（*， /）的最后加减运算（+， - ）的优先顺序；括号（(， )）用于调整运算先后顺序，既括号内部分先计算；赋值运算（=）最后进行。本实验系统的语法规则是： program → compound compound → declaration assignstatement compound | ε declaration → var identifier_list ; | ε dentifier_list →id, dentifier_list | id assignstatement →id= expression ; | ε expression → expression addop expression | expression mulop expression | expression ^ expression | ( expression ) | id | num 3、语义分析及代码生成 语义分析的主要任务是判断变量是否先定义后使用。代码生成的的主要任务是将赋值语句从中缀表达转换为后缀表达。
东南大学考试卷（ A 卷）课程名称通信原理考试学期04-05-3 得分 适用专业考试形式闭卷考试时间长度 150分钟 Section A(30%): True or False (Give your reason if False，2% for each question) 1. A typical mobile radio channel is a free propagation, linear, and time invariant channel. ( ) 2.The power spectral density of a stationary process is always nonnegative. ( ) 3.In a communication system, noise is unwanted and over which we have incomplete control. ( ) 4.If a random process is stationary, it is ergodic; if a Gaussian random process is stationary, then it is also strictly stationary. ( ) 5.Double Sideband-Suppressed Carrier (DSB-SC), Single Sideband (SSB), and Frequency Modulation (FM) are all linear modulation schemes. ( ) 6.Figure of merit (defined as (SNR)O/(SNR)C) of AM of DSB-SC is 1/3, and figure of merit of Amplitude Modulation (AM) is less than or equal to 1/3. ( ) 7. -law is a nonlinear compression law and A-law is a linear compression law. ( ) 8.The matched filter at the receiver maximizes the peak pulse signal-to-noise ratio, thus is optimal in a baseband data transmission system with Inter-Symbol Interference (ISI). ( ) 9.Correlative-level coding (also known as partial-response signaling) schemes are used to avoid ISI. ( ) 10.Time-Division Multiplexing (TDM) is used in Asymmetric Digital Subscriber Lines (ADSL) to separate voice signals and data transmission. ( ) 11.If coefficients of an equalizer is adjusted using the Least-Mean-Square (LMS) algorithm adaptively, then the matched filter in front of the equalizer is not necessary. ( ) 12.In an M-ary Phase-Shift Keying (M-PSK) system, if the average probability of symbol error is P e, then the average Bit Error Rate (BER) of the system is P e/log2M. ( ) 13.With the same Signal-to-Noise Ratio (SNR), 16-ary Quadrature Amplitude Modulation (16-QAM) has better performance than 16-ary Phase-Shift Keying (16-PSK). The reason is that 16-QAM has constant envelop. ( ) 14.With the same SNR, Minimum Shift Keying (MSK) has better performance than Sunde’s Frequency-Shift Keying (FSK). They are both Continuous-Phase Frequency-Shift Keying (CPFSK). ( ) 15.If the largest frequency component of an band-limited signal X(t) is at 100 Hz, then the corresponding Nyquist rate is 200 Hz. ( ) 共 5 页第1 页
编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在 语法分析过程中同时完成常量表达式的计算。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
东南大学考试卷(A卷) 课程名称 数 字 通 信 考试学期 04-05-2得分 适用专业无线电工程系 考试形式闭 卷 考试时间长度120分钟共 页 Section A：True or False （15%） 1. 1.When the period is exactly 2m, the PN sequence is called a maximal-length-sequence or simply m-sequence. 2. 2.For a period of the maximal-length sequence, the autocorrelation function is similar to that of a random binary wave. 3. 3.For slow-frequency hopping，symbol rate R s of MFSK signal is an integer multiple of the hop rate R h. That is, the carrier frequency will change or hop several times during the transmission of one symbol. 4. 4.Frequency diversity can be done by choosing a frequency spacing equal to or less than the coherence bandwidth of the channel. 5. 5.The mutual information of a channel therefore depends not only on the channel but also on the way in which the channel used. 6. 6.Shannon’s second theorem specifies the channel capacity C as a fundamental limit on the rate at which the transmission of reliable error-free messages can take place over a discrete memoryless channel and how to construct a good code. 7.7.The syndrome depends not only on the error pattern, but also on the transmitted code word. 8.8.Any pair of primitive polynomials of degree m whose corresponding shift registers generate m-sequences of period 2m-1 can be used to generate a Gold sequence. 9.9.Any source code satisfies the Kraft-McMillan inequality can be a prefix code. 10.10.Let a discrete memoryless source with an alphabet ? have entropy H? and produce symbols once every s T seconds. Let a discrete () memoryless channel have capacity and be used once every C c T
编译原理实验报告 班级 姓名： 学号： 自我评定：
实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。 输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。 输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。 四、实验设计 1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。 语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。 单词的分类：构造上述语言中的各类单词符号及其分类码表。 表I 语言中的各类单词符号及其分类码表 单词符号类别编码类别码的助记符单词值
《编译原理》课程设计题目 设计题一：正规式r与正规文法G相互转换的程序设计 任意给定一个正规式，求出其对应的正规文法；任意给定一个正规文法，求出其对应的正规式。（参考教材P53～55） 设计题二：布尔表达式的递归下降翻译器 针对布尔表达式的文法： 〈布尔表达式〉∷＝〈布尔项〉{〈与运算符〉〈布尔项〉} 〈与运算符〉∷＝and 〈布尔项〉∷＝〈布尔因子〉{〈或运算符〉〈布尔因子〉} 〈或运算符〉∷＝or 〈布尔因子〉∷＝〈非运算符〉〈布尔因子〉｜〈布尔量〉 〈非运算符〉∷＝not 〈布尔量〉∷＝（〈布尔表达式〉）｜〈标识符〉〈关系运算符〉〈标识符〉｜ true｜false 〈关系运算符〉∷＝＞｜＜｜≥｜≤｜＝｜≠ 〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉} 利用递归下降分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P92～93） 设计题三：正规式r与有穷自动机FA相互转换的程序设计 任意给定一个正规式，求出其对应的有穷自动机；任意给定一个有穷自动机，求出其对应的正规式。（参考教材P61～64） 设计题四：赋值语句的LR翻译程序 对教材P180中的赋值语句文法，给出该文法的属性文法，同时实现赋值语句的翻译，生成的中间代码为逆波兰式。（参考教材P179～181） 设计题五：正规文法G与有穷自动机FA相互转换的程序设计 任意给定一个正规文法，求出其对应的有穷自动机；任意给定一个有穷自
动机，求出其对应的正规文法。（参考教材P65～66） 设计题六：条件语句的LR翻译程序 对教材P187中的条件语句文法，给出该文法的属性文法，同时实现条件语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题七：NFA确定化为DFA及化简的程序设计 任意给定一个NFA，将其确定化为DFA，然后化简为最小的DFA。（参考教材P57～61） 设计题八：布尔表达式的LR翻译器 针对布尔表达式的文法： B →B and T | T T→T or F | F F→not F|true｜false |（B）| i rop i 利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P181～182） 设计题九：生成预测分析表的算法实现 任意给定一个LL(1)文法，生成相应的LL(1)分析表。（参考教材P75第5章） 设计题十：while循环语句的LR翻译程序 对教材P187中的循环语句文法，给出该文法的属性文法，同时实现循环语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题十一：利用LEX自动生成词法分析程序 输入描述某种语言词法规则的正规式，利用LEX自动生成词法分析程序。（参考教材P66～68） 设计题十二：生成LR分析表的算法实现 任意给定一个LR文法，生成相应的LR分析表。（参考教材P123第7章） 设计题十三：布尔表达式翻译为逆波兰式的算法实现 针对布尔表达式的二义性文法： B → B and B | B or B | not B | ( B ) | true｜false| i rop i 将文法拓广为G’[B’]： (0) B’ → B
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X
学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期
实验课程名称：编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 实验目的： 设计，编制并调试一个词法分析程序，加深对词法分析原理的理解。 实验要求： 在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写；上机时应随带有关的高级语言教材或参考书；要学会程序调试与纠错；每次实验后要交实验报告。 实验题目： 对于给定的源程序（如C语言或Pascal等），要求从组成源程序的字符行中寻找出单词，并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字，标志符等，并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述） 实验原理： 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候，使用了文件的输入和输出，以便于词法分析的通用型，同时在文件输出时，并保存在输出文件output文件中。 从左到右扫描程序，通过初始化：1为关键字；2为标志符； 3为常数；4为运算符或界符。 三、主要仪器设备及耗材 计算机
一、填空题（20分，每空1分） 1．双极型三极管是 控制器件，当其工作在放大区时发射结需要加 偏置，集电结需要加 偏置。场效应管是 控制器件。 2． 在有源滤波器中，运算放大器工作在 区；在滞回比较器中，运算放大器工 作在 区。 3． 在三极管多级放大电路中，已知A u1＝20，A u2＝－10，A u3＝1，则可知其接法分别为： A u1是 放大器，A u2是 放大器，A u3是 放大器。 4． 在双端输入、单端输出的差动放大电路中，发射极R e 公共电阻对 信号的 放大作用无影响，对 信号具有抑制作用。差动放大器的共模抑制比K CMR ＝ 。 5． 设某一阶有源滤波电路的电压放大倍数为 2001200 f j A += ，则此滤波器为 滤波器，其通带放大倍数为 ，截止频率为 。 6． 如图所示的功率放大电路处于 类工作状态；其静态损耗为 ；电路的 最大输出功率为 ；每个晶体管的管耗为最大输出功率的 倍。 二、基本题：（每题5分，共25分） 1．如图所示电路中D 为理想元件，已知u i = 5sin ωt V ，试对应u i 画出u o 的波形图。 2．测得电路中NPN 型硅管的各级电位如图所示。试分析管子的工作状态（截止、饱和、放 大）。 3． 已知BJT 管子两个电极的电流如图所示。求另一电极的电流，说明管子的类型（NPN 或PNP ）并在圆圈中画出管子。 4．如图所示电路中，反馈元件R 7构成级间负反馈，其组态为 ； 其作用是使输入电阻 、放大电路的通频带变 。 三、如图所示电路中，β＝100，Ω='100b b r ，试计算：(15分) 1．放大电路的静态工作点；（6分） 2．画出放大电路的微变等效电路；（3分） 3．求电压放大倍数A u 、输入电阻R i 和输出电阻R o ；（6分） 四、判断如图所示电路中引入了何种反馈，并在深度负反馈条件下计算闭环放大倍数。 （9分） 五、电路如图所示。试用相位条件判断下面的电路能否振荡，将不能振荡的电路加以改正。 （6分） 六、用理想运放组成的电压比较器如图所示。已知稳压管的正向导通压降U D =0.7V ，U Z = 5V 。 1．试求比较器的电压传输特性； 2．若u i =6sin ωt V ，U R 为方波如图所示，试画出u o 的波形。 （10分） 七、理想运放电路如图所示，设电位器动臂到地的电阻为KR W ，0≤K ≤1。试求该电路电压 增益的调节范围。 (10分) 八、一串联型稳压电路如图所示。已知误差放大器的A u >>1，稳压管的U z ＝6V ，负载R L ＝20Ω。 1．试标出误差放大器的同相、反相端； 2．说明电路由哪几部分组成？ 3．求U o 的调整范围； （10分） 参考答案 一、 1．电流、正向、反向；电压。 2．线性、非线性。
S o ut he a s t Uni v e r si ty E xa mi na ti o n P a per (i n-t e r m) Course Name Principles of Compiling Examination Term Score Related Major Computer & Software Examination Form Close test Test Duration120 Mins There are 5 problems in this paper. Y ou can write the answers in English or Chinese on the attached paper sheets. 1.Please construct context-free grammars with ε-free productions for the following languages (20%). (1){i|i∈N(Natural number), and i is a palindrome, and (i mod 5)=0} (2){ω| ω∈(a,b,c,d)* and the numbers of a’s ,b’s and c’s occurred in ω are even, and ωstarts with a or c , ends with d } 2.Please construct a DFA with minimum states for the following regular expression. (20%) (((a|b)*a)*(a|b))*(a|b) 3.Please eliminate the left recursions (if there are)and extract maximum common left factors (if there are) from the following context free grammar, and then decide the resulted grammar is whether a LL(1) grammar by constructing the related LL(1) parsing table.(20%) Please obey the rules of examination. If you violate the rules, your answer sheets will be invalid 共 2 页第 1 页
实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。 表Ｉ语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程
工程矩阵理论试卷 一、假如n n A C ?∈。 1、记} { ()n n V A X C AX XA ?===。证明：()V A 是n n C ?的子空间。 2、若A 是单位矩阵，求()V A 。 3、若2n =，0011A ?? = ?-?? 。求这里V （A ）的一组基及其维数。 4、假如} { 22 ()W A X C AX O ?===。问：对上一题中的()V A 和()W A ，()()V A W A +是否为直和？ 说明理由。 解： 1、证明子空间，即为证明该空间关于加法和数乘封闭。即若有,()x y V A ∈，()()x y V A +∈，()kx V A ∈。 设,()x y V A ∈，k F ∈， ()()A x y Ax Ay xA yA x y A +=+=+=+，()()x y V A +∈∴ ()()A kx kAx kxA kx A ===， ()kx V A ∈∴ ∴()V A 是n n C ?的子空间。 2、若A 是单位矩阵，则} { ()n n V A X C IX XI ?===，因为对单位阵I 来说，IX XI =恒成立，故， ()n n V A C ?=。 3、若2n =，0011A ??= ?-??，设a b X c d ?? = ??? ，有AX XA =，即， 00001111000a b a b c d c d b b a c b d d d b a c d b d d ???????? = ??? ???--???????? -????= ? ?---????=?? -=??-=-? ，→ 有0b a c d =??-=?，故0a X c a c ??= ?-??=0000a c c a ????+ ? ?-???? 故X 的一组基为00101101,???? ? ?-???? ，维数为2。