Abstract Syntax
概念
AST
⼀个短语就是⼀棵树，即抽象语法树
叶结点是变量，枝结点（内部结点）是运算符，⼦结点是它的参数
AST忠实于程序的结构，但它通常不会显式地处理变量绑定和作用域
变量是某种类型的不指定的语法⽚段（不能理解为PL中的变量）
PTA 查重就是根据编译过程中产生的 AST 来判断的，与表面形式无关
抽象语法树的族
结构归纳法 structural induction
AST中，一个结点下面的所有子树都满足某个性质，那么这个结点也满足这个性质
例如，一个表达式里所有的变量都满足某个性质，那这个表达式也满足这个性质
ABT
抽象绑定树，ABT在AST的基础上增加了对变量绑定的显式表示。
ABT不仅表示程序的语法结构，还明确表示了哪些变量在哪里被绑定，以及它们的作用范围。ABT更适合表示需要处理变量作用域、捕获和替换等操作的编程语言特 性，如函数、lambda表达式
约束绑定
202410091449
指定let运算符具有元数(Exp, Exp.Exp)Exp
类别
ast按语法的不同分成不同的类别sort，记做 \(s\)，类别的集合记作 \(S\)
常⻅的PL区分表达式和语句，两者的变量不能互相替换
运算符、元数
一个运算符用 \(o\) 表示，运算符一般是基于某类别的 ast，故运算符的集合记作 \(O_s\)，运算符的类别即其运算结果的类别
运算符的 元数 arity 记作 \((s_1,...,s_n)s\)，其规定了运算符的类别，以及参数的个数 \(n\) 和每个参数的类别 \(s_i\)
确切说，元数是所有参数的组合，
运算符的元数 == 运算符所有的参数与运算结果的类型，不包含运算结果运算符就是算子
例，基于 int 的 +，其类别是 int，因其运算结果为 int，其元数为 (int,int)int
变量
变量用 \(x\) 表示，变量的集合记作 \(X_s\)，变量族记作 \(X=\{X_s\}_{s\in S}\)
变量是⼀个未知的对象或者占位符，其含义由代换赋予
比如方程式里的 \(x\)，在带入值之前是不确定的
- 对于一个变量族，有以下概念：
- \(X\) 上下文无关时，如果 \(x\in X\)，则 \(x\) 类别为 \(s\)
- \(\forall s\)，\(x\notin X_s\)，则 \(x\) 对 \(X\) 来说是 新的 fresh
- \(X,x\) 中间的逗号表示，将 \(x\) 加入 \(X\)，这意味着 \(x\) 所属类别 \(s\) 对应的集合 \(X_s\) 被加进了\(X\)
代换
这里没看明白
变量绑定
当我们说一个变量被“绑定”时，通常是指这个变量在某个上下文中被定义，并且在 该上下文的范围内与某个值或表达式关联
比如函数形参只在该函数内发挥作用
- 绑定关系中的关键要素
- 绑定点（Binding Site）：变量首次被定义或绑定的地方
- 作用域（Scope）：作用域是指变量被绑定后可以被访问的代码区域
- 自由变量（Free Variable）：自由变量是在当前上下文中未被绑定的变量
- 约束变量（Bound Variable）：约束变量是已经在某个上下文中被绑定的变量。
变量捕获问题（Variable Capture Problem）
当一个变量在某个上下文中被绑定时，由于作用域或绑定关系不当，该变量意外地“捕获”了一个与其同名但定义在外部作用域的变量，导致程序行为不符合预期。
主要是以下两个情况：
- 自由变量变为绑定变量
- 意外的作用域扩展：由于嵌套作用域或重命名不当，外部作用域的变量被误认为是内部作用域的变量，从而“捕获”了它的值或行为。
*高阶函数（Higher-Order Function）
高阶函数（Higher-Order Function）是指至少满足以下两个条件之一的函数：
- 接收函数作为参数：高阶函数可以接受一个或多个函数作为输入参数。
- 返回一个函数：高阶函数可以返回一个函数作为其输出结果。
闭包（Closure）
比如可以在函数内定义函数，C 就不行
指在计算机科学和编程中，函数能够“记住”并访问其创建时所在的词法环境，即使在该函数执行时词法环境已经超出了它的作用范围。
闭包使得函数可以捕捉并保存其外部作用域中的变量，从而在函数调用时仍能访问这些变量。
-
闭包的特性
- 持久化的环境：闭包持有函数定义时的环境，因此即使外部作用域已经结束，函数仍然可以访问那些被捕获的变量。
- 数据的封装性：闭包允许你将函数和它操作的数据封装在一起，创建一种“私有”的 状态。其他代码无法直接访问这些数据，只有通过闭包才能间接地访问或修改它们。
- 延迟计算：闭包可以用于延迟执行某些操作，例如，当特定事件发生时才会计算或 处理某些数据。
闭包的应用场景
- 工厂函数：闭包可以用来创建具有特定配置的函数。例如，你可以用闭包生成不同的加法器函数，每个函数记住不同的增量值。
def make_incrementer(n):
def increment(x):
return x + n
return increment
add_five = make_incrementer(5)
print(add_five(10)) # 输出 15
- 回调函数和事件处理：在异步编程或事件驱动编程中，闭包常用于创建回调函数， 这些回调函数可以访问在注册时的状态。
- 数据隐藏：闭包可以用于隐藏数据，实现类似于面向对象编程中的私有属性的效果。
def counter():
count = 0
def increment():
nonlocal count
count += 1
return count
return increment
count_up = counter()
print(count_up()) # 输出 1
print(count_up()) # 输出 2
2024年10月8日22点25分
为什么可以用树来表示Lambda演算
- 叶子节点：表示变量
- 内部节点：
- 抽象节点：表示lambda抽象，记录被绑定的变量和对应的函数体
- 应用节点：表示函数应用，包含函数和参数两个子节点
在树结构中，我们能清晰地区分 FV 和 BV
- 绑定变量：在抽象节点中指定，例如 λx 绑定了变量 x
- 自由变量：在树中未被任何抽象节点绑定的变量
形式文法
这里的字符串不是 C 里那种双引号标记的东西，而是该语言能接受的句子
例如能被 C 语言编译运行的几行代码，就是 C 的一个字符串
我们将用这四个元组去描述任意一种语言
终结符（Terminal Symbols）
比如 C 语言函数最后一个符号一般是
}，这就是一个终结符
定义
终结符是文法中最基本的符号，不能再被替代或分解。它们是语言的字母表中的符号，直接出现在生成的字符串中。
作用
终结符用于构成语言的实际字符串。
文法的推导过程最终要生成由终结符组成的字符串。
终结符不会出现在推导规则的左侧，只会在右侧出现。
例子
在英语文法中，字母、数字、标点符号等都可以被视为终结符
非终结符（Non-terminal Symbols）
定义
非终结符是文法中的符号，用于帮助生成终结符序列。
它们可以被进一步替代为终结符或其他非终结符的组合。
作用
非终结符用于引导推导过程，表示文法中的结构或语法成分。
文法的推导从开始符号（也是一种非终结符）开始，通过应用产生式规则，逐步将非终结符替换 为终结符，直到生成最终的字符串。
形式文法例子
*上下文无关文法
这门课不考这个，但编译原理会考
一个文法 \(G\) 被称为上下文无关的，如果它的产生式规则都可以写成以下形式： $$ A\rightarrow \alpha $$
- \(A\) 是一个单独的非终结符（\(A\in V\)）
- \(\alpha\) 是非终结符与终结符组哼的字符串（\(\alpha\in(V\cup\Sigma)\)）
即，在上下文无关文法中，产生式左侧必须是单一的非终结符，而右侧可以是任何由 终结符和非终结符组成的字符串。
上下文无关 context-free grammar，CFG
C 语言之后的 PL 基本都是 CFG，除了 C
上下文无关语法取名为“上下文无关”的原因就是因为字符 A 总可以被字串 α 自由替换，而无需考虑字符 A 出现的上下文。如果一个形式语言是由上下文无关文法生成 的，那么可以说这个形式语言是上下文无关的。