(基于Java)编写编译器和解释器-第11章:解析程序、过程和函数-第二部分

时间:2022-12-25 17:07:46

第一部分

(因为BlockParser的parse()方法里面只改了一行,即在第41行增加了一个routineId参数,所以代码我就不贴了,自己看吧

新版本的parse方法多传了一个参数,即父程式名字对应的符号比表项,此参数接着被传给了declarationsParser.parse()。

解析过程和函数调用

图11-6 展示了作为语句的过程调用以及作为因子的函数调用对应的语法图,这些图扩展了图5-2 中关于因子的部分,以及图7-1中语句的部分。

(基于Java)编写编译器和解释器-第11章:解析程序、过程和函数-第二部分

可以看到,多了一个procedure call语句,在右边的factor(因子)部分,多了一个function all


 

(基于Java)编写编译器和解释器-第11章:解析程序、过程和函数-第二部分

左边的图11-7展示了语句解析子类的UML类图,它们被用来解析针申明或标准(内置)过程和函数的调用。

语句解析子类CallParser有两个子类, CallDeclaredParser 和 CallStandardParser。两个都用到了parseActualParameters()方法。

针对申明过的程式调用和Pascal标准程式的调用,你需要不同的类处理。标准程式某些情况下意味着调用不标准(因为标准是约定的,而申明是解析的,解析的你很定知道程式的每一个细节,而约定的不是,规定了什么就什么,这个规定就是不标准)。比如,过程read有一个可变实参表(是否想起了C的 ... ?)。过程writer和writeln的每个参数后面可以有一个可选并用冒号隔开的域宽数和精度值。函数诸如abs的参数可为整数或实数,其返回值与参数类型一致。基于这些原因,类CallStandardParser针对这些调用有特别的方法来处理。


清单11-10 展示了包intermediate.symtabimpl中的类Predefined附加的东西,即把Pascal标准过程和函数的名称放入全局符号表中。

   1: //预定义过程和函数
   2:    public static SymTabEntry readId;
   3:    public static SymTabEntry readlnId;
   4:    public static SymTabEntry writeId;
   5:    public static SymTabEntry writelnId;
   6:    public static SymTabEntry absId;
   7:    public static SymTabEntry arctanId;
   8:    public static SymTabEntry chrId;
   9:    public static SymTabEntry cosId;
  10:    public static SymTabEntry eofId;
  11:    public static SymTabEntry eolnId;
  12:    public static SymTabEntry expId;
  13:    public static SymTabEntry lnId;
  14:    public static SymTabEntry oddId;
  15:    public static SymTabEntry ordId;
  16:    public static SymTabEntry predId;
  17:    public static SymTabEntry roundId;
  18:    public static SymTabEntry sinId;
  19:    public static SymTabEntry sqrId;
  20:    public static SymTabEntry sqrtId;
  21:    public static SymTabEntry succId;
  22:    public static SymTabEntry truncId;
  23:  
  24:    /**
  25:     * 初始化预定义到符号表堆栈
  26:     * @param symTab 堆栈
  27:     */
  28:    public static void initialize(SymTabStack symTabStack)
  29:    {
  30:        initializeTypes(symTabStack);
  31:        initializeConstants(symTabStack);
  32:        initializeStandardRoutines(symTabStack);
  33:    }
  34:    //初始化标准程式到全局符号表中
  35:    private static void initializeStandardRoutines(SymTabStack symTabStack) {
  36:         readId    = enterStandard(symTabStack, PROCEDURE, "read",    READ);
  37:         readlnId  = enterStandard(symTabStack, PROCEDURE, "readln",  READLN);
  38:         writeId   = enterStandard(symTabStack, PROCEDURE, "write",   WRITE);
  39:         writelnId = enterStandard(symTabStack, PROCEDURE, "writeln", WRITELN);
  40:  
  41:         absId    = enterStandard(symTabStack, FUNCTION, "abs",    ABS);
  42:         arctanId = enterStandard(symTabStack, FUNCTION, "arctan", ARCTAN);
  43:         chrId    = enterStandard(symTabStack, FUNCTION, "chr",    CHR);
  44:         cosId    = enterStandard(symTabStack, FUNCTION, "cos",    COS);
  45:         eofId    = enterStandard(symTabStack, FUNCTION, "eof",    EOF);
  46:         eolnId   = enterStandard(symTabStack, FUNCTION, "eoln",   EOLN);
  47:         expId    = enterStandard(symTabStack, FUNCTION, "exp",    EXP);
  48:         lnId     = enterStandard(symTabStack, FUNCTION, "ln",     LN);
  49:         oddId    = enterStandard(symTabStack, FUNCTION, "odd",    ODD);
  50:         ordId    = enterStandard(symTabStack, FUNCTION, "ord",    ORD);
  51:         predId   = enterStandard(symTabStack, FUNCTION, "pred",   PRED);
  52:         roundId  = enterStandard(symTabStack, FUNCTION, "round",  ROUND);
  53:         sinId    = enterStandard(symTabStack, FUNCTION, "sin",    SIN);
  54:         sqrId    = enterStandard(symTabStack, FUNCTION, "sqr",    SQR);
  55:         sqrtId   = enterStandard(symTabStack, FUNCTION, "sqrt",   SQRT);
  56:         succId   = enterStandard(symTabStack, FUNCTION, "succ",   SUCC);
  57:         truncId  = enterStandard(symTabStack, FUNCTION, "trunc",  TRUNC);
  58:    }
  59:    //录入标准程式
  60:    private static SymTabEntry enterStandard(SymTabStack symTabStack,
  61:                                             Definition defn, String name,
  62:                                             RoutineCode routineCode)
  63:    {
  64:        SymTabEntry procId = symTabStack.enterLocal(name);
  65:        procId.setDefinition(defn);
  66:        procId.setAttribute(SymTabKeyImpl.ROUTINE_CODE, routineCode);
  67:        return procId;
  68:    }

清单11-11 展示了语句解析子类CallParser的parse方法

   1: public ICodeNode parse(Token token)
   2:     throws Exception
   3: {
   4:     //视情况调用申明解析或标准解析
   5:     SymTabEntry pfId = symTabStack.lookup(token.getText().toLowerCase());
   6:     RoutineCode routineCode = (RoutineCode) pfId.getAttribute(ROUTINE_CODE);
   7:     StatementParser callParser = (routineCode == DECLARED) ||
   8:                                  (routineCode == FORWARD)
   9:                                      ? new CallDeclaredParser(this)
  10:                                      : new CallStandardParser(this);
  11:  
  12:     return callParser.parse(token);
  13: }

parse()方法在符号表中搜寻被调用的程式名称,看是否是申明的、前向的还是预定义的,对于申明与前向调用CallDeclaredParser解析;对于预定义的,调用CallStandardParser解析。

调用申明(过)过程和函数

清单11-12 展示了类CallDeclaredParser的parse方法

   1: public ICodeNode parse(Token token)
   2:     throws Exception
   3: {
   4:     // 创建CALL节点
   5:     ICodeNode callNode = ICodeFactory.createICodeNode(CALL);
   6:     SymTabEntry pfId = symTabStack.lookup(token.getText().toLowerCase());
   7:     callNode.setAttribute(ID, pfId);
   8:     callNode.setTypeSpec(pfId.getTypeSpec());
   9:  
  10:     token = nextToken();  //跳过程式名称
  11:  
  12:     //解析参数
  13:     ICodeNode parmsNode = parseActualParameters(token, pfId,
  14:                                                 true, false, false);
  15:     //参数作为子节点
  16:     callNode.addChild(parmsNode);
  17:     return callNode;
  18: }

parse()调用parseActualParameters()来解析实参并返回一个PARAMETERS节点,如果没有参数值为null。CALL节点收纳PARAMETERS为子节点。

举个例子,假设你有如下的Pascal申明

 

TYPE
    arr = ARRAY [1..5] OF real;
 
VAR
    i, m : integer;
    a : arr;
    v, y : real;
    t : boolean;
 
PROCEDURE proc(j, k : integer; VAR x, y, z : real; VAR v : arr;
               VAR p : boolean; ch : char);
    BEGIN
        ...
    END;
那么过程调用proc(i, -7 + m, a[m], v, y, a, t, 'r'); 将会生成如清单11-13所示的分析树
  
  
  
<CALL id="proc" level="1" line="81">
<PARAMETERS>
<VARIABLE id="i" level="1" type_id="integer" />
<ADD type_id="integer">
<NEGATE>
<INTEGER_CONSTANT value="7" type_id="integer" />
</NEGATE>
<VARIABLE id="m" level="1" type_id="integer" />
</ADD>
<VARIABLE id="a" level="1" type_id="real">
<SUBSCRIPTS type_id="real">
<VARIABLE id="m" level="1" type_id="integer" />
</SUBSCRIPTS>
</VARIABLE>
<VARIABLE id="v" level="1" type_id="real" />
<VARIABLE id="y" level="1" type_id="real" />
<VARIABLE id="a" level="1" type_id="arr" />
<VARIABLE id="t" level="1" type_id="boolean" />
<STRING_CONSTANT value="r" type_id="char" />
</PARAMETERS>
</CALL>

调用标准过程和函数

清单11-14 展示了类CallStandardParser的parse()方法。它调用适当的私有方法解析每一个标准过程或函数的调用。

   1: public ICodeNode parse(Token token)
   2:     throws Exception
   3: {
   4:     ICodeNode callNode = ICodeFactory.createICodeNode(CALL);
   5:     SymTabEntry pfId = symTabStack.lookup(token.getText().toLowerCase());
   6:     RoutineCode routineCode = (RoutineCode) pfId.getAttribute(ROUTINE_CODE);
   7:     callNode.setAttribute(ID, pfId);
   8:  
   9:     token = nextToken(); // 跳过程式名称
  10:     //不同的程式,不同的解析
  11:     switch ((RoutineCodeImpl) routineCode) {
  12:         case READ:
  13:         case READLN:  return parseReadReadln(token, callNode, pfId);
  14:  
  15:         case WRITE:
  16:         case WRITELN: return parseWriteWriteln(token, callNode, pfId);
  17:  
  18:         case EOF:
  19:         case EOLN:    return parseEofEoln(token, callNode, pfId);
  20:  
  21:         case ABS:
  22:         case SQR:     return parseAbsSqr(token, callNode, pfId);
  23:  
  24:         case ARCTAN:
  25:         case COS:
  26:         case EXP:
  27:         case LN:
  28:         case SIN:
  29:         case SQRT:    return parseArctanCosExpLnSinSqrt(token, callNode,
  30:                                                         pfId);
  31:  
  32:         case PRED:
  33:         case SUCC:    return parsePredSucc(token, callNode, pfId);
  34:  
  35:         case CHR:     return parseChr(token, callNode, pfId);
  36:         case ODD:     return parseOdd(token, callNode, pfId);
  37:         case ORD:     return parseOrd(token, callNode, pfId);
  38:  
  39:         case ROUND:
  40:         case TRUNC:   return parseRoundTrunc(token, callNode, pfId);
  41:  
  42:         default:      new UnsupportedOperationException("No such routine "+token.getText());
  43:     }
  44:     return null;
  45: }

清单11-15 展示了CallStandardParser的各种私有方法(细节请参看源代码,这里不贴了

调用标准过程如read、readln、write、writeln可有任意个实参;每个对read和write的调用必须至少有一个参数。标准函数eof和eoln调用没有实参,而调用其它标准函数必须有且仅有一个实参。

在每一个解析方法里(即parseXXX),都会调用parseActualParameters()解析实参并返回一个PARAMETERS节点,没有参数返回null。CALL节点将PARAMETERS加为子节点。方法checkParmCount()用来验证调用中的实参数目是否正确。

函数eof和eoln返回布尔值。函数abs和sqr接受整数或实数参数并返回同类型的值。函数arctan、cos、exp、ln、sin和sqrt每个都接受一个整数或实数参数且它的返回值类型一定是实数。函数pred和succ可接受整数或枚举常量参数,其返回值与参数同类型。函数chr接受整数参数返回字符。函数odd接受整数参数返回布尔类型。函数ord有一个字符或枚举常量参数,返回整数值。函数round和trunc接受实数参数并返回整数值。

实参列表

如果被调用的申明/标准程式有实参,则用类CallParser的parseActualParameters()解析。布尔参数isDeclared, isReadReadln, isWriteWriteln用来分别说明调用的是否是一个申明程式,或者是标准过程read/readln,异或是标准过程write/writeln。这三个布尔值异或,也就是一个调用只可能有一个为真。参见清单11-16

   1: protected ICodeNode parseActualParameters(Token token, SymTabEntry pfId,
   2:                                              boolean isDeclared,
   3:                                              boolean isReadReadln,
   4:                                              boolean isWriteWriteln)
   5:        throws Exception
   6:    {
   7:        ExpressionParser expressionParser = new ExpressionParser(this);
   8:        ICodeNode parmsNode = ICodeFactory.createICodeNode(PARAMETERS);
   9:        ArrayList<SymTabEntry> formalParms = null;
  10:        int parmCount = 0;
  11:        int parmIndex = -1;
  12:        //如果是申明程式,很容易取得参数个数
  13:        if (isDeclared) {
  14:            formalParms =
  15:                (ArrayList<SymTabEntry>) pfId.getAttribute(ROUTINE_PARMS);
  16:            parmCount = formalParms != null ? formalParms.size() : 0;
  17:        }
  18:  
  19:        if (token.getType() != LEFT_PAREN) {
  20:            if (parmCount != 0) {
  21:                errorHandler.flag(token, WRONG_NUMBER_OF_PARMS, this);
  22:            }
  23:  
  24:            return null;
  25:        }
  26:  
  27:        token = nextToken();  // 跳过左口号XX(y,z)
  28:  
  29:        // 遍历每一个实参
  30:        while (token.getType() != RIGHT_PAREN) {
  31:            ICodeNode actualNode = expressionParser.parse(token);
  32:  
  33:            //如果是申明程式,需要检查形参和实参的匹配
  34:            if (isDeclared) {
  35:                if (++parmIndex < parmCount) {
  36:                    SymTabEntry formalId = formalParms.get(parmIndex);
  37:                    checkActualParameter(token, formalId, actualNode);
  38:                }
  39:                else if (parmIndex == parmCount) {
  40:                    errorHandler.flag(token, WRONG_NUMBER_OF_PARMS, this);
  41:                }
  42:            }
  43:  
  44:            // 对于read/readln来说,实参必须为标量/布尔还有整数子界
  45:            else if (isReadReadln) {
  46:                TypeSpec type = actualNode.getTypeSpec();
  47:                TypeForm form = type.getForm();
  48:  
  49:                if (! (   (actualNode.getType() == ICodeNodeTypeImpl.VARIABLE)
  50:                       && ( (form == SCALAR) ||
  51:                            (type == Predefined.booleanType) ||
  52:                            ( (form == SUBRANGE) &&
  53:                              (type.baseType() == Predefined.integerType) ) )
  54:                      )
  55:                   )
  56:                {
  57:                    errorHandler.flag(token, INVALID_VAR_PARM, this);
  58:                }
  59:            }
  60:  
  61:            // 对于write/writeln,除了参数要求外,还有可选的宽度和精度
  62:            else if (isWriteWriteln) {
  63:  
  64:                // Create a WRITE_PARM node which adopts the expression node.
  65:                ICodeNode exprNode = actualNode;
  66:                actualNode = ICodeFactory.createICodeNode(WRITE_PARM);
  67:                actualNode.addChild(exprNode);
  68:  
  69:                TypeSpec type = exprNode.getTypeSpec().baseType();
  70:                TypeForm form = type.getForm();
  71:  
  72:                if (! ( (form == SCALAR) || (type == Predefined.booleanType) ||
  73:                        (type.isPascalString())
  74:                      )
  75:                   )
  76:                {
  77:                    errorHandler.flag(token, INCOMPATIBLE_TYPES, this);
  78:                }
  79:  
  80:                //可选的宽度
  81:                token = currentToken();
  82:                actualNode.addChild(parseWriteSpec(token));
  83:  
  84:                //可选的精度
  85:                token = currentToken();
  86:                actualNode.addChild(parseWriteSpec(token));
  87:            }
  88:  
  89:            parmsNode.addChild(actualNode);
  90:            token = synchronize(COMMA_SET);
  91:            TokenType tokenType = token.getType();
  92:  
  93:            // 是否分割实参的逗号?
  94:            if (tokenType == COMMA) {
  95:                token = nextToken();
  96:            }
  97:            else if (ExpressionParser.EXPR_START_SET.contains(tokenType)) {
  98:                errorHandler.flag(token, MISSING_COMMA, this);
  99:            }
 100:            else if (tokenType != RIGHT_PAREN) {
 101:                token = synchronize(ExpressionParser.EXPR_START_SET);
 102:            }
 103:        }
 104:  
 105:        token = nextToken();  // 跳过右括号
 106:  
 107:        if ((parmsNode.getChildren().size() == 0) ||
 108:            (isDeclared && (parmIndex != parmCount-1)))
 109:        {
 110:            errorHandler.flag(token, WRONG_NUMBER_OF_PARMS, this);
 111:        }
 112:  
 113:        return parmsNode;
 114:    }

方法parseActualParameters()创建并返回一个PARAMETERS节点,在没有参数的情况下返回null。它遍历解析每个实参,然后PARAMETERS将每个实参的分析树收纳为子节点。

如果调用的是申明程式,方法将调用checkActualParameter()检查每个实参-形参的匹配,个数是否相等。对于标准过程read/readln的调用,此方法检查它的每个实参是否是一个类型为标量/布尔/整数子界的变量。

调用标准过程write/writeln有些特殊。每个实参必须是一个类型为标量/布尔/Pascal字符串的表达式。每个参数可跟着一个用冒号,然后是一个表示输出字符宽度的整数常量。宽度之后还可有第二个冒号,紧接着是一个表示输出实数值的精度值的整数常量(也就是小数个数)。例如:

writeln('The square root of ', number:5, ' is ', sqrt(number):10:6);

因此,对于每个实参,方法parseActualParameters()创建一个WRITE_PARM节点,它将实参表达式分析树加为第一个子节点。如果有宽度值,宽度值为WRITE_PARAM节点的第二个子节点;如果有精度,则精度将会是WRITE_PARAM的第三个子节点。清单11-17 展示了上面writeln调用解析产生的分析树。

<CALL line="11" id="writeln" level="0">
<PARAMETERS>
<WRITE_PARM>
<STRING_CONSTANT value="The square root of "
type_id="$anon_4cb088b" />
</WRITE_PARM>
<WRITE_PARM>
<VARIABLE id="number" level="1" type_id="integer" />
<INTEGER_CONSTANT value="5" type_id="integer" />
</WRITE_PARM>
<WRITE_PARM>
<STRING_CONSTANT value=" is " type_id="$anon_4cb0887" />
</WRITE_PARM>
<WRITE_PARM>
<CALL id="sqrt" level="0" type_id="real">
<PARAMETERS>
<VARIABLE id="number" level="1" type_id="integer" />
</PARAMETERS>
</CALL>
<INTEGER_CONSTANT value="10" type_id="integer" />
<INTEGER_CONSTANT value="6" type_id="integer" />
</WRITE_PARM>
</PARAMETERS>
</CALL>

清单11-18 展示了CallParser的checkActualParameter()方法。

   1: //检测实参/形参的匹配
   2:     private void checkActualParameter(Token token, SymTabEntry formalId,
   3:                                       ICodeNode actualNode)
   4:     {
   5:         Definition formalDefn = formalId.getDefinition();
   6:         TypeSpec formalType = formalId.getTypeSpec();
   7:         TypeSpec actualType = actualNode.getTypeSpec();
   8:  
   9:         // VAR参数(引用传递): 实参类型必须与形参类型保持一致
  10:         if (formalDefn == VAR_PARM) {
  11:             if ((actualNode.getType() != ICodeNodeTypeImpl.VARIABLE) ||
  12:                 (actualType != formalType))
  13:             {
  14:                 errorHandler.flag(token, INVALID_VAR_PARM, this);
  15:             }
  16:         }
  17:  
  18:         // VALUE参数(值传递): 检查实参能否与形参赋值兼容?
  19:         else if (!TypeChecker.areAssignmentCompatible(formalType, actualType)) {
  20:             errorHandler.flag(token, INCOMPATIBLE_TYPES, this);
  21:         }
  22:     }
方法checkActualParameter()检查与形参对应的每个实参(按照 参数位置 )。如果参数是VAR参数(引用传递),则实参必须是一个类型与形参相同的变量;如果参数通过值传递,那么实参必须能够与形参类型达到赋值兼容( 比如形参为real,而实参为int,而real := int是可以赋值兼容的
清单11-19 展示了parseWriteSpec()方法,用来解析write/writeln实参中额外的宽度和精度值。
   1: //解析write/writeln实参额外的宽度/精度 比如 writeln(xx:50:2)
   2:    private ICodeNode parseWriteSpec(Token token)
   3:        throws Exception
   4:    {
   5:        if (token.getType() == COLON) {
   6:            token = nextToken();  // 跳过冒号
   7:  
   8:            ExpressionParser expressionParser = new ExpressionParser(this);
   9:            ICodeNode specNode = expressionParser.parse(token);
  10:            //必须是整数
  11:            if (specNode.getType() == INTEGER_CONSTANT) {
  12:                return specNode;
  13:            }
  14:            else {
  15:                errorHandler.flag(token, INVALID_NUMBER, this);
  16:                return null;
  17:            }
  18:        }
  19:        else {
  20:            return null;
  21:        }
  22:    }

方法parseWriteSpec()先搜寻冒号,接着解析后面的整数常量。

修改类StatementParser,使之可以处理过程调用、赋值到形参以及函数标识符。清单11-20展示了其parse()方法中switch语句部分,新版本的case IDENTIFIER。

   1: case IDENTIFIER: {
   2:             String name = token.getText().toLowerCase();
   3:             SymTabEntry id = symTabStack.lookup(name);
   4:             Definition idDefn = id != null ? id.getDefinition()
   5:                                            : DefinitionImpl.UNDEFINED;
   6:  
   7:             // 赋值语句或是程式
   8:             switch ((DefinitionImpl) idDefn) {
   9:  
  10:                 case VARIABLE:
  11:                 case VALUE_PARM:
  12:                 case VAR_PARM:
  13:                 case UNDEFINED: {
  14:                     AssignmentStatementParser assignmentParser =
  15:                         new AssignmentStatementParser(this);
  16:                     statementNode = assignmentParser.parse(token);
  17:                     break;
  18:                 }
  19:  
  20:                 case FUNCTION: {
  21:                     AssignmentStatementParser assignmentParser =
  22:                         new AssignmentStatementParser(this);
  23:                     statementNode =
  24:                         assignmentParser.parseFunctionNameAssignment(token);
  25:                     break;
  26:                 }
  27:  
  28:                 case PROCEDURE: {
  29:                     CallParser callParser = new CallParser(this);
  30:                     statementNode = callParser.parse(token);
  31:                     break;
  32:                 }
  33:  
  34:                 default: {
  35:                     errorHandler.flag(token, UNEXPECTED_TOKEN, this);
  36:                     token = nextToken();  //跳过标识符
  37:                 }
  38:             }
  39:         }

如果当前token是一个函数名称,方法parse()会调用assignmentParser.parseFunctionNameAssignment();如果是过程名称,则调用callParser.parse()。

清单11-21 展示了AssignmentStatementParser额外的处理代码。

   1: //是否是一个函数为赋值目标
   2: private boolean isFunctionTarget = false;
   3:  
   4: //函数式的赋值
   5: public ICodeNode parseFunctionNameAssignment(Token token)
   6:         throws Exception
   7: {
   8:         isFunctionTarget = true;
   9:         return parse(token);
  10: }

方法parseFunctionNameAssignment()在调用parse之前设置私有isFunctionTarget为真。方法parse()同样需要个小改动。(第54行)

ICodeNode targetNode =isFunctionTarget
? variableParser.parseFunctionNameTarget(token)
: variableParser.parse(token);
TypeSpec targetType = targetNode != null ? targetNode.getTypeSpec()
: Predefined.undefinedType;

这需要修改类VariableParser,参见下面清单11-22