编译原理之语法分析

解析变量声明语句

语法分析的结果是生成 AST。算法分为自顶向下和自底向上算法，其中，递归下降算法是一种常见的自顶向下算法。

“int age = 45”这个语句，语法分析算法的示意图：

终结符都是词法分析中产生的 Token。而那些非叶子节点，就是非终结符。

• 首先把变量声明语句的规则，用形式化的方法表达一下。它的左边是一个非终结符（Non-terminal）。右边是它的产生式（Production Rule）。在语法解析的过程中，左边会被右边替代。如果替代之后还有非终结符，那么继续这个替代过程，直到最后全部都是终结符（Terminal），也就是 Token。只有终结符才可以成为 AST 的叶子节点。这个过程，也叫做推导（Derivation）过程。

intDeclaration : Int Identifier (’=’ additiveExpression)?;

• 上面的文法翻译成程序语句，代码如下

SimpleASTNode node = null;
Token token = tokens.peek();    // 预读
if (token != null && token.getType() == TokenType.Int) {   // 匹配 Int
    token = tokens.read();      // 消耗掉 int
    if (tokens.peek().getType() == TokenType.Identifier) { // 匹配标识符
        token = tokens.read();  // 消耗掉标识符
        // 创建当前节点，并把变量名记到 AST 节点的文本值中，
        // 这里新建一个变量子节点也是可以的
        node = new SimpleASTNode(ASTNodeType.IntDeclaration, token.getText());
        token = tokens.peek();  // 预读
        if (token != null && token.getType() == TokenType.Assignment) {
            tokens.read();      // 消耗掉等号
            SimpleASTNode child = additive(tokens);  // 匹配一个表达式
            if (child == null) {
                throw new Exception("invalide variable initialization, expecting an expression");
            }
            else{
                node.addChild(child);
            }
        }
    } else {
        throw new Exception("variable name expected");
    }
}

• 算法描述：解析变量声明语句时，我先看第一个 Token 是不是 int。如果是，那我创建一个 AST 节点，记下 int 后面的变量名称，然后再看后面是不是跟了初始化部分，也就是等号加一个表达式。我们检查一下有没有等号，有的话，接着再匹配一个表达式。

通常会对产生式的每个部分建立一个子节点，比如变量声明语句会建立四个子节点，分别是 int 关键字、标识符、等号和表达式。

语法规则

additiveExpression
    :   multiplicativeExpression
    |   multiplicativeExpression Plus additiveExpression
    ;

上面的表达式是语法规则，是用BNF表达的。以addtive为例，它有两个产生式。
产生式1：一个乘法表达式
产生式2：一个加法表达式 + 乘法表达式。
通过上面两个产生式的组合，特别是产生式2的递归调用，就能推导出所有的加减乘数算术表达式。
比如，对于2*3这个表达式，运用的是产生式1。
对于2+3*5，运用的是产生式2。
我上面用的语法规则的写法，实际上是后面会用到的Antlr工具的写法。你也可以这样书写，就是一般教材上的写法：
A -> M | A + M
M -> int | M * int
我们每个非终结符只用了一个大写字母代表，比较简洁。
其中的竖线，是选择其一。你还可以拆成最简单的方式，形成4条规则：
A -> M
A -> A + M
M -> int
M -> M * int
上面这些不同的写法，都是等价的。

• 在二元表达式的语法规则中，如果产生式的第一个元素是它自身，那么程序就会无限地递归下去，这种情况就叫做左递归。
• 终结符都是词法分析中产生的 Token。而那些非叶子节点，就是非终结符。文法的推导过程，就是把非终结符不断替换的过程，让最后的结果没有非终结符，只有终结符。