第五节 编译概述
一, 不同语言之间的翻译
1,翻译程序, 等价地变换
2,编译程序, 高级语言 ?低级语言
3,汇编程序, 汇编语言 ?机器语言
二, 编译执行和解释执行
1,编译执行
源程序 目标程序 计算结果
汇编语言程序 目标程序
2,解释执行,一边翻译一边解释执行
编译
编译
运行
汇编程序
初始数据
三, 编译程序的组成
1,词法分析, 输入字符串, 根据词法规则
识别出单词符号 。
2,语法分析, 根据语法规则, 将单词符号
构成各类语法单位, 并进行语法检查 。
3,语义分析与代码生成,
根据语义规则,进行初步编译 。
4,优化,对中间代码进行等价变换,以
使代码更有效 。
5,目标代码生成,生成机器语言程序
或汇编语言程序 。
6,符号表管理,完成符号表的建立,查
找,更新。
7,出错处理
源程序字符串
词法分析器
语法分析器
语义分析、中间代码生成器
代码优化器
目标代码生成器
单词流
语法单位
中间代码序列
中间代码序列
目标程序
符
号
表
管
理
程
序
出
错
处
理
程
序
编译程序的结构
第四章习题
4-2,4-3(a)(b),4-4
4-5(a)(c),4-6(b),4-9……NFA
4-10(a)(b)(c)babaab
均是必做题，第九周周五课后交作业
第五章 词法分析与语法分析
第一节 词法分析
一, 词法分析的功能
1,功能
扫描源程序的字符串,按照词法规则,识
别出单词符号作为输出 ;对识别过程中发
现的词法错误,则输出有关的错误信息 。
2,词法分析器和语法分析器的关系
（ 1） 词法分析作为单独的一遍
输出串 词法分析器 语法分析器 单词流
（ 2） 词法分析作为子程序
输入串 词法分析器
语法分析器
符号表
取
下
一
单
词
返
回
下
一
单
词
二, 单词的种类
(1)标识符,用来命名程序中出现的变量,
数组, 函数, 过程, 标号等
(2)基本字,也可称关键字或保留字,如 if、
while,for,do,goto等
(3)常数,各种类型的常数,如 216,3.14159、
TRUE等
(4)运算符,如 +,-,*,/等
(5)界符,如 ;,:,/*,*/等
三,单词的编码
1,单词的输出形式 —— 二元式
(单词类别,单词的属性 )
区分单词所属的类 (整数编码 ) 单词的值
2,单词类别的划分
?基本字, 运算符, 界符,一字一码
?标识符,单列一种
?常数,按类型分类
四, 词法错误检查
?非法字符
?不合规则的常数
?标识符前缀为保留字
五, 词法分析器的生成
1,词法分析技术 —— 超前搜索
为了判定一个单词符号的类别,必须扫
描到某一地方,而该单词符号并没有这么
长,这种扫描方式叫做, 超前搜索, 。
如,DO 100 I=1,10
DO100I=1.10
IF(5.EQ.M)GOTO 100
IF(5)=100
2,状态转换图
?有限的有向图
?有限边上标记字符
?一个初态
?若干终态
例, 某语言允许
标识符、基本字、数字串,
+,-,*,**,<,<=,<>,
=,>,>=,:=、：、；
0
4
1 2
3
5
6
7 8
9
开始
空白 字母 /数字
字母 非字母数字
数字
非数字
+
-
*
*
非 *
*
*
*
数字
10 11
12
<
>
=
13
14
15 16
17
>
其它
=
18 19
20
,
其它
=
其它
21
22
=；
其它
*
*
*
*
3,实现方法
每个状态结对应一小段程序
?分支状态 —— if或 case语句
?循环状态 —— while语句
?终态 —— return语句
4.一个示意算法
start,token:=‘ ‘;
getchar;getnb;
case character of
‘a’…’z’,begin
while letter or digit do
begin concatenate;getchar end;
retract;
c:= reserve;
if c = 0 then begin
buildlist;
return(id,id在符号表中的位置 )
end
else return(保留字码,— )
end;
‘0’…’9’,begin
while digit do
begin concatenate;getchar end;
retract;
return(num,num在常数表中的位置 )
end;
‘ + ’,return(plus-op,— );
‘ - ’,return(minus-op,— );
‘ * ’,begin getchar;
if character = ‘*’ then return(power-op,— );
retract;return(mul-op,— );
end;
‘ < ‘,begin getchar;
if character = ‘ = ‘ then return(rel-op,LE)
else if character = ‘>’ then return(rel-op,NE);
retract;
return(rel-op,LT)
end;
‘ = ‘,return(rel-op,EQ);
‘ > ‘,begin getchar;
if character = ‘ = ‘ then return(rel-op,GE);
retract;
return(rel-op,GT)
end;
‘, ‘,begin getchar;
if character = ‘ = ‘ then return(assign-op,— );
retract;
return(colon,— )
end;
‘ ; ‘,return(semicolon,— )
end of case;
error
全局量及过程,
(1)token
(2)character
(3)getchar
(4)getnb
(5)concatenate
(6)letter和 digit
(7)reserve
(8)retract:退一字符 ;character置空
(9)buildlist:为标识符登记符号表
第二节 自顶向下语法分析
?语法分析, 自上而下 (自顶而下 )
自下而上 (自底而上 )
?自顶向下语法分析法,或从开始符号出发,
找最左推导 ;或从根开始,构造推导树 。
一, 回溯分析法
1.一个实例
S→xAy
A→ab│a
输入串为 xay,说明分析过程
S
x A y
S
x A y
a b
S
x A y
a
2.存在的问题
(1)回溯 —— 公共左因子的存在
A→ ??1| ??2
(2)左递归
A→Aα 或 A?Aα *
二, 无回溯的递归下降分析法
1,提取公共左因子
A→ ??1| ??2|,.,|??n| δ
改写为,A→αB|δ
B→ ?1| ?2|,.,|?n|
2.左递归的消除
(1)直接左递归的消除
P→Pα│β
改写为,P→ ?P＇
P＇ → αP＇ │ε
A→A ?1|A?2|… |A?m|?1|?2|… |?n
（ ?i?ε,?j不以 A开头 ）
改写为,P→ ?1P’│ ?2P’│.,,│ ?nP’
P’ → ?1P’│?2P’│.,,│?mP’│ε
(2)间接左递归的消除
P?Pα
(a)将文法 G的所有非终结符按任一给定的顺序排列,设为
A1,A2,… An;
+
(b)消除可能的左递归 ;
for i:=1 to n do
for j:=1 to i-1 do
begin
把一个形如 Ai?Aj?的产生式改写为
Ai??1?|?2?|…| ?k?
其中 Aj??1|?2|…| ?k是 Aj的所有产生式 ;
消除 Ai产生式的直接左递归
end
(c)化简
以 S→Qc│c
Q→Rb│b
R→Sa│a
为例,按 S,Q,R排列,或 R,Q,S排列
一, 不同语言之间的翻译
1,翻译程序, 等价地变换
2,编译程序, 高级语言 ?低级语言
3,汇编程序, 汇编语言 ?机器语言
二, 编译执行和解释执行
1,编译执行
源程序 目标程序 计算结果
汇编语言程序 目标程序
2,解释执行,一边翻译一边解释执行
编译
编译
运行
汇编程序
初始数据
三, 编译程序的组成
1,词法分析, 输入字符串, 根据词法规则
识别出单词符号 。
2,语法分析, 根据语法规则, 将单词符号
构成各类语法单位, 并进行语法检查 。
3,语义分析与代码生成,
根据语义规则,进行初步编译 。
4,优化,对中间代码进行等价变换,以
使代码更有效 。
5,目标代码生成,生成机器语言程序
或汇编语言程序 。
6,符号表管理,完成符号表的建立,查
找,更新。
7,出错处理
源程序字符串
词法分析器
语法分析器
语义分析、中间代码生成器
代码优化器
目标代码生成器
单词流
语法单位
中间代码序列
中间代码序列
目标程序
符
号
表
管
理
程
序
出
错
处
理
程
序
编译程序的结构
第四章习题
4-2,4-3(a)(b),4-4
4-5(a)(c),4-6(b),4-9……NFA
4-10(a)(b)(c)babaab
均是必做题，第九周周五课后交作业
第五章 词法分析与语法分析
第一节 词法分析
一, 词法分析的功能
1,功能
扫描源程序的字符串,按照词法规则,识
别出单词符号作为输出 ;对识别过程中发
现的词法错误,则输出有关的错误信息 。
2,词法分析器和语法分析器的关系
（ 1） 词法分析作为单独的一遍
输出串 词法分析器 语法分析器 单词流
（ 2） 词法分析作为子程序
输入串 词法分析器
语法分析器
符号表
取
下
一
单
词
返
回
下
一
单
词
二, 单词的种类
(1)标识符,用来命名程序中出现的变量,
数组, 函数, 过程, 标号等
(2)基本字,也可称关键字或保留字,如 if、
while,for,do,goto等
(3)常数,各种类型的常数,如 216,3.14159、
TRUE等
(4)运算符,如 +,-,*,/等
(5)界符,如 ;,:,/*,*/等
三,单词的编码
1,单词的输出形式 —— 二元式
(单词类别,单词的属性 )
区分单词所属的类 (整数编码 ) 单词的值
2,单词类别的划分
?基本字, 运算符, 界符,一字一码
?标识符,单列一种
?常数,按类型分类
四, 词法错误检查
?非法字符
?不合规则的常数
?标识符前缀为保留字
五, 词法分析器的生成
1,词法分析技术 —— 超前搜索
为了判定一个单词符号的类别,必须扫
描到某一地方,而该单词符号并没有这么
长,这种扫描方式叫做, 超前搜索, 。
如,DO 100 I=1,10
DO100I=1.10
IF(5.EQ.M)GOTO 100
IF(5)=100
2,状态转换图
?有限的有向图
?有限边上标记字符
?一个初态
?若干终态
例, 某语言允许
标识符、基本字、数字串,
+,-,*,**,<,<=,<>,
=,>,>=,:=、：、；
0
4
1 2
3
5
6
7 8
9
开始
空白 字母 /数字
字母 非字母数字
数字
非数字
+
-
*
*
非 *
*
*
*
数字
10 11
12
<
>
=
13
14
15 16
17
>
其它
=
18 19
20
,
其它
=
其它
21
22
=；
其它
*
*
*
*
3,实现方法
每个状态结对应一小段程序
?分支状态 —— if或 case语句
?循环状态 —— while语句
?终态 —— return语句
4.一个示意算法
start,token:=‘ ‘;
getchar;getnb;
case character of
‘a’…’z’,begin
while letter or digit do
begin concatenate;getchar end;
retract;
c:= reserve;
if c = 0 then begin
buildlist;
return(id,id在符号表中的位置 )
end
else return(保留字码,— )
end;
‘0’…’9’,begin
while digit do
begin concatenate;getchar end;
retract;
return(num,num在常数表中的位置 )
end;
‘ + ’,return(plus-op,— );
‘ - ’,return(minus-op,— );
‘ * ’,begin getchar;
if character = ‘*’ then return(power-op,— );
retract;return(mul-op,— );
end;
‘ < ‘,begin getchar;
if character = ‘ = ‘ then return(rel-op,LE)
else if character = ‘>’ then return(rel-op,NE);
retract;
return(rel-op,LT)
end;
‘ = ‘,return(rel-op,EQ);
‘ > ‘,begin getchar;
if character = ‘ = ‘ then return(rel-op,GE);
retract;
return(rel-op,GT)
end;
‘, ‘,begin getchar;
if character = ‘ = ‘ then return(assign-op,— );
retract;
return(colon,— )
end;
‘ ; ‘,return(semicolon,— )
end of case;
error
全局量及过程,
(1)token
(2)character
(3)getchar
(4)getnb
(5)concatenate
(6)letter和 digit
(7)reserve
(8)retract:退一字符 ;character置空
(9)buildlist:为标识符登记符号表
第二节 自顶向下语法分析
?语法分析, 自上而下 (自顶而下 )
自下而上 (自底而上 )
?自顶向下语法分析法,或从开始符号出发,
找最左推导 ;或从根开始,构造推导树 。
一, 回溯分析法
1.一个实例
S→xAy
A→ab│a
输入串为 xay,说明分析过程
S
x A y
S
x A y
a b
S
x A y
a
2.存在的问题
(1)回溯 —— 公共左因子的存在
A→ ??1| ??2
(2)左递归
A→Aα 或 A?Aα *
二, 无回溯的递归下降分析法
1,提取公共左因子
A→ ??1| ??2|,.,|??n| δ
改写为,A→αB|δ
B→ ?1| ?2|,.,|?n|
2.左递归的消除
(1)直接左递归的消除
P→Pα│β
改写为,P→ ?P＇
P＇ → αP＇ │ε
A→A ?1|A?2|… |A?m|?1|?2|… |?n
（ ?i?ε,?j不以 A开头 ）
改写为,P→ ?1P’│ ?2P’│.,,│ ?nP’
P’ → ?1P’│?2P’│.,,│?mP’│ε
(2)间接左递归的消除
P?Pα
(a)将文法 G的所有非终结符按任一给定的顺序排列,设为
A1,A2,… An;
+
(b)消除可能的左递归 ;
for i:=1 to n do
for j:=1 to i-1 do
begin
把一个形如 Ai?Aj?的产生式改写为
Ai??1?|?2?|…| ?k?
其中 Aj??1|?2|…| ?k是 Aj的所有产生式 ;
消除 Ai产生式的直接左递归
end
(c)化简
以 S→Qc│c
Q→Rb│b
R→Sa│a
为例,按 S,Q,R排列,或 R,Q,S排列
