简单的一遍编译器

###1、概述###

程序设计语言可以通过以下两个方面来定义：第一方面是程序模式，即语言的语法；第二方面是程序含义，即语言的语义。

为了说明语言的语法，我们介绍一种广为使用的表示法：上下文无关文法或者BNF（Backus-Naur范式）。使用现有的表示语法描述语言的语义要比描述语言的语法难得多。因此，在定义语言的语义时，我们将使用非形式化方法和启发性实例。

上下文无关文法除了可以用于定义语言的语法之外，还可用于指导源程序的翻译，面向语法的编译技术，如语法制导翻译技术，对于组织编译器的前端十分有用。

在我们的编译器中，词法分析器首先把输入字符流转换成记号流。然后记号流作为下一个阶段的输入，产生源程序的中间表示。

###2、语法定义###
语句具有如下形式：

if(表达式) 语句 else 语句

如果用expr来标识表达式，使用stmt来标识一条语句，则if-else语句的构造规则可以表达为

stmt -> if(expr) stmt else stmt

箭头可以读作“可以具有形式”。这样的规则称为“产生式（Production）”。在一个产生式中，，像关键字if和括号这样的词法元素称为记号（token），像stmt和expr这样的变量标一个记号序列，并称之为非终结符（nonterminal）。

上下文无关文法包含如下四个部分：

1、一个记号集合。

2、一个非终结符集合

3、一个产生式集合。每个产生式都具有一个左部和一个右部，左部和右部由箭头连接，左部是一个非终结符。。右部是记号和非终结符序列。

4、一个开始符号。开始符号是一个指定的非终结符。

如果一个非终结符出现在一个产生式的左部，该产生式称为该非终结符的产生式。记号串是零个或者多个记号序列。一个包含零个记号的记号串称为空串，记为ε。

从开始符号出发，反复替代产生式中的非终结符（用该非终结符的产生式的右部），一个文法可以产生一个串。由一个文法的开始符号产生的记号串形成了该文法定义的语言。

####分析树####

分析树描绘了如何从文法的开始符号开始推导它的语言中的一个语句。

如果非终结符具有一个产生式A->XYZ，则A的一棵分析树如右图所示，内节点标记为A，A的三个子节点从左到右分别标记为X、Y和Z。

形式地说，给定一个上下文无关法，分析树是具有如下特性的树：

1、树根标记为开始符号。

2、每个叶节点由记号或空标记。

3、每个内节点由一个非终结符标记。

4、如果A是某个内节点的非终结符标记，X、Y、Z是该节点从左到右排列的子节点标记，则A->XYZ是一个产生式。这里的X、Y、Z是一个终结符或非终结符。对于A->空，分析树中标记A的节点只有一个标记为空的子节点。

一棵分析树从左到右地叶节点是这个分析树生成的结果。分析树生成的结果是由根节点的非终结符生成或导出的串。

使用分析树的概念，我们可以定义：一个文法生成的语言是它的某个分析树生成的串的集合。为给定的记号串找到一个分析树的过程称为这个串的语法分析（parsing）。

####二义性####