打造解释器第二部分 - Calc0玩具语言

• 下载示例 - 107 Kb
• 下载源代码 (过程式实现) - 9.71 Kb
• 下载源代码 (模板实现) - 10.4 Kb

引言

在关于构建解释器的第二篇文章中，我们讨论了一个非常简单的语言解释器的实现。我们使用解析表达式语法 (Parsing Expression Grammar, PEG) [1] [2] 来定义语法并实现解析器。我们展示了如何在解析过程中进行求值，以及如何扩展语法以在解析错误时发出错误消息。我们还进一步说明，有时为了便于解析过程中的直接求值，必须对语法进行微调。

为此目的使用的 Calc0 玩具语言支持表达式、赋值、变量和打印语句。 Calc0 解释器启动后，立即进入一个无限循环，该循环包含以下处理步骤：

• 读取用户输入的行。
• 解析该行，并在解析过程中，对识别出的表达式、赋值或打印语句进行求值。
• 更新内部的变量名及其关联值的映射。
• 输出求值结果。

Calc0 语法

Calc0 解释器期望单行输入。该行中最基本的元素是空格、标识符和数字。我们只允许空格字符、制表符和回车符作为空格。我们选择 C/C++ 标识符，并允许浮点数或整数作为数字。表达式支持加法、减法、乘法、除法和幂运算符。

我们需要一个与所使用的解析方法兼容的无上下文语法。由于我们选择了解析表达式语法形式化方法，这是一种 LL 解析方法，因此我们必须避免左递归规则。这将产生以下解析表达式语法：

//first attempt to calc0_grammar
calc0_grammar:    S  (print_variables /  assignement  / expression) S '\0';
assignement:      identifier S '=' S expression ;
print_variables:  '!' S (identifier (S '-'  S identifier)?)?  ;
expression:       multiplicative_expression 
                           (S ('+' / '-') S multiplicative_expression)* ;
multiplicative_expression: 
                  power_expression (S ('*' / '/') S power_expression)* ;
power_expression: primary_expression (S '^' S primary_expression)? ;
primary_expression: ('+' / '-')? S 
                  (identifier /  number / '(' S expression S ')') ;
number:           ([0-9]+ '.'? / '.'[0-9]) 
                                     [0-9]* (('e' / 'E') [0-9]+)? ;
identifier:       [A-Za-z_][A-Za-z_0-9]* ;
S:                [ \r\v\t]*  ;

该语法的起始规则称为 calc0_grammar。该规则的 PEG 操作解释如下：首先匹配可能的空格，然后尝试匹配剩余输入与 print_variables、assignement 或 expression 规则之一（按此顺序尝试）。如果成功，则通过跳过可能的空格继续解析，最后期望输入行的终止符，即零。其他规则可以类似地解释。

直接求值

解析过程中的直接求值意味着我们在解析它们的地方执行算术运算、变量赋值和变量访问。例如，加法和减法必须在负责解析 expression 的语法函数内完成。

expression: multiplicative_expression 
                   (S ('+' / '-') S multiplicative_expression)* ;

expression 规则的值的求值是通过将该规则组件的结果值相加/相减来完成的。中间结果存储在传递给每个语法规则函数的上下文结构中。下表显示了这一点。

double result= pS->result;

在解析循环中实际执行加法的最终代码显示在以下代码片段中。

 //code fragment taken from the template implementation of the rule expression
 double result= pS->result;
 for(;;){/*(S ('+' / '-') S multiplicative_expression)*; */
    S::Matches(p,pS);
    if( And<Char<'+'>,S,multiplicative_expression>::Matches(p,pS)){
       result+= pS->result;
    }else  if(  And<Char<'-'>,S, multiplicative_expression>::Matches(p,pS) ){
       result-= pS->result;
    }else ...

执行乘法和除法的 multiplicative_expression 规则的代码类似。直接求值中的一个主要问题出现在 identifier 语法规则中。根据标识符的使用位置，我们必须执行完全不同的操作，如下表所示。

在 PEG 解析方法中，语法规则与解析函数之间存在一对一的对应关系。但是，对于 identifier 的解析函数，我们必须根据调用者执行非常不同的操作。一种解决方案是在 identifier 的解析函数中检查调用者。但有一个更简单的解决方案：根据标识符的使用位置，为 identifier 使用不同的语法规则。对于 expression 规则也存在类似的问题。当用作顶层元素时（calc0_grammar 的替代项之一），我们应该打印出计算出的值，但如果表达式位于赋值的左侧或包含在括号中 (('(' expression ')'))，则不打印。我们可以通过引入两个等效的语法规则，即 expression 和 full_expression 来解决这个问题。这样，我们就得到了以下修订的 calc0 语法。

//Revised calc0_grammar
calc0_grammar:    S  (full_expression / assignement / print_variables) S '\0';
assignement:      variable S '=' S expression ;
print_variables:  '!' S (identFirst (S '-'  S identLast)?)?  ;
expression:       multiplicative_expression 
                           (S ('+' / '-') S multiplicative_expression)* ;
full_expression:  expression ;
multiplicative_expression: 
                  power_expression (S ('*' / '/') S power_expression)* ;
power_expression: primary_expression (S '^' S primary_expression)? ;
primary_expression: ('+' / '-')? S 
                  (identifier /  number / '(' S expression S ')') ;
number:           ([0-9]+ '.'? / '.'[0-9]) 
                                     [0-9]* (('e' / 'E') [0-9]+)? ;
identifier:         [A-Za-z_][A-Za-z_0-9]* ;
variable:         identifier ;
identFirst:       identifier ;
identLast:        identifier ;
S:                [ \r\v\t]*  ;

PEG 中的解析错误处理

解析器的输入是错误的，如果缺少预期的元素且没有其他替代项。PEG 形式化允许将错误识别集成到语法中，如下表所示。

PEG 语法中最简单的错误处理方式是停止在错误位置的解析过程，给出错误消息，然后抛出异常。我们在这里将使用这种技术，因为输入永远不会超过一行。我们通过附加一个 Fatal 替代项来增强带有错误情况指示符的语法。

//calc0_grammar with error handling indicators
calc0_grammar:    S 
                  (  print_variables /  
                     assignement     / 
                     full_expression      / 
                     Fatal<eExprAssPrintExpected>;
                  ) 
                  S 
                  ( '\0' / Fatal<eEndOfInputExpected>) ;

assignement:      variable S '=' S expression ;

print_variables: '!' 
                  S 
                  (
                      identFirst 
                      S 
                  ( '-'  S ( identLast / Fatal<eIdentExpected>) )?
                  )? ;

expression:       multiplicative_expression 
                           (S ('+' / '-') S multiplicative_expression)* ;

full_expression:  expression ;

multiplicative_expression: 
                  power_expression (S ('*' / '/') S power_expression)* ;

power_expression: primary_expression (S '^' S primary_expression)? ;

primary_expression: ('+' / '-')? S 
                    ( identifier /  
                      number     / 
                      '(' S expression S ( ')' / Fatal<eRParenExpected> ) /
                      Fatal<eIdentNumOrExprExpected>
                    ) ;

number:    ([0-9]+ '.'? / '.' ([0-9] / Fatal<eFracDigitsExpected>) ) 
    [0-9]* 
    (  ('e'|'E')
           ( '+' / '-' )? 
           ([0-9]+ / Fatal<eExponentDigitsExpected>)
        )?;

identifier:       [A-Za-z_][A-Za-z_0-9]* ;
variable:         identifier ;
identFirst:       identifier ;
identLast:        identifier ;

S:                [ \r\v\t]*  ;

在 PEG 实现中，上述语法规则（包括错误处理）与模板实例化之间存在一对一的关系。对于模板和过程式实现，其起始规则如下所示。

calc0_grammar: 
 S  (print_variables /  assignement / full_expression / Fatal) S ('\0' / Fatal) ;

typedef 
   And<
      S,
      Or<
         print_variables,
         assignement,
         full_expression,
         Fatal<
           eExprAssPrintExpected
         >
      >,
      S,
      Or<
         Char<0>,
         Fatal<eEndOfInputExpected> 
      >
 > rule;

inline bool calc0_grammar_rule(
          const uchar*& p, StateInfo* pS)
{ const uchar *p0,*p1;
   return 
   PEG_AND(p0,p,
      S  (p,pS)
   && PEG_OR4(p1,p,
      print_variables (p,pS),
      assignement     (p,pS),
      full_expression (p,pS),
      pS->Fatal(p0,
      "expression, "
        "v= expr or '!' expected")
     )
    && S(p,pS) 
    && (  Char(p,'\0')
      ||pS->Fatal(p, 
        "end of input expected")
     )
    );
}

维护跨运行的信息

此解释器在一个永恒的循环中运行，等待输入，然后读取、解析和求值。每次用户输入赋值时，它不仅会计算赋值中直接涉及的新变量值，还会查找使用该更改值的所有其他公式并重新计算它们。此信息存储在一个具有以下值类型的映射中。

typedef std::set<std::string,CompareNoCase> set_istring;
struct Formula{
   Formula(std::string e="",double v=0.0, const set_istring& sUsed=set_istring())
      :expression(e),value(v),setUsedIdents(sUsed){}
   std::string  expression;   //needed when recalculation necessary
   double       value;        //current value of the formula variable
   set_istring  setUsedIdents;//identifiers used by the formula
};

负责计算新变量值和重新计算相关公式的代码包含在规则 assignement: variable S '=' S expression; 的解析器部分中。作为赋值目标的变量及其值和名称，以及整个输入行，以及出现在赋值右侧的变量名，都作为 Formula 存储在 variables 映射中。

运行时错误处理

运行时错误处理是最常被低估的主题之一。运行时错误处理的两个主要问题是：

• 运行时错误检查的数量。
• 错误操作的类型：程序中止、抛出异常、设置标志或自动更正。

对运行时检查数量的期望因解释型语言和编译型语言而异，并且因语言而异。例如，数组边界检查在 Pascal 中是标准的，但在 C/C++ 中不可用。即使语言规范将运行时错误定义为严重错误，编程语言文化最终也可能温和地迫使实现者放弃发出运行时错误。一个很好的例子是 C/C++ 中的整数溢出，它会导致未定义的行为，但大多数 C/C++ 实现不会捕获。

关于运行时错误处理的第二个问题，即应执行何种错误操作，目前偏向于“抛出异常”。C++ 和 Java 甚至在其标准库中定义了完整的运行时异常继承树。唯一的例外是浮点错误处理，抛出异常可能不是正确的方法。IEEE 754（浮点运算标准）支持设置错误标志和触发陷阱。一旦设置了浮点错误标志，它将一直保持，直到被显式清除。标准流库识别 IEEE 754 错误标志并像下面示例中那样打印它们。

3/0
>> = 1.#INF

1e300*-1e300
>> = -1.#INF

当发生浮点溢出时，通过将浮点值设置为最大浮点值来继续计算可能是有意义的。Calc0 解释器在赋值给变量时会执行此操作，以避免变量映射中出现非法变量值。

x= 3/0
>> x= 1.#INF
      .. floating point overflow (=DBL_MAX)
>> x= 1.797693134862316e+308

Calc0 解释器通过使用非标准的 _fpclass 函数来识别浮点错误，该函数返回错误指示符，如 _FPCLASS_NINF（负溢出）、_FPCLASS_PINF（正溢出）等。C99 [2] 通过对 math.h 头文件进行补充来标准化浮点错误处理，但 VC6 和 VC7 尚不支持。

要点

由于解析过程中可用的上下文信息有限，因此解析过程中的直接求值可能很困难。有时通过修改语法可以改善这种情况。

由于 PEG 语法规则的组件是按顺序求值的，这使得执行顺序可预测，因此可以在 PEG 框架内轻松处理解析错误。

运行时错误处理必须适应目标用户群的期望。运行时错误处理的标准很少见。一个例外是浮点错误处理。

历史

• 2005 年 4 月：初始版本。

参考文献

1. 解析表达式文法，Bryan Ford，麻省理工学院，2004 年 1 月 [^]
2. 解析表达式语法，维基百科，自由的百科全书[^]
3. C99 <math.h> 库参考[^]