编译原理实验心得.doc

编译原理实验心得
第一章、引论
经过这一章节的学习我学到了如下知识：
1.自1954年FROTRANⅠ语言问世以来，计算机高级语言的到迅速发展。高级语言给编程带来了极大的方便，但是计算机只能直接执行用机器语言编写的程序，不能直接执行用高级语言编写的程序。要执行高级语言程序，必须提供该语言的翻译程序。翻译有编译和解释两种方式。编译方式是先将源程序翻译成目标程序，然后再执行目标程序，相应的翻译程序称为编译程序。解释方式是边翻译边执行，相应的翻译程序称为解释程序。
2、编译理论和技术主要研究和讨论编译程序的构造和设计原理。
3、编译程序一般包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格处理程序和出错处理程序等。
4、编译过程可采用分遍形式，及编译过程可由一遍或多遍完成。
5、对于具有自编译性的高级语言，可运行自展技术构造其编译程序，即将源程序分解成核心部分和扩充部分，对核心部分进行多次扩充之后得到源语言。
6、一个具有自编译性的高级语言在宿主机上的编译程序可以移植到目标机上。
7、LEX是一个有代表性的词法分析程序生成器。YACC是一种基于LALR（1）分析法的语法分析程序生成器。凡是有助于减少编写翻译程序工作的软件或工具包，统称为翻译程序的编写系统。
8、传统的串行编译程序只适应于SISD结构计算机，具有并行处理功能的并行编译程序则适于SISD和MISD结构计算机。
第二章、形式语言概论
1、形式语言由Chomsky于1956年提出，其理论的形成和发展推动了计算机考完学技术发展。形式语言理论是编译原理的重要理论基础。
2、文法是形式语言中十分重要的基本概念。文法可以定义为一个四元组，文法G=（VN，VT，P，S）。其中，VN是一个非终结符集，VT是一个终结符集，P是一个产生式集，S属于VN是文法的识别符。
3、Chomsky将文法分类为0型、1型、2型、3型文法。程序设计语言的语法规则属于3型文法（正规文法）。程序设计的语言和语义部分，一般属于1型文法（上下文有关文法），但实际上都是采用2型文法（上下文无关文法）来描述语法。
4、对于一个文法，我们需要研究它的句型、句子和语言。要识别一个符号串是不是一个文法的合法句子，需要对它进行语法分析。分析方法有两类，一列是自上而下分析法，另一类是自下而上分析法。
5、为了进行语法分析，需要事先将文法的产生式存储在计算机中，可以为文法建立一个产生式表，把文法的所有产生式都放在这个产生式表中。为了在分析过程中能迅速地查找到相应的产生式，还可以再建立一个目录表。
第三章、有穷自动机
1、自动机是一种能进行运算并能实行自我控制的装置。它是描述符号串处理的强有力地工具，是研究扫描器的理论基础。有穷自动机分为确定有穷自动机（DFA）和非确定有穷自动机（NFA）。
2、DFA=（Q，∑，t，q0，F），Q是状态集，∑是输入字母表，t：Q×∑→Q,q0属于Q是开始转台，F是终止状态集。
3、NFA DFA=（Q，∑，t，q0，F），t为Q×∑→Q的子集上的函数,Q0是开始状态集。
4、对于NFA可采用子集法和造表法进行确认化，将其转化为等价的DFA。对DFA化简的基本思想是将状态集分解成若干个互不相交的子集，使每个子集中的状态都是等价的，而不同子集的状态是可区分的。
5、正规文法与FA有着特殊的关系。从正规文法可直接构造其自动机；反之，由自动机也可以直接构造其正规文法。
6、正规表达式与FA也有着特殊的关系。对于字母表∑上的任意一个正规表达式e，一定可以构造一个NFA M，使L（M）=L（e）；反之，对于一个具有输入字母表∑的NFA M，在∑上也可以构造一个正规表达式e，使L（e）=L（M）。
7、正规语言可用正规文法描述，也可以用正规表达式描述。
8、DFA在计算机中有两种表示，一种是矩阵表示，另一种是表结构。
第四章、词法分析
1、词法分析是编译过程的第一阶段，是编译过程的基础。它负责对源程序扫描，从中识别出一个个的单词。
2、单词是程序设计语言的基本语法单位和最小的语义单位。单词一般分为五类，即关键字（又称为保留字或基本字）、标识符、常数、运算符和界限符。
3、源程序经词法分析程序识别的单词背表示成机内符，机内符包括单词类别和单词自身值两部分。
4、词法分析程序课利用状态转换图进行设计。状态转换图是一个有向图，每个节点表示一个状态，其中有一个初始状态，至少有一个终止状态。
5、词法分析程序还可以根据正规文法或正规表达式来进行设计、
第五章、自上而下语法分析
1、递归下降分析程序及其设计
例、设文法G[S]：
S→（A）|aAb
A→eA′|dSA′
A′→d A′|e
子程序P（S）：
READ(ch)
if ch=′(′then
begin
READ(ch);P(A);
if ch=′) ′then goto L
else error
end
else if ch≠′a′then error
else begin
READ(ch);P(A);
if ch=′b′then goto L
else error
end
L:READ(ch);
return
子程序P(A):
if ch=′e′then
begin
READ(ch);goto L
end
if ch≠′d′then error
P(S);
L:P(A′);
return
子程序P(A′):
L:if ch=′d′then
begin
read(ch);goto L
end
else if ch=′d′then goto L′
else if ch=′)′then goto L′
else error
L′:return
2、带回溯的自上而下分析算法
INIT:
p:=1;
k:=1;
j:=1;
s[k]:=(z,0,0,0);
goto TEST;
TEST:
if GOAL in VT then
if GOAL=INPUT[j] then
begin
j:=j+1;goto SUCC
end
else goto FALL;
i:=GOAL
goto LOOK;
LOOK:
if GRAMMAR[i]= ′|′then
if FATHER≠0 then goto SUCC
else STOP
if GRAMMAR[i]= ′$′ then
if FATHER≠0 then goto FALL
else STOP
k:=k+1;
s[k]:=(GRAMMAR[i],O,P,O,SON);
SON:=k;
p:=k;
goto TEST;
SUCC:
P:=FATHER;
i:=i+1;goto LOOK;
FALL:
P:FATHER;
SON:=S[SON].BRO;
K:=K-1;
goto ATRY;
ATRY:
if SON=0 then
begin
while GRAMMAR[i]≠′1 ′ do
i:=i+1;
i:=i+1;goto LOOK
end;
i:=i-1;
P:=SON;
if GOAL in VN then
goto ATRY;
j:=j-1;
goto FALL;
第六章、自下而上分析和优先分析方法
1、自下而上分析
自下而上分析法是一种“移进-归约”法。它用到一个符号栈S，待检查符号串的符号逐个被“移进”S栈，当栈顶符号串与某个产生式右部相匹配时，这个符号串被替换成（“归约”为）该产生式左部非终结符。
例子。设文法G[S]:
S→(T)|a|e
T→S|T,S
因为 S=>+(T,S),T=>+(a)
所以（a）是句型（（a）,S）相对于T的短语。再因为
S=>+((T),S),T=>T,S
所以T，S是句型（（（T），S），S）是相对于T的直接短语。
2、有关文法的一些关系尚未基本性质
2.1自反性
设R施定义在集合∑上的一个关系，如果对任何关系x属于∑，都有xRx
则称关系R是自反的。
2.2对称性
如果对任何x，y属于∑，xRy，都有yRx，则称关系R是对称的
2.3传递性
对任何x，y，z属于∑，如果能由xRy，都有yRx，则称关系R是对称的。
3、Warshall算法
Warshall算法是用于求关系传递闭包的一种算法。以下是描述这个算法的BASIC程序：
10 for i=1 to n
20 for j=1 to n
30 if M (j,i)=0 then 80
40 for k=1 to n
50 if M(i,k)=0 then 70
60 let M(j,k)=1
70 next k
80 next j
90 next i
100 end
4、简单优先分析方法
简单优先分析法是一种典型的自下而上分析方法。它对符号串进行语法分析的过程，实际是一个归约的过程。在这个归约过程中，它根据文法符号之间的简单优先关系来寻找符号串中课进行归约的字串，此子串称为句柄。
5、两种优先分析方法的比较
①两种方法都是自下而上语法分析法。它们对一个符号串进行分析的过程，实际上是对这个符号串进行归约的过程。在归约的每一步，它们都要寻找句型的一个可归约子串
②两种方法都引入优先关系，并创建了优先关系矩阵。优先关系以及优先关系矩阵是确定句型的课归约子串的根据
③由于算符优先方法只在终结符之间建立优先关系，在归约过程中，它不对单产生式进行归约，因而比简单优先分析法功效更高。
第七章、自下而上的KR（K）分析方法
1、拓广文法
E′→E
E→E+T|T
T→T*F|F
F→(E)|id
假定I={[E′→·E]},那么CLOSURE(I)则包含下面的项目：
E′→·E
E→·E+T
E→·T
T→·T*F
T→·F
F→·(E)
F→·id
计算CLOSURE的过程如下：
procedure CLOSURE(I);
begin
repeat
for
until
return I;
end;
2、LR（0）项目集规范族
procedure ITEM(G′);
begin
C:={CLOSURE({S′→·S})};
repeat
for C中每个项目集I和I中每个紧接“· ”后的不同文法符号X do
if goto（I，X）非空且不属于C then
将goto（I，X）加到C
until C不再增大；
end；
最终得到的C就是拓广文法G′的LR（0）项目集规范族。
3、列举
考虑文法G（S）：
S→A|B
A→aAb|c
B→aBb|d
其拓广文法G′(S)为
0 S′→S
1 S→A
2 S→B
3 A→aAb
4 A→c
5 B→aBb
6 B→d
文法G′(S′)的基本LR（0）项目集为
1 S′→·S
2 S′→S·
3 S→·A
4 S→A·
5 A→·aAb
6 A→a·Ab
7 A→aA·b
8 A→aAb·
9 A→·c
10 A→c·
11 S→·B
12 S→B·
13 B→·aBb
14 B→a·Bb
15 B→aB·b
16 B→aBb·
17 B→·d
18 B→d·
4、给定项目集I，X是一个文法符号，计算I的闭包CLOSURE(I)的算法是：
procedire CLOSURE(I)
begin I中的项目都属于CLOSURE（I）；
repeat
for
do if[]
until I 不再增大
return I ;
end;
第八章、语法制导翻译法
任何编译程序都可以看作这样一种翻译程序：它将用某种源程序语言写的程序（源程序）转换成等价的用某种目标语言写的程序（目标程序），其中的目标程序可以是某种中间语言程序，例如，汇编语言程序、四元式形式的程序，等等；而且，无论是源程序还是目标程序都看了一看做某种形式的符号串。
语法制导翻译额度基本思想是很简单的，就是先给文法中的每个产生式添加一个成分，这个成分长称为语义动作或翻译子程序，在执行语法分析的同时，执行相应产生式的语义动作。
所谓语法制导翻译，就是在语法分析的过程中，依从分析的过程，根据每个产生式添加的语义动作进行翻译的方法。
将下面的程序段用逆波兰表示法表示：
begin integer k;
k:=100;
h:if k>i+j then
begin k:=k-1;
goto h
end else k:=i*2-j*2;
i:=j:=0
end
该程序段的逆波兰表示是：
（1）Block
（2）k 100:=
（5）h:
（7）k i j+>(23) jumpf
（14）k k 1-:=jumpf(32) jumpf
（23）k i 2*j 2 * -:=
（32）i j 0 :=:=
（37）Blockend