前言
学习了词法分析(Lexical Analysis)，并且“装模作样”的实现了大概的词法分析工程，仅仅为了学习而已，接下来接下来就是语法分析(Syntactic Analysis, or Parsing)了。
开始
语法分析是在词法分析的基础上识别出程序的语法结构。这个结构是一个树状结构，是计算机容易理解和执行的.
以自然语言为例。自然语言有定义良好的语法结构，比如，“我喜欢又聪明又勇敢的你”这个句子包含了“主、谓、宾”三个部分。主语是“我”，谓语是“喜欢”，宾语部分是“又聪明又勇敢的你”。其中宾语部分又可以拆成两部分，“又聪明又勇敢”是定语部分，用来修饰“你”。定语部分又可以分成“聪明”和“勇敢”两个最小的单位.
这样拆下来，会构造一棵树，里面的每个子树都有一定的结构，而这个结构要符合语法。比如，汉语是用“主谓宾”的结构，日语是用“主宾谓”的结构。这时，我们说汉语和日语的语法规则是不同的。
程序也有定义良好的语法结构，它的语法分析过程，就是构造这么一棵树。一个程序就是一棵树，这棵树叫做抽象语法树（Abstract Syntax Tree，AST）。树的每个节点（子树）是一个语法单元，这个单元的构成规则就叫“语法”。每个节点还可以有下级节点。
所以，语法分析的结果就是生成AST。
生成ATS
如果我们要语法分析
- int age = 45
那么这个过程可以简单这样来概括：
解析变量声明语句时，我先看第一个 Token 是不是 int。如果是，那我创建一个 AST 节点，记下 int 后面的变量名称，然后再看后面是不是跟了初始化部分，也就是等号加一个表达式。我们检查一下有没有等号，有的话，接着再匹配一个表达式。
通常会对产生式的每个部分建立一个子节点，比如变量声明语句会建立四个子节点，分别是 int 关键字、标识符、等号和表达式。
我们把解析变量声明语句和表达式的算法分别写成函数。在语法分析的时候，调用这些函数跟后面的 Token 串做模式匹配。匹配上了，就返回一个 AST 节点，否则就返回 null。如果中间发现跟语法规则不符，就报编译错误。
在这个过程中，上级文法嵌套下级文法，上级的算法调用下级的算法。表现在生成 AST 中，上级算法生成上级节点，下级算法生成下级节点。
生成的ATS大概是这样：
1 | Programm Calculator |
当然这些都还在正则表达式的文法规则之内，没有超出词法分析时使用的文法。
我们解析算术表达式的时候，会遇到更复杂的情况，这时，正则文法不够用，我们必须用上下文无关文法来表达。
算术表达式要包含加法和乘法两种运算（简单起见，我们把减法与加法等同看待，把除法也跟乘法等同看待），加法和乘法运算有不同的优先级。我们的规则要能匹配各种可能的算术表达式：
2+3*5
2*3+5
2*3
….
思考一番之后，我们可以把规则分成两级：第一级是加法规则，第二级是乘法规则。把乘法规则作为加法规则的子规则，这样在解析形成 AST 时，乘法节点就一定是加法节点的子节点，从而被优先计算。
这种文法已经没有办法改写成正则文法了，它比正则文法的表达能力更强，叫做“上下文无关文法”。正则文法是上下文无关文法的一个子集。它们的区别呢，就是上下文无关文法允许递归调用，而正则文法不允许。
那有没有上下文相关的情况需要处理呢？也是有的，但那不是语法分析阶段负责的，而是放在语义分析阶段来处理的。
实现表达式求值
其实，要实现一个表达式计算，需要基于 AST 做求值运算，也就是对这棵树做深度优先的遍历。
深度优先的遍历也是一个递归算法。以“2 + 3 * 5”的 AST 为例看一下：
对表达式的求值，等价于对 AST 根节点求值
首先求左边子节点，算出是 2。
接着对右边子节点求值，这时候需要递归计算下一层。计算完了以后，返回是 15（3*5）。
把左右节点相加，计算出根节点的值 17。
总结
虽然我的目标是能通过这些学习写一个简单能用的解释器，起码可以看作一个玩具，但是，说实话，我有些地方，还不是很理解，只能说大概了解这个过程，所以要是写的话，也只能写个连玩具都算不上的东西，这很无聊，也不是我的本意，所以，还是先囫囵吞枣的学习一遍吧QAQ
为自己的菜而感到惭愧！