Bison语法分析器是如何匹配输入的？

语法是基于一系列规则的组成，语法分析器就是基于这些规则来匹配语法的输入，例如下面的这样一条规则

statement: NAME '=' expression
expression: NUMBER '+' NUMBER
                  | NUMBER '?' NUMBER

冒号左边的我们称之为规则的左部（left-hand side），通常简写为LHS，而右边的称为规则的右部（right-hand side），通常简写为RHS，几条规则可能会有同样的左边，通常用"|"来连接右部的几条规则，表示或的关系。在输入中出现并且被词法分析器返回的符号是终结符或者token，规则的左边语法符号是非终结符，token不能出现在规则的左边，我们通常用语法分析树来表示一个表达式，例如fred = 12 + 13,语法分析书如下图所示：

语法分析树
在上面的例子里 12 + 13 是一个expression， 而fred = expression 是一个statement，每个语法规则中都包含起始符号（上例中statement是起始符号），它作为语法分析树的根出现。每个规则可以直接或者间接的指向它们自身（递归规则），例如上面的例子可以改写为：

expression:NUMBER
                  | expression + NUMBER
                  | expression ? NUMBER

改写完之后就可以处理fred = 12 + 13 + 15 +16等这样的长式子了，在实际编写案例中基本上都会用到递归规则。