哈工大软件学院编译原理考试大纲重点

第二章高级语言及其文法

（1）什么是推导？什么是归约？

推导：用某条规则的右部替换该规则的左部

归约：用某条规则的左部替换该规则的右部

（2）什么是句型？什么是句子？

句型:如果符号串α是从开始符号S推导出来的，即有S?*α，α∈(ＶT∪ＶN)* ，则称α是G产生的一个句型

句子:如果S ?* α，且α∈ＶT* ，则称α是G产生的一个句子

（3）什么是0~3型文法？各由什么机器识别？

Ｇ = (ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β∈ P

L(G)为2型/上下文无关语言（CFL）

Ｌ(G)为3型/正规集/正则集/正则语言（RL）

第三章词法分析

词法分析器的基本任务：识别单词（的种类）

单词的机内表示(种别码，属性值)

单词种类：关键字，标识符，常量，运算符算术，关系，界限

（1）正规式、NFA和DFA之间的等价变换

（2）各类单词的状态转换图

第四章语法分析

（1）什么是最左推导？什么是最右推导？

最左推导：每次推导都施加在句型的最左边的语法变量上。与最右归约对应

最右推导：（规范句型）每次推导都施加在句型的最右边的语法变量上。

（２）自顶向下分析的基本思想

基本思想：

寻找输入符号串的最左推导

试图根据当前输入单词判断使用哪个产生式

基本过程：从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树

（３）产生回溯的原因

文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探

（4）文法的改造：消除左递归、消除回溯

直接左递归的消除方法A→Aα|β＝A→βA′A′→αA′｜ε

消除间接左递归：为非终结符编号，再采用代入法将间接左递，归变为直接左递归

消除回溯：提取左因子

（5）求FIRST(α) 的算法，求FOLLOW( A ) 的算法

FIRST(α) 的算法:

若X→Y…∈P ，且Y∈ＶN 则FIRST(X)= FIRST(X)∪FIRST(Y)；

若X→Y1…Yn∈P，且Y1...Yi-1?*ε：FIRST(X)= FIRST(X)∪…∪FIRST(Yk) ；

FOLLOW( A ) 的算法:

1) 将# 加入到FOLLOW(S)

2) 若A→αBβ，则FOLLOW(B)=FOLLOW(B)∪FIRST(β)

3) 如果A→αB或A→αBβ，且β?*ε，A≠B，则FOLLOW(B)=FOLLOW(B)∪FOLLOW(A) Selct( i) 的算法:

（6）LL(1)文法的判定，LL(1)分析表的构造

LL(1)文法:同一非终结符的各个产生式的可选集互不相交

不存在终结符a，使得同一非终结符A的两个候选式αi和αj都能导出以a为首的串

同一非终结符的各个候选式中最多只有一个可以推导出空串

（7）LL(1)通用控制算法

LL(1)通用控制算法

repeat

X=当前栈顶符号;a=当前输入符号；

if X∈ＶT∪{#} then

if X=a then

if X≠# then {将X弹出,且前移输入指针}

else error

else

if M[X,a]=Y1Y2…Yk then{将X弹出;依次将Yk…Y2Y1压入栈；输出产生式X→Y1Y2…Yk } else error

until X=#

（8）预测分析法实现步骤

预测分析法实现步骤

1）构造文法

2）改造文法：消除二义性、消除左递归、提取左因子

3）求每个变量的FIRST集和变量的FOLLOW集，从而求得每个候选式的SELECT集

4）检查是不是LL(1) 文法

5）构造预测分析表

6）实现预测分析器

（9）递归下降法的基本思想

递归下降法算法基本思想

为每个非终结符编制一个递归下降过程，过程名表示产生式左部的非终结符，过程体则是按该产生式右部符号串顺序编写的

每匹配一个终结符，则再读入下一个符号；

对于产生式右部的每个非终结符，则调用相应的过程

当一个非终结符对应多个候选式时，过程体将按可选集来决定选用哪个候选式

（10）LR分析器的工作过程

LR分析器的工作过程

1. 初始化:s0 # a1a2…an# 对应“句型” a1a2…an

2. 一般情况下s0s1… sm#X1…Xm aiai+1…an#对应“句型” X1…Xmaia i+1…a n

①If action[sm,ai]= si then 格局变为：s0s1… sm i#X1…Xmai ai+1…an#

②If action[sm,ai]= ri表示用第i个产生式A→Xm-(k-1)…X m进行归约then 格局变为：

s0s1… sm-k#X1…Xm-kA aiai+1…an#查goto表，当goto[sm-k,A]=i then 格局变为：

s0s1… sm-k I#X1…Xm-kA aiai+1…an#

③If action[s m,a i]=acc then 分析成功

④If action[s m,a i]=err then 出现语法错

分析器的四种动作

1) 移进：将下一输入符号移入栈

2) 归约：用产生式左侧的非终结符替换栈顶的句柄

3) 接收：分析成功

4) 出错：出错处理

（11）LR分析器主控程序(LR分析算法)

LR分析器主控程序(LR分析算法)

置输入指针ip 指向w# 的第一个符号；令s是栈顶状态， a 是ip 所指向的符号;分析栈中为# 和开始状态0

重复执行如下过程

if action[s,a]=si(shift i) then

{把符号a 和状态i先后压入栈；使ip 指向下一符号}

elseif action[s,a]=ri(reduce A→β) then

{从栈顶弹出2*|β|个符号；令s′是现在的栈顶状态；把A 和goto[s′,A]先后压入栈中；输出产生式A→β}

elseif action[s,a]=accept(acc) then return

else error()；

（12）什么是句柄？句柄和产生式右部之间的关系

假设Ｓ?rm* αγβ（即αγβ是句型），如果A→γ∈P，且Ｓ?rm* αＡβ，则称γ是句型αγβ的相对于变量A的直接短语

最左直接短语叫做句柄(Handle)

规范句型的活前缀:不含句柄右侧任意符号的规范句型的前缀

（13）LR(0)文法的判定，LR(0)分析表的构造

LR(0)项目:右部某个位置标有圆点的产生式称为相应文法的LR(0)

文法G= (VN, VT, P, S)的拓广文法G?：G?=（VN∪{S?}，VT，P∪{S?→S}，S?）

LR(0)文法的判定:

如果I 中至少含两个归约项目，则称I 有归约—归约冲突（Reduce/Reduce Conflict）

如果I 中既含归约项目，又含移进项目，则称I有移进—归约冲突（Shift/Reduce Conflict）

如果I 既没有归约—归约冲突，又没有移进—归约冲突，则称I 是相容的(Consistent)，否则称I 是不相容的

对文法G，如果?I∈C都是相容的，则称G为LR(0)文法

LR(0)分析表的构造算法

设G?的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应

的分析器状态(即相应的DFA状态)

1 0为开始状态

2 对Ii∈C：

if A→α.aβ∈Ii and go(Ii,a)=Ij then action[i,a]=sj

if A→α.Bβ∈Ii and go(Ii,B)=Ij then goto[i,B]=j

if A→α.∈Ii then for ?a∈VT∪{#} do action[i,a]=rj

if S'→S.∈Ii then action[i,#]=acc;

3 所有空格置error

（14）SLR(1)文法的判定，SLR(1)分析表的构造

SLR(1)文法的判定:SLR(1)分析表无冲突的CFG

SLR(1)分析表的构造算法

设G?的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应的

分析器状态(即相应的DFA状态)

1 0为开始状态

2 对Ii∈C：

if A→α.aβ∈Ii and go(Ii,a)=Ij then action[i,a]=sj

if A→α.Bβ∈Ii and go(Ii,B)=Ij then goto[i,B]=j

if A→α.∈Ii then for ?a∈FOLLOW(A)do action[i,a]=rj ;

if S'→S.∈Ii then action[i,#]=acc;

3 所有空格置error

（15）LR(1)文法的判定，LR(1)分析表的构造

LR(1)分析表的构造算法

设G?的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应

的分析器状态(即相应的DFA状态)

1 0为开始状态

2 对Ii∈C：

if [ A→α.aβ，b ]∈Ii and go(Ii,a)=Ij then action[i,a]=sj

if [ A→α.Bβ，b ]∈Ii and go(Ii,B)=Ij then goto[i,B]=j

if [ A→α. ，a ]∈Ii then action[i,a]=rj ;

if [ S'→S. ，# ]∈Ii then action[i,#]=acc;

3 所有空格置error

（16）语法分析的错误处理

预测分析中的错误恢复

错误恢复策略的基本思想

跳过一些输入符号，直到期望的同步记号中的一种出现为止

其效果依赖于同步记号集合的选择，这个集合的选择应该使得语法分析器能够迅速地从实际可能发生的错误中恢复过来

LR(0)不考虑后继符，SLR(1)仅在归约时考虑FOLLOW集

LR(1)在构造状态时就考虑后继符的作用：考虑对于产生式A→α的归约，在不同使用位置，A会要求不同的后继符号

第五章语法制导翻译

（1）什么是语法制导定义SDD？什么是语法制导翻译方案SDT？SDD与SDT之间是什么关系？

语法制导定义（SDD）:把一些语义属性附加到代表语言成分的文法符号上，通过与产生式相

关的语义规则来描述属性的值

语法制导翻译方案（SDT）:在产生式体中嵌入了程序片段（称为语义动作）的CFG

语法制导翻译方案（SDT）是语法制导定义（SDD）的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛｝括起来，可被插入到产生式右部的任何合适的位置上。

SDD：

是关于语言翻译的高层次规格说明

它隐蔽了许多具体实现细节

使用户不必显式地说明翻译发生的顺序

SDT：

指明了语义规则的计算顺序

以便说明某些实现细节

是对SDD的一种补充

（2）什么是属性文法？

属性文法：一个没有副作用的SDD有时也称为属性文法

属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

（3）什么是综合属性？什么是继承属性？

综合属性:节点N上的综合属性只能通过N的子节点或N本身的属性值来定义

继承属性：节点N上的继承属性只能通过N的父节点、N的兄弟节点和N本身的属性值来定义；终结符可以具有综合属性，但是不能有继承属性

（3）什么是S-属性定义？什么是L-属性定义？

S-属性定义：仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义

L-属性定义：一个语法制导定义SDD是L-属性定义，如果?A→X1X2…X n∈P，其每一个语义规则中的每一个属性要么是一个综合属性，要么是X j(1≤j ≤n)的一个继承属性，这个继承属性仅依赖于下列属性1.产生式中X j的左边符号X1，X2，…X j-1的属性；2.A的继承属性。

每一个S-属性定义都是L-属性定义

（5）L-属性定义的自顶向下翻译（在LL(1)语法分析过程中进行翻译、在递归下降语法分析过程中进行翻译）

L(1)语法分析过程中进行翻译：

程中完成翻译过程，其中的语法分析栈需要进行扩展，以存放语义动作和属性求值所需要的一些数据项（一般来说，这些数据项是属性值的复制）

除了那些代表终结符和非终结符的记录之外，语法分析栈中还将保存动作记录（action record）和综合记录（synthesizerecord）

在递归下降语法分析过程中进行翻译：

1.为A的每一个继承属性都设置一个形参，函数的返回值是A的综合属性值

2.对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量

3.对于每个动作，将其代码抄进翻译器中，并把对属性的引用改为对变量的引用

第六章运行存储分配

（1）什么是栈式存储分配策略？

栈式分配策略是一种以过程为单位的动态分配方案

当一个过程（函数或方法）被调用时，用于存放该过程的局部变量的空间被压入栈；

当这个过程结束时，该空间被弹出这个栈

使用过程、函数或方法作为用户自定义动作的单元的语言，其编译器的运行时刻存储大多都采用栈式分配策略

这种安排允许活跃时段不交叠的多个过程共享存储空间

（2）什么是活动？什么是活动记录？活动记录主要由哪些内容构成，各字段的作用？

活动：过程体的每次执行称为该过程的一个活动

活动记录：过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录

活动记录主要由内容构成：

实参

返回值

控制链：指向调用者的活动记录

访问链：用来访问存于其它活动记录中的非局部数据

保存的机器状态

局部数据

临时数据

（3）符号表管理

符号表的内容

变量：类型、地址、长度、形参标识、数组的内情向量

过程：类型、入口地址、外部过程、声明处理、形实结合信息

常数：类型、地址、值

第七章中间代码生成

（1）声明语句翻译的任务是什么？

声明语句:用于对程序中规定范围内使用的各类变量、常数、过程进行说明编译要完成的工作:在符号表中记录被说明对象的属性，为执行做准备

（2）数组引用翻译的任务是什么？

数组引用翻译的任务:1.完成上下界检查 2.生成完成相对地址的计算代码

（3）各类语句的代码结构

（4）各类语句的翻译

第八章代码优化

（1）什么是代码优化、代码优化的分类

代码优化：编译时刻为改进目标程序的质量而进行的各项工作（空间效率，时间效率）在代码中消除不必要的指令，或者把一个指令序列替换为一个完成同样功能的

较快的指令序列

优化的分类

按优化语言级：1。针对中间代码、2。针对机器语言

按优化范围：

局部优化：单个基本块范围内的优化

局部公共子表达式删除

计算强度削弱

全局优化：

全局公共子表达式删除

无用代码删除

基于循环的优化

循环不变表达式外提

归纳变量删除

计算强度削弱

（2）什么是基本块、如何划分基本块

基本块是满足下列条件的最大的连续三地址指令序列

控制流只能从基本块的第一个指令进入该块

除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机

基本块的划分

首先确定所有的入口语句

序列的第一个语句是入口语句

能由条件转移语句或无条件转移语句转到的语句是入口语句

紧跟在条件转移语句或无条件转移语句后面的语句是入口语句

每个入口语句到下一个入口语句之前的语句序列构成一个基本块

（4）什么是流图、如何构造流图？

流图是一种表示中间代码的方法。图中的结点表示基本块，流图的边指明了哪些基本块可能紧随一个基本块之后运行 --前驱（predecessor）、后继（successor）

流图的构造

以所有的基本块为节点集合

有B1到B2的边(B2是B1的后继)当且仅当：

B2是紧紧跟随在B1后面的四元式，且B1的最后四元式不是无条件转向语句

B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式

（5）什么是公共子表达式？

公共子表达式：如果表达式E先前已被计算过，并且从先前的计算到现在，E中变量的值没有改变，那么E的这次出现就称为公共子表达式

（6）什么是复制传播？

复制传播变换的思想是在复制语句f := g之后尽可能用g代替f

复制传播变换本身并不是优化，但它给其它优化带来机会：删除死代码常量合并

（7）什么是死代码？

死代码是指计算结果以后不被引用的语句

（8）什么是归纳变量？

归纳变量：在循环中，如果变量i的值随着循环的每次重复都固定地增加或者减少某个常量，则称i为循环的归纳变量

（9）什么是强度削弱？

强度削弱:用较快的操作代替较慢的操作，如用加代替乘

（10）基本块DAG图构造算法、基于DAG的基本块优化--无环有向图

基本块的DAG表示

叶节点表示一个出现在基本块中的变量的初值或常数，叶节点用标识符（变量名）或常数作为标记

内部节点n表示块中的一个语句s。内部节点n由语句s中用到的运算符来标记

n的子节点是那些在s之前最后一次对s中用到的操作数进行定值的语句所对应的节点

每个内部节点n有一个定值变量表，表示s是在此基本块内最晚对这些变量定值的语句

基本块DAG图构造算法

输入：一个基本块

输出：相应DAG图

算法说明：

通过逐个扫描四元式来逐步建立DAG图

函数node(x)表示最后给标识符x定值的节点

假设三地址语句为如下三种形式之一

(i)型：x:= y op z

(ii)型：x:= op y

(iii)型：x:= y

依次对基本块中的每个语句x:=y op z执行如下步骤。

如果node(y)没有定义，建立叶子节点，标记为y，让node(y) 等于这个节点。如果node(z)没有定义，为z建立叶子节点。

①如果语句为(i)型，查看是否存在标记为op的节点，且其左右子节点分别为node(y)和node(z)。如果找不到，建立这样的节点。无论是哪种情况，令n是所找到或建立的节点

②如果语句为(ii)型，寻找标记为op且子节点为node(y)的节点，如果找不到，建立这样的节点,并令n是这个找到的或创建的节点

③如果语句为(iii)型，则令n为node(y)

如果node(x)没有定义，则将node(x)设置为n,并把x加入到n的定值变量表中；

如果node(x)有定义，从node(x)的定值变量表中删除变量x，并把x加入到n的定值变量表中，并将node(x)设置为n

处理(i)型四元式的时候，如果op是满足交换率的运算符，可以允许其左右节点互换（11）在构造基本块的dag时，对于数组、指针、和过程调用需要有哪些特殊的处理？数组:对于形如a[j]=y的三地址指令，创建一个运算符为“[]=“的结点，这个结点的3个子结

点分别表示a、j和y。

该节点没有定值变量表。

该结点的创建将杀死所有已经建立的、其值依赖于a的结点

一个被杀死的结点不可能再获得任何定值变量，也就是说，它不可能成为一个公共子表达式

指针: *p=y进行一些全局指针分析，以便把p可能指向的变量限制在一个较小的范围内杀死这些变量对应的节点，不需杀死其它节点

过程调用:在缺乏全局数据流信息的情况下，必须假设一个过程调用使用和改变了它所访问

的所有数据.因此，如果变量x在过程p的访问范围之内，对p的调用将杀死x对应

的节点

（12）变量获得值的方式都有哪些？

变量获得值的方式:通过输入语句通过赋值语句通过过程形式参数

（13）什么是到达定值？

到达-定值:如果存在一条从紧随在定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被“杀死”（即在此路径上没有对变量x的的其它定值），则称定值d到达程

序点p。这表明，在p点使用变量x的时候，x的值可能是由d点赋予的。

到达定值分析的主要用途

代码外提中的循环不变量检测

判定x在p点上的值是否为常量

判定x在p点上是否未经定值就被引用

（14）什么是引用-定值链？如何构造引用-定值链？

引用-定值链（ud）：设变量x有一个引用u，变量x的所有能够到达u的一切定值称为x在u处的引用-定值链，简称ud链。（是一个集合）

如果B中变量x的引用u之前有x的定值d，且这个定值能够到达u，则u的ud链是{d}

否则，u的ud链就是IN[B]中x的定值集合

（15）什么是活跃变量？

对于变量x和流图上的某个点p，如果在流图中沿着从p开始的某条路径可以引用x在p点的值，则称变量x在点p是活跃变量，否则称x在点p不活跃。

主要用途：寄存器分配删除无用赋值

（16）什么是定值-引用链？如何构造定值-引用链？

定值-引用链：设变量x有一个定值d，该定值所有能够到达的引用u称为x在d处的定值-引用链，简称du链

主要用途复制传播

构造定值-引用链：

如果在求解活跃变量数据流方程中的OUT[B]时，将OUT[B]表示成从B的末尾处能够到达的引用的集合，那么，可以直接利用这些信息计算基本块B中每个变量x在其定值处的du链

如果B中x的定值d之后有x的第一个定值d?，则d和d?之间x的所有引用构成d的du链

如果B中x的定值d之后没有x的新的定值，则B中d之后x的所有引用以及OUT[B]中x的所有引用构成d的du链

（17）什么是可用表达式？

可用表达式的定义：如果从流图的首节点到达点p的每条路径上面都有对x op y的计算，并且从最后一个这样的计算到点p之间没有再次对x或y进行定值，那么表

达式x opy在点p是可用的(available)。

表达式可用的直观意义：在点p上，x op y已经在之前被计算过，不需要重新计算。

可用表达式信息的主要用途：消除全局公共子表达式

（17）到达-定值数据流方程、活跃变量数据流方程、可用表达式数据流方程

（18）什么是支配节点？

支配节点：如果从流图的初始节点到节点n的每条路径都经过节点d，则称节点d支配节点n，记为d dom n。任何节点都是自己的支配节点

（19）什么是回边？

回边：假定流图中存在两个节点d和n满足d dom n。如果存在从节点n到d的有向边n->d，那么这条边称为回边

（20）什么是自然循环？如何识别自然循环？

自然循环：满足以下性质的循环

有唯一的入口节点，称为首节点（header）

首结点支配循环中的所有结点

循环中至少有一条返回首结点的路径

自然循环是一种适合于优化的循环

自然循环的识别：根据回边识别自然循环

在流图中，给定一个回边n->d，与这个回边对应的自然循环为：d，以及所有可以不经过d 而到达n的节点。d为该循环的首节点。

（21）如何消除复制语句？

对于复制语句d: x=y，如果d的引用点u满足下列条件，那么可以在u点用对y的引用代替对x的引用

u的ud链只包含d（即d到达u的唯一的x的定值）

从d到达u的路径（可以穿过u若干次，但是不可以第二次穿过d）上，没有对y的定值。

如果x的所有引用都满足上述替换条件，那么可以删除复制语句x:=y

有效复制语句数据流方程

OUT[ENTRY]= φ

IN[B]= ∩P是B的一个前驱OUT[p] B≠ENTRY

OUT[B]= c_genB ∪(IN[B]- c_killB) B≠ENTRY

c_genB在基本块B中的所有复制语句x=y，并且从该语句开始到B的出口，x和y都没有再定值。c_killB:包含了所有在流图中出现并且满足下列条件的复制语句x=y：B中存在对x或者y的定值，并且之后在没有复制语句x=y出现。

（22）如何识别循环不变计算？

循环不变计算检测算法

输入：循环L，已经建立的ud链

输出：循环不变计算语句

方法

步骤1：将下面这样的语句标记为“不变”：语句的运算分量或者是常数，或者其所有定值点都在循环外部。

步骤2：重复执行下面的步骤，直到某次没有新的语句可标记为“不变”为止：

将下面这样的语句标记为“不变”：先前没有被标记过，且运算分量要么是常数，要么其ud 链中的定值点在循环外，或者该定值点已经被标记为“不变” 。

（23）循环不变计算外提的条件有哪些？

将循环不变语句s: x=y+z外提的条件

(1)s所在的基本块是循环所有出口节点（有后继节点在循环外的节点）的支配节点

(2)循环中没有其他语句对x赋值

(3)循环中x的引用仅由s到达

不考的内容

3.3.1扫描器的数据流图

3.3.2模块结构图

3.3.4状态转换图的程序实现

3.4 词法分析错误类型不考，但错误恢复策略需掌握

4.6 算符优先分析法

编译原理概念_名词解释

编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。 解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执 行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归) 第1个L：从左到右扫描输入串第2个L：生成的是最左推导 1：向右看1个输入符号便可决定选择哪个产生式 某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G：上下文无关文法。 V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。 F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。 (1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。 (2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。 在计算时：综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。 语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。 语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 中间代码（中间语言） 1、是复杂性介于源程序语言和机器语言的一种表示形式。 2、一般，快速编译程序直接生成目标代码。 3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。 (2)便于移植，便于修改，便于进行与机器无关的优化。 中间代码的几种形式：逆波兰记号，三元式和树形表示，四元式 符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。 符号表的功能：（1）收集符号属性(2) 上下文语义的合法性检查的依据：检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据

哈工大计算机考研考纲834软件工程基础

2016年硕士研究生入学考试大纲 考试科目名称：软件工程考试科目代码：[834] 本考试科目考试时间180分钟，满分150分。包括：C语言程序设计课程(占75分)和软件工程课程(占75分)。 C语言程序设计部分（75分） 一、考试要求 1. 要求考生全面系统地掌握C语言程序设计的基本方法，常用算法的流程 图描述方法。 2. 针对具体的实际应用问题，能够用流程图描述算法，并灵活运用C程序 设计语言编写程序。 二、考试内容 1）算法的描述方法 a:算法的基本概念 b:算法的流程图表示方法 2)基本控制结构 a:数据的键盘输入和屏幕输出 b: 顺序、分支和循环三种基本控制结构 c: 循环的三种控制方法（计数控制的循环，条件控制的循环，标记控制的循环），嵌套循环 d: 流程的转移控制 3)函数 a:函数的定义、调用和参数传递 b: 函数原型 c: 基本类型的变量做函数参数向函数传递变量的值 d: 从函数返回一个值 e: 函数的递归调用，递归函数 4)数组

a:一维数组和二维数组的定义、初始化和引用 b: 一维数组、二维数组做函数参数向函数传递一维数组和二维数组 c:字符数组或字符指针做函数参数向函数传递字符串 d: 常用的字符串处理操作（字符串的输入、输出、复制、连接、比较、计算长度、插入字符、删除字符等） e: 常用的排序算法（选择排序、交换排序、冒泡排序）和查找算法（顺序查找、折半查找） 5)指针 a:指针变量的定义、初始化和解引用 b:指针变量做函数参数 c: 指针数组 d: 函数指针 6) 结构体和共用体 a:结构体变量、结构体数组和结构体指针的定义和初始化 b: 结构体变量、结构体数组或结构体指针做函数参数向函数传递结构体c: 结构体成员和嵌套的结构体成员的访问 d: 共用体类型 e: 结构体和共用体占内存的字节数 7)文件操作 a:文件的打开和关闭 b:二进制文件和文本文件 c:文件的顺序读写 三、试卷题型结构 a: 单项选择题（8分） b: 写出程序运行结果题（8分） c: 程序填空题（8分） d: 画出算法的流程图（8分）

四川大学编译原理期末复习总结

一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么 答：

编译原理课程设计---C语言编译器的实现

扬州大学编译原理课程设计 学号：091202122 姓名： 专业：计算机科学与技术 课程：编译原理 指导教师：陈宏建

目录 一．程序简介与分析---------------------------------------------------------3 二．程序适用范围-----------------------------------------------------------3 三．词法分析---------------------------------------------------------------3 四．语法分析---------------------------------------------------------------4 五．语义分析和中间代码生成------------------------------------------------10 六．代码生成--------------------------------------------------------------12 七．流程图----------------------------------------------------------------13 八．实现------------------------------------------------------------------14 九．程序运行结果----------------------------------------------------------14 十．总结------------------------------------------------------------------18 十一.附录（源程序）--------------------------------------------------------18

2019年哈工大计算机基础考生大纲

2019年硕士研究生入学考试大纲 考试科目名称：计算机基础考试科目代码：[854] 本考试科目考试时间180分钟，满分150分。包括数据结构与计算机组成原理两部分，每部分各75分。 数据结构部分（75分） 一、考试要求 1. 要求考生全面系统地掌握数据结构与算法的基本概念、数据的逻辑结构和 存储结构及操作算法，并能灵活运用；能够利用数据结构和算法的基本知识，为应用问题设计有效的数据结构和算法；能够分析算法的复杂性。 2. 要求能够用C/C++/Java等程序设计语言描述数据结构和算法。 注：考试内容范围主要以参考书目1为标准，带*号部分不在考试范围之内。 二、考试内容 1）数据结构与算法的概念 a:数据结构与算法及其相关的基本概念 b: 算法及其复杂性分析 2)线性表 a:线性结构及其操作算法 b: 线性表的应用及算法 3)树与二叉树 a:二叉树的定义、性质、表示、遍历算法 b: 树的表示、操作算法 c: 森林与二叉树关系 d: 树与二叉树的应用及算法 4)图及其相关算法 a:图的相关概念 b: 图的存储结构与搜索算法 c: 图的应用及算法 5)查找与排序

a:查找与排序的相关概念 b:典型算法的描述及复杂性分析 c: 查找与排序算法的应用 6)外部排序与文件 a:外部排序的相关概念及其基本方法 b:文件的组织方式、特点及应用 三、试卷结构 1)题型结构 a:填空题(0—15分) b:选择题(0—30分) c:简答题(0—30分) d:算法设计题(0—30分) 注：题型分数在以上范围内浮动，总分为75分 2)注意事项 算法设计题，必须包含算法的基本思想、存储结构设计和算法的描述四、参考书目 1．廖明宏，郭福顺，张岩，李秀坤，数据结构与算法（第4版），高等教育出版社，2007.11 2．严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2002.09 计算机组成原理部分（75分） 一、考试要求 要求考生全面掌握计算机组成的基本原理、概念和方法，系统深入地理解计算机系统中总线、存储器、运算器、控制器、I/O系统等的组织结构和工作原理，掌握计算机硬件系统的基本分析与逻辑设计方法，理解计算机硬件系统各组成部分之间的关系，建立计算机系统的整体概念。 二、考试内容 1）计算机系统的基本概念

2017年哈工大计算机科学与技术专业854考研真题

2016年哈工大计算机科学与技术专业854考研真题 I．数据结构 一、选择题 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 Int x = n * n; While (x >= 1) { X = x / 2; } A.O(log2n) B.O(n) C.O(nlog2n) D.O(n1/2) 2.需要分配一个较大的存储空间并且插入和删除操作不需要移动，元素满足以上特点的线 性表存储结构是（）。 A.单向链表 B.静态链表 C.线性链表 D.顺序表 3.已知字符串S为”ababcabcacbab”，模式串T为”abcac”。若采用KMP算法进行模式匹配， 则需要（）遍（趟匹配），就能确定T是S的子串。 A. 3 B. 4 C. 5 D. 6 4.已知某棵二叉树的前序序列是1,2,3,4，则不可能为该二叉树的中序序列的是（）。 A.1,2,3,4 B.2,3,4,1 C.1,4,3,2 D.3,1,4,2 5.将森林F转换为对应的二叉树T，F中任何一个没有右兄弟的结点，在T中（）。 A.没有左子树 B.没有右子树 C.没有左子树和右子树 D.以上都不对 6.一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）个零元素。 A. e B.2e C.n2-2e D.n2-e 7.在一棵高度为2和7阶B树中，所含关键字的个数最少是（）。 A. 5 B.7 C.8 D.14

8.设待排序的元素个数为n，则基于比较的排序最坏情况下的时间复杂度的下界为（）。 A.log2n B.n C.nlog2n D.n2 9.下面关于B树和B+树的叙述中，不正确的是（）。 A.B树和B+树都能有效地支持随机检索 B.B树和B+树都能有效地支持顺序检索 C.B树和B+树都是平衡的多路树 D.B树和B+树都可以用于文件的索引结构 10.若待排序关键字序列在排序前已按其关键字递增顺序排列，则采用（）方法比较次数最 少。 A.插入排序 B.快速排序 C.堆排序 D.选择排序 二、填空题 11.在一棵n个结点的二叉树中，所有结点的空子树个数为11 。 12.若二叉树的一个叶结点是其某子树的中序遍历序列中的第一个结点，则它必是该子树的 后序遍历序列中的第12 个结点。 13.在有n个选手参加的单循环赛中，总共将进行13 场比赛。 14.在有4033个叶子结点的完全二叉树中，叶子结点的个数为14 个。 15.一个有向图G1的反向图是将G1的所有有向边取反而得到的有向图G2，若G1和G2 的邻接矩阵分别为A，B，则A与B的关系为15 。 16.N个顶点e条边的无环路有向图，若采用邻接表作为存储结构，则拓扑排序算法的时间 复杂度为16 。 17.在10阶B树中根结点所包含的关键字最多有17 个，最少有18 个。 18.在具有12个结点的平衡二叉树（A VL树）中，查找A VL树中的一个关键字最多需要 （18）次比较。 19.对初态有序的表，最少时间的排序算法是（19）。 三、简答题 20.在n个数据中找出前K个最大元素，可以采用堆排序或败者树来实现。分别说明上述两 种实现方法的基础步骤，并分析每种方法的时间复杂度和空间复杂度。 21.假设举办一个1000人参加的学术会议，作为会议报道组的负责人，你会收到会务组为 每名参会者开具的包含其英文名字的注册费发票，同时还会收到为每位参会者提供的印有其英文名字的参会胸牌和其他会议资料。请回答以下问题： （1）如何有效地把每个参会者注册费发票和参会胸牌等其他会议资料放在一起形成一份参会资料？ （2）如何在会议报道日更有效地把每份资料发放给参会者？ 要求：说明你所使用的主要技术和相关步骤。 四、算法设计题 按以下要求设计算法： （1）描述算法设计的基本思想； （2）根据设计思想，采用C或C++或Java语言描述算法；

编译原理及实现课后习题答案(1)

2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪…. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2∪…. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5 已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6 已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T} 2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F Array i i T T*F 简单短语：i T*F T 句柄：T

哈尔滨工业大学2018年机电工程学院《人机工程学及工业设计方法》考试大纲

哈尔滨工业大学2018年机电工程学院《人机工程学及工业设计方法》 考试大纲 一、考试要求 人机工程学要求学生全面系统地掌握下列主要内容：人机工程学的基本概念，起源与发展；人因学部分介绍人的构造尺寸与功能尺寸的测量与特点，人的心理特性与特点；典型常规作业环境的分析与设计原则；人的疲劳的分类，疲劳的测量与预防；安全的基本概念，安全分析的基本原理与方法，安全的预防与产品的安全设计；典型人机装置的设计包括显示控制装置设计，工作岗位与工作场所设计，工具的把手设计等；人机工程学的总体设计方法与设计应用实例；人机工程学的先进研究与技术介绍等。工业设计方法要求学生全面系统地掌握下列主要内容：包括设计的概念、设计思维、功能论、系统论、人性化和商品化的设计观念，以及设计调查、设计方法、设计评价、设计管理等。 二、考试内容 I、人机工程学部分(75分) 1、人机工程学的起源与发展 主要介绍人机工程学的命名、定义、起源、发展与应用，以及人机工程研究内容与方法。 1）人机工程学的基本概念，搞清楚本课程学习的目的、内容和方法； 2）人机工程学的研究内容和方法； 3）人机工程学的涉及的关键技术领域和发展趋势； 4）如何应用人机工程学技术。 2、人体基本数据测量与分析 介绍人的功能模型、人的结构特征；人体测量数据、人体测量数据的应用。 1）人体测量的基本概念、基本方法。人体测量使用仪器。人体模型介绍。人体构造尺寸与动态尺寸数据的设计应用。 2）人体测量百分位的选择。人体测量数据的设计应用。 3）如何在设计中应用人体测量数据。 3、人体感知能力分析 学习了解人的各种感知觉特性，了解人的反应与动作特性，了解人的生理特点与生理极限，为设计服务。 1）人体感知觉特点及生理极限。 2）人体各种感觉机能与特征。 3）人体的反射及反射弧。 4）人体的动作特点及基本规律。 5）感知觉的特征 6）视知觉的机能与特征 7）听觉与其它感觉的机能与特征 8）设计中利用感知觉的机能 9）如何在设计中利用各种知觉的特征。 4、人的心理及工效研究 人的心理学特点是人机工程学重要内容，了解心理学研究的基本方法，了解人的情绪特点人的激励机制。 1）工程心理学的研究内容与方法。 2）动机与激励的特征与影响因素。

编译原理结课论文

目录

1.绪论 概述 “编译原理”是一门研究设计和构造编译程序原理课程，是计算机各专业的一门重要的专业课。编译原理这门课程蕴含着计算机学科中解决问题的思路和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性很强的课程，要掌握这门课程中的思想，就必须要把所学到的知识应用于实践当中。而课程设计是将理论与实践相互联系的一种重要方式。 设计目的 课程设计是对学生的一种全面综合素质训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂很多，但也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构解决问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的能力。 设计题目及要求 基于这个学期所学习的内容以及自己所掌握到的知识，本次我所要设计的题目是赋值语句的四元式生成。

要求： （1）设计语法制导生成赋值语句的四元式的算法； （2）编写代码并上机调试运行通过； （3）输入一赋值语句； （4）输出相应的表达式的四元式； 2.背景知识 语法制导翻译方法 语法制导翻译的方法就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析的过程中，当一个产生式获得匹配（对于自顶向下分析）或用于规约（对于自底向上分析）时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。语法制导翻译分为自底向上语法制导翻译和自顶向下语法制导翻译。 属性文法 属性文法是编译技术中用来说明程序语言语义的工具，也是当前实际应用中比较流行的一种语义描述方法。属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。属性文法是一种

计算机组成原理第二章习题哈工大

计算机组成原理第二章习题 1.以真空管为主要器件的是______。 A. 第一代计算机 B. 第二代计算机 C. 第三代计算机 D. 第四代计算机 2.所谓第二代计算机是以______为主要器件。 A. 超大规模集成电路 B. 集成电路 C. 晶体管 D. 电子管 3.第三代计算机是以______为主要器件。 A. 超大规模集成电路 B. 集成电路 C. 晶体管 D. 电子管 4.ENIAC用的主要元件的是______。 A. 集成电路 B. 晶体管 C. 电子管 D. 以上都不对 5.目前被广泛使用的计算机是______。 A. 数字计算机 B. 模拟计算机 C. 数字模拟混合式计算机 D. 特殊用途的计算机 6.个人计算机（PC）属于______类计算机。 A. 大型机 B. 小型机 C. 微型机 D. 超级计算机 7.通常计算机的更新换代以______为依据。 A. 电子器件 B. 电子管 C. 半导体 D. 延迟线

8.目前大多数集成电路生产中，所采用的基本材料为______。 A. 单晶硅 B. 非晶硅 C. 锑化钼 D. 硫化镉 9.计算机科技文献中，英文缩写CAD代表______。 A. 计算机辅助制造 B. 计算机辅助教学 C. 计算机辅助设计 D. 计算机辅助管理 10.邮局把信件进行自动分拣，使用的计算机技术是______。 A. 机器翻译 B. 自然语言理解 C. 机器证明 D. 模式识别 11.微型计算机的发展通常以______为技术标志。 A. 操作系统 B. 磁盘 C. 软件 D. 微处理器 12.目前我们所说的个人台式商用机属于______。 A.巨型机 B.中型机 C.小型机 D.微型机 13. 电子邮件是指______。 A. 用计算机管理邮政信件 B. 通过计算机网络收发消息 C. 用计算机管理电话系统 D. 用计算机处理收发报业务

哈工大计算机组成大作业完整版

哈工大计算机组成大作业 哈工大计算机组成原理自主实验 计算机组成原理自主实验报告 第四章‐实验1 一个2114 存储芯片的实现 要求：外特性与2114 芯片一致（P77，图4.12），可以设计成为64*64 个存储单元的堆。 A0-A9：地址线 I/O：数据输入输出线 CS：片选信号 R/W：读写信号 VHDL代码： library IEEE;

use IEEE.STD_LOGIC_1164.ALL; USE IEEE.STD_LOGIC_UNSIGNED.ALL; entity shiyan41 is PORT(clk, we, cs,reset: in STD_LOGIC; data: inout STD_LOGIC_VECTOR(3 downto 0); adr: in STD_LOGIC_VECTOR(9 downto 0)); end shiyan41; architecture Behavioral of shiyan41 is typemem is array (63 downto 0) of STD_LOGIC_VECTOR(63 downto 0); signal data_in: STD_LOGIC_VECTOR(3 downto 0); signaldata_out: STD_LOGIC_VECTOR(3 downto 0); signalsram : mem; signalcs_s : std_logic; signalwe_s : std_logic; signaladdr_in_row: std_logic_vector(5 downto 0);

(完整版)编译原理及实现课后习题答案

编译原理及实现课后习题解答 2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

S S S * S S + a a a 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc 描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T}

编译原理学习心得

编译原理学习心得 编译原理学习心得1 编译程序在计算机科学与技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。而“编译原理”这门课程一直以来是国内外大学计算机相关专业的重要课程。因为它的知识结构贯穿程序设计语言、系统环境以及体系结构，能以相对的视角体现从软件到硬件以及软硬件协同的整机概念。其理论基础又涉及形式语言与自动机、数据结构与算法等计算机学科的许多重要方面，为联系计算机科学理论和计算机系统的典范。 虽然编译原理这门课程在大多数的人里认为枯燥无味，学起来就像看天书一样。然而学习这门课程还是有一定的好处的。比如可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的，可以更加客观的比较不同语言的差异，并且学习新的语言的效率也会更加高，语言转换也会更加游刃有余。 不学“编译原理”这门课程的话，自己的编程思想会很浅显。而且编程也只仅仅停留在编程上，无法深入理解其中的原理。 学习编译原理的话，从文法、正规式、NFA与DFA的定义，下手，要用心动脑去体会 编译原理学习心得2

从联系最紧密的操作系统来说吧，你写多线程/多进程的程序就得和操作系统的知识打交道。写多线程得加锁吧，临界区、死锁的四个条件之类的标准的操作系统的内容吧(不得不吐槽一下，某国内一线电商干了三年的程序猿，写多线程居然不知道加锁，也是醉了)。进程间通信的几种方式什么管道、socket、共享内存等，这也是操作系统的内容吧。文件系统，这也是经常要打交道的东西。还有内存什么的，你做Android 开发，这些里边有很多东西都在系统层面被封装好了，但是你要是不知道原理，一旦出了错根本无从调试，况且你该不会打算写一辈子写Android 就是填逻辑吧。 然后，是编译原理，普通的程序猿是接触不到编译器或者虚拟机的开发的。但是这并不意味着编译原理就用不到。说个最常见的读取配置文件，只要你的配置文件有自定义的语法，你就要用编译原理的东西。还有类似于自动生成代码啦、正则表达式啦这些都算是编译原理的内容。你既然是写Java 的不了解虚拟机怎么可以，最基本的字节码总是需要能看懂的吧，分析一些疑难杂症的时候字节码还是很有用的。 最后，是计算机原理，如果只是做应用开发的话计算机原理其实不必要掌握的多深入，但是一些基本的概念还是要清楚的。比如寄存器、缓存、中断什么的，关键的时候可以帮助你调试。在一些对性能要求非常高的场合，也是很有作用的。此外，学了

编译原理发展史

编译原理历史与发展 姓名：费张烨学号：09923206 指导老师：朱文华 基于形式语言理论中的有关概念来讨论编译实现问题。即 编译原理=形式语言理论+编译技术 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。 编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序（source language）编写的程序作为输入，而产生用目标语言（target language ）编写的等价程序。通常地，源程序为高级语言（high-level language ），如C或C + + ，而目标语言则是目标机器的目标代码（object code，有时也称作机器代码（machine code ）），也就是写在计算机机器指令中的用于运行的代码。这一过程可以表示为： 源程序→编译器→目标程序 编译技术的历史 在20世纪40年代，由于冯·诺伊曼在存储-程序计算机方面的先锋作用，编写一串代码或程序已成必要，这样计算机就可以执行所需的计算。开始时，这些程序都是用机器语言（machine language ）编写的。机器语言就是表示机器实

际操作的数字代码，例如：C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 （16进制）的指令。

[872]结构力学哈工大考纲

s2020年硕士研究生入学考试大纲 考试科目名称：结构力学考试科目代码：872 一、考试要求 要求考生全面系统地掌握结构力学的基本概念、基本理论和基本方法。并且能综合运用结构力学的理论、方法分析解决具体的问题。 二、考试内容 1）杆系结构组成分析 ●自由度、计算自由度 ●静定结构组成规则，杆件体系几何组成分析 2）静定结构受力分析 ●静定梁、刚架、组合结构、三铰拱和桁架结构的内力计算 ●静定结构的一般性质 3）静定结构的位移计算 ●变形体虚功原理 ●单位荷载法，图乘法，互等定理 ●荷载作用、温度作用、支座移动、制造误差所引起的结构位移计算 4）超静定结构受力分析 ●超静定次数的确定 ●力法解超静定结构（梁、刚架、组合结构、桁架）由荷载作用、温度 作用、支座移动、制造误差所引起的内力 ●位移法基本未知量和基本结构的确定 ●位移法解超静定结构（梁、刚架）由荷载作用、支座移动所引起的内 力 ●力矩分配法解超静定结构

●超静定结构的位移计算 ●超静定结构内力计算结果的校核 5）移动荷载作用下的结构分析 ●静力法作静定结构内力及支座反力影响线 ●机动法作静定结构内力及支座反力影响线 ●最不利荷载位置的确定 三、试卷结构 考试时间: 180分钟；试卷满分：150分 1）题型结构 ●客观题（填充题和单项选择题）（60分） ●分析计算题（90分） 2）内容结构 ●杆系结构组成分析（10-20分） ●静定结构受力分析（40-50分） ●结构位移计算（15-25分） ●超静定结构受力分析（50-60分） ●移动荷载作用下的结构分析（15-25分） 四、参考书目 1、结构力学教程（Ⅰ）龙驭球、包世华主编高等教育出版社2003年5月第一版 2、结构力学（Ⅰ）王焕定、章梓茂、景瑞编著高等教育出版社2010第3版

807控制理论考纲 哈工大

2015-2016年硕士研究生入学考试大纲考试科目名称：控制理论考试科目代码：[807] 一、考试要求： 闭卷、笔试。 二、考试内容： 1．自动控制的一般概念 （1）基本概念 （2）基本控制方式 （3）反馈控制系统的组成 （4）控制系统的分类 （5）对控制系统的基本要求 2．控制系统的数学模型 （1）微分方程 （2）传递函数 （3）结构图 （4）信号流图 （5）梅森增益公式 （6）控制系统的传递函数 3．线性系统的时域分析法 （1）稳定性 （2）稳态误差计算 （3）系统动态性能指标计算 4．线性系统的根轨迹法 （1）绘制根轨迹的基本条件 （2）绘制根轨迹的基本法则 （3）根轨迹与系统性能的关系 5．线性系统的频域分析法 （1）频率特性

（2）频率特性的几何表示 （3）频率特性的绘制 （4）稳定判据与稳定裕度 （5）频域性能指标与时域动态性能指标的关系6．线性系统的校正方法 （1）校正方式 （2）常用校正装置及特性 （3）串联校正装置的设计步骤 （4）控制系统的性能指标 7．线性系统的状态空间分析与综合 （1）线性系统的状态空间描述 （2）线性系统的可控性与可观性 （3）线性定常系统的线性变换 8．线性定常系统的综合 （1）线性反馈控制系统的基本结构及其特点（2）极点配置问题 （3）状态观测器 （4）利用状态观测器实现状态反馈的系统9．最优控制 （1）最优控制的一般概念 （2）最优控制的前提条件 （3）线性二次型最优控制问题 三、试卷结构： （1）考试时间：180分钟，满分：150分。（2）题型结构 a）简答题：30分 b）分析题：70分 c）计算题：50分

哈工大计算机组成原理试卷1及答案

哈工大学年秋季学期 计算机组成原理试题

一、填空（12分） 1.某浮点数基值为2，阶符1位，阶码3位，数符1位，尾数7位， 阶码和尾数均用补码表示，尾数采用规格化形式，用十进制数写 出它所能表示的最大正数，非0最小正 数，最大负数，最 小负数。 2.变址寻址和基址寻址的区别是：在基址寻址中，基址寄存器提 供，指令提供；而在变址寻址中，变址 寄存器提供，指令提供。 3.影响流水线性能的因素主要反映在和 两个方面。 4.设机器数字长为16位（含1位符号位）。若1次移位需10ns，一 次加法需10ns，则补码除法需时间，补码BOOTH 算法最多需要时间。 5.CPU从主存取出一条指令并执行该指令的时间 叫，它通常包含若干个，而 后者又包含若干个。组成 多级时序系统。 二、名词解释(8分) 1.微程序控制 2.存储器带宽 3.RISC 4.中断隐指令及功能

三、简答（18分） 1. 完整的总线传输周期包括哪几个阶段？简要叙述每个阶段的工作。 2. 设主存容量为1MB，Cache容量为16KB，每字块有16个字，每字32位。 (1)若Cache采用直接相联映像，求出主存地址字段中各段的位数。 (2)若Cache采用四路组相联映像，求出主存地址字段中各段的位数。 3. 某机有五个中断源，按中断响应的优先顺序由高到低为L0,L1,L2,L3,L4，现要求优先顺序改为L3,L2,L4,L0,L1，写出各中断源的屏蔽字。

4. 某机主存容量为4M ×16位，且存储字长等于指令字长，若该机的指令系统具备120种操作。操作码位数固定，且具有直接、间接、立即、相对四种寻址方式。 （1）画出一地址指令格式并指出各字段的作用； （2）该指令直接寻址的最大范围； （3）一次间址的寻址范围； （4）相对寻址的寻址范围。 四、（6分） 设阶码取3位，尾数取6位（均不包括符号位），按浮点补码运算规则 计算 [25169?] + [24)16 11(-?] 五、画出DMA 方式接口电路的基本组成框图，并说明其工作过程（以输入设备为例）。（8分）

编译原理第二版课后习答案

《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源

编译原理概念总结

第一章 引论 ? 为什么要用编译器 ? 与编译器相关的程序 ? 翻译步骤 ? 编译器中的主要数据结构 1、语言处理器 1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。 2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。 3、使用编译器是为了提高编程的速度和准确度。 4、与编译器相关的程序：解释程序（interpreter ）、汇编程序（assembler ）、连接程序（linker ）、装入程序（loader ）、预处理器（preprocessor ）、编辑器（editor ）、调试程序（debugger ）、描述器（profiler ）、项目管理程序（project manager ）。 5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。 6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在 一起的任务有时会由一个被称为预处理器（preprocessor ）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。 7、连接器（linker ）能够解决外部内存地址的问题。 8、加载器（loader ）把所有的可执行目标文件放到内存中执行。 2、一个编译器的结构 Output Source Program Front end Back end Object

1、将编译器看成黑盒，则源程序映射为在语义上等价的目标程序，而这个映射由两部分组成：分析部分和综合部分。 2、分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。 3、综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。 4、编译器的第一个步骤：词法分析（lexical）或扫描（scanning）。词法分析器读入组成源程序的字符流，并且将它们组成有意义的词素（lexeme）的序列。词法分析器产生词法单元（token）。 5、分隔词素的空格会被词法分析器忽略掉。 6、编译器的第二个步骤：语法分析（syntax）或解析（parsing）。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。 7、语义分析（static semantic analysis）：语义分析器使用语法树和符号表中的信息 来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查（type checking）。编译器检查每个运算符是否具有匹配的运算分量。 8、总的说，编译器的翻译步骤是：扫描程序----语法分析程序----语义分析程序---- 源代码优化程序----代码生成器----目标代码优化程序。 3、编译器结构中的主要数据结构 1、记号（token） 2、语法树（syntax tree） 3、符号表（symbol table） 4、常数表（literal table） 5、中间代码（intermediate code） 6、临时文件（temporary file） 4、将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（ back end））的操作两部分。 第二章词法分析 ? 扫描处理 ? 正则表达式 ? 有穷自动机 ? 从正则表达式到D FA ? 利用L e x自动生成扫描程序 1、Tokens记号标记：identifiers、keywords、integers、floating-point、symbols、strings、comments 1、使用正则表达式去描述程序语言tokens 2、一个正则表达式是归纳确定 3、一个正则表达式R描述一组字符串集合L(R) 4、L(R) = the language defined by R 5、所有的token都能用正则表达式表示 2、正则表达式： 1、基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配