您所在位置：主题：顶级程序原理讲义[编译原理|第一章续续]
w1212q
[专家分：660] 发布于 2006-11-29 11:38:00
语法分析；
功能:层次分析.依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).
position := initial + rate * 60 ;
规则
<赋值语句>::=<标识符>“:=”<表达式>
<表达式>::=<表达式>“+”<表达式>
<表达式>::=<表达式>“*”<表达式>
<表达式>::=“(”<表达式>“)”
<表达式>::=<标识符>
<表达式>::=<整数>
<表达式>::=<实数>
术语；
语法分析(syntax analysis or parsing) nThe purpose of syntax analysis is to determine the source program’s phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source language’s syntax,and to construct a suitable representation of its phrase structure.
语法树(推导树)(parse tree or derivation tree)
语义分析；
语义审查(静态语义)
-上下文相关性
–类型匹配
–类型转换
例:
Program p();
Var rate:real;
procedure initial;
…
position := initial + rate * 60
/* error */ /* error */ /* warning */; …
又如；
int arr [2],abc;
abc = arr * 10;
…
nProgram p();
Var rate:real;
Var initial :real;
Var position :real ;
…
position := initial + rate * 60
术语；
语义分析(semantic analysis)
The parsed program is further analyzed to determine whether it conforms to the source language’s contextual constraints:scope rules, type rules ne.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.
中间代码生成；
源程序的内部(中间)表示
三元式、四元式、P-Code、C-Code、 U-Code、bytecode
( * id3 t1 t2 )
t2 = id3 * t1
t2 := id3 * t1
中间代码生成；
id1:= id2 + id3 * 60
(1) (inttoreal, 60 - t1 )
(2) (* , id3 t1 t2 )
(3) (+ , id2 t2 t3 )
(4) (:= , t3 - id1 )
中间代码生成；
(intermediate code generation)nThis is where the intermediate representation of the source program is created.We want this representation to be easy to generate,and easy to translate into the target program.The representation can have a variety of forms,but a common one is called three-address code or 4- tuple code.
代码优化；
id1:= id2 + id3 * 60
(1) (inttoreal 60 - t1 )
(2) ( * id3 t1 t2 )
(3) ( + id2 t2 t3 )
(4) ( := t3 - id1 ) 变换 Þ
（1） ( * id3 60.0 t1 )
(2）（ + id2 t1 id1 )
代码优化；
t1 = b* c t1 = b* c
t2 = t1+ 0 -》 t2 = t1 + t1
t3 = b* c a = t2
t4 = t2 + t3
a = t4
代码优化；
(code optimization)nIntermediate code optimization nThe optimizer accepts input in the intermediate representation and output a version still in the intermediate representation .In this phase,the compiler attempts to produce the smallest,fastest and most efficient running result by applying various techniques. nObject code optimization
目标代码生成；
(* , id3 60.0 t1 )
(+ , id2 t1 id1 )
movf id3,R2
mulf #60.0,R2
movf id2,R1
addf R2,R1
movf R1,id1
符号表管理；
记录源程序中使用的名字
收集每个名字的各种属性信息
–类型、作用域、分配存储信息
Const1 常量 值：35
Var1 变量 类型：实 层次：2
符号表；
(symbol table)nSymbol table is a data structure which is employed to associate identifiers with their attributes . nAn identifier’s attribute consists of information relevant to contextual analysis,and is obtained from the identifier’s declaration.
出错处理；
检查错误、报告出错信息、排错、恢复编译工作
出错处理；
（error handling)(error reporting and error recovery)nThe compiler should report the location of each error,together with some explanation. The major categories of compile-time error: syntax error, scope error, type error. nAfter detecting and reporting an error,the compiler should attempt error recovery,means that the compiler should try to get itself into a state where analysis of the source program can continue as normally as possible.
编译程序结构；(components)
词法分析程序
语法分析程序
语义分析程序
中间代码生成程序
代码优化程序
目标代码生成程序
符号表管理程序
出错处理程序
编译阶段的组合；
分析，综合(synthesis)
–源程序的分析
•线性分析
•层次分析
•语义分析
–目标程序的综合
编译的前端（front end）
编译的后端（back end）
遍（趟）从头到尾扫描源程序（各种形式）一遍(pass)
高级语言解释系统；(interpreter)
功能 让计算机执行高级语言（basic,lisp,prolog)
与编译程序的不同 1）不生成目标代码 n 2）能支持交互环境 （同增量式编译系统）
源 程 序
-》计算结果果
初始数据
解释系统；
直接对源程序中的语句进行分析，执行其隐含的操作。
如
…
…
b := 2 ;
a := b+2 ;
编译程序
write a ;
…
…
解释程序直接将4的值输出（显示）
编译阶段和运行阶段存储结构；
编译时 运行时 名字表目标代码缓冲区编译用源程序中 间表示各种表格目标代码区数据区源程序缓冲区
解释系统存储结构；
解释系统
源程序
工作单元
名字表
标号表
缓冲区 (输入输出)
栈区
功能:层次分析.依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).
position := initial + rate * 60 ;
规则
<赋值语句>::=<标识符>“:=”<表达式>
<表达式>::=<表达式>“+”<表达式>
<表达式>::=<表达式>“*”<表达式>
<表达式>::=“(”<表达式>“)”
<表达式>::=<标识符>
<表达式>::=<整数>
<表达式>::=<实数>
术语；
语法分析(syntax analysis or parsing) nThe purpose of syntax analysis is to determine the source program’s phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source language’s syntax,and to construct a suitable representation of its phrase structure.
语法树(推导树)(parse tree or derivation tree)
语义分析；
语义审查(静态语义)
-上下文相关性
–类型匹配
–类型转换
例:
Program p();
Var rate:real;
procedure initial;
…
position := initial + rate * 60
/* error */ /* error */ /* warning */; …
又如；
int arr [2],abc;
abc = arr * 10;
…
nProgram p();
Var rate:real;
Var initial :real;
Var position :real ;
…
position := initial + rate * 60
术语；
语义分析(semantic analysis)
The parsed program is further analyzed to determine whether it conforms to the source language’s contextual constraints:scope rules, type rules ne.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.
中间代码生成；
源程序的内部(中间)表示
三元式、四元式、P-Code、C-Code、 U-Code、bytecode
( * id3 t1 t2 )
t2 = id3 * t1
t2 := id3 * t1
中间代码生成；
id1:= id2 + id3 * 60
(1) (inttoreal, 60 - t1 )
(2) (* , id3 t1 t2 )
(3) (+ , id2 t2 t3 )
(4) (:= , t3 - id1 )
中间代码生成；
(intermediate code generation)nThis is where the intermediate representation of the source program is created.We want this representation to be easy to generate,and easy to translate into the target program.The representation can have a variety of forms,but a common one is called three-address code or 4- tuple code.
代码优化；
id1:= id2 + id3 * 60
(1) (inttoreal 60 - t1 )
(2) ( * id3 t1 t2 )
(3) ( + id2 t2 t3 )
(4) ( := t3 - id1 ) 变换 Þ
（1） ( * id3 60.0 t1 )
(2）（ + id2 t1 id1 )
代码优化；
t1 = b* c t1 = b* c
t2 = t1+ 0 -》 t2 = t1 + t1
t3 = b* c a = t2
t4 = t2 + t3
a = t4
代码优化；
(code optimization)nIntermediate code optimization nThe optimizer accepts input in the intermediate representation and output a version still in the intermediate representation .In this phase,the compiler attempts to produce the smallest,fastest and most efficient running result by applying various techniques. nObject code optimization
目标代码生成；
(* , id3 60.0 t1 )
(+ , id2 t1 id1 )
movf id3,R2
mulf #60.0,R2
movf id2,R1
addf R2,R1
movf R1,id1
符号表管理；
记录源程序中使用的名字
收集每个名字的各种属性信息
–类型、作用域、分配存储信息
Const1 常量 值：35
Var1 变量 类型：实 层次：2
符号表；
(symbol table)nSymbol table is a data structure which is employed to associate identifiers with their attributes . nAn identifier’s attribute consists of information relevant to contextual analysis,and is obtained from the identifier’s declaration.
出错处理；
检查错误、报告出错信息、排错、恢复编译工作
出错处理；
（error handling)(error reporting and error recovery)nThe compiler should report the location of each error,together with some explanation. The major categories of compile-time error: syntax error, scope error, type error. nAfter detecting and reporting an error,the compiler should attempt error recovery,means that the compiler should try to get itself into a state where analysis of the source program can continue as normally as possible.
编译程序结构；(components)
词法分析程序
语法分析程序
语义分析程序
中间代码生成程序
代码优化程序
目标代码生成程序
符号表管理程序
出错处理程序
编译阶段的组合；
分析，综合(synthesis)
–源程序的分析
•线性分析
•层次分析
•语义分析
–目标程序的综合
编译的前端（front end）
编译的后端（back end）
遍（趟）从头到尾扫描源程序（各种形式）一遍(pass)
高级语言解释系统；(interpreter)
功能 让计算机执行高级语言（basic,lisp,prolog)
与编译程序的不同 1）不生成目标代码 n 2）能支持交互环境 （同增量式编译系统）
源 程 序
-》计算结果果
初始数据
解释系统；
直接对源程序中的语句进行分析，执行其隐含的操作。
如
…
…
b := 2 ;
a := b+2 ;
编译程序
write a ;
…
…
解释程序直接将4的值输出（显示）
编译阶段和运行阶段存储结构；
编译时 运行时 名字表目标代码缓冲区编译用源程序中 间表示各种表格目标代码区数据区源程序缓冲区
解释系统存储结构；
解释系统
源程序
工作单元
名字表
标号表
缓冲区 (输入输出)
栈区