编译原理报告(3) 本文关键词：编译，原理，报告
编译原理报告(3) 本文简介：课程实验报告课程名称：《编译原理》专业：信息安全院系：计算机科学与技术班级：学号：姓名：指导老师：目录实验一词法分析11.1实验目的11.2实验要求11.3词法分析程序的算法思想21.4词法分析程序的具体设计41.5词法实验结果及结果分析7实验二语法分析82.1实验目的82.2实验要求82.3语法分
编译原理报告(3) 本文内容：
课
程
实
验
报
告
课程名称：
《编译原理》
专
业：
信息安全
院
系：
计算机科学与技术
班
级：
学
号：
姓
名：
指导老师：
目录
实验一
词法分析1
1.1实验目的1
1.2实验要求1
1.3词法分析程序的算法思想2
1.4
词法分析程序的具体设计4
1.5词法实验结果及结果分析7
实验二
语法分析8
2.1
实验目的8
2.2
实验要求8
2.3
语法分析程序的算法思想8
2.4
语法分析程序的具体设计11
2.5语法分析程序的结果和结果分析14
总结与感悟16
实验一
词法分析
1.1
实验目的
设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。
1.2
实验要求
1.2.1、待分析的简单的词法
（1）关键字：
begin
if
then
while
do
end
所有的关键字都是小写。
（2）运算符和界符:
：=
+
-
/
>
>=
=
;
(
)
#
（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：
ID
=
letter
(letter
|
digit)*
NUM
=
digit
digit*
（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。
1.2.2、
各种单词符号对应的种别码如表1所示：
表1
各种单词符号对应的种别码
单词符号
种别码
单词符号
种别码
begin
1
：
17
If
2
：=
18
Then
3
21
do
5
23
lettet（letter|digit）*
10
>=
24
dight
dight*
11
=
25
+
13
；
26
—
14
(
27
15
)
28
/
16
#
0
1.2.3、
词法分析程序的功能
输入：所给文法的源程序字符串。
输出：二元组（syn,token或sum）构成的序列。
其中：syn为单词种别码；
token为存放的单词自身字符串；
sum为整型常数。
例如：对源程序begin
x:=9:
if
x>9
then
x:=2*x+1/3;
end
#的源文件，经过词法分析后输出如下序列：
(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)……
1.3
词法分析程序的算法思想
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
1.3.1
主程序示意图：
主程序示意图如图1.1所示。其中初始包括以下两个方面：
开始
置初值
调用扫描子程序
输出单词二元组
输入串结束?
否
结束
是
图1.1
词法分析主程序示意图
⑴
关键字表的初值。
关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：
Charrwtab[6]
=
{“begin”,“if”,“then”,“while”,“do”,“end”,};
（2）程序中需要用到的主要变量为syn,token和sum。
首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序scaner主要部分流程如图1.2所示。
开始
变量初始化
忽略空格
是否文件结束?
否
返回
是
拼数
拼字符串
字母
Syn=11
关键字?
Syn=10
否
是
Syn为对应关键字的种别码
对不同符给出相应的syn值
报错
其他符号
运算符界符等符号
返回
数字
图1.2
词法分析程序流程
1.4
词法分析程序的具体设计
1.4.1
数据结构
单词二元组的结构
typedef
struct
{
int
typenum;//用于存储该字符串的种别码；
charword;
//用于存储字符串；
}
在本次实验中，每一个特定的字符串，相应的输出为其单词种别码和该字符串，所以我按书中的要求设计一个特定的结构保存这两个值，便于程序的编写。
源程序字符缓冲区：input[255]
单词缓冲区：token[255]
源程序字符指针：p_input
单词缓冲区指针：p_token
关键字数组：*rwtab[]={“begin“,“if“,“then“,“while“,“do“,“end“,_KEY_WORD_END}
1.4.2
scaner函数的设计
1）对数字串和标识符的扫描：
设计思想：首先判断第一个输入的字符是否是数字或者是字母，读入下一个字符，判断是否是数字或是字母，如果是连接，并接着读下一个字符，否则回退一个字符，得到的数字串或者标识符，如果是标识符，还需要再进行一次判断，该标识符是否为关节字，最终返回相应的WORD结构。具体的代码实现如下所示：
if(letter())
{
while(letter()||digit())
{
concat();
m_getch();
}
retract();
myword->typenum=reserve();
myword->word=token;
return
myword;
}
else
if(digit())
{
while(digit())
{
concat();
m_getch();
}
retract();
myword->typenum
=11;
myword->word
=token;
return
myword;
}
2）对=，+，-，*等只有一个字符组成的符号进行扫描：
读入一个字符，判断其是否等于相应的符号，如果是返回该字符对应的WORD结构，否则对将该字符与下一个符号比对，直到匹配成功或返回错误为止，具体的代码实现如下所示：
case
=
:
m_getch();
if(ch==
=
)
{
myword->typenum
=29;
myword->word
=“==“;
return
myword;
}
retract();
myword->typenum
=25;
myword->word
=“=“;
return
myword;
break;
case
+
:myword->typenum
=13;
myword->word
=“+“;
return
myword;
break;
case
-
:myword->typenum
=14;
myword->word
=“-“;
return
myword;
break;
……
……
3）对>=
、:=等有两个字符组成的符号的扫描：
以>=为例，首先读入一个字符，判读其是否等于‘>’号，如果相等，再读入一个字符，判断其时候等于‘=’号，如果相等返回‘>=’号对应的WORD结构，否则返回‘>’号对应的word结构，并回退一个字符。如果都不相等，该字符与下一个符号比对，直到匹配成功或返回错误为。具体的代码如下所示。
case
:
:
if(input[p_input]==
=
)
{
myword->typenum
=18;
myword->word
=“:=“;
return
myword;
}
case
>
:
m_getch();
if(ch==
=
)
{
myword->typenum
=24;
myword->word
=“>=“;
return
myword;
}
retract();
myword->typenum
=23;
myword->word
=“>“;
return
myword;
break;
1.5
词法实验结果及结果分析
按课本上的测试数据输入，得到的结果如图1.3所示：
图
1
.3测试结果
分析结果可知，所有的字符扫描得到的结果都符合要求。
实验二
语法分析
2.1
实验目的
编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。
2.2
实验要求
利用C语言编制递归下降分析程序，并对简单语言进行语法分析。
2.2.1、
待分析的简单语言的语法
用扩充的BNF表示如下：
⑴：：=beginend
⑵：：={；}
⑶：：=
⑷：：=ID：=
⑸：：={+
|
-}
⑹：：={*
|
/
⑺：：=ID
|
NUM
|
（）
2.2.2、
实验要求说明
输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。
例如：
输入
begin
a:=9;
x:=2*3;
b:=a+x
end
#
输出
success！
输入
x:=a+b*c
end
#
输出
error
2.3
语法分析程序的算法思想
（1）主程序示意图如图2.1所示。
图2.1主程序
（2）递归下降分析程序示意图如图2.2所示。
（3）语句串分析过程示意图如图2.3所示。
图2.2
递归下降分析程序示意图
图2.3语句串分析示意图
（4）statement语句分析程序流程如图2.4,2.5,2.6,2.7所示。
图2.4
statement语句分析函数示意图
图2.5
expression表达分析函数示意图
图2.6
term分析函数示意图
图2.7
factor分析过程示意图
2.4
语法分析程序的具体设计
2.4.1数据结构
源程序字符缓冲区：input[100]
单词缓冲区：token[100]
单词缓冲区指针：p_token
关键字数组：char*
key_words[]={“begin“,“if“,“then“,“while“,“do“,“end“}
2.4.2函数的具体设计
1）scaner
函数的设计与词法分析中的设计大致相同，只不过返回值从原来的的WORD结构变成了该存储该字符串的种别码，更加的简单，在此不再赘述。
2）Irparser函数
首先判断是否为begin标示符号，调用scaner函数，调用语句串分析函数，判断是否为end，如果为end，打印成功否则出错。具体函数实现如下所示：
int
lrparser()
{
scaner();
if(syn==1)
{
scaner();
yucu();
if(syn==6)
{
scaner();
if((syn==0)
return
1;
}
}
else
{
if(kk!=1)
printf(“no
end
error/n“);
kk=1;
return
0;
}
}
else
{
printf(“no
begin
error/n“);
kk=1;
return
0;
}
}
3)语句串函数
调用statement函数，并判断时候还有下一条语句，如果有下一条语句，继续调用statement函数。具体的函数实现如下所示：
int
yucu()
{
statement();
while
(syn==29)
{
scaner();
statement();
}
return
1;
}
4)statement函数
首先判断scaner返回的值是否是标识符，是则调用scaner函数，再调用expression函数，否则报错。具体的代码实现如下所示：
int
statement()
{
if(syn==10)
{
scaner();
if
(syn==21)
{
scaner();
expression();
}
else
{printf(“输入赋值错误/n“);kk=1;}
}
else
{printf(“输入语句错误/n“);kk=1;}
return
1;
}
5)expression函数
调用term函数，判断scaner返回的值是否符合表达式的要求，并判断该条表达式是否结束，如果没有结束，继续调用term函数，具体的代码实现如下图所示：
int
expression()
{
term();
while
(syn==13||syn==14)
{
scaner();
term();
}
return
1;
}
6）term函数
调用factor函数，判断scaner返回的值是否符合项的要求，并判断该项是否结束，如果没有结束，继续调用factor函数，具体的代码实现如下图所示：
int
term()
{
factor();
while(syn==15||syn==16)
{
scaner();
factor();
}
return
1;
}
7）factor函数
判断scaner函数的返回值是否符合因子的要求，并调用scaner函数。具体的代码实现如下：
int
factor()
{
if(syn==10||syn==11)
scaner();
else
if(syn==17)
{
scaner();
expression();
if
(syn==18)
{
scaner();
}
else
{
printf(“输入错误/n“);kk=1;return
0;}
}
else
{printf(“输入表达式错误/n“);kk=1;return
0;}
return
1;
}
2.5语法分析程序的结果和结果分析
按照书上的测试输入进行测试，得到的结果如图所示：
同时该程序也能对一些错误进行判断，如图所示：
分析结果可知，本次实验完成了对于正确结果的判断，同时也对一些错误进行判断。
总结与感悟
编译原理是一门研究设计和构造编译程序原理和方法的课程，是计算机各个专业的一门重要专业基础课。对于我们本科生来说尤为重要，总的来说这两次实验分别是词法分析和使用递归下降分析法进行赋值语句的分析，在课本的最后有相应的提示，总的来说不算复杂，跟着课本上的操作一步一步来便可以完成本次实验，虽然简单，但也是对课本知识一个熟悉再实践的过程，经过这次实验，我对所学的编译原理的知识的具体的应用有了一个了解，我们平常生活中使用的如此方便的编译器尽然有这么复杂的设计过程，不得不感叹设计者们巧妙的设计思想。
经过本次实验，我对课本知识有了一个更全面的掌握，同时也锻炼了自己写代码的能力，但同样的，本次实验比较简单，并没有什么挑战性，我实现的代码也比较简单。在以后也会自己尝试去设计一些词法，语法的分析程序，同时也会学着使用yacc等一些工具，争取写出健壮性更强的代码。
17
篇2：编译原理报告(4)
编译原理报告(4) 本文关键词：编译，原理，报告
编译原理报告(4) 本文简介：课程实验报告课程名称：编译原理专业班级：信息安全1302班学号：姓名：报告日期：2015年11月11日计算机科学与技术学院目录1实验一21.1实验目的21.2实验要求21.3词法分析的算法思想31.4词法分析代码41.5结果验证81.6实验小结92实验二102.1实验目的102.2实验要求102.3
编译原理报告(4) 本文内容：
课
程
实
验
报
告
课程名称：
编译原理
专业班级：
信息安全1302班
学
号：
姓
名：
报告日期：
2015年
11
月
11日
计算机科学与技术学院
目录
1
实验一2
1.1
实验目的2
1.2
实验要求2
1.3
词法分析的算法思想3
1.4
词法分析代码4
1.5
结果验证8
1.6
实验小结9
2
实验二10
2.1
实验目的10
2.2
实验要求10
2.3
语法分析的算法思想10
2.4
语法分析代码12
2.5
结果验证18
2.6
实验小结18
实验一
词法分析
1.1
实验目的
设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。
1.2
实验要求
1.2.1
待分析的简单语言的词法
（1）
关键字：
begin
if
then
while
do
end
所有的关键字都是小写。
（2）
运算符和界符：
：
=
+
-
/
>
>=
=
;
(
)
#
（3）
其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：
ID=letter(letter|digit)*
NUM=digit
digit*
（4）
空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。
1.2.2
各种单词符合对应的种别码
表1.各种单词符号对应的种别码
单词符号
种别码
单词符号
种别码
begin
1
:
17
if
2
:=
18
then
3
21
do
5
23
lettet（letter|digit）*
10
>=
24
dight
dight*
11
=
25
+
13
;
26
-
14
(
27
15
)
28
/
16
#
0
1.2.3
词法分析程序的功能
输入：所给文法的源程序字符串。
输出：二元组(syn,token或sum)构成的序列。
其中：syn为单词种别码；
token为存放的单词自身字符串；
sum为整形常数。
1.3
词法分析程序的算法思想
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
1.
主程序示意图
（1）
关键字表的初值。
关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下。
charrwtab[6]={“begin“,“if“,“then“,“while“,“do“,“end“};
置初值
调用扫描子程序
输出单词二元组
输入串结束？
结束
Y
N
（2）
程序中需要用到的主要变量为syn,token,sum。
2.
扫描子程序的算法思想
首先设置3个变量：token用来存放构成单词符号的字符串；sum用来存放整型单词；syn用来存放单词符号的种别码。
扫描子程序的流程图如下图所示。
1.4
词法分析代码
#include
#include
char
prog[80],token[8],ch;
int
syn,p,m,n,sum;
charrwtab[6]={“begin“,“if“,“then“,“while“,“do“,“end“};
scaner();
main()
{
FILEfp;
fp=fopen(“1.txt“,“r“);
do
{
ch=fgetc(fp);
prog[p++]=ch;
}while(ch!=
#
);
p=0;
do{
scaner();
switch(syn)
{
case
11:printf(“(%-10d%5d)/n“,sum,syn);break;
case
-1:printf(“you
have
input
a
wrong
string/n“);break;
default:printf(“(%-10s%5d)/n“,token,syn);
break;
}
}while(syn!=0);
scaner();
}
词法分析程序
scaner()
{
sum=0;
for(m=0;m=
a
))||((ch=
A
)))
{
while(((ch=
a
))||((ch=
A
))||((ch=
0
)))
{
token[m++]=ch;
ch=prog[p++];
}
p--;
syn=10;
for(n=0;n=
0
))
{
while((ch=
0
))
{
sum=sum*10+ch-
0
;
ch=prog[p++];
}
p--;
syn=11;
}
else
switch(ch)
{
case
:token[m++]=ch;
ch=prog[p++];
if(ch==
=
)
{
syn=24;
token[m++]=ch;
}
else
{
syn=23;
p--;
}
break;
case
+
:token[m++]=ch;
ch=prog[p++];
if(ch==
+
)
{
syn=17;
token[m++]=ch;
}
else
{
syn=13;
p--;
}
break;
case
-
:token[m++]=ch;
ch=prog[p++];
if(ch==
-
)
{
syn=29;
token[m++]=ch;
}
else
{
syn=14;
p--;
}
break;
case
!
:ch=prog[p++];
if(ch==
=
)
{
syn=21;
token[m++]=ch;
}
else
{
syn=31;
p--;
}
break;
case
=
:token[m++]=ch;
ch=prog[p++];
if(ch==
=
)
{
syn=25;
token[m++]=ch;
}
else
{
syn=18;
p--;
}
break;
case
:syn=15;
token[m++]=ch;
break;
case
/
:syn=16;
token[m++]=ch;
break;
case
(
:syn=27;
token[m++]=ch;
break;
case
)
:syn=28;
token[m++]=ch;
break;
case
{
:syn=5;
token[m++]=ch;
break;
case
}
:syn=6;
token[m++]=ch;
break;
case
;
:syn=26;
token[m++]=ch;
break;
case
#
:syn=0;
token[m++]=ch;
break;
case
:
:syn=17;
token[m++]=ch;
break;
default:syn=-1;
break;
}
token[m++]=
/0
;
}
1.5
结果验证
对源程序
begin
x:=9;
if
x
>
0
then
x:=
2*
x
+
1/3;end#的源文件，经词法分析后的结果为：
1.6
实验小结
词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。通过实验，让我更加深刻地体会到了词法分析的原理和过程，通过编写C语言程序，也让我把词法分析的流程自己走了一遍，有了更加清晰的印象。
实验二
语法分析
2.1实验目的
编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。
2.2实验要求
利用C语言编制递归下降分析程序，并对简单语言进行语言分析。
2.2.1
待分析的简单语言的语法
用扩充的BNF表示如下：
（1）
：：=beginend
（2）
：：={;}
（3）
：：=
（4）
：：=ID:=
（5）
：：={+|-}
（6）
：：={*|/}
（7）
：：=ID|NUM|（）
2.2.2
实验要求说明
输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。
2.3
语法分析程序的算法思想
（1）
主程序示意图
（2）
递归下降分析程序示意图
（3）
语句串分析过程示意图
（4）
statement语句分析函数流程
Statement语句分析函数示意图
expression表达式分析函数示意图
term分析函数示意图
factor分析过程示意图
2.4
语法分析的代码
#include
#include
char
prog[100],token[8],ch;
charrwtab[6]={“begin“,“if“,“then“,“while“,“do“,“end“};
int
syn,p,m,n,sum;
int
kk;
factor();
expression();
yucu();
term();
statement();
parser();
scaner();
main()
{
p=kk=0;
FILEfp;
fp=fopen(“1.txt“,“r“);
do
{
ch=fgetc(fp);
prog[p++]=ch;
}while(ch!=
#
);
p=0;
scaner();
parser();
}
parser()
{
if(syn==1)
{
scaner();
yucu();
if(syn==6)
{
scaner();
if((syn==0)
}
else
{
if(kk!=1)printf(“the
string
haven
t
got
a
end
!/n“);
kk=1;
}
}
else{
printf(“haven
t
got
a
begin
!/n“);
kk=1;
}
return;
}
yucu()
{
statement();
while(syn==26)
{
scaner();
if(syn!=6)
statement();
}
return;
}
statement()
{
if(syn==10)
{
scaner();
if(syn==18)
{
scaner();
expression();
}
else{
printf(“the
sing
:=
is
wrong!/n“);
kk=1;
}
}
else{
printf(“wrong
sentence!/n“);
kk=1;
}
return;
}
expression()
{
term();
while((syn==13)||(syn==14))
{
scaner();
term();
}
return;
}
term()
{
factor();
while((syn==15)||(syn==16))
{
scaner();
factor();
}
return;
}
factor()
{
if((syn==10)||(syn==11))
scaner();
else
if(syn==27)
{
scaner();
expression();
if(syn==28)
scaner();
else{
printf(“the
error
on
(
/n“);
kk=1;
}
}
else{
printf(“the
expression
error!/n“);
kk=1;
}
return;
}
scaner()
{
sum=0;
for(m=0;m=
a
))||((ch=
A
)))
{
while(((ch=
a
))||((ch=
A
))||((ch=
0
)))
{
token[m++]=ch;
ch=prog[p++];
}
p--;
syn=10;
token[m++]=
/0
;
for(n=0;n=
0
))
{
while((ch=
0
))
{
sum=sum*10+ch-
0
;
ch=prog[p++];
}
p--;
syn=11;
}
else
switch(ch)
{
case
)
{
syn=21;
}
else
if(ch==
=
)
{
syn=22;
}
else{
syn=20;
p--;
}
break;
case
>
:m=0;
ch=prog[p++];
if(ch==
=
)
{
syn=24;
}
else
{
syn=23;
p--;
}
break;
case
:
:m=0;
ch=prog[p++];
if(ch==
=
)
{
syn=18;
}
else
{
syn=17;
p--;
}
break;
case
+
:syn=13;break;
case
-
:syn=14;break;
case
:syn=15;break;
case
/
:syn=16;break;
case
(
:syn=27;break;
case
)
:syn=28;break;
case
=
:syn=25;break;
case
;
:syn=26;break;
case
#
:syn=0;break;
case
if
:syn=2;break;
case
then
:syn=3;break;
case
while
:syn=4;break;
case
do
:syn=5;break;
case
end
:syn=6;break;
case
:=
:syn=18;break;
case
:syn=21;break;
case
=
:syn=24;break;
default:syn=-1;break;
}
}
2.5
结果验证
在文件中输入
begin
a:=9;x:=2*3;b:=a+x
end
#
在文件中输入
x：=a+b*c
end
#
在文件中输入
begin
x:=(a+b)*c
#
2.6
实验小结
通过做了递归下降分析法的实验，我也走了一遍语法分析器的流程，我明白了递归下降分析法的基本思想是对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该终结符所表示的语法成分，然后这些函数都以相互递归的方式进行调用，这样的方式非常清晰明了。比如递归下降的分析程序是按这样的顺序进行的，先检查是否是begin若是则调用scaner，不是则进行出错处理，然后进入语句串分析函数，再检查是否end，若否则又进行出错处理，接着再调用scaner，然后再判断syn=0&&kk=0这个条件是否成立，若否则进入出错处理，若是则打印分析成功。后面的子程序流程不再赘述，但是通过这样的顺序，可以让我们很清楚地想明白语法分析是一个怎样的过程，我觉得这是一个很清楚很简洁地方法。
19
篇3：编译原理概念总结
编译原理概念总结 本文关键词：编译，原理，概念
编译原理概念总结 本文简介：第一章引论?为什么要用编译器?与编译器相关的程序?翻译步骤?编译器中的主要数据结构1、语言处理器1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序
编译原理概念总结 本文内容：
第一章
引论
?
为什么要用编译器
?
与编译器相关的程序
?
翻译步骤
?
编译器中的主要数据结构
1、语言处理器
1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。
2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。
3、使用编译器是为了提高编程的速度和准确度。
4、与编译器相关的程序：解释程序（interpreter）、汇编程序（assembler）、连接程序（linker）、装入程序（loader）、预处理器（preprocessor）、编辑器（editor）、调试程序（debugger）、描述器（profiler）、项目管理程序（project
manager）。
Object
Program
5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。
Translator
Loader,Linker
and
Run-time
System
Output
Source
Program
6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在一起的任务有时会由一个被称为预处理器（preprocessor）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。
7、连接器（linker）能够解决外部内存地址的问题。
8、加载器（loader）把所有的可执行目标文件放到内存中执行。
2、一个编译器的结构
Lexical
Analysis
Syntax
Analysis
Semantic
Analysis
Controlflow/Dataflow
Optimization
Code
Generation
Source
Program
Assembly
Code
Scanner
Parser
High-level
IR
to
low-level
IR
conversion
Build
high-level
IR
Context
Symbol
Table
CFG
Machine
independent
asm
to
machine
dependent
Front
end
Back
end
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、
基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配
2、
正则表达式运算：
1、
从各选择对象中选择，用元字符“|”表示
2、
连结，由并置表示（不用元字符）
3、
重复或“闭包”，由元字符“*”表示
3、从各选择对象中选择：
4、连结：正则表达式r和正则表达式s的连接可写作rs
5、重复：正则表达式的重复有时称为Kleene闭包（（Kleene）closure），写作r*
6、运算的优先和括号的使用：前面的内容忽略了选择、连接和重复的优先问题。
7、正则表达式的名字：为较长的正则表达式提供一个简化了的名字很有用处，这样就不再需要在每次使用正则表达式时书写常常的表达式本身了。
3、有穷自动机（有穷状态机）：是描述（或“机器”）特定类型算法的数学方法。
1、确定性有穷自动机：下一个状态由当前状态和当前输入字符惟一给出的自动机。
2、非确定性有穷自动机：由它产生的。
4、从正则表达式到DFA
1、构造一个个扫描程序的自动过程可分为3步
2、从正则表达式到NFA
3、从NFA到DFA
4、将DFA中的状态最小化
第三章
上下文无关文法及分析
?
分析过程
?
上下文无关文法
?
上下文无关语言的形式特性
?
分析树与抽象语法树
?
二义性
1、分析过程：
2、上下文无关文法：
3、分析树与抽象语法树：
4、二义性：
可生成带有两个不同分析树的串的文法称作二义性文法（
ambiguous
grammar）
有两个解决二义性的基本方法。
其一是：设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。
另一种方法是将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。
第四章
自顶向下的分析
?
使用递归下降分析算法进行自顶向下的分析
?
LL(1)分析
?
First
集合和F
o
l
l
o
w集合
1、使用递归下降分析算法进行自顶向下的分析
2、LL(1)
分析方法是这样得名的：第1个“L”指的是由左向右地处理输入（一些旧式的分析程序惯于自右向左地处理输入，但现在已不常用了）。第2个“L”指的是它为输入串描绘出一个最左推导。括号中的数字1意味着它仅使用输入中的一个符号来预测分析的方向。
3、定义：如果文法G相关的L
L
(
1
)分析表的每个项目中至多只有一个产生式，则该文法
就是L
L
(
1
)文法(LL(1)
grammar)。