第3,4课 一个简单的语法制导翻译器

第四章语法制导的翻译在3.7节用Yacc写的例子中，我们看到一种有用的描述形式：语言结构的属性附加在代表语言结构的文法符号上，这些属性值由附加在文法产生式的语义动作来计算，这些语义动作在归约对应的产生式时进行计算，由此得到结果。

这种描述形式可用来描述编译器的语义分析，因此本章系统地研究这种称之为“语法制导下的语言翻译”的描述方法及其实现。

它的语义动作（有时称为语义规则）的计算可以产生代码、把信息存入符号表、显示出错信息、或完成其它工作。

语义规则的计算结果就是我们所要的记号流的翻译。

本章讨论语义规则和产生式相联系的两种方式：语法制导的定义和翻译方案。

语法制导定义是较抽象的翻译说明，它隐蔽了一些实现细节；而翻译方案陈述了一些实现细节，主要是指明了语义规则的计算次序。

在第五章说明语义检查和第七章描述中间代码生成时，大量使用这两种方法。

本章还讨论语法制导定义和翻译方案的实现方法。

概念上的方法是，首先分析输入的记号串，建立分析树，然后从分析树得到描述结点属性间依赖关系的有向图，从这个依赖图得到语义规则的计算次序，然后进行计算，最终得到翻译的结果。

实际的实现并不需要按上面步骤逐步进行，本章将讨论几种不同限制下的实现方法。

4.1语法制导的定义语法制导的定义是上下文无关文法的推广，其中每个文法符号都有一个属性集合，它分成两个子集，分别叫做该文法符号的综合属性集合和继承属性集合。

如果我们把分析树上的结点看成是保存对应文法符号的属性的记录，那么属性对应记录的域。

属性可以表示任何东西：串、数、类型、内存单元，或其它想表示的东西。

分析树结点的属性值由该结点所用产生式的语义规则定义。

在语法制导定义中，我们把其中的文法称为基础文法。

本节介绍语法制导定义的形式及其概念上的实现模型。

4.1.1语法制导定义的形式在语法制导定义中，每个文法符号有一组属性，每个文法产生式A →α有一组形式为b := f (c1, c2, …, c k )的语义规则，其中f是函数，b和c1, c2, …, c k是该产生式的文法符号的属性，并且：（1）如果b是A的属性，c1 , c2, …, c k是产生式右部文法符号的属性或A的其它属性，那么b叫做文法符号A的综合属性。

语法翻译法的实施步骤1. 简介语法翻译法是一种用于将一种程序设计语言转换为另一种程序设计语言的技术。

它通过将源语言的语法规则映射到目标语言的语法规则，实现源语言程序到目标语言程序的转换。

本文将介绍实施语法翻译法的具体步骤。

2. 步骤以下是实施语法翻译法的一般步骤：步骤1: 确定源语言和目标语言在开始进行语法翻译的过程中，首先需要确定源语言和目标语言。

源语言是我们要转换的程序设计语言，目标语言是将源语言转换成的语言。

确切地了解源语言和目标语言的语法规则和语义规则非常重要。

步骤2: 词法分析词法分析是将源程序分解为一个个的单词（Token）的过程。

在这一步骤中，我们需要编写一个词法分析器，它将源代码作为输入，并识别出其中的单词。

每个单词都包含一个词法类型和一个对应的字符串值。

示例：源代码: x = 5 * 2;词法分析输出：- 词法类型: 标识符，字符串值: x- 词法类型: 赋值运算符，字符串值: =- 词法类型: 数字，字符串值: 5- 词法类型: 运算符，字符串值: *- 词法类型: 数字，字符串值: 2- 词法类型: 分号，字符串值: ;步骤3: 语法分析语法分析是将词法分析器输出的单词流转换为语法树的过程。

在这一步骤中，我们需要编写一个语法分析器，它将识别源代码中的语法规则并生成一个语法树。

语法树用于表示程序的结构和层次关系。

示例：源代码: x = 5 * 2;语法树：=/ \\x */ \\5 2步骤4: 语法制导翻译语法制导翻译是基于语法树进行语法规则的翻译过程。

在这一步骤中，我们需要根据源语言和目标语言的语法规则，编写语法制导翻译器，它将遍历语法树并根据语法规则翻译每个节点。

示例：源代码: x = 5 * 2;目标语言: Python翻译结果: x = 5 * 2步骤5: 语义分析和翻译语义分析是对源代码进行静态语义检查的过程。

在这一步骤中，我们需要编写语义分析器，它将检查源代码是否符合源语言和目标语言的语义规则。

语法制导的翻译 语义分析的任务：语义分析的输入是语法分析的输出（分析树），输出是中间代码，但同时它还完成了很多语义处理工作。

 语义检查：如，类型、运算、维数、越界等。

 语义处理：如，变量的存储分配、表达式的求值、语句的翻译（中间代码的生成）等。

 总目标：生成等价的中间代码。

 语义分析的主流技术：语法制导翻译技术。

4.1 语法制导的翻译静态语义分析通常包括：① 类型检查。

② 控制流检查。

控制流语句必须使控制转移到合法 的地方。

③ 一致性检查。

④ 相关名字检查。

有时，同一名字必须出现两次或 多次。

例如，Ada语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾， 编译程序必须检查这两个地方用的名字是相同的。

⑤ 名字的作用域分析语法制导的翻译动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。

语法制导的翻译 语义动作的计算是在对应产生式被归约时进行。

 语义规则和产生式相联系的两种方式 语法制导定义 对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译。

 语法制导的翻译方案 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。

4.1 语法制导的定义例 简单台式计算器的语法制导定义产 生 式 语 义 规 则 L → E nprint (E .val ) E → E 1 + TE .val := E 1 .val + T.val E → TE .val := T.val T → T 1 * FT.val := T 1.val * F.val T → FT.val := F.val F → (E )F.val := E.val F → digit F.va l := digit .lexval 属性文法（也称属性翻译文法） K nuth在1968年提出 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。

2017年中国科学技术大学0812计算机科学与技术考研专业目录及考试科目一、报考说明：接收推免生及统考生。

二、专业介绍：本学科培养学生德、智、体全面发展，适合于在高等学校、科研机构、企事业单位从事计算机系统结构相关领域的教学、科研和应用开发等工作的高层次专门人才。

掌握计算机学科方面坚实的基础理论和系统的专门知识，了解本学科的发展方向及前沿动向，具备较强的综合运用所学理论知识从事科学研究工作和独立承担专门技术工作的能力，有严谨求实的科学作风和良好的科研道德，开拓进取的创新精神，团队合作和敬业精神。

熟练掌握一门外国语，能阅读本专业的外文资料并撰写专业领域外文文章。

具有较强的综合能力、语言表达能力及写作能力；具有健康的体魄和良好的心理素质。

本学科点具有计算机系统结构、计算机软件与理论、计算机应用技术以及信息安全4个二级学科。

相应的研究方向如下：1、计算机系统结构计算机系统结构是计算机科学技术最活跃的研究领域之一，特别是最近几年，随着高性能计算机的广泛研究和应用、计算机整体设计关键技术的突破、计算机网络体系结构的迅速发展，计算机系统结构的研究出现了新的热点和重大进展。

在微处理芯片体系结构方面主要研究新型微处理芯片体系结构及其编程技术，可重构的片上并行体系结构，通用微处理芯片设计技术，指令级并行关键技术和嵌入式系统整体设计方法，多处理器体系结构等；在计算机体系结构方面主要研究新型高效能并行计算机体系结构、模型及其关键技术，包括软件技术、超高扩展高密度计算技术、高可用集群中间件技术、可重构计算等，“并行结构-并行算法-并行编程”研究一体化；在网络及分布式计算方面主要研究新型网络体系结构和协议，网格计算平台及应用，对等网络、无线网络和移动计算等。

2、计算机软件与理论计算机软件与理论是指由计算机科学理论和研究、开发计算机软件所涉及的理论、方法、技术所构成的学科，是信息科学的核心研究领域之一，是计算机学科用来为国民经济、国防建设、人民生活服务的工具和基础。

语法制导翻译
语法制导翻译是一种将源语言（通常为自然语言）的语法结构与目标语言的语法结构相对应的翻译方法。

它通过语法分析器和语法制导翻译器来实现。

在语法制导翻译中，源语言和目标语言的语法规则被定义成一个或多个上下文无关文法。

语法制导翻译的主要思想是在语法分析树中嵌入翻译动作，并通过语法制导翻译器将源语言转换为目标语言。

语法制导翻译器的主要任务是对每个语法分析树节点进行翻译动作的定义，并将这些翻译动作与语法分析器的分析过程相结合，最终生成目标语言的语法结构。

语法制导翻译是机器翻译领域的一种重要研究方向，它可以有效地解决自然语言翻译中的语言差异和歧义问题。

同时，它也是编译原理、计算机语言学等领域中的基础性问题。