形式语言自动机——翻译原理.doc

第六章 翻译原理
“翻译”— 由一对字符串组成的对偶集合。
编译程序 -- <源程序，目标程序>
编译过程： 1. 词法分析 -- < 字符串，单词>
2. 句法分析 -- <单词的字符串，树表示的字符串>
3．代码生成 -- <树表示的字符串，机器/汇编语言 >

定义翻译的两种基本方法： 翻译式；转换器

翻译式： 模仿语言的文法定义方法，定义一个对偶系统（也是一个文法）,使在句子的推导过程中，相应于每个句型，同时也推算出其输出句型（翻译句型）。这样，在派生出句子时，也同时产生了其翻译句。
转换器：模仿语言的自动机识别方法，但在自动机的每次动作中，还发送一个有限长度的输出字符串。

$6.1 翻译的形式化
一． 翻译的一般定义
设L1 ÍT*，L2 Í∑*，从L1 到L2 的翻译是从T *→ ∑* 的一个映射关系。
如果对于输入句子x，存在（x, y）在映射H中，则称句子y为x的输出。
注： 一般的翻译可能不止一个输出，但对程序语言的翻译总是单值输出（最多容许一个输出）。

例一：简单翻译 （书P222）
英文小写字母 –〉ASCII码（一一对应）

例二：将中缀表达式翻译为等价的前缀、后缀波兰表达式
中缀： a+b , (a+b)*(c+d)
前缀： +ab , *+ab+cd
后缀： ab+ , ab+cd+*

二． 句法制导（引导）的翻译式
思路：类似于用有限条文法规则导出语言的无限条句子，也可运用有限条文法规则定义由无限个成员组成的翻译.
句法制导（引导）的翻译式：
模仿语言的文法定义来定义一个对偶系统, 使得这些对偶的集合符合给定的翻译要求。
直观的说，“翻译式”（翻译格式）类似于在原文法的每条产生式上粘附着一个“翻译元素”(Translation Element)的文法。

产生式 – 用于推导输出句型
翻译元 – 推算出相应于输入句型的输出句型
例：定义翻译 { （w，w ）| w ∈(a, b) *}}

(生成式, 翻译元)
1.
(A -> aA, A = Aa )
2.
(A --> bA, A = Ab)
3.
(A --> a, A = a)
4.
(A --> b, A = b)

类似于句子的推导过程（句型推导），将翻译的推导过程称“翻译型”。
初始翻译型 （A，A）
ð (aA , Aa )
ð (abA , Aba )
ð (abb, bba )

例： 中缀算术表达式到前缀波兰表达式的翻译

(生成式, 翻译元)
1.
(S --> S+A, S = +SA)
2.
(S --> A, S = A)
3.
(A --> A*B, A *AB)
4.
(A --> B, A = B)
5.
( B --> (S), B = S)
6.
(B --> i, B = i )
对于输入串 （i+i）*i, 按最左推导有
初始翻译型 （S，S）
ð (A, A)
ð (A*B , *AB )
ð (B*B , *BB)
ð ( (S)*B , *SB)
ð ( (S+A)*B , *+SAB)
ð ( (A+A)*B , *+AAB)
ð ( (B+A)*B , *+BAB)
ð ( ( i +A)*B , *+ i AB)
ð ( ( i +B)*B , *+ i BB)
ð ( ( i + i )*B , *+ i i B)
ð ( ( i + i )*i , *+ i i i )

定义：句法制导翻译式为五元组H = (N,T, ∑, R , S)
其中：
N 非终结符 T 输入字符集合（终结符），
∑ 输出符号 S 起始符
R 规则的有限集合，形如
Aàα,β α∈(NÈT)*, β∈(NÈ∑)*
且β中的非终结符是α中非终结符的一个排列。
如 A à B(1)aAB(2), B(2)AaB(1)
翻译式H产生的全部翻译的集合为：
t(H) = {(x，y) | （S，S）=> * (x，y), x∈T*, y∈∑* }

定义6.1.3: 简单句法制导翻译式
设H = (N, T, ∑, R , S)是句法制导翻译式，若对于R中的每个规则Aàα,β都有α,β中所有非终结符的排列次序相同，则称H为简单句法制导翻译式。它定义的翻译称为简单句法制导翻译。
例： 规则R是简单句法制导翻译
规则
E --> E(1)*E(2), *E(1)E(2)
E --> F, F
F --> i, i

$6.2 转换器
转换器实质是一种带输出的自动机。该自动机的输入端在接收到字符串α的同时，在它的输出端能够输出α的翻译β。
一． 有限转换器
定义：有限转换器为六元组， M=(Q, T, ∑,δ, q0, F)
其中：Q 有限状态集合
T 输入字母表，
∑ 输出字母表
q0 初始状态，q0∈Q
F: 终止状态集 FÍQ
δ 从 Q×（T∪{ε}）到Q×∑* 的子集的映射
(非确定的自动机)
定义：当上面定义中的δ满足下述条件时， M便是一个确定的转换器。
对 "q∈Q， "a∈T, 有
⑴ δ(q，a ) 只有一个选择，且δ（q，ε）＝φ
或者
⑵δ(q，ε ) 只有一个选择，且δ（q，a）＝φ
有限转换器的格局：
q —当前状态
格局(q, α,β) α— 当前待输入的字符串
β—当前已输出的字符串
其中q∈Q , α∈T*，β∈∑*
例： 若有 (p，x) ∈δ（q，a）
则有 (q, aα, β) ├ (p, α, βx)。
若有 (q0, α, ε) ├ * (q, ε, β), q∈F，
则称β是α的输出。
有限转换器M的所有输出字符串的集合称为M的翻译。
t(M) = {(α,β) | (q0, α, ε)├ * (q, ε, β)且 q∈F，}
例：设计一个有限转换器M, 可以识别算术表达式，并能从表达式中删除多余运算符。
E à a+E | a-E | +E | -E |a

例如: --a+--a ├ a+a
二． 下推转换器
下推转换器是有输出的下推自动机。
定义：下推转换器M是八元组，M＝（Q，T，Γ，∑，δ，q0，z0，F）
其中： Q：有限控制器的状态集合
T：有限输入字母表
Γ：有限下推栈字母表
∑ 输出字母表
δ：转换函数
q0：初始状态，q0∈Q
z0：下推栈的起始符号，z0∈Γ
F：终态集合，F Í Q
δ：Q ×（T∪{ε}）× Γ → Q×Γ*×∑*的子集的映射。

下推转换器的格局： (q, ω,α,β)
q —当前状态
格局(q ω,α,β) ω--当前待输入的字符串
α—当前栈中的内容
β—已输出的字符串

例： 若有 (p，α,x) ∈δ（q，a,Z）
则有 (q, aω,Zγ, β) ├ (p, ω, αγ, βx)。
终态接受：
t(M) = {(α,β) | (q0, α,Z0,ε)├ * (q, ε, γ, β)
且 q∈F，γ∈Γ*}
空栈接受：
tε(M) = {(α,β) | (q0, α,Z0,ε)├ * (q, ε, ε, β) }

例：设计下推转换器M, 将ω翻译为它的逆
tε(M) = {(ω, ω) | (q0, ω,Z0,ε)├ * (q, ε, ε, ω)，
ω ∈{a,b}*}
思路：(1). 将输入字符不断进栈，直至输入为空，其间不输出。
(2). 当输入为空时，开始退栈并输出之，直至栈空。

例：将前缀表达式变后缀表达式。
M=( {q}, {+,*,a}, {+,*,a}, {+,*,a},δ, q, E, {q} )
δ（q，α,E）= {（q，ε, a）}
δ（q，+,E）= {（q，EE+, ε）}
δ（q，*,E）= {（q，EE*, ε）}
δ（q，ε,+）= {（q，ε, +）}
δ（q，ε,*）= {（q，ε, *）}
例如：(q, +*aaa,E,ε)├ * (q, ε, ε, aa*a+)
(q, +*aaa,E,ε) ├ (q, *aaa,EE+,ε)
├ (q, aaa,EE*E+,ε)
├ (q, aa,E*E+,a)
├ (q, a,*E+,aa)
├ (q, a,E+,aa*)
├ (q, ε,+,aa*a)
├ (q, ε, ε,aa*a+)

定理：简单句法制导翻译式与下推转换器之间是等价的。

证明略。
6.3 词法分析
编译器的扫描或词法分析阶段可将源程序读作字符文件并将其分为若干个记号（token ）,即单词。
典型的Token：
关键字: 如if 和while ，它们是字母的固定串；
标识符: 通常由字母和数字组成并由一个字母开头；
特殊符号: 如算术符号+和*、一些多字符符号，如> = 和< >。
在扫描过程中, 最主要的格式说明和识别方法是正则表达式和有穷自动机。有穷自动机是对由正则表达式给出的串格式的识别算法。
例: 带有出错转换的标识符的有穷自动机

例: 浮点数的有穷自动机
6.3.1 用代码实现有穷自动机
例： 模拟接受标识符的D FA 。

模拟这个D FA, 最简单的方法是下面的伪代码：
{ starting in state 1 }
if the next character is a letter t h e n
advance the input;
{ now in state 2 }
while the next character is a letter or a digit do
advance the input; { stay in state 2 }
end while;
{ go to state 3 without advancing the input }
accept ;
else
{ error or other cases }
end if;
这段代码使用代码中的位置来隐含状态。适用于没有太多的状态（要求有许多嵌套层）且D FA 中的循环较小的情况。类似的代码可用来编写小型的扫描程序。
该方法有两个缺点：它是特殊的，即必须用不同的方法处理各个DFA ，而且将每个DFA 翻译为代码的算法也较难。其次：当状态增多时，以及当任意路径增多时，代码会变得非常复杂。

例：接受注释（C 风格的注释）的D FA可用以下的编码来实现.
{ state 1 }
if the next character is “ / ” t h e n
advance the input: { state 2 }
if the next character is “*” then
advance the input ；{ state 3 }
done := false;
while not done d o
while the next input character is not “*” d o
advance the input ；
end while;
advance the input ；{ state 4 }
while the next input character is “*” d o
advance the input;
end while;
if the next input character is “ / ” then
done : = true ;
end if;
advance the input;
end while;
accept; { state 5 }
else { other processing }
end if;
else { other processing }
end if;

这样做的复杂性已大大增加了，且还需要利用布尔变量done 来处理涉及到状态3和状态4 的循环。

一种更好的实现方法是：利用一个变量保持当前的状态，并将转换写成一个双层嵌套的case 语句而不是一个循环。其中第1 个case 语句测试当前的状态，嵌套着的第2 层测试输入字符及所给状态。

例如，标识符的D FA 可翻译为下面的的代码模式：
state := 1; {start }
while state = 1 or 2 d o
case state of
1: case input character of
letter: advance the input ；
state := 2;
else state := … {error or other};
end case;
2: case input character of
letter,digit: advance the input ；
state := 2; {actually unnecessary }
else state := 3;
end case;
end case;
end while;
if state = 3 then accept else error ；
接受C 风格注释的DFA可由以下的编码实现：
state := 1; {start }
while state = 1 to 4 d o
case state of
1: case input character of
“/”: advance the input ；
state := 2;
else state := … {error or other};
end case;
2: case input character of
“*”: advance the input ；
state := 3;
else state := … {error or other};
end case;
3: case input character of
“*”: advance the input ；
state := 4;
else advance the input {and stay in state 3};
end case;
4: case input character of
“/”: advance the input ；
state := 5;
“*”: advance the input {and stay in state 4};
else advance the input;
state := 3;
end case;
end case;
end while;
if state = 5 then accept else error ；

此外,还可将DFA 表示为二维转换表（transition table ），由表示转换函数T 值的状态和输入字符来索引：
例如：标识符的DFA 可表示为如下的转换表：

在表格中，假设列中的第1 个状态是初始状态。空表项表示未在DFA 图中显示的转换（即：它们表示到错误状态或其他过程的转换）。
但是，这个表格尚未指出哪些状态正在接受以及哪些转换不消耗它们的输入。可另将一些信息添加到上面的转换表中（指出接受状态并指出“未消耗输入”的转换）。
例： C 注释的DFA 表格:
相应代码:
state := 1;
ch : = next input character;
while not Accept[state] and not error[state] do
newstate := T [state, ch];
if Advance [state, ch] then ch := next input char;
state := newstate;
end while;
if Accept [state] then accept;

类似的算法被称作表驱动（table driven ），因为它们利用表格来引导算法的过程。
表驱动的优点：代码的长度缩短了，相同的代码可以解决许多不同的问题，代码较易维护。
表驱动的缺点：表格会变得非常大，从而使程序要求使用的空间也变得非常大。(实际上，数组中的许多空间都是浪费的)。
$ 6.4 句法分析

分析句子的结构： 自上而下的分析 à 左解析
自下而上的分析 à 右解析

例： 文法 G = ({S, B }, {a, b }, P, S )
产生式按序号分别为：
1. Sà bBS
2. Sà b
3. Bà SaB
4 Bà ab
最左推导： S Þ1 b B S
Þ3 b SaB S
Þ2 b baB S
Þ4 b ba ab S
Þ2 b ba ab b
最左推导所用的产生式序号 13242 称为 bbaabb 的左解析。

最右推导：S Þ1 b B S
Þ2 b B b
Þ3 b SaB b
Þ4 b Sa ab b
Þ2 b b a ab b
序号序列之逆 24321 称为 bbaabb 的右解析(自下而上的归约)。
可通过翻译式找左解析、右解析。

定义6.4.1. 设2型文法G=(N, T, P, S), 生成式序号为1, 2, … n
H=(N, T, {1, 2, …, n} , R, S)
其中R为Aàa, b 若Aàa是P中序号为k的生成式, 则b是ka’且a’是删去终结符的a.

例: G的生成式为
1. S àbBS
2. S àb
3. B àSaB
4. B àab
则H=({S, B}, {a, b}, {1, 2, 3, 4}, R, S )
其中R为
1) S àbBS, 1BS
2) S àb, 2
3) B àSaB, 3SB
4) B àab, 4
用最左推导, 有bbaabb的左解析为
(S, S) Þ ( b B S, 1BS)
Þ ( b Sa B S, 1 3S BS)
Þ ( b b a B S, 1 3 2 BS)
Þ ( b b a ab S, 1 3 2 4 S)
Þ ( b b a ab b, 1 3 2 4 2)

同理, 可构造右解析的翻译式
右解析 Aàa, b
若Aàa是P中序号为k的生成式, 则b是a’k, 且a’是删去终结符的a.
1) S àbBS, BS1
2) S àb, 2
3) B àSaB, SB3
4) B àab, 4

(S, S) Þ ( b B S, BS1 )
Þ* ( b b a ab b, 2 4 3 2 1)

左解析器的构造: 可用与简单句法制导翻译式等效的不确定下推转换器, 将句子翻译成它的左解析。该不确定下推转换器即称左解析器。
构造方法：设2型文法G=(N,T, P, S), 生成式序号为1, 2, … , n
M=({q0}, T, NÈT, {1, 2, …, n} , d, q0, S, f)
如有Aàa, b 序号为k
则d（q0, e, A）含有（q0, a, k）
对aÎT, d（q0, a, a）＝{ (q0, e, e）}

例： 对下面生成式
1) S àbBS
2) S àb
3) B àSaB
4) B àab 构造左解析器
M=({q0}, {a, b}, {S, B, a, b}, {1, 2, 3, 4} , d, q0, S, f)
其中
d（q0, e, S）＝{（q0, bBS, 1）, （q0, b, 2）}
d（q0, e, B）＝{（q0, SaB, 3）, （q0, ab, 4）}
因为a,b ÎT,
\ d（q0, a, a）＝{ (q0, e, e）}
d（q0, b, b）＝{ (q0, e, e）}
(q0, bbaabb, S, e) |- * (q0, e, e, 1 3 2 4 2 )

右解析器 ― 略。