打造解释器第三部分 - 解析树和语法树

• 下载演示 - 66 Kb
• 下载 PegWizard 源代码 (V0.01) - 19.2 Kb

引言

在关于构建解释器的第三篇文章中，我将展示如何从需要解析的源文本生成物理树。从源文本构建物理树有很多优点：它允许对原始源进行详细的分析、转换和优化。一棵树以及从树访问编译的符号表甚至可以作为简单解释器的基础。

对于递归下降解析器来说，树的生成特别容易，因为递归下降解析器由一组函数组成——每个函数对应一个语法规则。为了生成树，语法规则函数必须另外向已构建的树添加一个新子节点，其中新子节点代表由相应语法规则匹配的源部分。

有了树，语言分析和代码生成就会容易得多。尽管如此，并且尽管使用大多数解析器生成这种物理树很容易，但早期编译器（例如第一个 Pascal 或 C 编译器）并未生成此类树。这是因为内存占用的开销可能非常大——而内存是计算早期更宝贵的资源。

在本文系列中使用的 PEG 解析器 [1][2] 中，回溯会使树的生成复杂化。在解析失败的情况下，属于失败规则的树的部分必须再次删除。解析期间的异常必须像回溯一样处理。

作为树生成的一个有用应用，我将介绍一个解析器向导的核心，该向导接受文本形式的语法规则集，并为该语法生成解析器的骨架。如果没有解析树，这样的解析器向导（简单形式的解析器生成器）将难以构建。

树的优势

下表显示了一些问题，当有代表源文本的物理树时，可以轻松解决这些问题，而否则很难解决。

x= x + 1

x += 1

Int
(
  ('+' / '-') Int
)*

And< 
  Int, 
  OptRepeat< 
    And<
      OneOfChars<'+','-'>,
      Int
    >
  > 
>

while(i>0){
 j+= i;i--;
}

while( ConditionTrue(t) ){ 
   EvalStat(t->child);
}

if(G::Matches(pIn,&pContext)){
   pContext.Analyze();
   pContext.OptimizeTree();
   return pContext.GenCode();
}

解析树和语法树

解析树为每个非终结符使用一个物理树节点，这通常会导致巨大的树。语法树，通常称为抽象语法树或简称AST，是去除了大部分非终结符的解析树。区别在于内存使用，如下面的 PEG 语法示例中的解析树和语法树比较所示

//PEG grammar with start rule expr. 
//Note: this grammar does not accept any white space
expr : mexpr (('+'/'-')  mexpr )*;
mexpr: atom  ('*'  atom )*;
atom : [0-9]+ / '(' expr ')';

expr<
  mexpr<
    atom<'2'>
    '*'
    atom<
      expr<
        mexpr<atom<'3'>>
        '+'
        mexpr<atom<'5'>>
      >
    >
  >
>

mexpr<'2' '*' expr<'3' '+' '5'>>

与源文本相比，任何树形表示都会使用更多的内存，但解析树可能特别大。树的构建也比仅仅识别输入花费更多时间，如下面的输出所示，该输出来自本文随附的演示程序

-p
>> parse a 100000 char buffer filled with  2*(3+5)
>> CPU usage ( Syntax tree with 87504 nodes built) = 0.17 seconds
>> CPU usage ( Parse tree with 175003 nodes built) = 0.211 seconds
>> CPU usage (              Expression recognizer) = 0.03 seconds

与简单识别器相比，解析时间增加十倍并不少见。

树节点通常至少具有以下成员

• 两个指针成员——一个指向第一个子节点，另一个指向同级节点。
• 一个用于节点标识的成员
• 一个虚拟析构函数，以支持派生节点。

我当前的 PEG 实现具有以下节点接口

template<typename It >
struct TNode{
   typedef  TNode<It>        Self;
            TNode (int id=0, It beg=0, It end=0, Self* firstChild=0);
   virtual ~TNode (){} //support derived nodes

   virtual Self* AddChild (TNode* pChild);
  
   int   id;
   Self    *next,*child;
   BegEnd<It>  match; //references the source text matched by this node
};

将树生成集成到 PEG 解析器中

树的生成可以通过使用少量树生成模板添加到 PEG 解析器的基于模板的实现中。要使用这些模板，传递给 Matches 函数的 Context 结构必须派生自预定义的 TreeContext。这些树生成模板中的每一个都有一个用于识别 PEG 片段的类型参数和一个可选的整数值参数，用作生成树节点的标识键。下表列出了可用的树生成模板。

这些树生成模板的实际用法将通过一个支持运算符'+'、'-'、'*'以及括号用于子表达式的表达式语法来展示。

expr : 
  mexpr (('+'/'-')  mexpr )*;
mexpr: atom  ('*'  atom )*;
atom : [0-9]+ / '(' expr ')';

// ^ means: generate tree
// node for next terminal
expr : mexpr (^('+'/'-')  mexpr )*;
mexpr: atom  (^'*'  atom )*;
atom : ^([0-9]+) / '(' expr ')';

using namespace peg_templ;

struct expr{
typedef 
 //atom : [0-9]+ / '(' expr ')';

  Or<

    PlusRepeat<In<'0', 
               '9' > >,

    And<Char<'('>, expr, 
           Char<')'> >

  > atom;
typedef 
  //mexpr: atom  ('*'  atom )*;

  And<
    atom,
    OptRepeat<
      And<Char<'*'>, atom >
    >

  > mexpr;
typedef 
 //expr : mexpr (('+'/'-')  
                 mexpr )*;

  And<
    mexpr,
    OptRepeat<
      And<
        Or<Char<'+'>, 
              Char<'-'> >,
        mexpr
       >
     >
   > expr_rule;
   template<
     typename It,
     typename Context
   >
   static bool
     Matches(It& p,Context* pC)
   {
     return
     expr_rule::Matches(p,pC);
   }
};

using namespace peg_tree;
enum{eAtom,eMExpr,eInt,eExpr};
struct exprT{
typedef

 TreeNTWithId<eAtom,
    Or<

      TreeCharsWithId<eInt,
        PlusRepeat<In<'0', '9' > >
      >,
      And<Char<'('>, 
           exprT, Char<')'> >
    >
  > atom;
 typedef

 TreeNTWithId<eMExpr,
    And<
       atom,
       OptRepeat<

          TreeSafeAnd<TreeChars
             <Char<'*'> >, atom >
       >
    >
  > mexpr;
 typedef

 TreeNTWithId<eExpr,
    And<
      mexpr,
      OptRepeat<

        TreeSafeAnd<

          TreeChars<Or<Char
            <'+'>, Char<'-'> > >,
          mexpr
        >
      >
    >
   > exprT_rule;
  template<
    typename It,
    typename Context
  >
  static bool
    Matches(It& p,Context* pC)
  {
    return
    exprT_rule::Matches(p,pC);
  }
};

struct EmptyContext{};
bool CallRecognizingParser()
{
  EmptyContext c;
  typedef const 
     unsigned char* Iterator;
  const char* sTest= "2*(3+5)";
  Iterator it= (Iterator)sTest;
  return expr::Matches(it,&c);
}

bool CallTreeBuildingParser()
{
  typedef const 
    unsigned char* Iterator;
  //either use TreeContext 
  //or derived class

  peg_tree::TreeContext
        <Iterator> tc;
  const char* sTest= "2*(3+5)";
  Iterator it= (Iterator)sTest;
  return exprT::Matches(it,&tc);
}

接下来的章节将介绍解析器生成器和解析器向导作为复杂树构建解析器的示例。解析器生成器读取语法规范并输出解析器。解析器生成器通常会构建用户提供的语法规范的树形表示，因为它必须在生成相应的解析器之前分析和转换用户输入。

解析器生成器

在解析器领域，一个著名的产品类别是所谓的解析器生成器，例如YACC及其后续版本，或者一个更近期的发展ANTLR。它们接收文本形式的带注释的语法，并为其生成解析器。这些带注释的语法不仅包含语法规则 (使用接近我介绍的解释 PEG 解析器的表示法)，还包含当解析器经过注释点时要执行的代码 (所谓的语义动作)。这显示在以下摘录自ANTLR 文档 [3] 的一个对应于以下 PEG 语法的示例

//PEG grammar for expressions supporting 
//the operations '+','-','*' on integers.
expr : S mexpr S(('+'/'-') S mexpr S)*;
mexpr: atom  S('*' S atom S)*;
atom : [0-9]+ / '(' expr ')';
S    : [ \t\v\r\n]*;

class ExprParser extends Parser;

expr: mexpr ((PLUS|MINUS) mexpr)*
    ;

mexpr
    : atom (STAR atom)*
    ;

atom: INT
    | LPAREN expr RPAREN

class ExprParser extends Parser;

expr returns [int value=0]
{int x;}

    :      value=mexpr
        ( PLUS x=mexpr    {value += x;}
        | MINUS x=mexpr {value -= x;}

        )*
    ;

mexpr returns [int value=0]
{int x;}

    : value=atom 
      ( STAR x=atom {value *= x;} )*
    ;

atom returns [int value=0]

    : i:INT {value=
         Integer.parseInt(i.getText());}
    |   LPAREN value=expr RPAREN
    ;

通常，解析器生成器会将代码注释（上面 ANTLR 规范中的粗体部分）复制到生成解析器中的相应位置。下一步是编译生成的代码（例如，使用您的 Java 编译器）。如果编译出错或在测试解析器时出现意外行为，您可以返回编辑原始语法规范，或直接编辑生成的解析器代码。在后一种情况下，您将破坏规范和生成解析器之间的关系。但迟早您会这样做，使用 ANTLR 时，您会很幸运，因为生成代码相当可读。不幸的是，YACC 类型解析器的情况并非如此，它们生成的代码非常难以理解。C++ 的发明者 Stroustrup 在为他的 Cfront C++ 前端使用 YACC 时就遇到了这种情况。“回过头来看，对我来说，对于 C++ 来说，这是一个糟糕的决定。”[使用 YACC]。“Cfront 有一个 YACC 解析器，并辅以大量依赖于递归下降技术的词法技巧。”[4]

但我相信，即使对于像 boost::spirit 或 Perl 6 这样的集成解析器，类似解析器生成器的工具仍然有用。这样的工具，它生成一个入门解析应用程序，其目的与 MFC 应用程序向导类似，即生成初始对象和函数，然后由程序员进行编辑。

PegWizard 解析器向导

PegWizard 解析器向导具有与 MFC 应用程序向导类似的职责

MFC 应用程序向导会生成一个具有内置功能的应用程序，该应用程序在编译后实现了 Windows 可执行应用程序的基本功能。MFC 入门应用程序包括 C++ 源文件 (.cpp)、资源文件、头文件 (.h) 和项目文件 (.vcproj)。这些入门文件中的代码基于 MFC。[5]

转换为 PegWizard 解析器向导的情况

PegWizard 解析器向导会生成一个具有内置功能的应用程序，该应用程序在编译后实现了解析器应用程序的基本功能。PegWizard 入门应用程序包括 C++ 源文件 (.cpp) 和头文件 (.h)。这些入门文件中的代码基于 PEG 解析方法。

PegWizard 解析器向导应执行以下操作

下表显示了 PegWizard 解析器向导 V0.01.00 的一个示例用法。

PegWizard -g TestGrammar\expr.gram -o TestGrammar

Peg0Wizard 0.01.00 (alpha) [20050508]
INFO: file content of 'TestGrammar\expr.gram' read in
INFO: saved the generated parser in 'TestGrammar\expr.cpp'
program ended successfully

//PEG grammar for expressions supporting 
//the operations '+','-','*' on integers.
expr : S mexpr S(('+'/'-') S mexpr S)*;
mexpr: atom  S('*' S atom S)*;
atom : [0-9]+ / '(' expr ')';
S    : [ \t\v\r\n]*;

#include "peg_templ.h"
#include <iostream>
using namespace peg_templ;
struct expr;     //forward declarations
struct mexpr;
struct atom;
struct S;
struct expr{     //grammar rule implementation
   typedef And<
               S,
               mexpr,
               S,
    ...

输入语法文件必须符合以下 PEG 语法

Grammar:        S GrammarRule (S GrammarRule)* S ;
GrammarRule:    Nonterminal S ':' S RSideOfRule ;
RSideOfRule:    Alternative (S '/' S Alternative)* S ';' ;
Alternative:    Term (S Term)* ;
Term:        ('&' / '!')? S Factor S ( '*' / '+' / '?')?  ;
Factor:        (Nonterminal / Terminal / '(' S RSideOfRule S ')' ) ;
Nonterminal:    [a-zA-Z0-9_]+ ;
Terminal:    LiteralString | Charset | '.';
Charset:    '['  (CharsetRange / EscapeChar / CharsetChar   )+  ']' ;
LiteralString:  '\'' ( EscapeChar / !'\'' PrintChar )+ '\'' ;
CharsetChar:    !']' PrintChar ;
EscapeChar:    '\\' ( HexChar / PrintChar  ) ;
CharsetRange:    ( EscapeChar / CharsetChar ) '-' ( EscapeChar / CharsetChar ) ;
HexChar:    '(x|X)(' Hexdigit+ ')' ;
S:              ([ \v\t\r\n] | '//' [ \v\r\t]*  '\n')* ;
PrintChar:    //determined by 'isprint(c)' ;

为什么 PegWizard 内部构建解析树

PegWizard 读取 PEG 语法文件并生成相应的 C++ 源文件。如果没有解析树，这将很困难，因为 PEG 语法使用后缀表示法（例如，量词“*”、“?”、“+”出现在它们应用的构造的末尾），但生成的代码使用前缀运算符。此外，代码生成只是 PegWizard 的众多任务之一。其他任务包括检查左递归规则、检查语法完整性、自动插入错误处理代码等。如果没有树，这就需要重新解析语法文件。

总的来说，解析树或语法树几乎能让任何事情都变得更容易。物理树唯一的缺点是运行时和内存成本高。但在 PegWizard 的情况下，这无关紧要，因为语法文件通常很小。如今，语言编译器几乎肯定会从源文本构建物理树。例如，Cfront [4]（Stroustrap 的 C 前端）为所有全局元素和当前函数构建树结构。

未来方向

本文介绍的 PegWizard 作为一棵构建树的解析器，将被改进，并很快成为一个有用的工具。目前，它只生成识别解析器。

除了教授该主题——即解析——之外，本系列文章的目标是构建高效的解析器。这将通过比较手工制作的解析器和示意性构建的解析器来研究。

要点

在解析过程中很容易构建语法树或解析树。语法树使生活（解析和后续步骤）变得更加轻松，但也有其成本。当解析速度很重要并且可以不使用语法树时，应优先考虑。

历史

• 2005 年 5 月：初始版本。

参考文献

1. 解析表达式文法，Bryan Ford，麻省理工学院，2004 年 1 月 [^]
2. 解析表达式语法，维基百科，自由的百科全书 [^]
3. ANTLR 解析器生成器 [^]
4. Bjarne Stroustrap，《C++ 设计与演化》，Addison Wesley 1995。
5. MFC 应用程序向导 [^]