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

第六章 翻译原理 “翻译”— 由一对字符串组成的对偶集合。 编译程序 -- <源程序，目标程序> 编译过程： 1. 词法分析 -- < 字符串，单词> 2. 句法分析 -- <单词的字符串，树表示的字符串> 3．代码生成 -- <树表示的字符串，机器/汇编语言 > 定义翻译的两种基本方法： 翻译式；转换器 翻译式： 模仿语言的文法定义方法，定义一个对偶系统（也是一个文法）,使在句子的推导过程中，相应于每个句型，同时也推算出其输出句型（翻译句型）。这样，在派生出句子时，也同时产生了其翻译句。 转换器：模仿语言的自动机识别方法，但在自动机的每次动作中，还发送一个有限长度的输出字符串。 $6 .1 翻译的形式化 一． 翻译的一般定义 设 L1 T*，L2 ∑*，从 L1 到 L2 的翻译是从 T *→ ∑* 的一个映射关系。 x∈L1y∈L2翻译系统映射H 如果对于输入句子 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)...