编译原理复习笔记

背景

这门课学着十分痛苦，因为我认为学习如何编译没有什么作用。而且下一届网安同学这门课就变成考查课了，这让我愤愤不平。然而生活还是要继续，做做笔记吧——

计算机语言的发展

1. 机器语言 Machine Language 与汇编语言 Assemble Language
2. 高级语言 High Level Language
3. 命令语言 Command Language

目前我熟悉高级语言与命令语言，Linux的命令的简介与高效让我印象深刻。

汇编语言则是只是粗略得看了几个指令，没有实际使用过。感觉能熟练使用汇编得时候，就是已经对计算机组成十分熟悉了。

翻译系统

1. 翻译程序 Translator 将某一种语言描述的程序 Source Program 等价地翻译成另一种语言描述 Object Program 的程序。

   我没有见过具体的翻译程序。感觉IDA PRO里把汇编翻译成C貌似有点接近？

2. 解释程序 Interpreter

   这和翻译程序的差别类似于 口译和笔译，解释程序是对源程序是一句一句解释的，而翻译程序是一次性翻译好。

3. 编译程序 Compiler

   编译程序和翻译程序应该类似。只不过编译程序的源程序是高级程序语言，而目标语言是汇编或者机器语言程序。

编译系统是什么呢？

实际上就是编译程序加上运行系统。首先将源程序通过编译程序编译成为目标语言，然后这个目标语言在运行系统上运行，接受输入后运算后输出。

编译系统的功能分析

1. 程序分析

   需要分析 词法 语法 和语义

2. 分析综合

   语句的翻译、代码生成

3. 标识符处理：左值和右值的绑定

   变量：存储单元

   函数：目标代码序列

编译程序总体结构

1. 词法分析

   词法分析由词法分析器Lexical Analyzer 又叫做扫描器Scanner

   输入：字符串

   输出：（种别码，属性值）——序对

   ​ 属性值——token的机内表示

2. 语法分析由语法分析器 Syntax Analyzer 又叫所 Parser

   输入：token序列

   输出：语法成分

3. 语义分析

   分析由语法分析器识别出的语法单位的语义

4. 中间代码生成

   中间代码的特点：简单规范 与机器无关 易于优化与转换

5. 代码优化

   对中甲代码进行优化处理；对代码进行等价变化以提高执行效率

   之前做用C来做实验的时候，g -o2 貌似就能指定优化效率。现在看来就是g++编译器把中间代码就行优化的过程。

   优化分为和机器无关的优化和与机器有关的优化

   无关主要指的是代码层面比如常数运算在编译期就完成，将循环不变的计算移出循环等等。

   而有关优化是会影响到机器的，比如将常用量放入寄存器，根据算法访存的要求安排Cache等等。

6. 目标代码生成

   目标代码的形式具有绝对地址的机器指令 汇编语言形式的目标程序 模块结果的机器指令

7. 表格管理

   管理各种符号表（常数、标号、变量、过程、结构），查、填源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。

8. 错误处理

   进行各种错误的检查、报告、纠正，以及相应的续编译处理

模块分类

1. 分析：词法分析 语法分析 语义分析 中间代码生成

2. 综合： 代码优化 目标代码生成

3. 辅助：符号表管理 出错管理

   这8项功能分别对应8个模块

编译的前端和后端

1. 前端

   与源语言有关、与目标机无关的部分

   词法分析 语法分析 语义分析 中间代码生成 与机器无关的代码优化

2. 后端

   与目标机有关的部分

   与机器有关的代码优化 目标代码生成

编译程序的生成

1. 编译程序的自展技术

   直接实现一个C语言 编译器太复杂。先用汇编语言实现一个C语言子集的编译程序。那么我们就可以汇编语言处理这个编译程序了。然后我们用这个子集来编制C语言的编译程序。便实现了编译。

2. 利用编译 程序自动生成器

词法分析器的功能

词法分析器叫做$Scanner$，直接翻译的话就是扫描器，实际上这和它实际干的活也十分匹配。词法分析器干的活就是去分析源代码，然后输出单词符号token。

这个所谓的token实际上通常就是一个二元组(单词种类，属性值)

所以词法分析器的关键就是找到符号的分隔符，从而将各个符号写成一个个token，最后我们扫描完了，也就获得了一个token序列。这便是词法分析器的输出了。

单词符号的表示

单词符号，也就是token可以分类以下5类。

1. 关键字，也称保留字

   这个比较好理解，比如c中的return、int都是保留字。我们不能这这些关键字来定义变量名。

2. 标识符

   这实际上就是我们定义的一些变量名，函数名之类的。是一些用来表示名字的合法串。

3. 常数

   比如整形，实型，布尔型，字符型等。

4. 运算符

   有算数运算符、逻辑运算符、关系运算符等

5. 界限符

   这个可能比较陌生，比如, ; () :=，用于运算也用于分隔对象。

   比如python中逗号的使用实例

   a, b = 1, 2

   至于这个例子中的:=是什么意思，我挺好奇的，课上看到的时候也有些困惑。

单词符号的机内表示之前说过，是一个二元组。内容为$(单词种别码, 单词自身值)$。

以下为种别码的确定规则：

1. 关键字：一种一码

   不知道关键字是怎么分"种"的

2. 标识符：一种码。

   这说明所有的标识符的种别码都是一个，可能就叫id？

3. 常数： 一类型一码

   这里我们可以看到，不同种类的常数将有不同的种别码。

4. 界限符：一符一码

   这里可以看到没个界限符都有一个独一无二的种别码，十分牛皮

那单词符号种的属性值是怎么样的呢？

我们发现有一些符号是没有自身值得，比如关键字、界限符、运算符。

而有些是有值得，比如常数或者标识符。常数本身就是属性值。而标识符的属性值要写什么呢？我们需要写符号表中的入口地址。

符号表的作用

符号表这个表格是由编译程序简历的，用于存储程序在编译或者运行中所使用的变量或常量等信息。

并且这个符号表贯穿于整个编译过程，包括词法分析阶段、语法分析阶段、语义分析阶段及中间代码生成阶段、数据存储分配、代码优化阶段、目标代码生成阶段。

符号表首先是在词法分析阶段建立的。 词法分析阶段将不重复的标识符、数字和字符常量的性质填入符号表中，不日名字、类型、数值等。并将变量在符号表中的入口地址写道其本身的TOKEN字中。

符号表中包括名字 NAME, 类型 TYPE, 种属 KIND, 数值 VAL, 作用域和地址 ADDR, 还带有一个字符串表。

名字栏中包含两个子栏，分别存放标识符在字符串表中的起始位置和长度。类型栏表示该标识符的类型(整型，实型，布尔还是字符)，种属栏表示该标识符属于哪一类的名字（简单变量、常数名、数组名、过程名）；数值栏存放常数标识符的值，地址栏存放分配给符号的地址。

感觉这个符号表填的东西还挺多的。

词法单元的识别

词法分析器要求能够检查输入字符串，在前缀中找出和某个模式匹配的词素。

通过正则定义来描述各个词法单元的描述。

编译原理的正则就是我们常见的正则，和形式语言里古板的，没有生气的正则不同，在这里，我们可使用以许多已经习以为常的拓展

1. r+ 等价于rr*
2. r? 等价于 $\epsilon | r$
3. $[a_1a_2..a_n]$等价于$a_1|a_2|..|a_n$
4. $[a-e]$等价于$a|b|c|d|e$

这才是正则嘛！

状态转化图

状态转化图 transition diagram是词法分析器的重要组件之一。

1. 状态(State)
   • 状态可以看作是已处理部分的总结
   • 某些状态为接受状态或总结状态，表名已经找到了词素
   • 加上*的接受状态表示最后读入的符号不在词素中
   • 开始符号用 start边表示。
2. 边(edge) 从一个状态转向另一个状态。

当状态到达接受状态表名我们识别到了某个标识符。

词法分析器的设计与实现

我们可以用转化图来构造词法分析器。所以我们需要将状态转化图的一些功能用代码实现。

1. 变量State记录当前状态
2. 一个Switch根据State的值换到相应代码
3. 每个状态对应一段代码
   • 这段代码根据读入的符号确定下一个状态
   • 如果找不到相应的边，则调用fail()进行错误恢复
4. 进入某个接受状态时，返回相应的词法单元
   • 注意状态有*标记时，（即终结符号）需要回退forward指针。

处理多个模式的方法

以上只考虑了一个模式，那实际上词法分析肯定时有多种模式供识别的，那怎么办呢？

有以下3种可能的方法。

1. 顺序地尝试各个词法单元对用地状态转化图。如果引发fail()，回退并启动下一个状态图。可以根据优先级确定尝试顺序。
2. “并行”地运行各个状态转化图。通过贪心策略，识别最长地和某个模式匹配地输入前缀。
3. 预先把各个状态转化图合成一个状态转化图，然后运行这个状态转换图。

LEX介绍

1. LEX源程序->LEX编译器->Lex.yy.c
2. Lex.yy.c->C编译器->词法分析器L
3. 输入流->词法分析器L->Token序列

第三章总结

1. 词法从组成源程序地字符行中寻找出单词，并给出它们地种别和属性——输出二元组序列

2. 高级语言地单词组成一个3型语言

   0型文法：短语结构语法 Phrase Structure Grammars

   1型文法：上下文有关语法 Context-Sensitice Grammars

   2型文法：上下文无关文法 Context-Free Grammars

   3型文法：正规文法 Regular Grammars。也许翻译成正则文法更好。

   3型文法产生的语言就就叫做3型语言。

3. 3型语言可以用RE、RG、FA描述。

   RE 应该是Regular Expression

   RG 应该是Regular Grammar

   FA 应该是Finite Automata

4. FA的状态转移图，可以被用来指导相应的语法分析器的实现

5. 3型语言相应的理论指导人们构造出了高级语言的词法分析器的自动生成器，如Lex

语法分析的功能

ok，我们已经完成了词法分析。接下来就是语法分析啦！

语法分析需要实现什么功能呢？

我们指导，词法分析已经将源代码转化为了单词符号序列。所以语法分析器就需要判断该Token序列是否符合该语言的文法，即是否构成一个合法的“句子”。

即语法分析器的输入：Token序列

语法分析器的输出：

• 分析树
• 出错处理：定位、续编译

我们可以运用的分析方法有：

1. 自顶向下（递归下降、预测分析）

2. 自底向下（算符优先、LR分析器）

   目前还看不懂（

自顶向下分析面临的问题与CFG的改造

自顶向下的分析

什么是自顶向下的分析呢？是从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。

比如从树根S出发，构造所给输入符号串的语法树

例，G为$S\rightarrow xAy\ \ A\rightarrow**|* $，输入串：$x**y$

它的语法分析树是怎么样的呢？远程连接不好截图，这里描述一下，首先根据第一个推导式，就是根节点S分出三个节点$x,A,y$。然后A节点再分出两个节点$*$和$**$。

存在的问题

这个自顶向下的语法分析技术存在一些问题。

1. 回溯

   为什么会有回溯呢？

   文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。试探的过程中发现匹配不上，就会产生回溯。

   就拿我们之间的G为例子。G中有个非终结符A，它的产生式有两个值，分别为$*$和$**$。如果我们的语法分析器第一次将A尝试为$*$，结果为$A*B$，发现和输入不符合，则需要进行回溯。

2. 左递归问题

   左递归大概就是可以无穷递归，然后陷入一个循环。

   比如$S\rightarrow Say|*$。那么在判断某个句子的时候，可能会陷入循环$S\rightarrow Sayayay...ayay$。

重要概念回顾

1. 推导：$\alpha A\beta \Rightarrow \alpha\gamma\beta$（依据$A\rightarrow\gamma$）
2. 最左（Left-most）推导——最左分析
   • 左句型
   • 最左推导对应最右规约
3. 最右（Right-most）推导——最右分析
   • 规范推导、规范句型（右句型）
   • 最右推导对应最左规约（规范规约）
4. 二义性（先天二义性语言、二义性文法）

第四章 语法分析

语法分析的功能

检查由扫描器输出的单词符号序列是否符合该语言的文法——句子。

经过我们形式语言的学习，我们已经知道了一个文法可以生成一个语言。而句子就是语言这个集合中的一个元素。

语法分析器的输入：Token序列

语法分析器的输出：分析树

出错处理：定位、续编译

分析方法： 自顶向下（递归下降 预测分析） 自底向上（算符优先 LR分析器）

自顶向下的分析

从文法的开始符号出发，寻求所给的输入符号串的最左推导

从树根S开始，构造所给输入符号串的语法树。

自顶向下的分析可能会产生回溯。

产生回溯的原因是因为文法产生式的右侧如果有多个候选式，并且这几个候选式的第一个符号相同的话，那么语法分析程序就无法根据当前输入符号来选择产生式，只能去试探。试探的时候发现出错了，就需要回溯。

左递归问题

这个左递归确实非常离谱。因为如果$S$一开始推到为了*。因为*是一个终结符号，它就不会往后继续推导了。所以语法分析器就会认为这样不对。进行回溯。

语法分析器接着会去尝试推到为Say，发现不对，继续推导，还是不对，永远的循环。

感觉左递归问题应该是文法写的不好。如果这里文法写为$S\rightarrow*S|Say|ay$就可以产生出*ayay了。

以下是更加直观的二义性的例子。所以二义性，就是同一个句子，当我们推导的顺序不同时，可能会产生出不同的结果。【实际上更加专业说会产生出两颗不同的语法树】

解决的办法就是重写文法，并且引入新的语法变量

注意这里的M 后面的other的位置。实际上时$M\rightarrow [if\ E\ then\ M\ else\ M]|other$

所以如果是有一些不是if else的结果的式子的话，就得选择M得other。

这样改造后消除了二义性。

实际上对于 if $a\neq0$ then if $a\gt0$ then b=1 else b = -1

这个改造后得文法将会把把第一个if后面得句子看作一个整体，也就是 if $a\neq0$ then {if $a\gt0$ then b=1 else b = -1}。

左递归得消除方法

1. 直接左递归 $A\Rightarrow A\alpha$

2. 间接左递归 $A\Rightarrow^+ A\alpha$

   先复习形式语言还是有好处得，这里得加号就是经过1步以上推导得意思。

3. 消除方法

   将$A\rightarrow A\alpha|\beta$ 替换为 $A\rightarrow\beta A'$和$A'\rightarrow\alpha A|'\epsilon$

   主要方法就是利用增加语法变量的方法，将产生式的右侧中的语法变量不在最左侧。

   这个消除方法貌似很重要，需要背下来。

直接左递归消除

利用上面说的消除公式来直接消除。什么样的产生式需要消除呢？只需要看产生式右侧是不是满足$A\rightarrow A\alpha |\beta$的形式，即是有候选式，并且第一个候选式的最左边是一个语法变量。

在这里例子中就将前两个产生式进行了直接左递归消除。第三个式子不用消除，为什么呢？因为它虽然有两个候选式，但是第一个候选式的左侧是一个左括号，它是一个终结符号，不是一个语法变量，所以不需要进行左递归消除。

间接左递归消除

它利用的方法就是把所有的产生式从低级往高级慢慢代进去，最后得到一个S（即开始符号）的产生式。

这个时候一般只有一个产生式了，看这个S的产生式是不是可以符合$A\rightarrow A\alpha|\beta$的模式。

如果是，则利用公式进行左递归消除。

这里我们也见证了如果右侧是多个候选式的处理办法，因为$A\rightarrow A\alpha|\beta$ 消除式子中看起来只有两个候选式嘛，而上面的例子中S的产生式有4个候选式，其中第一个候选式中的第一个是语法变量。

所以我们需要把后面三个候选式看成一个$\beta$。然后$A\rightarrow \beta A'$要怎么弄呢？

我们看到它们三个候选式都分别成了$S'$。

变成了$abcS'|bcS'|cS'$。

消除左递归的一般方法

这个产生式组不知道是怎么得到的。

解决回溯问题 ——提取左因子

实际上就是将两个产生式共同部分单独写出了形成一个产生式。这样语法分析器就不会犯选择困难症了。因为现在只有一个产生式供它选择。

CFG的使用限制

1. 没有一种方法能够有效地分析所有上下文无关文法 context free grammar
   • 存在无法处理地2型文法
2. 每种方法能够处理一部分上下文无关文法
   • 每种方法都有适用范围

常用文法与分析方法

1. LL方法和LR文法都是CFG的子集（无二义性）

   可用不同的文法来描述同一种语言

2. 对于不同的文法，可用不同的分析方法

   • LL文法——递归下降分析法、预测分析法
   • LR文法——LR分析法
   • LL文法多用于编译的手工实现
   • LR文法多用于编译的自动实现

自顶向下的分析方法

基本思想

1. 寻找输入符号串的最左推导
2. 试图根据当前输入单词判断适用哪个产生式

基本过程

从根开始，按与最左推导相对应的顺序，构造输入符号串 token的分析树。

自顶向下例子1

FIRST集

定义：对于$\forall\alpha\in(V_T\cup V_N)^*$ 定义$\alpha$的首符号集

$FIRST(\alpha)=\{a|\alpha\Rightarrow^*a...., a\in V_T^*\}$

这里的$V_T$表示终结符号集合。$V_N$表示非终结符号集合，即语法变量集合。

实际上FIRST集就是某个符号可以经过若干步推导得到的第一个符号为终结符号的所有符号。

当然了，如果你开始一开始本身就是一个终结符号，你自己肯定也在你的first集中啦！

这里举个例子，比如$First(T)$。T能够推到为$FT'$。因为First集中的字符都是推导后的第一个字符，这也是first的含义，故$First(T)=First(F)$。我们再看F能够推导出$(E)|id$。首先括号是一个终结符号，然后id也是一个非终结符号。故$First(F)=\{(,id\}$。

如果考试直接让我们写出一个变量的first集的话，应该算是送分题了！

Follow集

定义：对于$\forall(A)\in V_N$定义A的后续符号集：$FOLLOW(A)=\{a|S\Rightarrow^* ...Aa..., a\in V_T\}$

Follow(A)的求法

1. 若$B\rightarrow \alpha A a \beta$，a是终结符，则a放入follow集中

   这和定义完全一致，不多说

2. 若$B\rightarrow \alpha AX\beta$，X是非终结符，则把$FIRST(X\beta)$放入Follow集中。注意需要删除first集合中的空串$\epsilon$

   follow集的定义中看起来那个非终结符号一定要紧紧挨着A。确实应该这样，但是有时候又可以不是这样，在A和a中如果夹了一些语法变量的话，在现在看来可能a不是follow集中的值，但是如果那些语法变量通过推导变为$\epsilon$了，这时a又是follow集中的值了。这里就把$X\beta$可以推导出的第一个语法变量【follow集已经帮你做好了推导】，即$First(X\beta)$放入follow集中了。

   Follow集中貌似是没有空串的，如果first集中有空串，记得删除。见书P141

3. 若$B\rightarrow \alpha A$或者$B \rightarrow \alpha A \beta$，但$\beta \Rightarrow \epsilon$，则把Follow(B)放到Follow(A)中。

   因为A在B的末尾，follow(A)就是follow(B)挺好理解的。你可能会疑惑follow(B)怎么求，这里我们就不用管啦，因为信息还不够，在式子中B后面可能还有式子了，比如Bc。

4. 若A是开始符，则$\$\in FOLLOW(A)$。

   这里的$应该和汇编中的符号相同，表示字符串的结束。

5. 若$A\rightarrow\alpha B \beta$，那么将所有$FIRST(\beta)$中除了$\epsilon$以外的所有符号都在FOLLOW(B)中。

6. 若$A\rightarrow\alpha B$或者$A\rightarrow\alpha B\beta$且$FIRST(\beta)$中包含$\epsilon$，那么FOLLOW(A)中所有的符号都在FOLLOW(B)中。

求follow集的例子

只能感叹求follow比求first难多了，需要把以上六条规则烂熟于心，而且在求follow之前，你得先把first集都求出来，因为会用到。

这里直接把first集给你了，然后让你求follow集。

我们来分析一下，这些follow都运用了哪些求法。

1. follow(E) 首先，这里E应该算开始符号，故$加入follow集，然后根据产生式$F\rightarrow(E)|id$。我们可以看到右括号紧紧挨着语法变量E，直接符合定义，故follow(E) = {$, )}

2. 然后follow(E’) 为什么直接等于follow(E)了呢？因为根据产生式$E\rightarrow TE'$。这里运用求法3，可以直接把Follow(E)放入Follow(E’)中。

   这里注意要求什么符号得follow集，就要把看成A，把其他的符号看成B来运用6个求法。

   你可能会怀疑这里为什么不用产生式 $E'\rightarrow +TE' | \epsilon$。因为你会发现这个无法运用任何求法。

3. 然后求follow(T)。求什么，我们就需要去看哪些产生式中有T。首先第一个产生式$E\rightarrow TE'$中有T。这里其实符合两个求法，首先符合求法2，我们需要将$FIRST(E')$加入follow集中，然后其实还符合求法3，因为E’可以推导为空串。故还需要将$FOLLOW(E)$放入follow集中。 再看产生式$E'\rightarrow+TE'|\epsilon$。同样符合求法3，原因同上，故需要将$FOLLOW(E')$加入follow集中。 然后因为我们之前加了三个东西，可能会产生重复，故用并集来合并。

   你可能会疑惑为什么没有使用产生式$ F \rightarrow FT’$。

   我们发现这个产生式，F在左侧，所以我们也许可能应用求法5和求法6。

   但是都不符合。

   实际上我们再观察一下，这些解法中都由一个基本要求，你这个产生式中至少得有一个终结符号吧233，这个产生式是一个语法变量推导出了两个语法变量，就没法求follow集了。

LL(1)文法

对于G中得任意变量A，$A\rightarrow \alpha_1|\alpha_2|...|\alpha_n$是G得所有A产生式，它们满足下列条件，则称G是LL(1)文法。

• $FITST(\alpha_i)\cap FIRST(\alpha_j)=\phi\ \ i\ne j$
• 当$\epsilon\in FIRST(\alpha_i)$时，$FOLLOW(A)\cap FIRST(\alpha_i)=\phi$

LL(1)文法表示了自顶向下方法能够处理的一类文法。

1. 第一个L表示从左向右扫描输入符号串
2. 第二个L表示生成最左推导
3. 1表示读入一个符号可确定下一步推导

表达式文法是LL(1)文法。

不是LL(1)的文法就会不确定性。

我们观察第二个产生式$A\rightarrow ab|a$。它有两个候选式，分别是a和ab。first(ab)和first(a)的值都是a，它们有了交集，不符合LL(1)文法的定义，所以它不是LL(1)文法。我们可以看到就因为first集有重叠，当语法分析器去分析cad这个字符的时候，就会去试探和回溯，这就是不确定性。

所以LL(1)的直观映像就是候选式那些follow集没有重叠的文法，也就是语法分析的时候不会有不确定性，非常顺畅。

不确定性的解决方法

1. 采用回溯算法

   这让编程能力羸弱的我无所应对

2. 改写文法

   将非LL(1)文法该写为等价的LL(1)文法

3. 无法改写时：

   • 增加其他的判别因素
   • 文法过于复杂，无法用自顶向下方法处理。

预测分析器 LL（1）分析器 结构

LL（1）分析器主要的组成部分有输入缓冲区、栈、预测分析表M。

栈就是普通的堆栈，有栈底，有栈顶，栈底为$。

输入缓冲区里就是我们需要来分析的句子。串结束符也是$

预测分析表是我们分析的依据，实际情况下需要程序员根据文法的产生式手动写。

LL（1）分析器 栈的变化的例子

看懂了下面的图，你对LL（1）分析法就了解的差不多了。

文法：

E->TE’

E’->+TE’|ε

T->id

要分析的句子 1+1

首先分为分析的句子是1+1，我们需要把它加入输入缓冲区中，注意在结尾加上结束标识。

然后开始初始化分析栈，即图中的第一步。它有两个步骤，一是将栈底符号$和开始符号E分别入栈。二是将输入指针指向输入缓冲区的第一个字符。

接着开始开始分析栈顶符号E和当前输入符号1。我们以人的视角来看的话，这时候很显然需要把$E$进行推导，因为E不等于1。所以根据产生式$E\rightarrow TE'$，把栈中的E用$TE'$代替。注意在栈中的排列顺序，产生式最左边的符号需要放到栈顶。

因为这时LL分析法，它需要找到一个最左推导。故它需要对最左侧的语法变量先进行推导。故把它们放到栈上方的话才能够优先和输入字符进行反应。

图中省略的第二部应该就是E弹栈的过程，因为肯定需要先把E弹掉，E’ 和T才能进来嘛233。之后省略的步骤也是省略的弹栈的过程。

现在我们考虑图中的第三步。再分析栈顶符号T和当前输入符号1。因为T能够推导出id，所以这时候我们需要将T推导为id，即到了第五步。

在第五步中，栈顶符号为id，当前输入符号为1，1就是id，匹配了，这时候我们需要把id弹栈。然后把输入指针往后移1位。相当于1已经被识别了。

第七步。栈顶符号E’，输入符号位+。这时候很显然我们需要利用产生式$E'\rightarrow +TE' | \epsilon$ 。将E’ 推导为$+TE'$。就到了第九步。

第九步，栈顶符号+和输入符号+完全一致，弹栈。输入指针指向下一个。

类似的操作，到了第十三步，栈顶符号位E’，输入符号为串终结符号。很显然这时候我们需要将E’ 推导为 $\epsilon$，相当于直接把E’弹栈了。

所以让我们续写这个图的话，第十三步应该是把E’推导为$\epsilon$。即弹栈。

然后第十四步，栈顶符号为$。输入符号$。两者同时达到终结符号。说明分析成功。

然后我们考虑一下程序如何知道如何推导，因为在之前的过程中我们是通过人眼看出接下来应该怎么推导的。这个时候需要用到预测分析表了，表的行对应栈顶符号，表的列对应当前输入字符。表中的项代表在行对应的栈顶符号和列定影的输入字符情况下应该干的事，是可以进行推导，还是报错。

我们看到，表中的E在遇到id的时候会进行推导为TE’，这正是我们在之前第一步到第三步干的事情。

再看E’遇到$的时候 进行空串推导，这正是我们最后第十二步到第十四步干的事情。

所以程序实现时，分析栈顶符号和输入符号的时候就需要来查这个预测分析表。

那比如我们在栈顶符号为E而输入符号为+，那要怎么办呢？我们仔细观察产生式就能知道，E直接遇到了+应该是不正常的，因为E只有一个产生式E->TE’，而T也只有一个产生式T->id。所以E应该会先遇到一个id，而不是一个+。这个时候我们就需要进行报错。

以下为LL（1）分析的详细过程

LL（1）分析器 预测分析表的构造算法

我们可以看到构造算法中会用到first集和follow集。我们先把上面例子的每个语法变量的first集和follow集算出来吧!

文法:

$E\rightarrow T E'$

$E'\rightarrow +TE' | \epsilon$

$T\rightarrow id$

先求Firsr集。

$Firsrt(E)=\{id\}$

$First(E')=\{+,\epsilon\}$

$First(T)=\{id\}$

再求Follow集，follow集从开始符号算起。

$Follow(E)=\{\$ \}$

开始符号的follow集中有字符串结束符号

$Follow(E')=Follow(E)=\{\$\}$

$Follow(T)=First(E')=\{+,\epsilon\}$

求完了，我们现在来按照上面的定义来生成预测分析表。

对于第一个产生式，$First(TE')=First(T)=\{id\}$。

填表。

	id
E	$E\rightarrow T E'$

对于第二个产生式，$First(+TE'|\epsilon)=\{+,\epsilon\}$

	id	+	$\epsilon$
E	$E\rightarrow T E'$
E’		$E'\rightarrow +TE'$	$E'\rightarrow \epsilon$

这里要注意，我们需要手动将产生式的的候选式分开。不然到时候栈不知道具体怎么推导。

实际上 $E'\rightarrow +TE' |\epsilon$ 是两个产生式

$E'\rightarrow +TE'$和$E'\rightarrow \epsilon$。只不过我们为了形式简单进行了合并。到时候具体程序实现的时候可能还是要分开。就像这里手动填表的时候，需要分开。

然后$First(+TE'|\epsilon)=\{+,\epsilon\}$有空串，更准确的说是$First(\epsilon)=\{\epsilon\}$中有空串，即$E'\rightarrow \epsilon$贡献的。

便去看$Follow(E')=\{\$\}$，于是将$E'\rightarrow \epsilon$写入M[E’, $]中。

	id	+	$\epsilon$	$
E	$E\rightarrow T E'$
E’		$E'\rightarrow +TE'$	$E'\rightarrow \epsilon$	$E'\rightarrow \epsilon$

再去看最后一个产生式$T\rightarrow id$。$First(id)=\{id\}$。

填表。

	id	+	$\epsilon$	$
E	$E\rightarrow T E'$
E’		$E'\rightarrow +TE'$	$E'\rightarrow \epsilon$	$E'\rightarrow \epsilon$
T	$T\rightarrow id$

现在我们处理好了每个产生式。然后将表中所有的空闲位置都加上错误标志即可。

	id	+	$\epsilon$	$
E	$E\rightarrow T E'$	错误	错误	错误
E’	错误	$E'\rightarrow +TE'$	$E'\rightarrow \epsilon$	$E'\rightarrow \epsilon$
T	$T\rightarrow id$	错误	错误	错误

这便是预测分析表的构造过程了。

预测分析中的错误恢复

当预测分析器报错时，标识输入的串不是句子

对于使用者而言，希望预测分析器能够进行恢复处理后继续语法分析过程，以便在一次分析中找到更多的语法错误

但是有可能恢复的并不成功，之后找到的语法错误有可能是假的

进行错误恢复时可用的信息：栈里的符号，待分析的符号

两类错误恢复方法：

1. 恐慌模式
2. 短语层次的恢复

恐慌模式

语法分析器忽略输入中的一些符号，直到出现由设计者 选定的某个同步词法单元

同步词法单元就是这个程序结构结束的标志

我在词法分析实验中时，发现一个单词不符合某个模式后，就一直找到换行符。换行符前面的单词截取出来报错。

这里举一个例子。

这里的文法在书本P138。这里摘录一下。

$E\rightarrow TE'$

$E'\rightarrow +TE' | \epsilon$

$T\rightarrow FT'$

$T' \rightarrow *FT' | \epsilon$

$F \rightarrow (E) | id$

例子说使用First 和 Follow集作为同步集合。实际上书上只用了Follow集，这里我们来 求一下E T 和F的follow集。

先求First集。

$First(E)=\{(,id\}$

$First(T)=\{(,id\}$

$First(F)=\{(,id\}$

再后Follow集。

$Follow(E)=\{), \$\}$

$Follow(T)=First(E')\cup Follow(E)=\{+, ), \$\}$

因为在第一个产生式中E’在T后面，而E’ 可能会推导为空串，则E的follow集需要加入到follow(T)中

值得注意的是，貌似follow集 中是不考虑空串的，需要手动去掉。

$Follow(F)=First(T')\cup Follow(T)=\{*, +, ), \$\}$

我们可以看到上面图中表sync的符号就是 E T F对应follow集中的符号。

这里解释一下用follow集的合理性。同步词法单元就程序结构结束的标志。而follow集标识某个语法变量后面紧跟着的终结符号，遇到终极终极符号了，自然说明这个语法变量的作用域已经结束了。

同时要注意follow集中的那个终极符号不是这个结构里的内容，而属于下个结构的开始符号。

然后我们实际来恐慌处理一个错误输入 $+id*+id$

开局E与+，表中为空，即+不是Follow(E)中的符号。直接忽略+。

然后一路顺畅，到了F与+。一看发现是sync。ok，弹出非终结符号F。

为什么不把+也弹掉呢？因为+是follow(F)。属于下个结构里的开始符号，不是F的作用域。

删除输入符号即忽略输入符号只出现在表格中为空时，这正是恐慌处理正在干的事情。

实际这个例子没有体现出恐慌性，因为我们发现F非常牛，它要么是正确推导，要么就是synch。因为它的follow集很多。

实际上恐慌体现在遇到表中为空格的情况，因为每次遇到空格，我们就需要丢弃输入的字符，去看下一个输入字符。当我们遇到一个sync的时候，实际上恐慌已经结束了。

短语层次的恢复

• 在预测语法分析表的空白条目中插入错误处理例程的函数指针
• 例程可以改变、插入或删除输入中的符号，发出适当的错误消息。