atitit.自己动手开发编译器and解释器(2) ------语法分析，语义分析，代码生成--attilax总结

1. 建立AST 抽象语法树 Abstract Syntax Tree，AST） 1

2. 建立AST 语法树----递归下降（recursive descent）法 2

3. 语法分析概念 2

3.1. 上下文无关语言，非终结符（nonterminal symbol），终结符（terminal symbol）。注 2

3.2. 最左推导。当然也有最右推导 3

3.3. 分支预测的方法是超前查看 4

3.4. LL(k) 跟个LR(k)文法 4

3.5. ast错误报告 CPS（Continuation Pass-in Style）风格 。 5

4. ---code 6

5. 下一个编译器重要的阶段——语义分析8

5.1. 语义分析任务1--类型检查 8

5.2. 语义分析的第二个主要任务是找到所有标识符的定义。 9

5.2.1. 。所以我们无法只用一次抽象语法树的遍历来完成语义分析。我采用的做法是分成三次遍历， 9

6. 下一个阶段——代码生成（设计模式---解释器模式来实现。） 9

7. 参考 10

1. 建立AST 抽象语法树 Abstract Syntax Tree，AST）

1.那么什么是抽象语法树呢？其实就是经过简化和抽象的语法分析树。在完整的语法分析树中每个推导过程的终结符都包含在语法树内，而且每个非终结符都是不同的 节点类型。实际上，如果仅仅是要做编译器的话，很多终结符（如关键字、各种标点符号）是无需出现在语法树里的；而前面表达式文法中的Factor、 Term也实际上没有必要区分为两种不同的类型，可以将其抽象为BinaryExpression类型。这样简化、抽象之后的语法树，更加利于后续语义分 析和代码生成。使用.NET里的面向对象语言来实现语法树，最常见的做法就是用组合模式，将语法树做成一颗对象树，每种抽象语法对应一个节点类。下图就是 miniSharp的抽象语法树的所有类。

Attilax的总结是从上而下，先写大框架组成法。。在在里面的表达式里面使用建设函数或者set函数注入类k...或者更好的办法但基本思想是使用一个Stack，在进入一个新的作用域（大括号包围的语句块）时压入一个新的HashSet，储存这一作用域内声明的变量。当作用域结束时弹出一个HashSet，这个作用域内的变量就从表里删除了

Attilax初次大概用了一天时间就解决了AST构建问题

作者:: 老哇的爪子 Attilax 艾龙，  EMAIL:1466519819@qq.com

转载请注明来源： http://blog.csdn.net/attilax

2. 建立AST 语法树----递归下降（recursive descent）法

今天我们就来讨论实际编写语法分析器的方法。今天介绍的这种方法叫做递归下降（recursive descent）法，这是一种适合手写语法编译器的方法，且非常简单。递归下降法对语言所用的文法有一些限制，但递归下降是现阶段主流的语法分析方法，因 为它可以由开发人员高度控制，在提供错误信息方面也很有优势。就连微软C#官方的编译器也是手写而成的递归下降语法分析器。

手写的递归下降语法分析器可以很容易地加入错误恢复，但需要针对每一处错误手工编写代码来恢复。像C#官方编译器，给出的语法错误信息非常全面、精确、智能，全都是手工编写的功劳

手写递归下降的方式是目前很多编译器采用的方式，如果你想写一个商业质量的编译器，这是首选的方

使用递归下降法编写语法分析器无需任何类库，编写简单的分析器时甚至连前面学习的词法分析库都无需使用

Attilax的总结是从上而下，先写大框架组成法。。在在里面的表达式里面使用建设函数或者set函数注入类k...或者更好的办法但基本思想是使用一个Stack，在进入一个新的作用域（大括号包围的语句块）时压入一个新的HashSet，储存这一作用域内声明的变量。当作用域结束时弹出一个HashSet，这个作用域内的变量就从表里删除了

Attilax初次大概用了一天时间就解决了AST构建问题

3. 语法分析概念

3.1. 上下文无关语言，非终结符（nonterminal symbol），终结符（terminal symbol）。注

语法分析。简单而言，这一步就要完整地分析整个编程语言的语法结构。上回说到词法分析的结果是将输入的字符串分解成一个个的单词流，也就是诸如关键字、标 识符这样有特定意义的单词。一种完整的编程语言，必须在此基础上定义出各种声明、语句和表达式的语法规则。观察我们所熟悉的编程语言，其语法大都有某种递 归的性质。例如四则运算与括号的表达式，其每个运算符的两边，都可以是任意的表达式。比如1+a是表达式，

再比如if语句，其if的块和else的块中还可以再嵌套if语句。我们在词法分析中引入的正则表达式和正则语言无法描述这种结构，如果用DFA来解释，DFA只有有限个状态，它没有办法追溯这种无限递归。所以，编程语言的表达式，并不是正则语言。我们要引入一种表现能力更强的语言——上下文无关语言。

非终结符（nonterminal symbol），代表可以继续产生新符号的“文法变量”。 符号→表示非终结符可以“产生”的东西。而上述产生式中的蓝色id、+、（等符号，是具有固定意义的单词，它们不再会产生新的东西，称作终结符（terminal symbol）。注

3.2. 最左推导。当然也有最右推导

产生式经过一系列的推导，就能够生成各种完全由终结符组成的句子。比如，我们演示一下表达式(a + b) + c的推导过程：

E  =>  E + E  =>  (E) + E  =>  (E + E) + E  =>  (a + E) + E  =>  (a + b) + E  =>  (a + b) + c

推导过程中的=>代表将当前句型中的一个非终结符替换成产生式右侧的内容。以上推导过程中，我们每次都将句型中最左边一个非终结符展开，所以这种推导称为最左推导。当然也有最右推导，不同之处就算是每次将句型中最右边的非终结符展开：

可见，同一个结果可以具有多种不同的推导过程。使用最左推导时，句型的左侧逐渐变得只有终结符；而最右推导正好相反，推导过程中句型的右侧逐渐变得只有终结符，最终结果都是整个句子变为终结符。所有符合文法定义的句子，都可以用文法的产生式推导出来

可以看到最左推导和最右推导的语法分析树是一样的，这证明用相同的文法解析同样的输入也至少存在两种不同的分析方法。后续篇章介绍的递归下降法就是一种最左推导的分析方法，而另一类非常流行的LR分析器则是基于最右推导的分析方法。目前流行的编译器开发方式是在语法分析阶段构造一棵真正的语法分析树，然后再通过遍历语法树的方法进行后续的分析，所以最左推导和最右推导的过程对我们来讲区别不大。

为何这种语言和文法叫做“上下文无关”呢？其实这里的“上下文无关”是指文法中的产生式都可以无条件展开为箭头右侧的内容。另外存在一种上下文相关文法， 它的产生式都需要在一定条件下才能展开。上下文相关语言要比上下文无关文法复杂得多，而其没有一种通用的方法可以有效地解析上下文相关语言，因此它也不会 用在编程语言的设计当中。 也许已经意识到，即使是上下文无关文法和语言，也要比正则表达式和正则语言复杂得多。

3.3. 分支预测的方法是超前查看

到非终结符N有两个产生式，所以在ParseNode方法的一开始我们必须做出分支预测 。。分支预测的方法是超前查看（look ahead）。就是说我们先“偷窥”当前位置前方的字符，然后判断应该用哪个产生式继续分析

上面我们采用的分支预测法是“人肉观察法”，编译原理书里一般都有一些计算FIRST集合或FOLLOW集合的算法，可以算出一个产生式可能开头的字符， 这样就可以用自动的方法写出分支预测，从而实现递归下降语法分析器的自动化生成。ANTLR就是用这种原理实现的一个著名工具。

其实我觉得“人肉观察法”在实践中并不困难，因为编程语言的文法都特别有规律，而且我们天天用编程语言写代码，都很有经验了。

3.4. LL(k) 跟个LR(k)文法

支持递归下降的文法，必须能通过从左往右超前查看k个字符决定采用哪一个产生式。我们把这样的文法称作LL(k)文法。这个名字中第一个L表示从左往右扫描字符串，这一点可以从我们的index变量从0开始递增的特性看出来；而第二个L表示最左推导，想必大家还记得上一篇介绍的最左推导的例子。大家可以用调试器跟踪一遍递归下降语法分析器的分析过程，就能很容易地感受到它的确是最左推导的（总是先展开当前句型最左边的非终结符）。最后括号中的k表示需要超前查看k个字符

来看LL(k)文法的第二个重要的限制——不支持左递归。所谓左递归，就是产生式产生的第一个符号有可能是该产生式本身的非终结符。下面的文法是一个直截了当的左递归例子： ，如果在编写E的 递归下降解析函数时，直接在函数的开头递归调用自己，输入字符串完全没有消耗，这种递归调用就会变成一种死循环。所以，左递归是必须要消除的文法结构。解 决的方法通常是将左递归转化为等价的右递归形式： 大家应该牢牢记住这个例子，这不仅仅是个例子，更是解除大部分左递归的万能公式！

LR(k)文法的语法分析器。LR代表从左到右扫描和最右推导。LR型的文法允许左递归和左公因式，但是并不能用于递归下降的语法分析器，而是要用移进-归约型的语法分析器，或者叫自底向上的语法分析器来分析。我个人认为LR型语法分析器的原理非常优雅和精妙

3.5. ast错误报告 CPS（Continuation Pass-in Style）风格 。

作为编程语言的语法分析器，不能在遇到语法错误的时候简单地返回null，那样程序员就很难修复代码中的语法错误。我们需要的是准确报告语法错误的位置，更进一步，是程序中所有的语法错误，而不仅仅是头一个。后者要求解析器具有错误恢复的 能力，即在遇到语法错误之后，还能恢复到正常状态继续解析。错误恢复不仅仅可以用在检测出所有的语法错误，还可以在存在语法错误的时候仍然提供有意义的解 析结果，从而用于IDE的智能感知和重构等功能。手写的递归下降语法分析器可以很容易地加入错误恢复，但需要针对每一处错误手工编写代码来恢复。像C#官 方编译器，给出的语法错误信息非常全面、精确、智能，全都是手工编写的功劳。又回到我们是懒人这个残酷的事实，能不能在让解析器组合子生成的解析器自动具 有错误恢复能力呢？

如果要对失败的情形进行错误恢复，有两种可行的选择：1、假装要解析的Token存在，继续解析（这种做法相当于在原位置插入了一个单词）；2、跳过不匹配的单词，重新进行解析（这种做法相当于删除了 一个单词）。如果漏写一个分号或者括号，插入型错误恢复就能有效地恢复错误，如果是多写了一个关键字或标识符造成的错误，删除型错误恢复就能有效地恢复。 但问题是，我们怎么能在组合子的代码中判断出哪种错误恢复更有效呢？最优策略是让两种错误恢复的状态都继续解析到末尾，然后看哪种恢复状态整体语法错误最 少。但是，只要有一个字符解析失败，就要分支成两个完整解析，那么错误一旦多起来，这个分支的庞大程度将使得错误恢复无法进行..我们可以让两条分支都解析到底，然后挑错误较少的分支作为正式解析结果。但同上所述，这种做法的分支多得难以置信，效率上决定我们不能采用。

为了避免效率问题，我们需要一种“广度优先”的处理方案。在遇到错误时产生的“插入”和“删除”两条分支，要同时进行，但要一步一步地进行。这里所谓的一 “步”，就是指AsParser组合子读取一个词素。我们看到四种基本组合子中，只有AsParser组合子会用scanner来真正读取词素，其他组合 子最终也是要调用到AsParser组合子来进行解析的。我们让两个可能的分支都向前解析一步，然后看是否其中一条分支的结果比另外一条更好。所谓更好， 就是一条分支没有进一步遇到错误，而另外一条分支遇到了错误。如果两条分支都没有遇到错误，或者都遇到了错误，我们就再向前推进一步，直到某一步比另外一 步更好为止。Union组合子也可以采用同样的策略处理。这是一种贪心算法的策略，我们所得到的结果未必是语法错误最少的解析结果，但它的效率是可以接受 的

那么怎么进行“广度优先”推进呢？我们上次引入的组合子，当前的组合子无法知道下一个要运行的组合子是什么，更无法控制下一个组合子只向前解析一步。为了达到目的，我们要引入一种新的组合子函数原型，称作CPS（Continuation Pass-in Style）风格的组合子。不知道大家有多少人听说过CPS，这在函数式编程界是一种广为应用的模式，在.NET世界里其实也有采用。.NET 4.0引入的Task Parallel Library库中的Task类，就是一个典型的CPS设计范例。

而如果采用CPS，则是把B传递给A，这时我们称B是A的continuation，或者future。

自行决定如何调用future。这里最关键的思想是实现延迟调用future，从而实现“广度优先”的单步解析效果。

这个类里我们定义了整个解析器最终的一个future——它产生令所有分支判断停止的StopResult。这里最关键的是利用 result.GetResult虚方法推进广度优先的分支选取，并且收集这条路线上所有的语法错误。我们所有的语法错误就只有两种：“丢失某单词”（采 用了插入方式错误恢复）和“发现了未预期的某单词”（采用了删除方式错误恢复）。

4. ---code

private void ini() throws CantFindRitBrack {

// 定义一个堆栈，安排运算的先后顺序

Stack<AbstractExpression> stack = ctx.stack;

List<Token> tokenList = (List<Token>) fsmx.getTokenList();

// 运算

for (int i = 0; i < tokenList.size(); i++) {

Token tk = tokenList.get(i);

switch (tk.value) {

case "(": // comma exp

AnnoDeclaration annoDeclar = (AnnoDeclaration) stack.pop();

int nextRitBrackIdx = getnextRitBrackIdx(i, tokenList);

List sub = tokenList.subList(i + 1, nextRitBrackIdx);

annoDeclar.setAssList(sub, ctx);

stack.push(annoDeclar);

i = nextRitBrackIdx;

break;

default: // var in gonsi 公式中的变量

AbstractExpression left2 = new AnnoDeclaration(

tokenList.get(i).value);

stack.push(left2);

}

}

// 把运算结果抛出来

this.expression = stack.pop();

}

public void setAssList(List subTokenList, Context ctx) {

Stack<AbstractExpression> stack =  new Stack<AbstractExpression>();

List<Token> tokenList = subTokenList;

for (int i = 0; i < tokenList.size(); i++) {

Token tk = tokenList.get(i);

switch (tk.value) {

case ",": // comma exp

AbstractExpression right = new Assignment(tokenList.get(++i).value,tokenList.get(++i).value,tokenList.get(++i).value);

this.assignments.add((Assignment) right); 

break;

default: // var in gonsi 公式中的变量

AbstractExpression left2 =new Assignment(tokenList.get(i).value,tokenList.get(++i).value,tokenList.get(++i).value);

this.assignments.add((Assignment) left2) ;

//stack.push(left2);

}

}

//this.setAssList((List<Assignment>) stack.pop());

}

5. 下一个编译器重要的阶段——语义分析

所谓编程语言语义，就是这段代码实际的含义。 

语义分析是编译器前端最复杂的部分。因为这些编程语言的语义都非常复杂。语义分析不像之前词法分析、语法分析那样，有一些特定的工具来帮助。这一部分通常都是要纯手工写代码来完成。

好像attilax这个阶段可以没有，忽略。。

5.1. 语义分析任务1--类型检查

在语义分析中，类型检查是贯穿始终的一个步骤。像miniSharp这样的静态类型语言，类型检查通常要做到：

1. 判定每一个表达式的声明类型 

2. 判定每一个字段、形式参数、变量声明的类型 

3. 判断每一次赋值、传参数时，是否存在合法的隐式类型转换 

4. 判断一元和二元运算符左右两侧的类型是否合法（比如+不就不能在bool和int之间进行） 

5. 将所有要发生的隐式类型转换明确化

5.2. 语义分析的第二个主要任务是找到所有标识符的定义。

标识符在miniSharp里主要有：类名、字段名、方法名、参数名和本地变量名。遇到每个名称，我们必须解析出标识符表示的类、方法或字段的定义。

5.2.1. 。所以我们无法只用一次抽象语法树的遍历来完成语义分析。我采用的做法是分成三次遍历，

前两次分别对类的生命和成员的声明进行解析并构建符号表（类型和成员），第三次再对方法体进行解析。这样就可以方便地处理不同顺序定义的问题。总的来说，三次遍历的任务是：

1. 第一遍：扫描所有class定义，检查有无重名的情况。 

2. 第二遍：检查类的基类是否存在，检测是否循环继承；检查所有字段的类型以及是否重名；检查所有方法参数和返回值的类型以及是否重复定义（签名完全一致的情况）。 

3. 第三遍：检查所有方法体中语句和表达式的语义。

经过完善的语义分析，我们就得到了一个具有完整类型信息，并且没有语义错误的AST

6. 下一个阶段——代码生成（设计模式---解释器模式来实现。）

我们使用设计模式---解释器模式来实现。。解释器模式大大简化了语义分析的过程。。

attilax初次做解释器/编译器，也只需要一天时间就可以实现。。

前一阶段我们完成了编译器中的重要阶段——语义分析。现在，程序中的每一个变量和类型都有其正确的定义；每一个表达式和语句的类型都是合法的；每一 处方法调用都选择了正确的方法定义。现在即将进入下一个阶段——代码生成。代码生成的最终目的，是生成能在目标机器上运行的机器码，或者可以和其他库链接 在一起的可重定向对象。代码生成，和这一阶段的各个优化手段，统称为编译器的后端。目前大部分编译器，在代码生成时，都倾向于先将前段解析的结果转化成一 种中间表示，再将中间表示翻译成最终的机器码。比如Java语言会翻译成JVM bytecode，C#语言会翻译成CIL，再经由各自的虚拟机执行；IE9的javascript也会先翻译成一种bytecode，再由解释器执行或 者进行JIT翻译；即使静态编译的语言如C++，也存在先翻译成中间语言，再翻译成最终机器码的过程。中间表示也不一定非得是一种bytecode，我们 在语法分析阶段生成的抽象语法树（AST）就是一种很常用的中间表示。.NET 3.5引入的Expression Tree正是采用AST作为中间表示的动态语言运行库。那为什么这种做法非常流行呢？因为翻译中中间语言有如下好处：

1. 使用中间语言可以良好地将编译器的前端和后端拆分开，使得两部分可以相对独立地进行。 

2. 同一种中间语言可以由多种不同的源语言编译而来，而又可以针对多种不同的目标机器生成代码。CLR的CIL就是这一特点的典型代表。 

3. 有许多优化可以直接针对中间语言进行，这样优化的结果就可以应用到不同的目标平台。

7. 参考

自己动手开发编译器（九）CPS风格的解析器组合子 - 装配脑袋 - 博客园.htm

自己动手开发编译器（十一）语义分析 - 装配脑袋 - 博客园.htm

Atitit. 解释器模式框架选型 and应用场景attilax总结 oao - attilax的专栏 - 博客频道 - CSDN.NET.htm

Atitit.注解and属性解析(2)---------语法分析 生成AST attilax总结 java .net - attilax的专栏 - 博客频道 - CSDN.NET.htm

Atitit. 构造ast 语法树的总结attilax oao - attilax的专栏 - 博客频道 - CSDN.NET.htm

atitit.自己动手开发编译器and解释器(2) ------语法分析，语义分析，代码生成--attilax总结