编译原理第一周

​

前言

1.Compiler(编译器)：将计算机不能识别的高级语言翻译成能够识别的低级语言(其中低级语言大多数为汇编语言，少数为机器语言)。

2.Java语言的源程序：无法枚举的集合。通过编译器把Java语言翻译成统一的低级语言，是一件很困难的事。

3.中文翻译成英文往往存在误差，但严谨的计算机高级语言一定要配有编译程序，必须要做到百分百正确。

为什么编译程序能做到百分百正确？首先语言定义要正确。其次限制越多、翻译越准确。

4.编译程序是一个系统软件，不是应用软件。

5.形式语言/形式化描述技术：用于描述无法枚举的源程序。

6.本栏以PL/0语言为例，学习编译原理。

7.语言的限制越多，用户越不好用，但翻译程序越好写。

绪论Introduction

对于翻译程序、汇编程序、编译程序，清华大学出版社《编译原理》曾言：

​

从书中可提炼出三点：

        编译程序很重要，且往往不唯一。

       以语言的翻译程序作为基础，根据翻译源和目标的不同，可延伸出汇编程序和编译程序。

        汇编程序：汇编语言-->机器语言；编译程序：高级语言-->低级语言。

翻译程序

把一种语言书写的程序翻译成另一种语言书写的程序。往往为自然语言（如法语、中文等）或特定领域语言（如科技、法律、金融等，当然也包括编程语言~）

汇编程序和编译程序的基础。

读者可能会想，在翻译过程中，经常出现向汇编、机器语言等低级语言的翻译过程，这种翻译程序是否必须通过低级语言编写？答案是不一定，可以使用高级语言编写，如java。

汇编程序

汇编程序不是用汇编语言写的程序，而是对汇编语言所写的源程序进行翻译。翻译为由机器语言所写的目标程序。

编译程序

编译程序将高级语言程序翻译为低级语言程序。是高级语言和低级语言的桥梁。

​

编译程序考虑对于程序员透明的操作、在黑箱中的操作(怎么运行、怎么分配内存空间？) 这些方面。对于平常的操作，以赋值为例，编译程序考虑的就是赋值背后深层底层的操作，涉及到地址、内存等等。

​

高级语言程序执行步骤(双阶段)

        第一步：用一个编译程序把高级语言翻译成机器语言程序；(下图1.2处理过程)

        第二步：运行翻译的机器语言程序求得结果。

​

既然提到编译程序，那也说明一下编译器吧。首先我们要明确的一点是：编译器不是硬件，是软件。 主要作用是将源代码（高级语言）转换成目标代码（汇编语言或机器语言），为计算机执行程序提供便利。它和编译程序的概念大致相同，但不完全相同。

一般来说，编译器一般是指完整的编译系统，包括预处理、源码编译、链接等多个步骤，而编译程序则更多的指的是执行单一编译过程的程序。

编译器包括多个步骤，可以将源代码进行多次转换和处理，以生成可执行代码。而编译程序通常只包括最基本的编译工具，仅能将源代码编译为目标代码的指定格式。

解释程序

对源程序语句逐条翻译，边解释边执行直至得到执行结果，不产生目标程序，这样的翻译程序就称为解释程序。没有目标代码，直接输出计算结果。

相关概念

宿主机(host machine)

        执行编译程序的机器

目标机(object machine)

        执行编译程序所产生目标代码的机器

例如，一个编译程序可以将 C 语言源代码编译成 x86 架构的目标代码，这时宿主机是编译程序所运行的计算机，而目标机是指一台 x86 架构的计算机。如果将同一份源代码编译成 ARM 架构的目标代码，那么目标机就是指一台 ARM 架构的计算机。

编译过程概述

例子

举一个例子：I am a teacher. 我们看一下编译的过程：

        1.词法分析：先识别切分单词。即检测I 、am 、a 、teacher四个单词。

        2.语法分析：判断一个一个单词能否组成正确的句子，注意是合法的句子。比如：I am a teacher.有主语、谓语、定冠词、名词，则这句话完整合法，通过了语法分析检验。

        3.语义分析+中间代码生成：根据句子含义进行初步翻译，发现“我是一个老师”，语义正确，简而言之就是：是一句人话。不是人话的例子如：“我被馒头吃了”。

注意，这种实际的语言要远远比计算机语言复杂：多义、双关、幽默。

        4.优化：在本例中，优化指的是对译文进行修饰。

        5.目标代码生成：在本例中，即写出最后的译文。

其中，老师写成I am a tercher.引起了我的兴趣，但是老师没有解释，作者在此解释一下：

如果你要将"I am a tercher"编译成英文，则会在词法分析阶段报错，因为"tercher"这个单词在英语中是不存在的，所以这个单词会被视作错误的符号（或单词符号无法识别） 。在语法分析之前，词法分析的任务是将输入文本分解成词法单元。因此，词法分析不仅仅是拆分，还要判断这些单词符号是否正确。如果形式不正确，就会在词法分析阶段报错。

作者又想到别的情况Iamateacher，这种情况词法分析是不报错的，在此解释一下：

如果输入"Iamateacher."，在词法分析阶段，程序会把"Iamateacher."拆分成"I"、"am"、"a"、"teacher"和"."这些词法单元。程序会认为"I", "am", "a", "teacher"和"."都是一个完整的词法单元。在这种情况下，因为"teacher"是一个合法的单词，所以不会产生任何错误。但是，程序依旧会把"."看做一个单独的词法单元，而不是将它视为"teacher"的一部分。

也就是说 ，词法分析很智能，相当于自动切分单词，而且必须是现实中存在的单词，不管这句话有多少空格，它都不管，最后切分的内容早就忽略所有空格了。

综上，给出编译的各个阶段(有时把语义分析和中间代码生成合并)：

​

编译阶段

词法、语法、语义分析

        编译原理中编译器是如何具体进行词法、语法、语义分析的？

        编译器设计与实现是计算机科学中的一个复杂且有趣的领域。一个编译器通常会执行以下步骤将源代码转化为中间代码：

1. 词法分析（Lexical Analysis）:

​

​
- 该阶段将源代码转化为一系列的令牌token。
- 使用工具如lex、flex或手工编写的扫描器来识别和提取令牌。
- 常用算法：有限自动机。
- 输出：令牌流。

关于字符，可分为五种类型：

        保留字(关键字)、标识符(如变量)、算符(运算符，包括=)、界符(如括号)、常数

2. 语法分析（Syntax Analysis）:

​
- 这一阶段使用令牌流并将其转化为抽象语法树（Abstract Syntax Tree, AST）或其他中间表示。
- 使用工具如yacc、bison或手工编写的解析器。
- 常用算法：LL、LR、SLR、LALR等。
- 输出：抽象语法树或其他中间表示。

也就是说，语法分析就是将词法分析传过来的令牌流转化成语法树，也就是将程序、语句、表达式都识别到位、分配到位，你是加法，我就记上算符。如果你是X=X+，这就不符合表达式的语法，不能通过语法检验。如果是X=X+1，那么就表示该表达式语法上正确，它是一个表达式，继续进行下一步语义分析。

"自顶向下做推导，自底向上做归约"是指在语法分析阶段的两种不同的处理方法。

自顶向下推导是一种从语法的高层到底层的分析方法，从起始符号开始，逐渐推导出各个产生式的过程。该方法通常采用递归下降分析或预测分析等算法，特点是易于理解和实现，但容易产生回溯和歧义。

自底向上归约是一种从语法的底层到高层的分析方法，从词法分析器输出的单词流开始，逐渐合并成较大的语法单元，最终合成起始符号。该方法通常采用LR分析、SLR分析或LALR分析等算法，特点是具有高效性和语法分析能力强的优点。

语法分析属于半形式化，比语义分析复杂。也是编译过程中最为重要的部分。

​

3. 语义分析（Semantic Analysis）:

​
   - 这是检查程序语义正确性的阶段，包括类型检查、名称解析、作用域检查等。
- 使用AST或其他中间表示。
- 可能会引用消解信息、类型信息对AST进行更改或注释，以捕获关于源程序的更多信息。
- 输出：注释后的AST。

语义分析给AST每个阶段附加语义规则， 让编译器去理解。通过执行每个节点附带的语义规则，机器就能够知道程序、语句、表达式的含义。进而分析这些程序、语句、表达式的含义是否正确。(先给它们赋予它们本身的含义，然后再去检验它们的含义是否正确，这是好理解的对叭)

消解信息用于分析变量的作用域，类型信息用于分析变量的数据类型是否正确。它们作为语义分析获得的信息的一部分，会被注释到原本语法分析产生的AST抽象语法树中，这样的AST就被称为带有标准信息的AST，能够更好地表达源代码的含义。

执行流程

具体来说，以下是编译器如何进行上述三个阶段的细节：

1.词法分析

扫描器按顺序读取输入字符。
使用正则表达式或有限自动机来匹配关键字、操作符、标识符等。
每次成功匹配时，都会生成一个令牌，并继续扫描下一个令牌。

2. 语法分析

解析器读取令牌流。
使用文法（通常是上下文无关文法）来确定如何构建AST。
例如，考虑一个简单的算术表达式a + b * c。解析器将首先识别b * c是一个表达式，然后再认识到整体a + (b * c)是一个表达式，因此正确地保留了操作符的优先级。

3. 语义分析

在这个阶段，编译器可能会为每个变量创建一个符号表条目，其中包含其类型、作用域等信息。
对于诸如int a = "hello";这样的语句，即使在语法上是正确的，但在语义分析阶段会被识别为错误，因为字符串不能赋给整数类型的变量。
语义分析还可以包括其他任务，例如确保函数在调用前已被声明，或检查变量在使用前已被初始化等。所以作者目前认为，语义分析就是在做题或者分析的时候人工需要考虑的可能出现的问题，比如检查一下数据类型是否正确匹配等等。也就是说，程序中大部分存在的能被编译器检查出来的错误，基本上都是新手常犯的常见错误。

名词解释

以下是对上述出现陌生概念的简要说明：

关于token

在系统开发和编译原理中，尽管“token”这个词在两者中都有其特定的意义，但这两个上下文中的token实际上是不同的概念，并且在设计和目的上都有所区别。它们的相似之处仅在于，两者都代表了某种有意义的“单位” 。

3.二者关联性：

虽然这两种token在设计和目的上都有所不同，但它们都可以被看作是“代表某种信息或身份的标识符” 。在系统开发中，token代表了用户的身份和权限；而在编译原理中，token代表了源代码中的一个词法元素。然而，除了这种抽象的相似性之外，两者在实际应用和具体细节上并没有直接的关联。

这两种token的相似之处仅在于名称和它们都代表了某种“信息单元”的概念，但它们在不同的上下文中有完全不同的定义和用途。

中间代码、优化、目标代码

中间代码

​

​

简而言之，中间代码存储一系列记号，常用“四元式”形式表示，如上图，运算对象1为运算符左操作数，运算对象2为运算符右操作数。四元式有以下优点：

因此，四元式在编译器中被广泛使用，但并不是最常用的中间代码表示方式。 其他常用的中间代码表示方式包括三元式、抽象语法树等。选择中间代码表示方式需要考虑具体的情况和需要，没有一种万能的最常用方式。

为什么会用到中间代码？

1.有一些优化在高级语言中无法进行，所以一般都在中间层做优化。

中间层优化可以针对特定的硬件和架构进行优化，例如编译器优化、汇编优化、CPU微架构优化等等，这些优化可以提高程序的性能和效率。同时，中间层优化也可以将代码进行一些转换和重构，以使代码更容易理解和维护。在高级语言中，存在一些语言特性和限制，无法获得与中间层优化相同的效果，因此中间层优化可以弥补这些不足。

2.中间代码的使用可以减少编译器的数量、提高编译速度、提高可移植性

N-->L-->M，一步步转化，N是源代码，L是中间代码，M是目标代码。中间代码L可以减少N和M的转换次数，比如N有t个源代码，M有s个目标代码，不用L中间代码就需要s*t个编译器，用的话就用s+t个编译器。

老师就是这么讲的，作者过于愚钝，特此进行详细的查询解释：

对于一个源代码，通常只需要一个目标代码。但是，在实际的开发中，可能会有不同的目标平台，比如Windows、Linux、Mac等，每个平台的指令集和体系结构都不同，因此需要不同的编译器来生成适合该平台的目标代码。 因此，如果有s个源代码和t个目标平台，那么就需要s*t个编译器来生成适合不同目标平台的目标代码。

在没有使用中间代码的情况下，每个源代码需要使用不同的编译器来生成适合不同目标平台的目标代码。因为不同编译器的生成目标代码的方式和结果都不同，所以同一个源代码使用不同的编译器生成的目标代码也会不同。

而使用中间代码后，可以将源代码转换为通用的中间代码，这里需要s个编译器。再使用不同的编译器来将中间代码转换为适合不同目标平台的目标代码，这里需要t个编译器。从而减少了编译器的数量，提高了编译效率和可移植性。

3.编译器前后端的接口，让后端参与其中

具体来说，后端可以实现中间代码的解释器或者编译器，从而实现对中间代码的处理。这样既可以减轻前端的负担，又可以充分发挥后端的优势，提高编译器的效率和性能。

在一些编程语言中，中间代码还可以被作为目标代码生成的一部分来使用，就像是汇编语言中的汇编指令一样。比如Java语言中的字节码就是一种典型的中间代码，在Java虚拟机上运行时被解释器或者即时编译器转成具体的机器指令。这种方式除了可以让后端参与编译过程，还可以让编程语言具有平台无关性，提高了代码的可移植性。

逆波兰式

逆波兰表示法（RPN）是一种将运算符置于操作数之后的表示方法，其实就是后缀式。例如，中缀表达式“3 + 4”可以写为后缀表达式“3 4 +”，其中运算符“+”置于操作数“3”和“4”之后。

逆波兰表示法的优点在于可以使用栈来实现计算，因为每次遇到操作符时，都可以从栈中弹出相应的操作数进行计算。这样可以避免使用递归或者深度优先搜索算法进行计算。计算机更喜欢后缀式

例如，计算后缀表达式“3 4 + 5 *”，我们可以从左到右遍历这个表达式，遇到操作数就将其压入栈中，遇到操作符则从栈中弹出相应的操作数进行计算，并将结果压入栈中。具体计算过程如下：

计算机为什么喜欢二进制、八进制、十六进制？

计算机内部处理和存储数据的方式都是二进制的，而使用二进制编码可以最大程度地保证计算机处理数据的准确性和速度。

虽然二进制比较接近计算机内部的处理方式，但在编程和输入输出时使用二进制并不是很方便。因此，我们通常会使用其他进制，如八进制和十六进制，来表示二进制数值，这样可以让编写程序和进行输入输出的操作更加直观和易于理解。比如，八进制数和十六进制数的每位都可以直接与二进制数的三位和四位对应，分别用一个八进制位和一个十六进制位表示，使得我们在表示二进制数时，无需写那么多的0和1，更容易读写和理解。

优化

​

编译系统中的优化是代码优化的一种类型，它包括了编译器前端优化、中间代码优化和后端优化。前端优化主要处理源代码和中间代码之间的优化，例如常量折叠、循环展开和死代码删除等；中间代码优化则是在中间表示上进行优化，例如数据流分析、寄存器分配和指令选择等；后端优化则是在目标代码生成阶段进行的优化，例如指令调度和代码缩小等。这些优化的目的是提高程序的性能、执行效率和可维护性。

优化是由程序员来完成的，计算机系统只是执行程序员编写的优化代码。 计算机系统只是一个工具，它无法自主地进行优化。 程序员可以通过修改代码来提升程序的性能和效率，从而实现优化。

在优化过程中，程序员可以尝试使用一些技术来优化目标代码的生成，比如函数内联、循环展开、代码复制优化等，这些技术可以减少程序的运行时间和占用空间，提高程序的效率和性能。同时，优化也可以遵循一些编码规范和最佳实践，例如减少不必要的内存分配、避免频繁的系统调用、使用高效的数据结构等，以保证程序的可维护性和可扩展性。

目标代码

​

它是能够直接在计算机上运行的可执行代码。目标代码通常不包含高级语言的语法结构，而是由底层的机器指令或汇编语言的指令组成，因此执行起来更加高效和快速。

其他

计算机发展

第一台电子计算机ENIAC于1946年问世，它是当时世界上第一台通用电子计算机。而第一门高级编程语言Fortran（公式翻译系统）于1956年诞生，它是第一门被广泛使用和推广的高级编程语言，极大地简化了编程和程序设计的过程。

人年、人月

人年、人月：人年和人月是软件开发中常用的两个时间单位，它们是指一个人在一年或一个月内可以完成的工作量。它们都参考于标准工时，标准工时是指一个人在一周工作40小时的情况下，一年的总工作时间为2080小时。个人月等价于160小时的工作量。

这两个时间单位通常用于计算软件项目的人力资源需求和项目进度安排。

《人月神话》

《人月神话》：早期计算机学科圣书。指出在一个团队内增加人力并不一定能够缩短工期，因为新加入的成员需要适应整个开发过程和代码结构，增加了沟通、协调和管理的成本。因此，它提出了“伯鲁斯定律”，即“增加人手只会使问题更加严重”，并提出了一些解决方案，如增加人力时适量增加管理人员、确保各成员之间有效的沟通和合作等。

当然，作者认为在软件项目开发初期，增加一定的人力是有一定的帮助的。但《人月神话》仍然具有重要的现实意义。

单词与字符

程序最基本单位是单词，不是字符，字符没有语义，且有限，都是键盘上的东西。单词具有语义并且可以被编译器或解释器识别和转换为计算机指令。

而字符则只是单词的组成部分。编程中的字符主要用于描述单词的组成方式、字符串的表示和注释等。因此，单词才是编程中最基本的语法单位。

计算机语言——上下文无关语法

计算机语言的语法通常被描述为上下文无关语法，也称为文法或产生式。这是因为计算机语言的语法规则只与语言中的词汇和基本结构相关，而与语言中的上下文或语境无关。所以，无论在哪个位置使用哪个单词，它们的含义都是固定的，与周围的单词和语境无关。

由于计算机语言的语法规则是上下文无关的，所以编译器和解释器可以通过简单的静态分析来验证和识别程序的语法结构，这样可以提高程序的编译和执行效率。同时，这也使得编写和修改程序更加方便，因为语法规则都是固定的，遵循相同的规则编写程序可以减少错误和提高代码质量。

上下文无关语法（Context-Free Grammar, CFG）是计算机科学中描述形式语言的一种方法，计算机语言的语法规则通常可以用CFG来描述，因为它们也是上下文无关的。所以，编译器和解释器常常使用CFG来分析和处理程序代码。

语法制导的翻译？属性文法？语义规则？

语法制导翻译是编译原理中的一种翻译技术，它将语法分析和语义分析相结合，通过为语法规则添加语义动作，自底向上地确定每个语法结构的属性值。这些属性值可以被用来完成后续的翻译任务，如代码生成、中间代码生成等。

属性文法是一种描述语法规则和语义动作的形式化语言，它为每一个语法结构定义了一个或多个属性，并规定了这些属性值如何被计算。属性可以是继承属性或合成属性，继承属性由父节点传递给子节点，合成属性由子节点计算得到并向父节点返回。

语义规则是对编程语言语意的规定，通常涉及类型检查、变量声明、变量作用域、常量定义等方面。通过编写正确的语义规则和属性文法，可以检测出程序中的各种语义错误，并在翻译过程中实现自动类型转换、代码优化等功能。

例如，在C语言中，if-else语句的语义规则可以描述为：如果if条件为真，则执行if块中的语句，否则执行else块中的语句。

在编译原理中，语法制导翻译通常使用属性文法（就是属性值）来描述语法规则和语义动作，并借助语义规则来推导和验证属性值的正确性。通过这种方式，可以实现高效、准确地将源代码翻译成目标代码。

循环语句的翻译程序的实现

这是作者将来要实现的实验，循环语句的翻译程序实现通常包括以下步骤：

• 检查循环控制变量的定义和类型是否正确。
• 检测循环体中的语句是否符合语法规则和语义规则。
• 确定循环体的语句是否有副作用，如果有，则需要对其进行处理。

• 生成循环控制变量的初始化语句。
• 生成循环控制变量的比较语句，判断循环是否需要继续进行。
• 生成循环体内的语句序列。
• 生成循环控制变量的更新语句。

• 删除无用代码。
• 简化表达式。
• 循环展开等。

总之，循环语句的翻译程序实现需要考虑语法分析、语义分析、中间代码生成和代码优化等方面，以实现正确的代码翻译和执行。以下是一个基本的循环语句的翻译程序伪代码：

// 解析循环语句的语法结构
loopStmt -> for ( initExpr ; cmpExpr ; updateExpr ) blockStmt

// 对循环语句进行语义分析
initStmts = analyze(initExpr); // 分析循环变量初始化语句
condExpr = analyze(cmpExpr); // 分析循环条件表达式

// 检查循环体语句的语义正确性
loopStmt = analyze(blockStmt); 

if (loopStmt.hasSideEffects()) { 
   // 若循环体内有副作用，则需要生成一个新的临时变量来存储结果
   loopVar = createTempVar(); 
   loopVarStmt = loopStmt.assignTo(loopVar); // 生成赋值语句
   loopStmt = new BlockStmt(loopVarStmt, loopStmt); // 生成新的循环语句块
}

// 生成中间代码
initCode = generateCode(initStmts);
loopVar = extractLoopVar(cmpExpr);
condCode = generateCode(condExpr);
loopCode = generateCode(loopStmt);
updateCode = generateCode(analyze(updateExpr));

// 生成完整的循环语句中间代码
loopCode = new BlockCode(loopCode, updateCode);
loopCode = new LoopCode(condCode, loopCode);
loopCode = new BlockCode(initCode, loopCode);

// 对生成的中间代码进行优化
optimizedCode = optimizeCode(loopCode);

// 将生成的中间代码转换成目标代码
targetCode = compileCode(optimizedCode);
 

此段伪代码展示了循环语句的翻译程序的基本步骤，包括语法分析、语义分析、中间代码生成、代码优化和目标代码生成等环节。具体实现会因编程语言的不同而有所不同。作者刚开始编译原理，具体代码敬请期待。

单趟扫描、多趟扫描

在编译器的编译过程中，词法分析是第一个要处理的阶段。其实现一般可以通过单趟扫描或多趟扫描两种方式来实现。

单趟扫描即一次性扫描整个字符流，对每个字符进行处理，并将识别出的单词存储在一个数据结构中，然后将该数据结构传递给下一个阶段的编译器进行处理。由于只需扫描一次，因此单趟扫描具有较快的速度，但会占用较多的内存空间。

多趟扫描则是将词法分析分为两次或多次扫描。第一次扫描主要是进行字符的初步过滤，去掉空格、注释等不必要的字符，将有意义的字符组合成单词。第二次或多次扫描则是根据语法规则对单词进行进一步的判定，得到语法分析树。多趟扫描可以有效地降低内存使用，但相对来说速度较慢。

在选择词法分析的扫描方式时，需要综合考虑应用场景和需求来进行选择。单趟扫描适合简单的编译器或编译速度要求较高的场合，而多趟扫描则适用于需要更高精度语法分析的场合。

形式化语言

无法枚举的东西如何表示然后交给自动生成工具呢？这里就用形式化语言(研究语言/定义语言的语言，相当于指定语言的规则)，里面有正则表达式(Regular Expression)。

形式化语言是用来描述和定义语言的规则的一种工具，通过使用形式化语言，可以将自然语言转化为计算机能够处理的语言。常见的形式化语言包括正则表达式、上下文无关文法、自动机等。

在自动化工具中，常用的是正则表达式，通过正则表达式可以匹配不同格式的字符串，并将其转化为计算机能够处理的数据结构，如树、图等。自动化工具可以根据不同的正则表达式来生成不同的代码或模板，并自动维护和更新这些代码或模板。

需要注意的是，正则表达式虽然可以描述许多有限状态自动机可以接受的字符串，但是并不是所有类型的语言都可以用正则表达式来描述。例如，对于一些具有嵌套结构的语言，如HTML和XML，使用正则表达式可能无法完全描述其语言规则。在这种情况下，上下文无关文法可能成为更好的选择。

考试注意

​

注意考题中：编译的各个阶段和编译程序结构是有所区别的，编译程序结构侧重于完整的编译过程，包括出错处理程序，并且涉及到编译程序，其内部结构相应的也对应程序。对比图如下：

​​

这是作者在进行编译原理第一次课记录整理的笔记，由于作者初学，问题肯定会有很多，请大家多多包含。随着课件与后续的进一步学习，编译原理的内容会持续更新修整。

​