编译原理报告(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
篇2：编译原理概念总结
编译原理概念总结 本文关键词：编译，原理，概念
编译原理概念总结 本文简介：第一章引论?为什么要用编译器?与编译器相关的程序?翻译步骤?编译器中的主要数据结构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)。
篇3：不确定有穷自动机的确定化编译原理实验报告
不确定有穷自动机的确定化编译原理实验报告 本文关键词：自动机，不确定，编译，原理，实验
不确定有穷自动机的确定化编译原理实验报告 本文简介：编译原理实验报告实验名称不确定有穷自动机的确定化实验时间_____2014年4月10日_______院系_______管理信息工程学院_______班级_______11计算机科学与技术____学号______201101020109____________姓名________姜高_________
不确定有穷自动机的确定化编译原理实验报告 本文内容：
编译原理实验报告
实验名称
不确定有穷自动机的确定化
实验时间_____
2014年4月10日_______
院
系_______管理信息工程学院_______
班
级_______11计算机科学与技术____
学
号______201101020109____________
姓
名________姜高__________________
1、
实验目的
不确定有穷自动机的确定化
2、
实验原理
用子集构造算法构造子集加入子集族中直到收敛（所有构造的子集都已存在于子集族）为止。如原来不确定有穷自动机的五元组形式为：M=（K，
For
每输入字母a
DO
{
U:=closure(move(T,a));
If
U
不在S中
then
将U作为未被标记的子集加在S中
}
}
5.代码实现
#include
#include
#define
MAXS
100
using
namespace
std;
string
NODE;
//结点集合
string
CHANGE;
//终结符集合
int
N;
//NFA边数
struct
edge{
string
first;
string
change;
string
last;
};
struct
chan{
string
ltab;
string
jihe[MAXS];
};
void
kong(int
a)
{
int
i;
for(i=0;iNODE.find(a[i+1]))
{
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
}
}
void
eclouse(char
c,string
for(k=0;khe.length())
he+=b[k].last;
eclouse(b[k].last[0],he,b);
}
}
}
void
move(chan
k=he.ltab.length();
l=he.jihe[m].length();
for(i=0;ihe.jihe[m].length())
he.jihe[m]+=b[j].last[0];
for(i=0;ihe.jihe[m].length())
he.jihe[m]+=b[j].last[0];
}
//输出
void
outputfa(int
len,int
h,chant)
{
int
i,j,m;
cout>b[i].first;
if(b[i].first==“#“)
break;
cin>>b[i].change>>b[i].last;
}
N=i;
/*for(j=0;jNODE.length())
NODE+=b[i].first;
if(NODE.find(b[i].last)>NODE.length())
NODE+=b[i].last;
if((CHANGE.find(b[i].change)>CHANGE.length())
}
len=CHANGE.length();
cout>endnode;
for(i=0;iNODE.length())
{
cout“;
move(t[i],k,b);
//求move(I,a)
//coutednode.length())
d[0]+=NODE[i];
endnode=ednode;
cout< outputfa(len,h,t); //输出DFA cout<<“其中终态为：“< //DFA最小化 m=2; sta.erase(); flag=0; for(i=0;i { //cout<<“d[“< for(k=0;k { //cout<<“I“< y=m; for(j=0;j { for(n=0;n { if(d[n].find(t[NODE.find(d[i][j])].jihe[k]) ) { if(t[NODE.find(d[i][j])].jihe[k].length()==0) x=m; else x=n; if(!sta.length()) { sta+=x+48; } else if(sta[0]!=x+48) { d[m]+=d[i][j]; flag=1; d[i].erase(j,1); //cout< j--; } break; //跳出n } }//n }//j if(flag) { m++; flag=0; } //cout<<“sta=“< sta.erase(); }//k }//i cout< for(i=0;i cout<<“{“< “; cout< //状态重新命名 chanmd=new chan[m]; NODE.erase(); cout< for(i=0;i { md[i].ltab= A +i; NODE+=md[i].ltab; cout<<“{“< } for(i=0;i for(k=0;k for(j=0;j { if(d[i][0]==t[j].ltab[0]) { for(n=0;n { if(!t[j].jihe[k].length()) break; else if(d[n].find(t[j].jihe[k]) { md[i].jihe[k]=md[n].ltab; break; } } break; } } ednode.erase(); for(i=0;i for(j=0;j if(d[i].find(endnode[j]) endnode=ednode; cout< outputfa(len,m,md); cout<<“其中终态为：“< }