编译原理笔记

回到主页

词法分析与自动机

确定有穷自动机DFA

  • ：状态

  • ：输入字母表

  • ：一个单值映射()

  • ：初态（唯一）

  • ：终态集

非确定有穷自动机NFA

  • ：状态

  • ：输入字母表

  • ：一个映射()

  • ：初态（不一定唯一）

  • ：终态集

构造NFA

略，记得必须从正规式构造

NFA确定化

指的是NFA的一个状态子集，指的是在这个NFA中，所有中的状态，或可以通向中状态输入得到的状态来组成的集合。

具体构造方法

  1. 找出NFA起始状态的，记为新的DFA起始状态（这里设为A）

  2. 从输入字母表中选择一个输入字母

  3. 找出A对应的NFA状态接收该输入字母后能转化到的新NFA状态集合的，弱与之前已经找出的DFA状态都不相同，则给一个新标记

  4. 返回2，选择一个新输入，直到输入穷举完

  5. 对剩下的DFA状态各进行一遍2-4过程，直到所有DFA状态都被处理完

  6. 已经获取了新的DFA，画图/表

DFA化简

  1. 将状态分划为终态集与非终态集

  2. 对集合不断进行分划，直到不可分

  3. 在每个分划中选一个代表状态，删去其它状态

分划的方法

对于多个分划里的状态，如果他们对所有输入转化后的状态机都分别在同一个分划下，则它们可以被视为一个新的分划

语法分析

自上而下分析法

  • 非确定自上而下分析

  • 确定自上而下分析

非确定自上而下分析法很简单，就是一个一个试，试错了就回溯。

这里重点讲一下确定自上而下分析

确定自上而下分析主要有两个需求

  • 没有左递归，对有左递归的文法可以：

    • 添加新的非终结符

    • 使用BNF写法改写

  • 没有回溯，回溯一般有两种：

    • 某规则右部第一个非终结符相同引起的回溯

    • 右部为空引起的回溯

消除回溯---LL(1)文法

需要引入三个相关集：

  • FIRST

  • FOLLOW

  • SELECT

假设文法为：

  • 对于符号，为可以推导出的所有的首终结符或者可能的。

  • 对非终结,为所有的句型中之后的非终结符或者$（当且仅当时才会有$）

  • 设为中的规则，则有集定义（公式（1））

\tag{1}
SELECT(A\rightarrow{\alpha{}})=
\left\{
\begin{aligned}
& FIRST(\alpha)  &若\alpha\overset{*}{\nRightarrow}\xi\\
& FIRST(\alpha)\backslash\{\xi \}\cup FOLLOW(A) &若\alpha\overset{*}{\Rightarrow}\xi
\end{aligned}
\right.

文法为文法，当且仅当对中每个非终结符的任何两个不同的规则，有，其中，至多只有一个能推出空串

文法第一个L表明从左到右扫描输入串，第二个L表明分析过程使用最左推导，1表示每步只需要向前看一个符号就可以确定所使用的规则。

部分非文法可以改写为文法，主要途径有：

  • 消除左递归

  • 提取公共左因子来消除回溯

递归下降分析法

对文法进行分析的一种方法，很简单，略

预测分析法（LL(1)分析法）

对预测分析表，有：

  • 对文法中每个规则，若，则

  • 若，则对任意 有

其实，说白了上方两个规则的意思就是：对于规则，任何在中的元素都有

有了分析表之后就没有难点了，剩下内容略。

自下而上分析法

算符优先分析法

要求规定运算符之间的优先级关系

优先关系一般和出现的左右次序有关

要求所分析文法时算符优先文法

算符优先文法

算符文法：

定义：

  • 对文法，若它任何规则的右部都不存在两个相邻的非终结符，则称其为算符文法（即文法）

性质：

  • 任何句型都不含两个相邻的非终结符（废话

  • 若或出现在算符文法的句型中，则中任何含的短语必定含有

三种优先关系定义如下：

  • 当且仅当文法中含有或的规则

  • 当且仅当文法中含有的规则，且 或

  • 当且仅当文法中含有的规则，且或

算符优先文法：

  • 对任意两个终结符的优先关系都唯一确定的算符文法（也叫做文法）

算符优先关系表的构造

首先，对每一个非终结符定义以下两个集合：

然后，对于每个产生式，有：

  • for i from 1 to n - 1

    • 若和皆为终结符，则它们的优先级相等

    • 若和为非终结符，为非终结符，则和优先级相等（超出范围则跳过这一步）

    • 如果为终结符，为非终结符，那么对于中的每一个有：

      • 的优先级小于

    • 如果为非终结符，为终结符，那么对于中的每一个有：

      • 的优先级大于

  • 对于的所有，置；对于中的所有，置；置

LR(0)分析法

活前缀

  • 字符串不包含字柄右部任何符号的前缀

构造活前缀DFA

（1）定义闭包函数

若在中，则每一形如的项目也在其中

（2）转移函数

的意义就是找出状态中后所有带有的规则，将后移一位形成的新项目集

构造LR(0)分析表

根据自动机构造就完事了，在规则最后就规约，不在就移进；遇到则acc

Important

注意：LR(0)语法不能有移进-规约冲突或者规约-规约冲突，即在活前缀DFA的任意状态中：

  • 不能同时有和

  • 不能有多个以结尾的规则

SLR(1)分析法

  • 要求移进项目的后方一个符号和规约项目的集合两两相交为空（符合这个要求的文法叫SLR(1)文法）

则在分析过程中遇到冲突时可以

  • 检查输入是否和某个移进项目之后的符号相同，是则移进

  • 否则检查在哪个规约项目的集中，在哪个就用哪个规约

  • 此外报错

LR(1)分析法

和SLR(1)其他部分相同，分析时遇到规约项目不检查集合，而是检查搜索符

  • 若，搜索符为在中，则每一形如的项目也在其中，且搜索符为

注意，最终搜索符可能是多个算式合并后的结果

LALR(1)分析法

合并LR(1)中的同心集

Tip

同心集：除了搜索符以外主体部分都相同的集

同心集的合并就是合并搜索符