笔记-编译原理 | WWD’s Blog

type

status

date

slug

summary

一、概论

编译程序的结构

二、高级语言及其语法描述

Chomskey文法体系

语法树

三、词法分析

Thompson (正规式→NFA)

子集法 (NFA→DFA)

状态等价法 (DFA化简)

DFA与正规文法转化

DFA代码化

四、语法分析(自上而下)

消除左递归算法

提取公共左因子法(避免歧义)

FIRST构造算法(可以初步实现LL(1))

FOLLOW构造算法(解决取ε的情况)

递归下降分析程序构造算法(伪代码)

LL(1)分析表生成算法

预测分析程序构造算法(输入字符串得分析树)

五、语法分析(自上而下)

自上而下分析基本问题

规范规约

LR(0)方法构造状态

构造LR(0)分析表

构造SLR(1)分析表(使得LR(0)作用范围更广)

规范LR(1)方法(使得SLR的r更有意义)

LR分析过程

六、属性文法和语法制导翻译

属性文法

每个文法符号联系于一组属性（类型、地址、值等），且对每个产生式都给出其语义规则的文法称为属性文法。

对于产生式A→BC而言：

A.v=f(B.v,C.v)，则v是A的综合属性【即依赖于其子节点】
B.v=g([A.v,]C.v)，则v是B的继承属性【即依赖于其父节点/兄弟节点】

用下标区分同一产生式中相同符号的多次出现

S-属性文法

只使用综合属性的属性文法，可以使用自底向上的方式（如LR分析法）进行规约

L-属性文法

如果每个产生式A→X1…Xj-1Xj…Xn的每条语义规则计算的属性是A的综合属性；或者是Xj的继承属性，但它仅依赖：①该产生式中Xj左边符号X1,X2, …, Xj-1的属性；②A的继承属性【转为LL分析法打造】

目的是将数据类型更新到变量所在的符号表中

终结符只有综合属性，由词法分析器

提供非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值

对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性

出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供

语义规则所描述的工作可以包括属性计算、符号表操作、静态语义检查、代码生成等等。

语法制导翻译

边分析语法结构，边生成语法树，边进行中间代码生成

一遍扫描：在语法分析的同时计算属性值（需要注意所采用的语法分析方法、属性的计算次序）

S-属性文法适合于一遍扫描的自下而上分析

R-属性文法适合于一遍扫描的自上而下分析

七、语义分析和中间代码生成

中间语言

中间语言（复杂性界于源语言和目标语言之间）

后缀式（逆波兰式）：用一个栈来实现，每次碰到一个k目op就将栈顶的k个项提取出来，并用运算结果来代替这个项。

抽象语法树：去掉中间节点，去掉非终结符

DAG（有向无环图）：在一个DAG中代表公共子表达式的结点具有多个父结点【适合于代码优化】

三地址代码：图表示法的线性表达，写作A:=B op C，可以使用四元式(op, arg1, arg2, result)来实现三地址代码，

赋值语句的翻译

布尔表达式的翻译

优先级（not>and>or）

计算：①传统计算，一步一步算；②优化措施（短路计算）

使用M作为空字，存放后面的表达式的入口地址，在LR分析（只能看后面一个）的时候，可以用于回填

backpatch表示得知后面的地址就立刻填上，merge表示将两个出口merge成一个挂在真出口上；对于E1/E2，每一个都有两个出口，需要考虑悬挂方式

变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。

函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。