(基于Java)编写编译器和解释器-第7章：解析(Parsing)控制语句-第二部分(连载)

博客园 - Bang

Bang · 2012-07-28 · via 博客园 - Bang

续第一部分

解析FOR语句

Pascal FOR语句稍微有些麻烦。语句解析器子类ForStatementParser的parse()方法解析如下语句：

FOR k := j TO 5 DO n := k

会产生如图7-5展示的分析树。

这个分析树的根是一个COMPOUND节点。此COMPOUND节点的第一个孩子是嵌套的赋值语句子树，用来初始化控制变量；第二个孩子是一个LOOP节点。

LOOP节点的第一个孩子是一个TEST节点。TEST节点的孩子视FOR语句是TO或DOWNTO类型分别对应GT或LT关系表达式子树，这个子树对照限值(这里是5）测试控制变量的值。LOOP节点的第二个孩子是嵌套的语句子树。如果是TO，控制变量按单位1递增，第三个孩子将是一个ADD算术表达式节点；否则控制变量递减，第三个孩子是一个SUBSTRACT(减)节点。

清单7-11 展示了ForStatementParser中的parse()方法（这个代码多了起来)。

   1: // TO和DOWNTO同步集合 for expr ->to|downto CONST do stmt

   2:   private static final EnumSet<PascalTokenType> TO_DOWNTO_SET =

   3:       ExpressionParser.EXPR_START_SET.clone();

   4:   static {

   5:       TO_DOWNTO_SET.add(TO);

   6:       TO_DOWNTO_SET.add(DOWNTO);

   7:       TO_DOWNTO_SET.addAll(StatementParser.STMT_FOLLOW_SET);

   8:   }

   9:   // DO同步集合for expr to|downto CONST ->do stmt

  10:   private static final EnumSet<PascalTokenType> DO_SET =

  11:       StatementParser.STMT_START_SET.clone();

  12:   static {

  13:       DO_SET.add(DO);

  14:       DO_SET.addAll(StatementParser.STMT_FOLLOW_SET);

  15:   }

  16:   //发生的变量节点拷贝可以认为是源节点和拷贝节点树中关系不一样，但是一些属性

  17:   //比如对应的符号表项还是一样的引用。

  18:   public ICodeNode parse(Token token)

  19:       throws Exception

  20:   {

  21:       token = nextToken();

  22:       Token targetToken = token;

  23:       //参见图7-11

  24:       ICodeNode compoundNode = ICodeFactory.createICodeNode(COMPOUND);

  25:       ICodeNode loopNode = ICodeFactory.createICodeNode(LOOP);

  26:       ICodeNode testNode = ICodeFactory.createICodeNode(TEST);

  27:       // 初始赋值语句，调用一次

  28:       AssignmentStatementParser assignmentParser =

  29:           new AssignmentStatementParser(this);

  30:       ICodeNode initAssignNode = assignmentParser.parse(token);

  31:       setLineNumber(initAssignNode, targetToken);

  32:       compoundNode.addChild(initAssignNode);

  33:       //循环主体的复合节点

  34:       compoundNode.addChild(loopNode);

  35:       //同步在TO/DOWNTO处

  36:       token = synchronize(TO_DOWNTO_SET);

  37:       TokenType direction = token.getType();

  38:       if ((direction == TO) || (direction == DOWNTO)) {

  39:           token = nextToken();

  40:       }

  41:       else {

  42:           direction = TO;

  43:           errorHandler.flag(token, MISSING_TO_DOWNTO, this);

  44:       }

  45:       //根据TO/DOWNTO创建判断表达式GT或LT

  46:       ICodeNode relOpNode = ICodeFactory.createICodeNode(direction == TO

  47:                                                          ? GT : LT);

  48:       //拷贝初始变量语句中的左边变量成为关系表达式的左边

  49:       ICodeNode controlVarNode = initAssignNode.getChildren().get(0);

  50:       relOpNode.addChild(controlVarNode.copy());

  51:       //TO或DOWNTO的限值表达式，成为关系表达式的右边

  52:       ExpressionParser expressionParser = new ExpressionParser(this);

  53:       relOpNode.addChild(expressionParser.parse(token));

  54:       //loop-->test-->relop三层

  55:       testNode.addChild(relOpNode);

  56:       loopNode.addChild(testNode);

  57:       // 在DO处同步

  58:       token = synchronize(DO_SET);

  59:       if (token.getType() == DO) {

  60:           token = nextToken();

  61:       }

  62:       else {

  63:           errorHandler.flag(token, MISSING_DO, this);

  64:       }

  65:       //循环的主体语句

  66:       StatementParser statementParser = new StatementParser(this);

  67:       loopNode.addChild(statementParser.parse(token));

  68:       //创建一个根据TO|DOWNTO来递增或递减控制变量的表达式。控制变量:=控制变量+/- 1;

  69:       ICodeNode nextAssignNode = ICodeFactory.createICodeNode(ASSIGN);

  70:       nextAssignNode.addChild(controlVarNode.copy());

  71:       ICodeNode arithOpNode = ICodeFactory.createICodeNode(direction == TO

  72:                                                            ? ADD : SUBTRACT);

  73:       //递减发生在控制变量上，要拷贝。

  74:       arithOpNode.addChild(controlVarNode.copy());

  75:       ICodeNode oneNode = ICodeFactory.createICodeNode(INTEGER_CONSTANT);

  76:       oneNode.setAttribute(VALUE, 1);

  77:       arithOpNode.addChild(oneNode);

  78:       //将递增/递减后的值付给控制变量

  79:       nextAssignNode.addChild(arithOpNode);

  80:       loopNode.addChild(nextAssignNode);

  81:       setLineNumber(nextAssignNode, targetToken);

  82:       return compoundNode;

  83:   }

parse()方法创建COMPOUND，LOOP和TEST节点并构建如图7-5所示的分析树。它使用同步集合TO_DOWNTO_SET在TO或DOWNTO token处同步自己，用同步集合DO_SET在DO处同步自己。此方法为"initial"和"next" ASSIGN节点都设置了源代码行位置信息。

这个方法记得TO或DOWNTO设置。如果是TO，它生成一个GT(大于)关系操作符节点和一个ADD算术符节点；否则生成相反的LT和SUBTRACT节点。

在Eclipse中运行Pascal，使用参数"compile -i for.txt"，查看正确的输出结果。使用参数"compile -i forerrors.txt"，查看带错误的输出结果。这里省略输出结果。

设计笔记

LOOP节点容许中间码以一种语言无关的方式匹配各种不同花样的循环结构(WHILE/DO WHILE/REPEAT/FOR)

解析IF语句

语句分析器子类IfStatementParser解析Pascal IF语句并生成它的分析树。比如语句：

IF (i = j) THEN 
    t := 200
ELSE 
    f := -200;

类的parse()方法将生成如图7-6所示的分析树

IF节点有两个或三个孩子节点。第一个是比较表达式子树，第二个是THEN后的嵌套语句子树。如果还有一个ELSE部分，第三个将会是ELSE嵌套语句的子树。

清单7-14展示了IfStatementParser的parse()方法

   1: // THEN的同步集合

   2:    private static final EnumSet<PascalTokenType> THEN_SET =

   3:        StatementParser.STMT_START_SET.clone();

   4:    static {

   5:        THEN_SET.add(THEN);

   6:        THEN_SET.addAll(StatementParser.STMT_FOLLOW_SET);

   7:    }

8:

   9:    public ICodeNode parse(Token token)

  10:        throws Exception

  11:    {

  12:        token = nextToken();

  13:        ICodeNode ifNode = ICodeFactory.createICodeNode(ICodeNodeTypeImpl.IF);

  14:        //IF语句的条件表达式

  15:        ExpressionParser expressionParser = new ExpressionParser(this);

  16:        ifNode.addChild(expressionParser.parse(token));

  17:        // THEN处同步一下

  18:        token = synchronize(THEN_SET);

  19:        if (token.getType() == THEN) {

  20:            token = nextToken();

  21:        }

  22:        else {

  23:            errorHandler.flag(token, MISSING_THEN, this);

  24:        }

  25:        //THEN后的语句

  26:        StatementParser statementParser = new StatementParser(this);

  27:        ifNode.addChild(statementParser.parse(token));

  28:        token = currentToken();

  29:        //试探后没有ELSE语句

  30:        if (token.getType() == ELSE) {

  31:            token = nextToken();

  32:            ifNode.addChild(statementParser.parse(token));

  33:        }

  34:        return ifNode;

  35:    }

在Eclipse中运行Pascal，使用参数"compile -i if.txt"，查看正确的输出结果。使用参数"compile -i iferrors.txt"，查看带错误的输出结果。这里省略输出结果。做个补充演示：

按照左边图设置之后看运行输出，留意级联的IF THEN ELSE语句。在每个ELSE IF 分支处，嵌套的IF语句被当做另一个语句。(这个特性跟Java的一样)。

著名的"dangling ELSE"很容易出问题(dangling else意思说如果if xxx then yyy if mmm then nnn else kkk，这儿出现了else到底是被解释成第一个if语句的一部分还是第二个if语句的一部分？摇摆不定啊，通用的做法是紧贴近最里层的if，即第二个if）。在源文件(if.txt)第17行处，ELSE可以跟第一个和第二个THEN配对。遵照语法图7-1，IF语句

IF (j = 2) THEN t := 500 ELSE f := -500

是THEN语句的嵌套子句，即 IF (i = 1) THEN 嵌套子句。因此，ELSE与第二个THEN配对。

解析CASE语句

CASE语句是Pascal控制语句解析中最有挑战的一个。语句解析器子类CaseStatementParser解析CASE语句并生成它的分析树，比如语句：

CASE i+1 OF
    1:       j := i;
    4:       j := 4*i;
    5, 2, 3: j := 523*i;
END

类的parse()方法生成如图7-7所示的分析树。

我们看看类的parse()方法

   1: //一个CASE条件分支的起始同步集合

   2:    private static final EnumSet<PascalTokenType> CONSTANT_START_SET =

   3:        EnumSet.of(IDENTIFIER, INTEGER, PLUS, MINUS, STRING);

4:

   5:    // OF同步集合

   6:    private static final EnumSet<PascalTokenType> OF_SET =

   7:        CONSTANT_START_SET.clone();

   8:    static {

   9:        OF_SET.add(OF);

  10:        OF_SET.addAll(StatementParser.STMT_FOLLOW_SET);

  11:    }

  12:    public ICodeNode parse(Token token)

  13:        throws Exception

  14:    {

  15:        //干掉开头的CASE

  16:        token = nextToken();

  17:        ICodeNode selectNode = ICodeFactory.createICodeNode(SELECT);

  18:        //CASE表达式

  19:        ExpressionParser expressionParser = new ExpressionParser(this);

  20:        selectNode.addChild(expressionParser.parse(token));

  21:        //同步OF

  22:        token = synchronize(OF_SET);

  23:        if (token.getType() == OF) {

  24:            token = nextToken();  // consume the OF

  25:        }

  26:        else {

  27:            errorHandler.flag(token, MISSING_OF, this);

  28:        }

  29:        //分支选项集合

  30:        HashSet<Object> constantSet = new HashSet<Object>();

  31:        while (!(token instanceof EofToken) && (token.getType() != END)) {

  32:            selectNode.addChild(parseBranch(token, constantSet));

  33:            token = currentToken();

  34:            TokenType tokenType = token.getType();

  35:            // 一个分支以分号';'结束

  36:            if (tokenType == SEMICOLON) {

  37:                token = nextToken();

  38:            }

  39:            else if (CONSTANT_START_SET.contains(tokenType)) {

  40:                errorHandler.flag(token, MISSING_SEMICOLON, this);

  41:            }

  42:        }

  43:        //CASE expr OF branches END

  44:        if (token.getType() == END) {

  45:            token = nextToken();

  46:        }

  47:        else {

  48:            errorHandler.flag(token, MISSING_END, this);

  49:        }

50:

  51:        return selectNode;

  52:    }

同步集合CONSTANT_START_SET包含所有能开始一个CASE常量的token类型(比如CASE xxx OF 1: dosomething; 2: doanything; end中的1，2处的同步检测)。parse()方法创建一个SELECT节点，在解析过CASE的表达式后，它用同步集合OF_SET将自己同步在OF token处。while循环调用parseBranch解析每一个CASE分支，接着寻找分号(结束一个分支)。循环在遇到END token退出。此方法返回这个SELECT节点。

清单7-18 展示了CaseStatementParser中的parseBranch()方法

   1: private ICodeNode parseBranch(Token token, HashSet<Object> constantSet)

   2:     throws Exception

   3: {

   4:     //每个分支都有一个SELECT_BRANCH节点，constantsNode是第一个孩子

   5:     ICodeNode branchNode = ICodeFactory.createICodeNode(SELECT_BRANCH);

   6:     ICodeNode constantsNode =ICodeFactory.createICodeNode(SELECT_CONSTANTS);

   7:     branchNode.addChild(constantsNode);

   8:     //解析常量列表，每个常量节点是是constantNode的子节点)

   9:     parseConstantList(token, constantsNode, constantSet);

  10:     //查找分支冒号

  11:     token = currentToken();

  12:     if (token.getType() == COLON) {

  13:         token = nextToken();

  14:     }

  15:     else {

  16:         errorHandler.flag(token, MISSING_COLON, this);

  17:     }

  18:     //冒号:后面的语句

  19:     StatementParser statementParser = new StatementParser(this);

  20:     branchNode.addChild(statementParser.parse(token));

  21:     return branchNode;

  22: }

parseBranch()方法在调用parseConstantList()方法之前，创建一个SELECT_BRANCH和一个SELECT_CONSTANTS节点。解析完常量列表后，查找后面的冒号。SELECT_CONSTANTS节点收纳这些常量节点，它本身变成SELECT_BRANCH节点的第一个孩子。接着调用一次statementParser().parse()解析分支语句，这个分支语句的子树根节点成为SELECT_BRANCH节点的第二个子节点。

清单7-19 展示了parseConstantList()方法

   1: private void parseConstantList(Token token, ICodeNode constantsNode,

   2:                                   HashSet<Object> constantSet)

   3:        throws Exception

   4:    {

   5:        // 遍历每一个常量

   6:        while (CONSTANT_START_SET.contains(token.getType())) {

   7:            constantsNode.addChild(parseConstant(token, constantSet));

   8:            token = synchronize(COMMA_SET);

   9:            // 常量以','隔开

  10:            if (token.getType() == COMMA) {

  11:                token = nextToken();

  12:            }

  13:            else if (CONSTANT_START_SET.contains(token.getType())) {

  14:                errorHandler.flag(token, MISSING_COMMA, this);

  15:            }

  16:        }

  17:    }

parseConstantList()方法解析被逗号分隔的常量列表(1,2,3,4等)，它调用parseConstant()解析每一个常量。在本章中，parseConstant()能通过调用parseIntegerConstant()解析整数常量（常量前可能有+或-的符号位)，还有通过调用parseCharacterConstant()解析字符常量。因为你还是没有解析常量声明，名称常量(标识符token)是不被允许的，后面会解决（引入常量声明之后，比如const a :=1，可以在第9章之后)。
解析常量的代码过于简单，跟解析常量token类似，这里不演示了，有兴趣可以看源代码的第153到268行

这里对CASE分支常量要强调的2点是：

一个分支常量可以是一个整数或者单个的字符，比如1,2,3: 或 'a','b','c:
CASE语句中的分支常量不能被使用多次，只能使用一次。

在Eclipse中运行Pascal，使用参数"compile -i case.txt"，查看正确的输出结果。使用参数"compile -i caseerrors.txt"，查看带错误的输出结果。这里省略输出结果。

本章完.

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - Bang

解析FOR语句

解析IF语句

解析CASE语句