编译原理概念总结

时间：2021-03-12 12:08:12 来源：蒲公英阅读网 本文已影响人

相关热词搜索：编译 原理 概念

编译原理概念总结 本文关键词：编译，原理，概念

编译原理概念总结 本文简介：第一章引论?为什么要用编译器?与编译器相关的程序?翻译步骤?编译器中的主要数据结构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)。

篇2：不确定有穷自动机的确定化编译原理实验报告

不确定有穷自动机的确定化编译原理实验报告 本文关键词：自动机，不确定，编译，原理，实验

不确定有穷自动机的确定化编译原理实验报告 本文简介：编译原理实验报告实验名称不确定有穷自动机的确定化实验时间_____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<<“其中终态为：“<

}

篇3：语法分析编译原理实验报告昆明理工大学

语法分析编译原理实验报告昆明理工大学 本文关键词：昆明，理工大学，编译，语法，原理

语法分析编译原理实验报告昆明理工大学 本文简介：昆明理工大学信息工程与自动化学院学生实验报告（2012—2013学年第上学期）课程名称：编译原理开课实验室：4442012年11月23日专业、班级计科101班学号姓名成绩实验项目名称语法分析指导教师严馨教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.

语法分析编译原理实验报告昆明理工大学 本文内容：

昆明理工大学信息工程与自动化学院学生实验报告

（

2012

—2013学年

第上学期

）

课程名称：编译原理

开课实验室：

444

2012年

11

月

23

日

专业、班级

计科101班

学号

姓名

成绩

实验项目名称

语法分析

指导教师

严馨

教师评语

该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□

该同学的实验能力：A.强

□B.中等

□C.差

□

该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□

实验报告是否规范：A.规范□B.基本规范□C.不规范□

实验过程是否详细记录：A.详细□B.一般

□

C.没有

□

教师签名：*年*月*日

一、实验目的

编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。

二、

实验要求

利用C语言编制递归下降分析程序，并对简单语言进行语法分析。

2.1

待分析的简单语言的语法

用扩充的BNF表示如下：

→main()

→‘{’‘}’

→

{;

};

→

||

→ID=

→if‘(‘条件’)’

→while’(‘’)‘

→

→{+|-}

→

{*

|/

}

→ID|NUM|

‘(’‘)’

→|>=|==|!=

2.2

实验要求说明

输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。

三、

语法分析程序的C语言程序源代码

#include

#include

char

prog[80],token[8];

char

ch;

int

syn,p,m=0,n,sum,kk=0;

charrwtab[6]={“function“,“if“,“then“,“while“,“do“,“endfunc“};

void

yucu();

void

expression();

void

statement();

void

factor();

void

term();

void

irparser();

void

scaner()

{for

(n=0;n=

a

)

||

(ch=

A

))

{while((ch=

a

)

||

(ch=

A

)

||

(ch=

0

))

{token[m++]=ch;

ch=prog[p++];

}

syn=10;

for(n=0;n=

0

)

{sum=0;

while(ch=

0

)

{sum=sum*10+ch-

0

;

ch=prog[p++];

}

syn=11;

}

else

{switch(ch)

{case

:m=0;token[m++]=ch;

ch=prog[p++];

if(ch==

=

)

{syn=24;

token[m++]=ch;

}

else

{syn=23;p--;

}

break;

case

=

:m=

0;token[m

++

]=ch;

ch=prog[p++];

if(ch==

=

)

{

syn=

25;

token[m++]=

ch;

}

else

{syn=18;

ch=prog[--p];

}

break;

case

!

:m=0;

token[m++]=

ch;

ch=prog[++p];

if(ch==

=

)

{

syn=22;

token[m++]=

ch;

}

else

syn=-1;

break;

case

+

:syn=13;

token[0]=ch;break;

case

-

:syn=14;

token[0]=ch;break;

case

:syn=15;

token[0]=ch;break;

case

/

:syn=16;

token[0]=ch;break;

case

;

:syn=26;

token[0]=ch;break;

case

(

:syn=27;

token[0]=ch;break;

case

)

:syn=28;

token[0]=ch;break;

case

#

:syn=0;

token[0]=ch;break;

default:syn=-1;//break;

}

ch=prog[p++];

}

}

void

irparser()

{

if(syn==1)

{scaner();

yucu();/*语句串分析*/

if(syn==6)

/*读到endfunc*/

{

scaner();

if(syn==0

}

else

{if(kk!=1)

/*没以endfunc结束*/

{printf(“error!need

endfunc

“);

kk=1;

}

}

}

else

{printf(“error!need

function

“);

kk=1;

}

}

void

yucu()

/*语句串分析*/

{

statement();/*调用语句分析函数*/

while(syn==26)/*一个语句识别结束，继续识别*/

{scaner();

statement();

}

return;

}

void

statement()/*语句分析函数*/

{

if(syn==10)

{scaner();

if(syn==18)

//如果是赋值语句

{scaner();

expression();

}

//这个过程实现语法分析判断语句

else

{printf(“error!evaluate

tag

error“);

kk=1;

}

}

else

if(syn==6)

return;

else

if(syn==2)

//如果是条件判断语句

就判断条件表达式的语法!

{scaner();

if(syn==27)

//判断括号匹配

{do

{scaner();

//进入括号内部进行表达式分析

expression();

}while(syn!=28);

}

else

{

printf(“error!

need

another

)

“);

kk=1;

}

//()内判断完成

!

scaner();

//然后进行语句块分析!

statement();

}

//到这里是实现判断if语句的语法分析

//

类似的往里添加

循环语句

！

else

if(syn==4)

//如果是循环语句

就判断条件表达式的语法!

{scaner();//ch=prog[p++];

if(syn==27)

{

do

{scaner();

expression();

}while(syn!=28);

}

else

{

printf(“error!

need

another

)

“);

kk=1;

}

//()内判断完成

!

scaner();

//然后进行语句块分析!

statement();

}

//这里是实现判断while语句的语法分析

else

{printf(“error!the

statement

error!“);

kk=1;

}

}

void

expression()/*表达式分析函数*/

{

term();

while(syn==13||syn==14)

{

scaner();

term();}

return;

}

void

term()/*项分析函数*/

{factor();

while(syn==15||syn==16)

{scaner();

factor();}

return;

}

void

factor()/*因子分析函数*/

{

if(syn==10||syn==11)

{scaner();}

else/*看是否是表达式*/

{expression();

if(syn==27)

{

scaner();

expression();

if(syn==28)

{

scaner();}

else

{

printf(“error!

need

another

)

“);

kk=1;

}

}

else

{

printf(“error!

expression

error!“);

}

}

}

void

main()

{p=0;

printf(“/n

请输入待分析的字符串:/n“);

do

{ch=getchar();

prog[p++]=ch;

}

while(ch!=

#

);

p=0;

ch=prog[p++];

scaner();

irparser();

}

四、

程序测试结果

五、总结

在这次实验中，我获得了很大的收获，让自己对语法分析程序的功能有了更进一步认识。虽然在程序的设计和编写过程中出现了一些错误，但是经过同学的帮助和指导，顺利的将程序中存在的错误顺利解决，从而顺利完成了本程序的设计和编译。从一开始对程序的陌生，到后来逐步了解程序的流程，当我耐心的一步一步理解程序思想，一次次的更改测试用例，一遍遍的调试，最终终于得到了预期的答案。这次实验使我对理论的语法分析递归下降的理解更加具体清晰，受益匪浅。同时，自己对语法分析的流程有了深刻的了解，使得语法分析递归向下思想更加具体化。

注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。