第二章 一个微小的编译器
1,小语言 Micro的定义
2,Micro程序的编译过程
3,表达式的处理
小语言 Micro的定义
? P ? begin VDL;SL end.
? VDL ? VD | VD ; VDL
? VD ? var id, T
? SL ? S | S ; SL
? S ? id:= E | write(E) | read(id)
? T ? integer | real
? E ? id | num
| E + E
| E * E
|(E)
程序例：
begin
var x1:real ;
var z1:real ;
x1,= 0.5 ;
z1,= x1 + 55 ;
write( z1 +5.5 );
read( x1 ) ;
z1,=z1 + x1
end.
Micro的词法分析
? 单词的种类
? Token定义
? 词法分析过程
Micro的词法分析
Micro语言中单词的分类：
? 标识符：字母开头的字母 /数字串
? 整常数：数字开头的数字串
? 实常数：整数,整数
? 保留字,begin end var read write
integer real
? 符号词,+ * ( ),,= ;,
? 控制词,? (换行符）
Micro的词法分析
TOKEN定义：
二元组（单词种类，单词自身值）
? 标识符的 Token,($id,标识符）如 ($id,x)
? 整常数的 Token,($intC,整常数）如（ $intC,5)
? 实常数的 Token,($realC,实常数）如 ($realC,0.5)
? 保留字的 Token,($begin,-),($end,-),($var,-) …
? 符号词的 Token,($plus,-),($mult,-),($LParen,-)…
? 换行符的 Token,($line,-)
Micro的词法分析
? 词法分析过程：
读当前字符流，直至文件结束。如果是：
(1)标识符时判断是保留字还是变量标识
符，构造 Token表示
(2)数字时判断是整型还是实型，构造
Token表示
(3)构造其它合法的符号的 Token表示
(4)遇到非法符号则报错。
Micro的词法分析;; ?
?
?
??
?
l
l
a
a
e
e1z
1x△a
a r
△nib
etirw;5 5+1x=:z 1
x
5.0=
1
=z;)1(dae
r) ;.51z(
,#n d?1
x1z
图 2.2.1 源程序在文件中的表示
e g v r r
rv △,
:
:;
+ 5
V 1 +
e
:
Micro的词法分析
($id,z1)
（ $begin
，－）
($line，
-)
($line，
-)
（ $semi
，－）
（ $assig
，－）
($id,x1)
（ $semi
，－）
（ $semi
，－）
（ $real
，－）
（ $real
，－）
（ $colon
，－）
($line，
-)
($line，
-)
（ $var，
－）
（ $var，
－）
$assig ($realC，
0.5)
（ $colon
，－）
($id,x1)
($line，
-)
($line，
-)
（ $semi，
－）
($intC，
55)
（ $plus
，－）
（ $assig
，－）
($id,x1)($id,z1)
$Lparen
,－ ）
（ $read
，－）
（ $semi，
－）
($realC
,5.5)
$Rparen
，－）
（ $plus
，－）
($id,z1)（ $write
，－）
$Lparen
，－ )
#（ $stop
，－）
（ $end
，－）
($id,x1)（ $plus
，－）
($id,z1)
($id,z1)（ $semi
，－）
($id,x1) $Rparen
，－）
图 2.2.2 词法分析后的 TOKEN表示
Micro的语法分析
? 输入：是词法分析后所得的 Token序列。
? 功能：进行语法检查。 构造语法短语的
表示形式（语法树）
? 说明：语法分析只用到单词的 Token表
示，并不改变单词的 Token表示。
Micro程序结构语法图
Ibegin var, T ;
I,= E
write ( E
read ( I )
) end,
var;
I
C
( E ) +/*
Micro的语义分析
功能：
? 检查语义错误：
没有声明；重复声明； 类型不相容
? 构造符号表；修改 Token表示
符号表 (标识符名，地址，类型）
过程,读入 Token
遇到标识符声明时，检查是否已声明，是则报
错，否则构造标识符的符号表；
遇到标识符定义和使用时，检查是否声明过。
将变量的 Token改为（ $id,entry)形式,entry
表示标识符在符号表中的地址。
Micro的目标代码
? 生成语句的目标代码
表达式的处理
? 检查赋值语句左右类型是否相容
表达式的处理
? 表达式的求值
? 表达式的目标代码生成
? 表达式（中缀）到后缀式的转换
表达式处理涉及的主要数据结构
和符号约定
?DS, 数据栈
?OS, 运算符栈
?RE, 剩余表达式
?Push(s,a), 将 a压入栈 s
?Pop(s,i), 从栈 s中弹出 i个元素
算符的优先关系
1,单目算符 +a,-a
2,指数算符 a?n
3,乘法算符 a * b,a/b
4,加法算符 a + b,a - b
5,关系算符 a < b,a ?b,a =b,
a ?b,a>b,a?b
6,逻辑非 ~b
7,逻辑与 a ? b
8,逻辑或 a ? b
关于优先关系的几点说明
1,优先关系是相对同层算符而言的
2,按括弧层次，里层算符优先
3,编号越大，优先级越低
无括号表达式 求值 算法思想
? 运算分量 N/I, push(DS,N/I)
? 运算符 ?,
L,if OS[top]=[ ] then push(OS,?)
if OS[top]< ? then push(OS,?)
else
goto L；
? RE=[#],
while OS[top] ?[ ] do
? DS[top] 表示表达式的最终值
Process
Process
d1= pop(DS,1) ; d2= pop(DS,1);
op= pop(OS,1) ; v= d2 op d1;
push(DS,v) ;
带括号表达式求值的算法思想
? push(OS,△ )
? 运算分量 N/I和 左括弧（,push(DS,N/I),push(OS,△ )
? 运算符 ?,
if OS[top]=[△ ] then push(OS,?)
if OS[top]< ? then push(OS,?)
else Process
? 右括弧）：
if OS[top]=[△ ] then pop(OS,1)
if OS[top]?[△ ] then Process
? RE=[#],
while OS[top] ?[△ ] do
Process
? DS[top] 表示表达式的最终值
表达式的代码生成
? 目标代码功能,把表达式的值计算出来，
并存到某临时变量，我们称此临时变量
为结果变量。
? 目标代码例：
CODE(10),(-,-,10,T1)
CODE(x),(-,-,x,T1)
CODE(a+10*x):(*,10,x,T1)
(+,a,T1,T2)
表达式代码生成中用到的数据结构和辅助函数
? DS…… 同前
? OS…… 同前
? RE…… 同前
? CODE…… 代码部分
? 格局组成, （ DS,OS,RE,CODE)
? 初始格局,DS,OS,CODE=[ ],RE为初始表达式
? 终止格局,DS只含一个元素（表达式的结果变量）。
OS,RE为空,CODE为被生成的代码部分
? 函数 NewTemp:自定义函数，每调用一次，它将返回一
个新临时变量。
表达式代码生成算法思想
? 算法思想与表达式求值的思想基本一致
? 区别只在于 Process部分
我们只需把 Process中 求值 的部分改为 代码生
成 部分即可,
T:=NewTemp
生成代码,（ ?,DS[top-1],DS[top],T),
// ? = OS[top’]
pop(DS,2)
pop(OS,1)
push(DS,T)
表达式（中缀）到后缀式的转换
? 若用 [ E ]表示中缀表达式 E的后缀表达式，
则定义：
? [ n ] ? n
? [ x ] ? x
? [ (E) ] ? [ E ]
? [ E1 ? E2 ] ? [ E1 ] [ E2 ] ?
? 例子：
1 [a*b+c] ? [a*b] [c] +
? ? [a] [b] * c +
? ? a b * c +
2 [a+b*(c+d)] ? [a] [b*(c+d)] +
? ? a [b] [(c+d)] * +
? ? a b [c+d] * +
? ? a b [c] [d] + * +
? ? a b c d + * +
后缀表达式的特点
? 后缀式中的常量和变量的顺序保持原表
达式中出现的顺序。
? 后缀式中没有括弧
? 后缀式中的算符顺序代表计算顺序
? 后缀式的计算例：
? 2 3 * 4 + 5 * ? 6 4 + 5 *
? ? 10 5 *
? ? 50
中缀式到后缀式的转换原理
? 遇变量名或常量时，将其压入 DS栈中。
? 其它符号的进 OS栈,过程同求值。
? 当 OS栈顶中操作符可处理时：将其压入
DS栈中。即把 Process过程改为
push (DS,OS[top]);
pop (OS,1);
?DS栈作为结果栈（后缀式）
中缀式到后缀式转换的例子
? DS=[] OS=[] RE= a + b * c #
1,a + b * c #
2,a + b * c #
3,a b + * c #
4,a b + * c #
5,a b c + * #
6,a b c * + #
7,a b c * + #
后缀表达式的求值
? 只用到数据栈 DS。
? 思想：
运算分量压栈；
遇到运算符 ?：
v:= DS(top-1) ? DS (top);
pop (DS,2);
push (DS,v)
遇到结束标志＃，求值结束，结果为 DS栈顶。
1,小语言 Micro的定义
2,Micro程序的编译过程
3,表达式的处理
小语言 Micro的定义
? P ? begin VDL;SL end.
? VDL ? VD | VD ; VDL
? VD ? var id, T
? SL ? S | S ; SL
? S ? id:= E | write(E) | read(id)
? T ? integer | real
? E ? id | num
| E + E
| E * E
|(E)
程序例：
begin
var x1:real ;
var z1:real ;
x1,= 0.5 ;
z1,= x1 + 55 ;
write( z1 +5.5 );
read( x1 ) ;
z1,=z1 + x1
end.
Micro的词法分析
? 单词的种类
? Token定义
? 词法分析过程
Micro的词法分析
Micro语言中单词的分类：
? 标识符：字母开头的字母 /数字串
? 整常数：数字开头的数字串
? 实常数：整数,整数
? 保留字,begin end var read write
integer real
? 符号词,+ * ( ),,= ;,
? 控制词,? (换行符）
Micro的词法分析
TOKEN定义：
二元组（单词种类，单词自身值）
? 标识符的 Token,($id,标识符）如 ($id,x)
? 整常数的 Token,($intC,整常数）如（ $intC,5)
? 实常数的 Token,($realC,实常数）如 ($realC,0.5)
? 保留字的 Token,($begin,-),($end,-),($var,-) …
? 符号词的 Token,($plus,-),($mult,-),($LParen,-)…
? 换行符的 Token,($line,-)
Micro的词法分析
? 词法分析过程：
读当前字符流，直至文件结束。如果是：
(1)标识符时判断是保留字还是变量标识
符，构造 Token表示
(2)数字时判断是整型还是实型，构造
Token表示
(3)构造其它合法的符号的 Token表示
(4)遇到非法符号则报错。
Micro的词法分析;; ?
?
?
??
?
l
l
a
a
e
e1z
1x△a
a r
△nib
etirw;5 5+1x=:z 1
x
5.0=
1
=z;)1(dae
r) ;.51z(
,#n d?1
x1z
图 2.2.1 源程序在文件中的表示
e g v r r
rv △,
:
:;
+ 5
V 1 +
e
:
Micro的词法分析
($id,z1)
（ $begin
，－）
($line，
-)
($line，
-)
（ $semi
，－）
（ $assig
，－）
($id,x1)
（ $semi
，－）
（ $semi
，－）
（ $real
，－）
（ $real
，－）
（ $colon
，－）
($line，
-)
($line，
-)
（ $var，
－）
（ $var，
－）
$assig ($realC，
0.5)
（ $colon
，－）
($id,x1)
($line，
-)
($line，
-)
（ $semi，
－）
($intC，
55)
（ $plus
，－）
（ $assig
，－）
($id,x1)($id,z1)
$Lparen
,－ ）
（ $read
，－）
（ $semi，
－）
($realC
,5.5)
$Rparen
，－）
（ $plus
，－）
($id,z1)（ $write
，－）
$Lparen
，－ )
#（ $stop
，－）
（ $end
，－）
($id,x1)（ $plus
，－）
($id,z1)
($id,z1)（ $semi
，－）
($id,x1) $Rparen
，－）
图 2.2.2 词法分析后的 TOKEN表示
Micro的语法分析
? 输入：是词法分析后所得的 Token序列。
? 功能：进行语法检查。 构造语法短语的
表示形式（语法树）
? 说明：语法分析只用到单词的 Token表
示，并不改变单词的 Token表示。
Micro程序结构语法图
Ibegin var, T ;
I,= E
write ( E
read ( I )
) end,
var;
I
C
( E ) +/*
Micro的语义分析
功能：
? 检查语义错误：
没有声明；重复声明； 类型不相容
? 构造符号表；修改 Token表示
符号表 (标识符名，地址，类型）
过程,读入 Token
遇到标识符声明时，检查是否已声明，是则报
错，否则构造标识符的符号表；
遇到标识符定义和使用时，检查是否声明过。
将变量的 Token改为（ $id,entry)形式,entry
表示标识符在符号表中的地址。
Micro的目标代码
? 生成语句的目标代码
表达式的处理
? 检查赋值语句左右类型是否相容
表达式的处理
? 表达式的求值
? 表达式的目标代码生成
? 表达式（中缀）到后缀式的转换
表达式处理涉及的主要数据结构
和符号约定
?DS, 数据栈
?OS, 运算符栈
?RE, 剩余表达式
?Push(s,a), 将 a压入栈 s
?Pop(s,i), 从栈 s中弹出 i个元素
算符的优先关系
1,单目算符 +a,-a
2,指数算符 a?n
3,乘法算符 a * b,a/b
4,加法算符 a + b,a - b
5,关系算符 a < b,a ?b,a =b,
a ?b,a>b,a?b
6,逻辑非 ~b
7,逻辑与 a ? b
8,逻辑或 a ? b
关于优先关系的几点说明
1,优先关系是相对同层算符而言的
2,按括弧层次，里层算符优先
3,编号越大，优先级越低
无括号表达式 求值 算法思想
? 运算分量 N/I, push(DS,N/I)
? 运算符 ?,
L,if OS[top]=[ ] then push(OS,?)
if OS[top]< ? then push(OS,?)
else
goto L；
? RE=[#],
while OS[top] ?[ ] do
? DS[top] 表示表达式的最终值
Process
Process
d1= pop(DS,1) ; d2= pop(DS,1);
op= pop(OS,1) ; v= d2 op d1;
push(DS,v) ;
带括号表达式求值的算法思想
? push(OS,△ )
? 运算分量 N/I和 左括弧（,push(DS,N/I),push(OS,△ )
? 运算符 ?,
if OS[top]=[△ ] then push(OS,?)
if OS[top]< ? then push(OS,?)
else Process
? 右括弧）：
if OS[top]=[△ ] then pop(OS,1)
if OS[top]?[△ ] then Process
? RE=[#],
while OS[top] ?[△ ] do
Process
? DS[top] 表示表达式的最终值
表达式的代码生成
? 目标代码功能,把表达式的值计算出来，
并存到某临时变量，我们称此临时变量
为结果变量。
? 目标代码例：
CODE(10),(-,-,10,T1)
CODE(x),(-,-,x,T1)
CODE(a+10*x):(*,10,x,T1)
(+,a,T1,T2)
表达式代码生成中用到的数据结构和辅助函数
? DS…… 同前
? OS…… 同前
? RE…… 同前
? CODE…… 代码部分
? 格局组成, （ DS,OS,RE,CODE)
? 初始格局,DS,OS,CODE=[ ],RE为初始表达式
? 终止格局,DS只含一个元素（表达式的结果变量）。
OS,RE为空,CODE为被生成的代码部分
? 函数 NewTemp:自定义函数，每调用一次，它将返回一
个新临时变量。
表达式代码生成算法思想
? 算法思想与表达式求值的思想基本一致
? 区别只在于 Process部分
我们只需把 Process中 求值 的部分改为 代码生
成 部分即可,
T:=NewTemp
生成代码,（ ?,DS[top-1],DS[top],T),
// ? = OS[top’]
pop(DS,2)
pop(OS,1)
push(DS,T)
表达式（中缀）到后缀式的转换
? 若用 [ E ]表示中缀表达式 E的后缀表达式，
则定义：
? [ n ] ? n
? [ x ] ? x
? [ (E) ] ? [ E ]
? [ E1 ? E2 ] ? [ E1 ] [ E2 ] ?
? 例子：
1 [a*b+c] ? [a*b] [c] +
? ? [a] [b] * c +
? ? a b * c +
2 [a+b*(c+d)] ? [a] [b*(c+d)] +
? ? a [b] [(c+d)] * +
? ? a b [c+d] * +
? ? a b [c] [d] + * +
? ? a b c d + * +
后缀表达式的特点
? 后缀式中的常量和变量的顺序保持原表
达式中出现的顺序。
? 后缀式中没有括弧
? 后缀式中的算符顺序代表计算顺序
? 后缀式的计算例：
? 2 3 * 4 + 5 * ? 6 4 + 5 *
? ? 10 5 *
? ? 50
中缀式到后缀式的转换原理
? 遇变量名或常量时，将其压入 DS栈中。
? 其它符号的进 OS栈,过程同求值。
? 当 OS栈顶中操作符可处理时：将其压入
DS栈中。即把 Process过程改为
push (DS,OS[top]);
pop (OS,1);
?DS栈作为结果栈（后缀式）
中缀式到后缀式转换的例子
? DS=[] OS=[] RE= a + b * c #
1,a + b * c #
2,a + b * c #
3,a b + * c #
4,a b + * c #
5,a b c + * #
6,a b c * + #
7,a b c * + #
后缀表达式的求值
? 只用到数据栈 DS。
? 思想：
运算分量压栈；
遇到运算符 ?：
v:= DS(top-1) ? DS (top);
pop (DS,2);
push (DS,v)
遇到结束标志＃，求值结束，结果为 DS栈顶。
