CMM语法分析器

最新版代码可见Gitee。

文法

经过分析，定义了一个如下文所示的文法，我们要做的就是自己手写递归下降分析实现这个文法。

grammar Cmm;
import CmmLex;

program: stmt+;

stmt    : declStmt
        | ifStmt
        | whileStmt
        |(assignStmt SEMI)
        | writeStmt
        | stmtBlock
        | forStmt
        ;

declStmt: type deAs(COMMA deAs)* SEMI | type L_BRACKET INT R_BRACKET ID SEMI;

deAs: ID | ID ASSIGN MINUS? expr;

ifStmt: IF L_PAREN compare R_PAREN stmtBlock ( ELSE_IF L_PAREN compare R_PAREN stmtBlock)* (ELSE stmtBlock)*;

whileStmt: WHILE L_PAREN compare R_PAREN stmtBlock;

assignStmt: variable ASSIGN MINUS? expr;

writeStmt: WRITE L_PAREN expr R_PAREN SEMI;

stmtBlock: L_BRACE stmt* R_BRACE;

forStmt : FOR L_PAREN((assignStmt SEMI)|declStmt) compare SEMI assignStmt R_PAREN stmtBlock;

type: T_INT | T_DOUBLE;

variable: ID | ID L_BRACKET (expr) R_BRACKET ;

constant: INT| DOUBLE ;

compare :  UN_EQUAL compare | expr RELATION expr | L_PAREN compare R_PAREN ;

RELATION : BIGGER_THAN|LESS_THAN|NO_LESS|NO_MORE|EQUAL|UN_EQUAL;

expr    : expr1 expr2;
expr1   : expr4 expr3;
expr2   : (Plus|Minus) expr1 expr2
        |
        ;
expr3   : (Mul|Div|Mod) expr4 expr3
        |
        ;
expr4   : variable
        | constant
        | L_PAREN expr R_PAREN
        ;

关键

获取Token流

本次作业效仿了之前使用antlr处理全部文法的代码结构，使用Antlr进行词法分析后，得到词法分析器lexer，而后使用getAllTokens()方法获得一个Token List, 将其导入自己手写的Parser类中进行处理，并使用visit方法访问生成的AST并将其打印出来。

public class   Main {

    public static void main(String[] args) throws IOException{
    // write your code here
        InputStream is = args.length > 0 ? new FileInputStream(args[0]) : System.in;

        ANTLRInputStream input = new ANTLRInputStream(is);
        CmmLex lexer = new CmmLex(input);
        Parser parser = new Parser(lexer.getAllTokens());
        parser.prog();
        parser.visit();

    }
}

生成AST

其实语法分析递归下降调用子函数的过程本身就可以看做是对一个隐含的树的前序遍历，因此，我们只要在每次递归下降调用函数的时候都生成对应的节点和边即可。基于这个思路，主要写了三个类，一下分别介绍。

Node类

enum NodeType{ terminal, prog, stmt, declStmt, deAs, ifStmt, whileStmt, assignStmt ,
    writeStmt, stmtBlock, forStmt, type, constant, compare, variable, relation, expr, expr1, expr2, expr3, expr4}

enum visitFlag{ visited, unvisited, finished}

public class Node {
    public NodeType type;
    public Node parent;
    public LinkedList<Node> child = new LinkedList<Node>();
    public int tokenType;
    public int level;
    public String text;
    public visitFlag flag;
}

枚举类型NodeType说明了节点是中间节点还是叶子节点，terminal说明是末端节点，即终止符，其他类型为非终结符。而枚举类型visitFlag记录的是节点的访问状况，用于后面遍历AST时进行标记。同时用链表记录了子节点，level则记录了节点的深度，根节点的level为0，tokenType利用了自动生成的CmmLex类中的Int，便于判断节点中的类型，终结符节点的tokenType非0，中间节点的tokenType为0.

Parser类

Parser类中主要有如下几个变量，迭代器用于对token流组成的List进行遍历，同时维护一个栈，curerent发挥了指针的作用，始终指向栈顶以指向当前节点，便于回溯和链接新生成的节点。全局变量level用于记录节点的层级。

• protected List<CommonToken> tokens;
• protected static Iterator<CommonToken> iter;

• protected static CommonToken token;
• public AST ast;
• protected Stack<Node> S;
• protected Node current;
• public int level = 0;

newNode 函数在Node函数的基础上进一步封装，在生成新节点的基础上，将父子节点关联起来，并且压入栈中，每次递归下降进入子函数时，都会被调用。

public Node newNode(NodeType t,  Node p, Node c, int to, int l){
        Node x = new Node(t, p, c, to, l);
        p.child.add(x);
        if(c!=null){
            c.parent=x;
        }
        S.push(x);
        return x;
    }

rollBack() 函数在每个分析函数的末尾被调用，用于恢复level的层级，同时出栈，更新当前节点。

    public void rollBack(){
        --level;
        S.pop();
        current = S.peek();
    }

以whileStmt函数为例，这个函数处理的是while语句。根据语法

whileStmt: WHILE L_PAREN compare R_PAREN stmtBlock;

我们在进入函数时调用newNode()函数，生成当前节点，然后依次匹配字符‘while’，‘（’，‘）’等终结符，并且在其中调用compare*()和stmtBlock()函数进行递归下降分析，在函数返回时调用rollBack()恢复。

protected void whileStmt(){
        current = newNode(NodeType.whileStmt, current, null, 0,++level);
        match(WHILE);
        match(L_PAREN);
        compare();
        match(R_PAREN);
        stmtBlock();
        rollBack();
}

访问并打印AST

AST类

Parser类还有一个AST类型，即语法分析树，递归下降分析完成后，这棵树也就生成了。类AST中的方法主要是对AST进行深度优先搜索，并将内容打印出来，终结符节点，即树中的叶子节点被访问一次，而中间节点，即非终结符节点都被访问了两次，第一次visitFlag状态变为visited, 第二次说明访问完毕，处于被回溯的状态，被标记为finished。

public void gotoHLVFL(){
        Node x;
        ListIterator<Node> it;
        x=S.peek();
        while(x.type!=NodeType.terminal) {
            visit(x);
            it = x.child.listIterator();
            while (it.hasNext()) it.next();
            while (it.hasPrevious()) {
                S.push(it.previous());
            }
            x=S.peek();
        }
    }

    public void travPost(Node x){
        if(x!=null) S.push(x);
        while (!S.isEmpty()){
            if(!S.peek().equals(x.parent)) gotoHLVFL();
            x = S.pop();
            visit(x);
        }

同时还维护了一个数组，当节点被访问时，对应数组中值也会根据情况进行修改，用于打印时做标记。每访问一个节点，打印一行，当树被遍历完毕后，AST也就被打印出来了。

结果

对词法分析时助教提供的9个Test Cases, 都能成功输出（删除了Read语句）,可直接运行脚本，第8个Case输出的结果如下

outcome