考前笔记
目录
实验
实验 1：简单的词法分析器的构造
实验 2：预测分析程序的构造
实验 3：算符优先分析表的构造
第 1 章
1.1 什么叫编译程序
翻译程序：把某种语言（源语言）的程序翻译成另一种语言（目标语言）的程序，翻译的结果是等价的，即源程序和目标程序在逻辑上是等价的。
编译程序：把源程序翻译成目标程序的程序。一般来说是把类似 Java、C、C++等高级语言翻译成汇编语言或机器语言。
解释程序：不解释成目标程序，而是一边解释一边执行。
编译程序的种类：
- 翻译程序：将源程序翻译成目标程序。
- 编译程序：将一种高级语言源程序翻译成目标（低级语言）程序。
- 解释程序：以某种语言作为输入，但不生成目标程序，一边解释一边执行。
- 诊断编译程序：诊断源程序的错误。
- 优化编译程序：优化目标程序的性能。
- 交叉编译程序：在一种计算机上编译另一种计算机的程序。
第一个编译程序：Fortran （1957）
1.2 编译过程描述
- 词法分析
- 语法分析
- 词义分析与中间代码生成
- 优化
- 目标代码生成
词法分析
对源程序进行扫描，识别出单词（基本字，标识符，常数，运算符，界符）。
- 工具：正规式（正则表达式），有限自动机
参考资料：
- 正规式_正规式是什么 | CSDN
- 编译原理 —— 正规式、正规集和正则定义 | CSDN
- 有限自动机 | 知乎
- 编译原理学习笔记（三）：有限自动机_有限自动机例题 | CSDN
- 编程——有限自动机 | 知乎
语法分析
对单词进行语法分析，识别出语法结构。
语义分析 & 中间代码生成,优化
分析代码的含义，进行初步的翻译
翻译成更接近目标代码的中间代码，并对中间代码进行优化。
目标代码生成
目标代码的形式：
- 绝对指令代码：可直接在内存中执行
- 可重定位代码：可在内存中执行，但需要链接器来载入
- 汇编指令代码：可在汇编程序中执行
在有写编译过程中，可以省去一些优化或者中间代码生成的步骤，这样能够减少编译时间，但是会影响目标代码的性能。
1.3 编译程序的结构
编译程序的结构：
词法分析器：将源程序分解成单词
语法分析器：将单词分解成语法结构
语义分析器：分析语法结构的含义
中间代码生成器：生成中间代码
优化器：对中间代码进行优化
目标代码生成器：生成目标代码
表格管理模块：管理符号表
- 符号表：存放源程序中的标识符信息，如名字，类型，地址等
错误处理模块
1.5 编译程序的实现
首先做个定义便于理解：
定义 P=S-A->T 为在 A 机器/平台/系统/语言上将 S 语言编译成能在 T 机器/平台/系统上运行的程序
例子 1:
现有 P1=L1-A->A 想要得到 P2=L2-A->A
那么我们可以使用 L1 语言编写一个 P3=L2-L1->A 的程序
然后用前面的 P1=L1-A->A 编译器将 P3=L2-L1->A P2=翻译成 L2-A->A
例子 2：程序移植
现有 P1=L-A->A 想要得到 P2=L-B->B
构建 P3=L-L->B 程序，并用 P1 编译为 p4=L-A->B
然后用 P4 编译 P3 得到 P2=L-B->B
第 2 章 高级语言及其语法描述
高级语言分为：
- 强制式语言
- 作用式语言
- 基于规则的语言
- 面向对象语言
- 等
2.1 语言的定义
程序语言由语法和语义组成。
语言程序可以看作是一定的字符集（字母表）的有限序列。
比如 0.5 是一个浮点数，if 是一个关键字。
把数字也看成字符的想法非常新颖
语法包括词法和语法
- 词法：单词的构成规则
- 语法：句子的构成规则（或者称产生规则）（不包含对句子的意义）
一般的语法单位有：表达式，语句，分程序，函数，过程等。
语义：定义程序的规则
2.2 高级语言的特点
分类：
- 强制式语言：FORTRAN，C，Pascal
- 作用式语言：LISP
- 基于规则的语言：PROLOG
- 面向对象语言：C++，Java
程序结构：
一般是 过程，函数，对象，模块啥的
数据类型：
- 基本数据类型：整数，浮点数，字符，布尔
- 结构数据类型：数组，记录，集合
- 指针类型
- 引用类型
- 用户自定义类型
数据结构：
- 线性结构：数组，链表，栈，队列
- 非线性结构：树，图
- 文件结构：顺序文件，索引文件，散列文件
- 抽象数据
语句与控制结构：
- 表达式：由运算符和操作数构成的式子
- 语句
- 分类
- 可执行语句/说明语句
- 简单语句/复合语句：简单语句是一个基本操作，复合语句是一组语句
- 赋值语句
- 控制语句
- 说明语句：定义变量，常量，类型等
- 分类
2.3 程序语言的语法描述
上下文无关文法（CFG）
- 开始符号：比如
程序是一个开始符号 - 非终结符：比如
语句，表达式等 - 终结符：比如
if，else，while等 - 产生式：比如
语句->if 条件 then 语句 else 语句，表达式->表达式+项|项
一个上下文无关文法是一个四元组 G=(Vt,Vn,P,S)
- Vt 是终结符集合
- Vn 是非终结符集合
- P 是产生式集合
- S 是开始符号
产生式的形式
A->α，其中 A 是非终结符，α 是由终结符和非终结符组成的串- A 是产生式的左部，α 是产生式的右部
eg:定义 含有 + 和 * 的表达式 的 CFG
# E 是一个非终结符，代表`算数表达式`
# i 是一个终结符，代表`变量`
E -> i # E 可以由 i 构成
E -> E + E # E 可以由 E + E 构成
E -> E * E # E 可以由 E * E 构成
E -> (E) # E 可以由 (E) 构成产生式 E -> (E) 的作用
这个规则的作用是处理表达式中的括号，确保括号内的表达式能够被解析器识别并计算。例如，在表达式 3 _ (2 + 1) 中，括号内的 2 + 1 必须先被解析，然后结果再与 3 _ 结合。
也可以简写成：
E->i|EAE|(E)
A->+|*推导
eg2
假设我们有一个表达式 (3 + 2) * 4，我们可以通过以下步骤进行解析：
识别最内层的括号表达式：(3 + 2)
使用规则 E -> (E)，可以识别括号内的 3 + 2 是一个有效的子表达式。
解析括号内的表达式：
括号内的 3 + 2 可以进一步分解：
3 和 2 可以通过规则 E -> i 解析为基本表达式。
3 + 2 通过规则 E -> E + E 解析为两个子表达式的加法。
将解析后的结果替代原括号表达式：
解析 (3 + 2) 的结果为 5，然后将其替代原括号表达式，变成 5 * 4。
继续解析剩余的表达式：
使用规则 E -> E * E 将 5 * 4 解析为两个子表达式的乘法，结果为 20。
语法分析树示例
构建 (3 + 2) * 4 的语法树如下：
markdown
*
/ \
+ 4
/ \
3 2
根节点是 *（乘法操作符）
左子节点是 +（加法操作符）
+ 的左子节点是 3
+ 的右子节点是 2
右子节点是 4so
假定 G 是一个上下文无关文法，S 是 G 的开始符号，w 是一个字符串，如果存在一个推导 S=>*w，则称 w 是 G 的一个句子。
文法 G 所产生的句子的集合称为文法 G 的语言，记作 L(G)。
eg
S-> ab A->aA|a
那么 L(G) =
eg
S->AB A->aA|a B->bB|b
那么 L(G) =
eg
S->aSb|ab
那么 L(G) =
注意这里的 n 是相等的
最左推导
在推导过程中，每次都选择最左边的非终结符进行推导。
eg
示例文法
考虑以下简单的文法：
E -> E + E
E -> E * E
E -> (E)
E -> i我们希望推导出字符串 i + i * i。 推导过程
- 开始于起始符号 E
E
- 选择第一个替换规则 E -> E + E
E + E
- 替换最左边的 E（即第一个 E），使用规则 E -> i
i + E
- 替换最左边的 E（即第二个 E），使用规则 E -> E * E
i + E * E
- 替换最左边的 E（即第二个 E），使用规则 E -> i
i + i * E
- 替换最左边的 E（即第三个 E），使用规则 E -> i
i + i * i
我们得到了目标字符串 i + i * i。
语法分析树
对应的语法分析树（或解析树）如下：
E
/|\
E + E
/ /|\
i E * E
/ \
i i语法分析树和二义性
对于一个给定的文法，可能存在多个语法分析树，这种情况称为二义性。
二义性可能导致解析器无法准确地解析输入，因此需要避免二义性。
假设对于上面的文法，我们有一个输入字符串 i + i * i，我们可以构建两个不同的语法分析树：
E
/|\
E + E
/|\ \
E * E i
/ \
i i E
/|\
E * E
/|\ \
E + E i
/ \
i i对于输入字符串 i + i * i，有 2 中不同的最左推导，因此有 2 个不同的语法分析树。
这两个语法分析树都是有效的，但是它们对应的解析结果不同。因此，我们需要避免二义性，以确保解析器能够准确地解析输入。
改善文法的方法
设置优先级和结合性规则，以消除二义性。
E->E+T|T
T->T*F|F
F->(E)|i让 + 的优先级高于 _，并且让 _ 和 + 都是左结合的。
对于这样的文法，我们可以构建一个唯一的语法分析树，确保解析器能够准确地解析输入。
例如，对于输入字符串 i + i * i，我们可以构建以下语法分析树：
E
/|\
E + T
/ /|\
T T * F
| | |
F F i
| |
i i额外限制
文法中不包含 p->p 的产生式
每个非终结符都有用处，即对于每个非终结符 A，存在一个句子 w，使得 S=>cAb ，且 A=>a(其中 a 是终结符)
形式语言鸟瞰
诺姆·乔姆斯基（Noam Chomsky）在 1956 年提出了著名的乔姆斯基层级（Chomsky Hierarchy），将形式文法分为四种类型，每种类型有不同的限制和表达能力。这四种类型分别是：0 型文法（无限制文法）、1 型文法（上下文相关文法）、2 型文法（上下文无关文法）和 3 型文法（正则文法）。
0 型文法（无限制文法）
定义：0 型文法（Type-0 Grammar）也称为递归可枚举文法或无限制文法，是最一般的形式文法，没有任何限制。它们能够生成所有递归可枚举语言。
产生式规则：形如 α → β，其中 α 和 β 可以是任何字符串（包括空字符串），但 α 必须包含至少一个非终结符。
识别器：图灵机。
示例：
rust
S -> aSb S -> ab
该文法生成语言：
1 型文法（上下文相关文法）
定义：1 型文法（Type-1 Grammar）也称为上下文相关文法（Context-sensitive Grammar），生成的语言称为上下文相关语言。
产生式规则：形如 αAβ → αγβ，其中 A 是一个非终结符，α、β、γ 是终结符和非终结符的字符串，且 γ 不能为空。
识别器：线性有界自动机。
示例：
rust
S -> aSBC SBC -> aBC aBC -> abc bBC -> bbC bC -> bc cC -> cc
该文法生成语言：
2 型文法（上下文无关文法）
定义：2 型文法（Type-2 Grammar）也称为上下文无关文法（Context-free Grammar），生成的语言称为上下文无关语言。上下文无关文法广泛应用于编程语言的语法定义和解析。
产生式规则：形如 A → γ，其中 A 是一个非终结符，γ 是由终结符和非终结符构成的字符串。
识别器：非确定性下推自动机。
示例：
rust
S -> aSb S -> ab
该文法生成语言：
3 型文法（正则文法）
定义：3 型文法（Type-3 Grammar）也称为正则文法（Regular Grammar），生成的语言称为正则语言。正则文法是表达能力最弱的形式文法，但其解析算法非常高效。
产生式规则：形如 A → aB 或 A → a，其中 A 和 B 是非终结符，a 是终结符。
识别器：有限状态自动机。
示例：
rust
A -> aB B -> bC C -> c
该文法生成语言：
乔姆斯基层级总结
| 文法类型 | 产生式规则形式 | 识别器 | 语言类型 |
|---|---|---|---|
| 0 型文法 | α → β（其中 α 和 β 可以是任何字符串（包括空字符串），但 α 必须包含至少一个非终结符） | 图灵机 | 递归可枚举语言 |
| 1 型文法 | αAβ → αγβ（γ ≠ ε） | 线性有界自动机 | 上下文相关语言 |
| 2 型文法 | A → γ | 非确定性下推自动机 | 上下文无关语言 |
| 3 型文法 | A → aB 或 A → a | 有限状态自动机 | 正则语言 |
实际应用
正则文法（3型文法）：用于定义和解析正则语言，比如正则表达式。
上下文无关文法（2型文法）：广泛用于编程语言的语法定义，比如语法分析器和编译器前端。
上下文相关文法（1型文法）：在自然语言处理和某些编程语言（如PL/I）的语法定义中有一定应用。
无限制文法（0型文法）：理论研究和证明所有递归可枚举语言都可以被图灵机识别。
通过这些层次的划分，可以清晰地理解不同复杂度的语言及其解析器的实现难度和表达能力。
0 型文法
S -> aSb S -> ab
生成文法：L(G) =
练习参考
1
写出下列的程序设计语言所采用的输入字母表并进行比较
- FORTRAN
- C
- Pascal
- Ada
- Java
程序设计语言所采用的输入字母表主要包括字母（大小写）、数字和各种符号。下面列出了 FORTRAN、C、Pascal、Ada 和 Java 这几种编程语言的输入字母表，并对它们进行了比较。
- FORTRAN
输入字母表：
字母：A-Z（不区分大小写）
数字：0-9
特殊符号：+ - * / = ( ) , . ' : $
特点：
FORTRAN最早版本不区分大小写。
早期版本仅支持基本的特殊符号。
- C
输入字母表：
字母：A-Z，a-z
数字：0-9
特殊符号：+ - * / % = & | ^ ! ~ << >> && || == != <= >= += -= *= /= %= &= |= ^= <<= >>= ? : ; , . ' " [ ] { } ( ) #
特点：
支持丰富的操作符和符号。
区分大小写。
- Pascal
输入字母表：
字母：A-Z，a-z
数字：0-9
特殊符号：+ - * / := = < > <= >= <> ( ) [ ] . , : ; ' { } ^ @
特点：
使用:=作为赋值运算符。
设计用于教学，语法清晰严谨。
区分大小写。
- Ada
输入字母表：
字母：A-Z，a-z
数字：0-9
特殊符号：+ - * / = < > <= >= <> : => .. ** := => () [] {} ; , . ' " %
特点：
语法严格、冗长，用于高安全性和可靠性要求的系统。
支持一些独特的符号，如=>和..。
区分大小写。
- Java
输入字母表：
字母：A-Z，a-z
数字：0-9
特殊符号：+ - * / % = & | ^ ! ~ << >> >>> && || == != <= >= += -= *= /= %= &= |= ^= <<= >>= >>>= ? : ; , . ' " [ ] { } ( ) @ # _ $ \
特点：
非常丰富的操作符和符号集。
引入了新的位运算符>>>。
支持Unicode字符集，允许使用多种语言字符（如中文、日文等）。
区分大小写。
比较
字母支持：所有语言都支持A-Z和a-z，FORTRAN最早版本不区分大小写，其余语言区分大小写。
数字支持：所有语言都支持0-9。
特殊符号：
基本运算符：+ - * / 在所有语言中都支持。
逻辑运算符：&& || ! 在C和Java中有丰富的表示法，Pascal和Ada使用不同的符号。
位运算符：C和Java提供了丰富的位运算符（如& | ^ ~ << >>），Ada和Pascal提供基本的位操作符。
赋值运算符：C和Java使用=，Pascal使用:=，Ada使用:=。
其他符号：Java支持最多的特殊符号，包括@ # _ $ \等。
总的来说，Java 和 C 的输入字母表最为丰富，支持更多的符号和操作符，而 FORTRAN 相对最简单。Ada 和 Pascal 在操作符和符号支持上介于 C 和 Java 之间。
2
关于变量，数组说明上一题所列语言的有何相同和不同之处
在不同的编程语言中，变量和数组的声明和使用有着各自的语法和特点。以下是对 FORTRAN、C、Pascal、Ada 和 Java 五种语言的变量和数组的相同点和不同点的说明。
- FORTRAN
变量声明：
FORTRAN中的变量类型在声明时需要指定。
常见的数据类型包括INTEGER、REAL、DOUBLE PRECISION、COMPLEX、LOGICAL、CHARACTER。
变量名通常可以由字母和数字组成，但必须以字母开头。
INTEGER :: i, j
REAL :: x, y
CHARACTER(LEN=10) :: name数组声明：
FORTRAN支持多维数组。
数组下标通常从1开始，但也可以自定义下标范围。
INTEGER, DIMENSION(10) :: array1
REAL, DIMENSION(1:10, 1:10) :: matrix- C
变量声明：
C语言要求在使用变量之前声明其类型。
常见的数据类型包括int、float、double、char等。
变量名区分大小写。
int i, j;
float x, y;
char name[10];数组声明：
C语言支持多维数组。
数组下标从0开始。
int array1[10];
float matrix[10][10];- Pascal
变量声明：
Pascal中的变量在使用前必须声明，类型在声明时指定。
常见的数据类型包括Integer、Real、Char、Boolean等。
变量名区分大小写，但习惯上不区分大小写。
var
i, j: Integer;
x, y: Real;
name: String[10];数组声明：
Pascal支持静态数组和动态数组。
数组下标可以自定义起始值。
var
array1: array[1..10] of Integer;
matrix: array[1..10, 1..10] of Real;- Ada
变量声明：
Ada要求在使用变量之前声明其类型，语法更为严格。
常见的数据类型包括Integer、Float、Character、Boolean等。
变量名区分大小写。
i, j : Integer;
x, y : Float;
name : String(1..10);数组声明：
Ada支持静态数组和动态数组。
数组下标可以自定义起始值。
array1 : array (1..10) of Integer;
matrix : array (1..10, 1..10) of Float;- Java
变量声明：
Java要求在使用变量之前声明其类型。
常见的数据类型包括int、float、double、char、boolean等。
变量名区分大小写。
int i, j;
float x, y;
char[] name = new char[10];数组声明：
Java支持多维数组。
数组下标从0开始。
int[] array1 = new int[10];
float[][] matrix = new float[10][10];相同点
变量声明：
所有语言都要求在使用变量之前声明其类型。
所有语言都支持基本的数据类型，如整数、浮点数、字符等。
数组声明：
所有语言都支持数组，允许声明和使用一维和多维数组。
数组元素类型必须一致。
不同点
语法：
FORTRAN、Pascal、Ada使用的声明语法较为冗长和严格，C和Java则相对简洁。
FORTRAN和Pascal允许自定义数组下标范围，而C和Java的数组下标从0开始。
变量类型和命名：
FORTRAN变量名不区分大小写，其他语言区分大小写。
Java和C语言变量名区分大小写，Pascal和Ada习惯上不区分大小写。
数组下标：
FORTRAN和Pascal允许数组下标范围的灵活定义。
C和Java数组下标从0开始。
内存管理：
Java中的数组是动态分配的对象，支持垃圾回收。
C语言中的数组是静态分配的，使用指针进行动态内存管理。
Pascal和Ada支持静态和动态数组，但需要显式的内存管理。
通过以上对比，可以看出不同编程语言在变量和数组的声明与使用上有其独特的语法和特点。这些差异反映了各语言在设计理念和应用场景上的不同侧重点。
3
何谓“标识符”，何谓“名字”？两者的区别是什么？
“标识符”（Identifier）和“名字”（Name）在编程语言中是两个相关但不同的概念，尽管在许多情况下它们可能被混用。以下是对这两个概念及其区别的详细解释。 标识符（Identifier）
定义：
标识符是编程语言中用于标识变量、函数、类型、标签等各种编程元素的符号。它通常由字母、数字和下划线组成，并且通常不能以数字开头。
特点：
语法规则严格：不同编程语言对标识符的组成有具体的语法规则，例如长度限制、允许的字符集等。
区分大小写：许多编程语言（如C、Java）区分标识符中的大小写字母，即Variable和variable是两个不同的标识符。
作用域限制：标识符的有效范围通常受限于其声明的作用域（如局部变量、全局变量）。
示例：
int myVariable = 10; // myVariable 是一个标识符
void myFunction() {} // myFunction 是一个标识符名字（Name）
定义：
名字是指在程序中用于引用特定实体（如变量、函数、类型等）的符号。它可以看作是程序中所有能用来指代某个实体的方式的总称。
特点：
泛化的概念：名字是一个更为泛化的概念，可以包含标识符以及更复杂的引用方式。
包含空间：名字不仅包括简单的标识符，还可以包括名字空间、类成员等更复杂的结构。
不一定遵守标识符的语法规则：名字可能包含特殊字符或结构，例如对象的方法调用（object.method()）中的名字。
示例：
String name = "John"; // name 是一个标识符，同时也是一个名字
System.out.println(name); // System 是一个名字空间，out 是一个对象，println 是一个方法区别
定义和使用范围：
标识符是一个具体的、语法上受到严格限制的概念，主要用于变量、函数、类等编程元素的命名。
名字是一个更泛化的概念，包含标识符以及其他更复杂的引用方式。
组成和语法规则：
标识符的组成和语法规则较为严格，通常只包含字母、数字和下划线，且不能以数字开头。
名字可以包含更复杂的结构，如名字空间、对象的成员等，不一定遵守标识符的语法规则。
上下文和复杂度：
标识符通常用于简单的命名，如变量名、函数名、类名等。
名字可以涉及更复杂的引用和上下文，如对象的方法调用、名字空间中的成员等。
实际使用：
在实际编程中，标识符是实现代码中最基本的命名元素。
名字则是实际引用和使用代码元素时所采用的符号系统，可以包含标识符，也可以是更复杂的表达式。
具体示例
public class Example {
public static void main(String[] args) {
int count = 10; // count 是一个标识符，也是一个名字
Example ex = new Example(); // ex 是一个标识符，也是一个名字
ex.printCount(count); // ex.printCount 是一个名字，包括对象和方法的引用，count 是一个名字，也是一个标识符
}
public void printCount(int num) {
System.out.println(num); // num 是一个标识符，也是一个名字
}
}在上述示例中：
count, ex, num, printCount 等都是标识符，它们用于命名变量和方法。
ex.printCount(count) 是一个名字，其中包含了对象 ex 和方法 printCount 以及参数 count 的引用。
通过以上对比，可以看出标识符和名字的概念和用途的不同。在编程中，理解这些区别有助于更清晰地命名和引用程序元素。
4
令 + * ↑ 代表加法、乘法和幂运算，按如下的非标准优先级和结合性规则，计算 1+1*2↑*1↑2
- 优先顺序为 + > * > ↑，同级优先采用左结合
- 优先顺序为 ↑ > + > *，同级优先采用右结合
为了计算表达式 1+1*2↑*1↑2，我们需要按照给定的优先级和结合性规则进行逐步解析和计算。以下是按不同规则计算的详细过程：
- 优先顺序为 + > * > ↑，同级优先采用左结合
规则解释：
+ 有最高优先级。
* 有次高优先级。
↑ 有最低优先级。
同级操作符从左到右结合（左结合）。
计算步骤：
按照优先级和结合性对表达式进行括号化：
((1+1)∗2)↑((1∗1)↑2)
计算括号内的表达式：
计算 1 + 1：
2
计算 1 * 1：
1
代入已计算的值：
(2∗2)↑(1↑2)
继续计算：
计算 2 * 2：
4
计算 1 ↑ 2：
1^2=1
最后计算：
计算 4 ↑ 1：
4^1=4
结果：4
- 优先顺序为 ↑ > + > *，同级优先采用右结合
规则解释：
↑ 有最高优先级。
+ 有次高优先级。
* 有最低优先级。
同级操作符从右到左结合（右结合）。
计算步骤：
按照优先级和结合性对表达式进行括号化：
1+(1∗(2↑(1∗(1↑2))))
计算括号内的表达式：
计算 1 ↑ 2 = 1^2=1
1 * 1 = 1
代入已计算的值：
1+(1∗(2↑1))
继续计算：
计算 2 ↑ 1：
21=2
代入已计算的值：
1+(1∗2)
最后计算：
计算 1 * 2：
2
2
计算 1 + 2：
3
3
结果：3 总结
按照规则1（优先顺序为 + > * > ↑，同级左结合），结果为：4
按照规则2（优先顺序为 ↑ > + > *，同级右结合），结果为：3
5
对你所熟悉的某种语言中的某种基本数据类型: (1)描述这种类型数据对象可以包含的值; (2)确定这种类型的值的存储表示; (3)定义这种类型的常量的语法表示; (4)确定对这种类型的数据对象可以进行哪些运算: (5)对每一种运算,确定它的实现是通过软件仿真还是仅用一条简单的硬件指令? (6)对这种类型的数据进行运算的合法性是静态确定还是必须动态确定?
在 Node.js 中，我们可以选择一种基本数据类型，例如 Number 类型，来回答以下问题。
- 描述这种类型数据对象可以包含的值
Number 类型：
包含所有的双精度64位IEEE 754浮点数。
包括整数和浮点数。
特殊值：NaN（不是一个数字），Infinity，-Infinity。
- 确定这种类型的值的存储表示
存储表示：
JavaScript中的 Number 类型使用64位双精度浮点数格式（IEEE 754标准）。
具体表示为：1位符号位，11位指数位，52位尾数位。
- 定义这种类型的常量的语法表示
常量语法表示：
可以使用 const 关键字定义常量。
javascript
const pi = 3.14159; const maxInt = Number.MAX_SAFE_INTEGER; // 9007199254740991 const minInt = Number.MIN_SAFE_INTEGER; // -9007199254740991
- 确定对这种类型的数据对象可以进行哪些运算
支持的运算：
算术运算：+, -, *, /, %（模运算）, **（幂运算）
位运算：&, |, ^, ~, <<, >>, >>>
比较运算：==, ===, !=, !==, >, <, >=, <=
其他运算：Math对象提供的函数，例如 Math.sqrt(), Math.pow(), Math.round(), Math.floor(), Math.ceil(), Math.random()
- 对每一种运算，确定它的实现是通过软件仿真还是仅用一条简单的硬件指令？
运算实现：
算术运算：通常由硬件直接支持的简单指令实现（如加法、减法、乘法、除法）。
位运算：直接由硬件指令支持。
比较运算：通常由硬件指令支持。
其他运算：部分通过硬件指令支持（如平方、平方根），复杂运算（如对数、三角函数等）通过软件仿真实现。
- 对这种类型的数据进行运算的合法性是静态确定还是必须动态确定？
合法性确定：
动态确定：在JavaScript中，大多数运算的合法性是动态确定的。例如，除以零会在运行时产生 Infinity，对非数值进行算术运算会在运行时产生 NaN。
const a = 10;
const b = "5";
const sum = a + b; // 动态确定，结果为 "105" 因为 `+` 在这种情况下执行字符串连接
const diff = a - b; // 动态确定，结果为 5，因为 `-` 强制将 "5" 转为数值5
const invalidOp = a / "foo"; // 动态确定，结果为 NaN，因为 "foo" 无法转换为数值代码示例
const pi = 3.14159; // 定义常量
const maxInt = Number.MAX_SAFE_INTEGER; // 最大整数
const minInt = Number.MIN_SAFE_INTEGER; // 最小整数
// 算术运算
let sum = 5 + 10; // 15
let difference = 15 - 5; // 10
let product = 5 * 3; // 15
let quotient = 15 / 3; // 5
let remainder = 15 % 4; // 3
let power = 2 ** 3; // 8
// 位运算
let andResult = 5 & 1; // 1
let orResult = 5 | 1; // 5
let xorResult = 5 ^ 1; // 4
let notResult = ~5; // -6
let leftShift = 5 << 1; // 10
let rightShift = 5 >> 1; // 2
let unsignedRightShift = 5 >>> 1; // 2
// 比较运算
let isEqual = 5 == "5"; // true (== 比较会进行类型转换)
let isStrictEqual = 5 === "5"; // false (=== 比较不会进行类型转换)
let isNotEqual = 5 != "5"; // false (!= 比较会进行类型转换)
let isStrictNotEqual = 5 !== "5"; // true (!== 比较不会进行类型转换)
let isGreaterThan = 5 > 3; // true
let isLessThan = 5 < 3; // false
let isGreaterOrEqual = 5 >= 5; // true
let isLessOrEqual = 5 <= 3; // false
// 其他运算
let sqrtResult = Math.sqrt(16); // 4
let powResult = Math.pow(2, 3); // 8
let roundResult = Math.round(4.6); // 5
let floorResult = Math.floor(4.9); // 4
let ceilResult = Math.ceil(4.1); // 5
let randomResult = Math.random(); // [0, 1) 之间的随机数通过上述代码示例和解释，我们可以清晰地理解 Number 类型在 Node.js 中的表现及其相关运算的细节。
6
令文法 G6 为 N->D|ND D-0|1|2|3|4|5|6|7|8|9
(1)G6 的语言 L(G6)是什么? (2)给出句子 0127、34 和 568 的最左推导和最右推导。
(1) G6 的语言 L(G6) 是什么?
文法 G6 描述了一种语言，该语言的每个句子由一个或多个数字字符组成。文法规则如下：
mathematica
N -> D | ND D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
从规则中可以看出：
D 生成单个数字字符（0到9）。
N 生成一个数字字符或一个由数字字符构成的字符串。
因此，语言 L(G6) 是由一个或多个数字字符（0 到 9）组成的字符串的集合。这意味着 L(G6) 是十进制非负整数的字符串表示。 (2) 给出句子 0127、34 和 568 的最左推导和最右推导 句子 0127
最左推导：
N
ND (应用 N -> ND)
NDD (应用 N -> ND)
NDDD (应用 N -> ND)
DDDD (应用 N -> D)
0DDD (应用 D -> 0)
01DD (应用 D -> 1)
012D (应用 D -> 2)
0127 (应用 D -> 7)
最右推导：
N
ND (应用 N -> ND)
NDD (应用 N -> ND)
NDDD (应用 N -> ND)
NDD7 (应用 D -> 7)
ND27 (应用 D -> 2)
N127 (应用 D -> 1)
0127 (应用 D -> 0)
句子 34
最左推导：
N
ND (应用 N -> ND)
DD (应用 N -> D)
3D (应用 D -> 3)
34 (应用 D -> 4)
最右推导：
N
ND (应用 N -> ND)
N4 (应用 D -> 4)
34 (应用 D -> 3)
句子 568
最左推导：
N
ND (应用 N -> ND)
NDD (应用 N -> ND)
DDD (应用 N -> D)
5DD (应用 D -> 5)
56D (应用 D -> 6)
568 (应用 D -> 8)
最右推导：
N
ND (应用 N -> ND)
NDD (应用 N -> ND)
ND8 (应用 D -> 8)
N68 (应用 D -> 6)
568 (应用 D -> 5)
总结
通过上述推导过程，可以看出文法 G6 的句子生成过程。最左推导总是优先展开最左边的非终结符，而最右推导总是优先展开最右边的非终结符。
7
写一个文法,使其语言是奇数集,且每个奇数不以 0 开头。
文法 G
定义非终结符：
S：开始符号，生成整个奇数。
N：生成除最后一位外的数字部分。
D：生成单个数字。
定义终结符：
1, 3, 5, 7, 9：奇数数字。
0, 2, 4, 6, 8：偶数数字。
文法规则
rust
S -> F N L // F 表示奇数的首位，N 表示奇数的中间部分，L 表示奇数的最后一位 F -> 1 | 3 | 5 | 7 | 9 // 奇数首位不能为 0 N -> D N | ε // 中间部分可以是任意数字，包括空 D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 // 任意数字 L -> 1 | 3 | 5 | 7 | 9 // 最后一位必须是奇数
解释：
S 开始符号生成一个由 F、N 和 L 构成的奇数，其中 F 是奇数的首位，N 是中间部分，L 是最后一位。
F 生成一个非零奇数数字，确保首位不为 0。
N 生成任意长度的数字序列，包括空序列。ε 表示空字符串。
D 生成单个数字，包括0在内的任意数字。
L 生成一个奇数数字，确保最后一位是奇数。
示例推导 生成奇数 135
最左推导：
S
F N L (应用 S -> F N L)
1 N L (应用 F -> 1)
1 D N L (应用 N -> D N)
1 3 N L (应用 D -> 3)
1 3 ε L (应用 N -> ε)
1 3 5 (应用 L -> 5)
最右推导：
S
F N L (应用 S -> F N L)
1 N L (应用 F -> 1)
1 N 5 (应用 L -> 5)
1 D N 5 (应用 N -> D N)
1 3 N 5 (应用 D -> 3)
1 3 ε 5 (应用 N -> ε)
1 3 5 (应用 ε 省略)
生成奇数 789
最左推导：
S
F N L (应用 S -> F N L)
7 N L (应用 F -> 7)
7 D N L (应用 N -> D N)
7 8 N L (应用 D -> 8)
7 8 D N L (应用 N -> D N)
7 8 9 L (应用 D -> 9)
7 8 9 ε L (应用 N -> ε)
7 8 9 (应用 L -> 9)
最右推导：
S
F N L (应用 S -> F N L)
7 N L (应用 F -> 7)
7 N 9 (应用 L -> 9)
7 D N 9 (应用 N -> D N)
7 8 N 9 (应用 D -> 8)
7 8 D N 9 (应用 N -> D N)
7 8 9 ε N 9 (应用 N -> ε)
7 8 9 (应用 ε 省略)
生成奇数 3
最左推导：
S
F N L (应用 S -> F N L)
3 N L (应用 F -> 3)
3 ε L (应用 N -> ε)
3 3 (应用 L -> 3)
最右推导：
S
F N L (应用 S -> F N L)
3 N L (应用 F -> 3)
3 N 3 (应用 L -> 3)
3 ε 3 (应用 N -> ε)
3 3 (应用 ε 省略)
通过上述文法规则，我们确保了每个生成的数字不以 0 开头并且以奇数结尾，这样生成的所有字符串都是有效的奇数。
8
令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|i
(1)给出 i+ii、i(i+i)的最左推导和最右推导; (2)给出 i+i+i、i+i*i 和 i-i-i 的语法树。
(1) 给出 i+ii、i(i+i) 的最左推导和最右推导 表达式 i+i*i
最左推导：
EE
E+TE+T （应用 E→E+TE→E+T）
T+TT+T （应用 E→TE→T）
F+TF+T （应用 T→FT→F）
i+Ti+T （应用 F→iF→i）
i+T∗Fi+T∗F （应用 T→T∗FT→T∗F）
i+F∗Fi+F∗F （应用 T→FT→F）
i+i∗Fi+i∗F （应用 F→iF→i）
i+i∗ii+i∗i （应用 F→iF→i）
最右推导：
EE
E+TE+T （应用 E→E+TE→E+T）
E+T∗FE+T∗F （应用 T→T∗FT→T∗F）
E+F∗FE+F∗F （应用 T→FT→F）
E+i∗FE+i∗F （应用 F→iF→i）
E+i∗iE+i∗i （应用 F→iF→i）
T+i∗iT+i∗i （应用 E→TE→T）
F+i∗iF+i∗i （应用 T→FT→F）
i+i∗ii+i∗i （应用 F→iF→i）
表达式 i*(i+i)
最左推导：
EE
TT （应用 E→TE→T）
T∗FT∗F （应用 T→T∗FT→T∗F）
F∗FF∗F （应用 T→FT→F）
i∗Fi∗F （应用 F→iF→i）
i∗(E)i∗(E) （应用 F→(E)F→(E)）
i∗(E+T)i∗(E+T) （应用 E→E+TE→E+T）
i∗(T+T)i∗(T+T) （应用 E→TE→T）
i∗(F+T)i∗(F+T) （应用 T→FT→F）
i∗(i+T)i∗(i+T) （应用 F→iF→i）
i∗(i+F)i∗(i+F) （应用 T→FT→F）
i∗(i+i)i∗(i+i) （应用 F→iF→i）
最右推导：
EE
TT （应用 E→TE→T）
T∗FT∗F （应用 T→T∗FT→T∗F）
F∗FF∗F （应用 T→FT→F）
i∗Fi∗F （应用 F→iF→i）
i∗(E)i∗(E) （应用 F→(E)F→(E)）
i∗(E+T)i∗(E+T) （应用 E→E+TE→E+T）
i∗(E+F)i∗(E+F) （应用 T→FT→F）
i∗(E+i)i∗(E+i) （应用 F→iF→i）
i∗(T+i)i∗(T+i) （应用 E→TE→T）
i∗(F+i)i∗(F+i) （应用 T→FT→F）
i∗(i+i)i∗(i+i) （应用 F→iF→i）
(2) 给出 i+i+i、i+i*i 和 i-i-i 的语法树 语法树 for i+i+i
mathematica
E
/|\
E + T
/|\ |
E + T i
/|
T i
语法树 for i+i*i
r
E
/|\
E + T
/| |
T i T
/|\
T * F
| |
i i
语法树 for i-i-i
r
E
/|\
E - T
/| |
E - T
/| /| T i T i | i
总结
通过上述文法规则和推导过程，可以清晰地看出生成表达式的推导过程和语法树。推导过程分别展示了从左至右和从右至左的替换步骤，而语法树则直观地显示了表达式的结构。
9
证明下面的文法是二义的:
S->iSeS|iS|i
要证明文法是二义性的，我们需要找到一个句子，该句子有两种不同的推导树（解析树）。文法如下：
css
S -> iSeS | iS | i
让我们考虑句子 iii，并展示两种不同的推导树。 推导 1
推导树 1:
vbnet
S
|
iS
|
iS
|
i
最左推导 1:
SS
iSiS （应用 S→iSS→iS）
iiSiiS （应用 S→iSS→iS）
iiiiii （应用 S→iS→i）
推导 2
推导树 2:
css
S
/|\
i S e S
| |
iS i
|
i
最左推导 2:
SS
iSeSiSeS （应用 S→iSeSS→iSeS）
iSiiSi （应用 S→iS→i）
通过这两种不同的推导树，可以看出：
推导树 1 展示了表达式 iii 通过连续应用 S -> iS 和最终 S -> i 的生成过程。
推导树 2 展示了表达式 iii 通过应用规则 S -> iSeS 和最终 S -> i 的生成过程。
这两种推导树的结构明显不同，因此文法是二义性的。
10
把下面文法改写为无二义的: S->SS|(S)|()
二义性证明：
S -> SS -> (S)S -> (S)(S) -> ()(S) -> ()() S -> SS -> ()S -> ()(S) -> ()()
为了消除文法的二义性，我们需要修改文法，使得每个句子只有唯一的一种解析树。考虑到原文法中的二义性主要来自于 S 可以扩展为两个 S，我们可以通过引入新的非终结符来消除这种二义性。
修改后的文法如下：
S -> A | (S) | () A -> S S
在这个修改后的文法中，我们引入了一个新的非终结符 A，用来表示两个 S 的连接。现在，每个 S 会被展开为一个 A，而 A 会展开为两个 S，从而消除了原文法中的二义性。
这个修改后的文法保留了原文法的语言，但是确保了每个句子只有唯一的一种解析树，从而消除了二义性。
这个方案似乎并没有解决问题！！！
11
给出下面语言的相应文法
L1={a^n b^n c^i | n>=1,i>=0} L2={a^i b^n c^n | n>=1,i>=0} L3={a^n b^n a^m b^m | n>=0,m>=0} L4=
这些方案似乎有问题！！！
L1 文法
L1 的语言表示为：L1={anbnci | n>=1,i>=0}L1=
文法：
S -> aBc | abc
B -> aB | εL2 文法
L2 的语言表示为：L2={aibncn | n>=1,i>=0}L2=
文法：
S -> Ac | aBc
A -> aA | ε
B -> bBc | bcL3 文法
L3 的语言表示为：L3={anbnambm | n>=0,m>=0}L3=
文法：
S -> AB
A -> aAb | ε
B -> bB | εL4 文法
L4 的语言表示为：L4={1n0m1m0n | n>=0,m>=0}L4=
文法：
S -> XY
X -> 1X0 | ε
Y -> 0Y1 | ε12(难题)
假定已知语言{a^n b^n c^n | n>=1} 不是上下文无关的,请证明上下文无关语言对于交和补这两个运算是不封闭的。(提示:利用练习 11 那两个语言集 L 和 L。作媒介)
交运算
我们将证明如果上下文无关语言对于交运算是封闭的，那么 LL 必须是上下文无关的，这与我们的假设相矛盾。
补运算
我们将证明如果上下文无关语言对于补运算是封闭的，那么 LL 必须是上下文无关的，这与我们的假设相矛盾。
综上所述，我们证明了上下文无关语言对于交和补这两个运算不封闭。
13(难题)
证明任何上下文无关语言都可由仅含下述三种形式的产生式的文法所产生: A->BC A->a S->ε
其中,A、B、C、S 为非终结符;S 为开始符号。
我们将证明任何上下文无关语言都可以由仅含有所给形式的产生式的文法产生。
考虑一个上下文无关语言 LL，我们将通过归纳的方式来证明，对于语言 LL 中的每个字符串，都可以使用所给形式的产生式生成。 基本情况
如果 LL 中的字符串为空串，即 LL 包含空串 ϵϵ，那么我们可以使用产生式 S→ϵS→ϵ 来生成空串。 归纳假设
假设对于 LL 中长度小于等于 nn 的字符串，都可以使用所给形式的产生式生成。 归纳步骤
考虑 LL 中长度为 n+1n+1 的字符串 ww。我们知道 ww 可以写成 w=uvw=uv，其中 | u | =k | u | =k， | v | =n | v | =n，且 uu 和 vv 也是 LL 的成员。
根据归纳假设，我们可以使用所给形式的产生式生成字符串 uu 和 vv。假设对于 uu 生成的产生式序列为 A⇒∗uA⇒∗u，对于 vv 生成的产生式序列为 B⇒∗vB⇒∗v。
现在我们可以使用 A→BCA→BC 的产生式来连接 uu 和 vv，从而生成 ww。因此，我们可以通过 A⇒∗u⇒∗wA⇒∗u⇒∗w 的产生式序列来生成字符串 ww。
由归纳法的原理可知，任何上下文无关语言 LL 都可以由仅含有所给形式的产生式的文法产生。
14(难题)
证明:对任何上下文无关文法 G,存在一个正整数 p,使对任何 a 属于 L(G),若 |a| >=p,则 a 可表示成 xuwmyy,使得 |uwv|≤p,|uv|>0,且对任何 i>=0,xu^i wv^i y 属于 L(G)。 2024.06.07 01:00 要证明这个结论，我们将使用推导树的概念来构造证明。
考虑一个上下文无关文法 GG，我们将证明存在一个正整数 pp，对于任何 aa 属于 L(G)L(G)，如果 | a | >=p | a | >=p，那么 aa 可以表示为 xuwmyyxuwmyy，其中 | uwv | ≤p | uwv | ≤p， | uv | >0 | uv | >0，并且对于任何 i>=0i>=0，xuiwviyxuiwviy 属于 L(G)L(G)。 正整数 pp 的选择
我们选择 pp 为文法 GG 的产生式右侧非终结符的最大长度加一，即 p=max{ | u | , | v | }+1p=max{ | u | , | v | }+1，其中 A→uBvA→uBv 是 GG 的一个产生式。这样选择 pp 是为了确保在任何 | a | >=p | a | >=p 的情况下，至少有一个产生式右侧的非终结符长度不超过 pp。 证明思路
对于长度大于等于 pp 的字符串 aa，我们可以通过在 aa 中找到长度大于 pp 的子串来构造 xuwmyyxuwmyy 形式的字符串。
我们将从 aa 中选择最左边和最右边的产生式右侧非终结符的最大长度不超过 pp 的子串作为 uu 和 vv。
通过消除 uu 和 vv 中的非终结符，我们得到 xx、ww 和 yy，然后我们可以使用产生式右侧非终结符的替代字符串 uu 和 vv 来构造 xuwmyyxuwmyy 形式的字符串。
由于选择 pp 的方式，我们可以保证在 xuwmyyxuwmyy 形式的字符串中，至少有一个非终结符的长度不超过 pp。这样，我们可以确保 xuiwviyxuiwviy 属于 L(G)L(G)。
详细步骤
选择 pp 为文法 GG 中右侧最长非终结符长度加一。
对于输入字符串 aa，如果 | a | <p | a | <p，则无需进行任何处理，直接返回 aa。
如果 | a | >=p | a | >=p，则从 aa 中选择最左边和最右边的产生式右侧非终结符的最大长度不超过 pp 的子串作为 uu 和 vv。
将 uu 和 vv 中的非终结符替换为空串，得到 xx、ww 和 yy。
使用产生式右侧非终结符的替代字符串 uu 和 vv 构造 xuwmyyxuwmyy 形式的字符串。
由于选择 pp 的方式，确保 xuiwviyxuiwviy 属于 L(G)L(G)。
通过这样的构造，我们可以确保对于任何长度大于等于 pp 的字符串 aa，都存在一个 pp，满足 aa 可以表示为 xuwmyyxuwmyy，并且对于任何 i>=0i>=0，xuiwviyxuiwviy 属于 L(G)L(G)。
第 3 章 词法分析(PDF-p48)
3.1 对于词法分析器的要求
词法分析器的任务是将源程序中的字符流转换为单词流。
单词符号一般可以分为以下几类：
- 关键字 (KEYWORD) 如 if、else、while、for 等
- 标识符 (IDENTIFIER) 如变量名、函数名等
- 常量 (CONSTANT) 如整数、浮点数、字符、字符串等
- 运算符 (OPERATOR) 如 +、-、*、/、=、==、!= 等
- 分隔符 (DELIMITER) 如 (、)、{、}、[、]、,、; 等
单词符号包括单词符号的种别码和属性值两部分。种别码用于标识单词符号的类型，属性值用于存储单词符号的具体值。
种类：标识符一般分为一种，常数则按照类型分为整数、浮点数、字符、字符串等多种，运算符和分隔符也有多种，界符一般分为一种。
eg:while (a < 10) { a = a + 1; }
<WHILE, while>
<LP, (>
<ID, a>
<LT, <>
<CONST, 10>
<RP, )>
<LB, {>
<ID, a>
<ASSIGN, =>
<ID, a>
<ADD, +>
<CONST, 1>
<SEMICOLON, ;>
<RB, }>词法分析器一般是独立的一遍，当然也可以和语法分析器一起实现。
3.2 词法分析器的设计
输入&预处理
输入传放入缓冲区，然后进行预处理，比如去掉注释，去掉空格，制表符，换行符，处理 C 中的的#define/#include等。
使用起点和终点指针来指示当前处理的字符，起点指针指向当前单词的第一个字符，终点指针指向当前搜索的字符。
超前搜索
对于 FORTRAN，关键词识别是困难的，因为 FORTRAN 中的特殊词没有保护，do 可以是一个变量名，也可以是一个关键字。
需要超前看后面的情况来确定这个词是不是关键字。
3.3 正规表达式与有限自动机
状态转换图
一开始是 0 状态，识别到什么字符之后变为另一个状态，最后到达终止状态（不一定有终止状态）。
对于关键字的话，会存在一个关键字表，上面列出的所有关键字，状态转换图识别到一些字符进入某个状态后会和关键字表进行匹配，如果匹配成功，那么就是一个关键字。
状态转换图的实现
定义一组函数
char ch; // 当前字符
char[] strToken; // 当前单词
void GetChar(); // 将下一个字符读入 ch，搜索指针后移
void GetBC(); // 检查 ch 是否是空格，如果是，继续读入下一个字符
void Concat(); // 将当前字符ch连接到strToken后面
bool IsLetter(); // 判断 ch 是否是字母
bool IsDigit(); // 判断 ch 是否是数字
int Reserve();// 查找 strToken 是否是关键字,返回种别码,如果不是关键字，返回 0(假设 0 不是任何关键字的种别码)
void Retract(); // 指针回退,将 ch 设置为 '\0'
sList* InsertId();// 将 strToken 插入符号表
cList* InsertConst(); // 将 strToken 插入常数表设计一下之后，就能用代码实现状态转换图了。
正规表达式
定义
正规式（Regular Expressions）是一种用来描述和匹配字符串集合的模式。正规式广泛应用于文本搜索、文本替换和词法分析等领域。 基本组成
正规式由字符和运算符组成，常见的运算符有：
字符（Literals）：匹配自身，例如 a 匹配字符 a。
连接（Concatenation）：将两个正则表达式连接起来，例如 ab 匹配字符串 ab。
或（Alternation）：表示选择，例如 a|b 匹配字符 a 或 b。
星号（Kleene Star）：表示零个或多个重复，例如 a* 匹配零个或多个 a。
加号（Plus）：表示一个或多个重复，例如 a+ 匹配一个或多个 a。
问号（Question Mark）：表示零个或一个，例如 a? 匹配零个或一个 a。
括号（Parentheses）：用于分组，例如 (ab)* 匹配零个或多个 ab。
示例
a* 匹配："", "a", "aa", "aaa", ...
(a|b)c 匹配："ac", "bc"
ab+ 匹配："ab", "abb", "abbb", ...
有限自动机（Finite Automata）
定义
有限自动机（Finite Automata, FA）是一种数学模型，用于识别正规语言。它分为确定性有限自动机（Deterministic Finite Automata, DFA）和非确定性有限自动机（Non-deterministic Finite Automata, NFA）。 组成
一个有限自动机由以下部分组成：
状态集（States）：有限个状态的集合。
字母表（Alphabet）：有限个符号的集合。
转移函数（Transition Function）：定义从一个状态到另一个状态的转移规则。
初始状态（Start State）：自动机开始工作的状态。
接受状态集（Accept States）：自动机接受输入字符串的状态集合。
DFA 和 NFA 的区别
DFA：在任何给定状态下，对于每一个输入符号，都有且仅有一个转移状态。
NFA：在任何给定状态下，对于一个输入符号，可以有多个转移状态，也可以没有转移状态。
示例 DFA 示例
假设我们有一个 DFA，用于识别包含偶数个 a 的字符串。
状态集：{q0, q1}
字母表：{a, b}
转移函数：
δ(q0, a) = q1
δ(q0, b) = q0
δ(q1, a) = q0
δ(q1, b) = q1
初始状态：q0
接受状态：{q0}
该 DFA 的状态图如下：
q0 --a--> q1
q0 --b--> q0
q1 --a--> q0
q1 --b--> q1NFA 示例
假设我们有一个 NFA，用于识别包含子串 ab 的字符串。
状态集：{q0, q1, q2}
字母表：{a, b}
转移函数：
δ(q0, a) = {q0, q1}
δ(q0, b) = {q0}
δ(q1, b) = {q2}
δ(q2, a) = {}
δ(q2, b) = {}
初始状态：q0
接受状态：{q2}
该 NFA 的状态图如下：
q0 --a--> q0
q0 --a--> q1
q0 --b--> q0
q1 --b--> q2正规式与有限自动机的关系
正规式和有限自动机之间有密切的关系：
从正规式到 NFA：可以将任意正规式转换为等价的 NFA。这个过程通常使用 Thompson 构造法。
从 NFA 到 DFA：可以将 NFA 转换为等价的 DFA，这个过程使用子集构造法。
从 DFA 到正规式：可以将 DFA 转换为等价的正规式，这个过程使用状态消除法。
总结
正规式 是描述和匹配字符串模式的工具，广泛用于文本处理和词法分析。
有限自动机 是识别正规语言的数学模型，分为 DFA 和 NFA。
正规式与有限自动机之间可以相互转换，这使得它们在理论上是等价的，均能表达正规语言。
理解正规式和有限自动机的概念和关系，对于构建词法分析器和理解编译原理是至关重要的。
正规式与有限自动机的等价性
从正规式到 NFA
任何正规式都可以转换为等价的 NFA，通常使用 Thompson 构造法。这个方法通过递归地构造 NFA 来匹配正规式。
例如，正规式 a|b 可以转换为如下 NFA：
ε a ε
-> (q0) ----> (q1)
| |
| ε | ε
v v
(q2) ----> (q3)
b从 NFA 到 DFA
可以使用子集构造法（Subset Construction Method）将 NFA 转换为等价的 DFA。这个方法通过创建 DFA 的状态集，其中每个状态代表 NFA 状态集的一个子集。 从 DFA 到正规式
可以使用状态消除法将 DFA 转换为等价的正规式。这个方法通过逐步消除 DFA 中的状态，构造出等价的正规式。
正规文法与有限自动机的等价性
从正规文法到 NFA
对于每个右线性文法的产生式 A→aBA→aB，可以构造 NFA 的状态转移 δ(A,a)=Bδ(A,a)=B。 例如，产生式 S→aAS→aA 和 A→bA→b 可以构造如下 NFA：
(q0) --a--> (q1)
(q1) --b--> (q2)其中，状态 q0q0 是初始状态，q2q2 是接受状态。 从 NFA 到正规文法
对于 NFA 的每个状态转换 δ(qi,a)=qjδ(qi,a)=qj，可以构造右线性文法的产生式 qi→aqjqi→aqj。 例如，NFA 状态转换 δ(q0,a)=q1δ(q0,a)=q1 和 δ(q1,b)=q2δ(q1,b)=q2 可以构造产生式：
q0→aq1q0→aq1
q1→bq2q1→bq2
总结
正规式与有限自动机的等价性：任何正规式都可以转换为等价的NFA，然后NFA可以转换为等价的DFA，反之亦然。正规式、NFA和DFA在表达能力上是等价的。
正规文法与有限自动机的等价性：右线性文法和NFA是等价的。任何右线性文法都可以转换为等价的NFA，反之亦然。
通过理解这些等价性，可以更好地理解正规语言和词法分析的基础原理。
3.4 词法分析器的生成
LEX 的实现
对于每一个正规式，都可以生成一个有限自动机，然后将所有的有限自动机合并成一个大的有限自动机。
练习
第 4 章（PDF-P78）
- 仔细看看 3,7,10 对应重点内容，再去磨 4 和 5
4.1 语法分析器的功能
4.2 自上而下分析面临的问题
4.3 LL(1)分析法
4.4 递归下降分析程序构造
4.5 预测分析程序
第 5 章
5.1 自下而上分析基本问题
5.2 算符优先分析
第 7 章 语义分析和中间代码生成(PDF-P 177)
在词法分析和语法分析之后，语义分析和中间代码生成是编译器的下一个重要步骤。
主要工作包括：
- 静态语义分析
- 翻译
静态语义分析包括
- 类型检查
- 控制流检查
- 一致性检查
- 相关名字检查
7.1 中间语言
后缀式，三元式，四元式，间接三元式，DAG 图
ChatGPT
中间代码是编译器的一个中间表示形式，它介于源代码和机器代码之间，用于简化和优化代码生成过程。常见的中间代码表示形式包括后缀式、三元式、四元式、间接三元式和 DAG 图方法。下面详细介绍这些表示方法。
1. 后缀式（Postfix Notation）
后缀式，也称逆波兰表示法（Reverse Polish Notation, RPN），是一种不需要括号的算术表达式表示方法。操作符位于操作数的后面。 示例
中缀表达式：a + b _ c 后缀表达式：a b c _ + 转换规则
操作数按出现顺序加入输出。
遇到操作符，将操作符应用于前面两个操作数，然后将结果加入输出。
2. 三元式（Three-address Code, TAC）
三元式使用三元组（op, arg1, arg2）表示运算，其中 op 是操作符，arg1 和 arg2 是操作数。每个三元式表示一个基本操作。 示例
中缀表达式：a + b * c 转换为三元式：
t1 = b * c
t2 = a + t1
3. 四元式（Quadruples）
四元式在三元式的基础上增加了结果变量，格式为 (op, arg1, arg2, result)。每个四元式表示一个基本操作，并明确指出结果存储的位置。 示例
中缀表达式：a + b * c 转换为四元式：
( *, b, c, t1 )
( +, a, t1, t2 )
4. 间接三元式（Indirect Three-address Code）
间接三元式使用指针数组表示三元式，数组元素指向实际的三元式。通过这种方式，可以更灵活地修改和优化代码。 示例
中缀表达式：a + b * c 转换为三元式并用指针数组表示：
t1 = b * c
t2 = a + t1
指针数组：[指向 t1 的三元式, 指向 t2 的三元式]
5. DAG 图方法（Directed Acyclic Graph）
DAG 图方法用于表达基本块中的表达式，以便发现和消除公共子表达式。DAG 是有向无环图，每个节点代表一个操作或变量，每条边代表数据依赖关系。 示例
中缀表达式：a = b + c _ d + b _ c * d 转换为 DAG 图：
创建节点 b、c、d
创建节点 t1 = c * d
创建节点 t2 = b + t1
创建节点 t3 = b * t1
创建节点 a = t2 + t3
通过 DAG 图，可以发现并消除 b _ c _ d 这样的公共子表达式，从而优化代码。
总结
后缀式：一种简化的表达式表示法，不需要括号。
三元式：使用三元组表示基本操作，适用于简单运算表示。
四元式：在三元式基础上增加结果变量，更明确操作结果的存储位置。
间接三元式：使用指针数组表示三元式，提高灵活性和可优化性。
DAG 图方法：用于表达基本块中的表达式，发现并消除公共子表达式，实现代码优化。
通过这些中间代码表示方法，编译器可以在代码生成和优化过程中更高效地处理源代码。
对于文法规则，每一个产生式都可以转换为一个三元式，比如 A->B+C 可以转换为 t1=B+C。
然后可以更方便得产生中间代码树
第 10 章 代码优化 （PDF-P 284）
10.1 概述
10.2 局部优化
在编译器优化中，局部优化和循环优化是两种常见的优化技术。它们的主要目标是提高生成代码的运行效率和减少资源消耗。下面分别介绍局部优化和循环优化的概念及其常见技术。 局部优化（Local Optimization）
局部优化是针对程序的某个基本块（Basic Block）进行的优化。基本块是指没有分支跳转的直线代码序列，除了块的入口和出口。局部优化仅在这些小的代码区域内进行，不会跨越基本块边界。 常见的局部优化技术
常量折叠（Constant Folding）
在编译时计算常量表达式。
例如，将 3 + 4 优化为 7。
常量传播（Constant Propagation）
将已知的常量值传播到使用该常量的地方。
例如，若 x = 5，则将 y = x + 3 优化为 y = 8。
冗余代码消除（Dead Code Elimination）
删除不会影响程序输出的代码。
例如，删除从未使用的变量赋值。
子表达式消除（Common Subexpression Elimination）
识别并消除重复计算的表达式。
例如，将 t1 = a + b 和 t2 = a + b 优化为 t2 = t1。
强度削弱（Strength Reduction）
用较低开销的操作替换高开销的操作。
例如，将乘法 x * 2 优化为加法 x + x。
示例
c
// 原始代码 int a = 3 + 4; int b = a + a;
// 优化后的代码 int a = 7; // 常量折叠 int b = 14; // 常量传播
10.3 循环优化
循环优化（Loop Optimization）
循环优化是针对循环结构进行的优化，因为循环通常是程序中执行频率最高的部分。优化循环可以显著提高程序的性能。 常见的循环优化技术
循环不变代码外提（Loop-Invariant Code Motion）
将循环内不变的代码移到循环外，以减少重复计算。
例如，将循环中的常量计算移到循环外。
循环展开（Loop Unrolling）
通过增加循环体的大小，减少循环控制的开销。
例如，将循环体重复几次，然后减少循环次数。
循环交换（Loop Interchange）
交换嵌套循环的顺序，以提高数据局部性和缓存性能。
例如，交换行优先和列优先的遍历顺序。
循环拆分（Loop Splitting）
将复杂的循环拆分成多个简单的循环。
例如，将一个复杂循环拆分成两个独立的循环。
循环融合（Loop Fusion）
将多个相同索引范围的循环合并成一个循环。
例如，将两个独立的循环合并为一个循环。
示例
c
// 原始代码 for (int i = 0; i < n; i++) { a[i] = b _ c; // b _ c 是循环不变的 }
// 优化后的代码 int temp = b * c; // 循环不变代码外提 for (int i = 0; i < n; i++) { a[i] = temp; }
总结
局部优化 主要在基本块内进行，旨在优化小的代码区域，通过常量折叠、常量传播、冗余代码消除等技术提高代码效率。
循环优化 针对循环结构进行优化，因为循环往往是程序性能的瓶颈，通过循环不变代码外提、循环展开、循环交换等技术显著提升程序性能。
理解和应用这些优化技术，可以帮助编译器生成更高效的目标代码，提高程序的运行速度和资源利用率。