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

• 下载示例 - 98.6 Kb

引言

解析器、解释器和编译器正日益普及，普通程序员也能够接触到它们。最初，这些工具都是手工制作的。随后出现了解析器和编译器生成器（例如，流行的 UNIX 解析器生成器 YACC 或 ANTLR），而目前我们正在经历语法和解析器直接集成到宿主语言中的时代。例如，boost::spirit 作为库集成到 C++ 中，它带有一个领域特定的子语言（使用运算符重载和表达式模板）。Perl 6 甚至更进一步，将语法作为语言的一部分。这些工具对你帮助很大，但它们仍然需要对底层理论框架有相当多的了解。

这是系列文章的第一部分，解释了处理解析和编译的最基本概念和实践。它使用玩具编程语言及其解释器来揭示这些概念。对于每种玩具语言，都提供了示例程序。这些示例是手工编写的，但风格展示了如何自动化该任务。这篇语言处理的介绍面向新手和经验丰富的程序员。前者获得足够的解释性文本，后者获得 C++ 代码示例，展示如何以最少的负担进行语言处理。整个系列文章力求在理论和实现上都做到最小化。

构建解释器的步骤

让我们以一个用于算术公式的命令行计算器作为介绍性示例。以下摘录显示了一个示例会话，其中以“>>”开头的行表示程序输出。

Pi=3.1415926535
>> Pi= 3.1415926535

Area=Pi*r^2
>> Area= 0

r=3
>> Area= 28.2743338815
>> r= 3

为了实现这一点，计算器程序必须完成以下任务

解析和语法

解析是将层次结构与源文本关联的过程。程序员适当地缩进其源文本（例如，她缩进循环体）是一种简单的解析形式。解析是语言处理中的第一个任务，也是最重要的任务之一，因为它指导翻译系统的所有后续步骤。解析的正式框架由描述源语言的语法设定。语法由一组规则组成，这些规则共同将唯一的树结构与任何正确的输入文本关联起来。语法根据其表达能力分为不同的类别。最低级别是正则表达式的语法。这些语法无法描述递归嵌套的构造，而这些构造是表达（例如）语句具有其他语句作为其组成部分这一事实所必需的。通常用于描述编程语言的语法类别称为“上下文无关”。上下文无关语法的每条规则都具有 R: a b c | d ; 的形式，其中 R 是规则的名称（也称为非终结符），: 将规则名称与规则的右侧分开，而 a b c d 等是终结符或更多规则的名称（非终结符），| 用于分隔替代方案。下表将进一步解释这一点

以下示例上下文无关语法规则描述了一个由任意数量的括号括起来的数字字符串

EnclosedDigits: [0-9]+ | '(' EnclosedDigits ')' ;

此语法规则将输入字符串 ((123))) 与以下解析树关联起来

EnclosedDigits
               '(' EnclosedDigits                             ')'
                                 '(' EnclosedDigits       ')'
                                                    '123'

在接下来的示例中，我们将使用以下线性形式作为树表示法

EnclosedDigits< '(' EnclosedDigits< '(' EnclosedDigits<123> ')' > ')' >

有趣的是，规则 EnclosedDigits: 匹配从第一个字符到最后一个字符的完整输入字符串 ((123))，它还匹配内部部分，如 (123) 和 123。这之所以可能，是因为上下文无关语法的递归性质。当语法用于识别输入字符串时，我们说我们使用语法进行解析。语法也可以通过称为替换的过程生成语言字符串。替换发生在所谓的*起始规则*的右侧。替换意味着将一个非终结符替换为被替换非终结符规则右侧的替代项之一。通过在起始规则的右侧重复替换，我们可以生成属于语法描述的语言的所有输入字符串。这将通过以下示例*起始规则*进行展示

Expression: Expression '+' Expression | '(' Expression ')' | [0-9]+ ;

下表显示了一种可能的替换历史

Expression

Expression 
'+'
Expression

Expression< 
Expression 
'+' 
Expression
>

Expression 
'+'
Expression

Expression 
'+' 
'(' Expression ')'

Expression< 
  Expression 
  '+' 
  Expression<
     '(' Expression ')'
  >
>

Expression
'+'
'(' Expression ')'

'1001'







'+'
'(' Expression ')'

Expression<
  Expression<'1001'>
  '+'
  Expression<
    '(' Expression ')'
  >
>

'1001'
'+'
'(' Expression ')'

'1001'
'+'
'(' '37' ')'

Expression<
  Expression<'1001'>
  '+'
  Expression<
    '('
    Expression<'37'>
    ')'
  >
>

生成的语言字符串是 1001+(37)。请注意，替换的顺序——无论是先替换最右边的非终结符还是最左边的非终结符——并没有由上下文无关语法指定。因此，解析器不仅需要上下文无关语法来完成其工作，还需要一个解析策略，这只不过是一个内置规则，告诉哪个可能的替换首先执行。常见的解析策略是 LL 和 LR。这两种解析器都从左到右读取输入，这就是 LL 和 LR 中第一个 L 的原因。LL 解析器总是首先替换最左边的非终结符，而 LR 解析器总是首先替换最右边的非终结符。通常，LL 和 LR 解析器不接受相同的语法规则。LL 解析器不喜欢左递归规则，而 LR 解析器不喜欢右递归规则，这由以下示例语法规则说明

LR 语法 Digits: Digits? [0-9] 是左递归的，因为其右侧的第一个符号是规则名称。幸运的是，将 LR 语法重写为 LL 语法反之亦然并不困难，我们稍后会看到。

上下文无关语法的表达能力

现有编程语言的许多重要属性要么无法用上下文无关语法表达，要么描述起来非常繁琐。考虑一种带有过程的语言，其中过程名必须同时出现在开头和结尾

Proc: 'proc' Name  Parameters Body Name ';' ;

无法描述开头的 *Name* 必须与结尾的 *Name* 相同。再举一个长度限制的例子，例如，标识符不能超过 32 个字符的规则。虽然可以用上下文无关语法规则来描述，但这要么需要大量的编写，要么需要添加一个新的量词（例如：[a-zA-Z]{1,32}）。在许多情况下，事实证明，最好在成功解析后检查限制的违反，而不是试图在语法中表达该限制。一般来说，编程语言的语法总是接受合法构造的超集。上下文无关语法的真正强大之处在于正确描述层次关系，如下面的简单算术表达式语法示例所示。这是一个选择不佳的表达式语法

expr0: expr0 ('+'|'-') expr0 | expr0 ('*'|'/') expr0  | [0-9]+ ;

此语法没有表达 '+' 的优先级与 '*' 不同这一事实。以下是更好的表达式语法

expr1:    mul_expr | expr1 ('+'|'-') mul_expr ;
mul_expr: [0-9]+ | mul_expr ('*'|'/') [0-9]+ ;

源文本 2*3+5 可以由 expr0 解析为以下树

expr0<
   expr0<'2'>
   '*'
   expr0< expr0<'3'> '+' expr0<'5'> >
>

而 expr1 将产生此树

expr1<
   expr1<mul_expr<'2'> '*'  '3' >
   '+'
   mul_expr<'5'>
>

只有第二棵树反映了 '+' 和 '*' 运算符的优先级。顺便说一句，expr1 的语法规则适用于 LR 解析器，但不适用于 LL 解析器。

歧义的危险

如果源文本可以根据替换顺序解析成两个不同的解析树，则该语法是模糊的。上面的示例 expr0: expr0 ('+'|'-') expr0 | expr0 ('*'|'/') expr0 | [0-9]+ ; 是模糊的，因为源文本 2*3+5 可以解析成以下两棵树

expr0<expr0<'2'> '*' expr0< expr0<'3'> '+' expr0<'5'> > >

expr0<expr0<expr0<'2'> '*' expr0<'3'> > '+' expr0<'5'> >

取决于替换顺序。歧义破坏了语法的主要目的，即源文本与唯一层次结构的关联。语法的歧义是否真的导致不同的层次结构不仅取决于语法，还取决于解析策略。

递归下降解析

递归下降解析是最简单直观的解析方法。它是一种 LL 解析方法，因此它从左到右读取输入（LL 中的第一个 L），并从左到右遍历语法（LL 中的第二个 L）。递归下降这个名称是因为这种解析方法为每个语法规则使用一个函数。起始规则的函数必须解析完整的源。它通过提供一个函数体来完成此操作，该函数体通过以下方式实现起始规则的右侧

• 在有备选项的情况下，它会尝试所有有希望的备选项，执行相应备选项的代码，直到其中一个成功（匹配输入文本）
• 在语法符号序列（标记或非终结符）的情况下，它执行序列中每个符号的相应代码，直到其中一个失败，或者整个序列的代码成功。

请注意，递归下降解析器的实现有时需要*回溯*。回溯意味着您回到计算的先前状态。例如，如果所选备选项的第一部分成功匹配输入文本，然后发生不匹配，我们必须将源位置设置回进入备选项之前的位置，并选择另一个备选项。让我们通过一个示例实现来展示这一点。规则

EnclosedDigits: Digits | '(' EnclosedDigits ')' ; 
Digits: [0-9] Digits? ;

可以通过以下解析过程来实现，这些过程仅仅测试输入是否匹配语法规则

typedef const unsigned char* Iterator;
bool MatchesDigits(Iterator& it)         //[0-9]Digits?
{
   return (*it>='0' && *it<='9'?(++it,true):false)//[0-9]
      &&  (MatchesDigits(it),true);               //Digits?
}
bool MatchesEnclosedDigits(Iterator& it) //Digits | '(' EnclosedDigits ')'
{
   Iterator itSave= it;
   return
      MatchesDigits(it)                          // Digits
   ||                                            // |
       (   (itSave=it,
              (*it=='('?(++it,true):false)       //  '('
            && MatchesEnclosedDigits(it)         //   EnclosedDigits
            && (*it==')'?(++it,true):false)      //  ')'
           )
         ||(it=itSave,false)
       );                     
}

*起始语法函数* MatchesEnclosedDigits 接受一个迭代器（例如，字符指针）作为输入，如果匹配成功，则返回 true 并将迭代器设置为已识别文本之后的位置；如果匹配失败，则返回 false 并保持迭代器不变。语法规则与相应解析函数之间的密切关系表明，递归下降解析器无法处理以下语法规则

Digits: Digits? [0-9]  ;

因为这会导致无限递归。许多语言规范附带的语法都是为 LR 解析器编写的（著名的 YACC 工具需要 LR 语法）。但是，将 LR 语法重写为 LL 语法是相当容易的。

解析表达式文法（PEG）

所谓的解析表达式文法（PEG）形式主义 [1] 背后的思想是对上下文无关文法的“过程解释”。PEG 文法可以使用文法和源字符串作为输入进行“执行”。执行结果要么是输入字符串的匹配，在这种情况下，解析位置在识别部分的末尾；要么结果是“不匹配”，在这种情况下，输入位置保持不变。这个语句不仅适用于整个文法，也适用于每个文法规则。PEG 形式主义只不过是将递归下降解析中的常见实践映射到文法。它由以下文法元素组成

下表显示了 PEG 语法结构对示例输入字符串的影响。字符 | 表示输入位置

PEG 与正则表达式

由于 PEG 涵盖上下文无关文法，因此它们比正则表达式更强大。解析表达式文法和正则表达式之间最重要的区别在于前者支持递归定义，而后者不支持。但是，简单的非递归情况通常需要更短的正则表达式模式，这可以从电子邮件地址识别器中看出。

Regular expression as email address recognizer:
          [A-Za-z0-9._%-]+@[A-Za-z0-9._%-]+\.[A-Za-z]{2,4}

Incorrect PEG rule as email address recognizer:
   EMail: [A-Za-z0-9._%-]+'@'[A-Za-z0-9._%-]+'.'[A-Za-z]{2,4} ;

Correct PEG rules as email address  recognizer:
   EMailChar:   [A-Za-z0-9._%-];
   EMailSuffix:  [A-Za-z]{2,4} !EMailChar ;
   EMail:   EMailChar+
            '@'
            ([A-Za-z0-9_%-] |'.'!EMailSuffix)+
            '.'
            EmailSuffix ;

正确的 PEG 电子邮件地址识别器比正则表达式电子邮件地址识别器更复杂，并且使用隐式回溯（在 !EMailSuffix 中）。当我们使用 PEG 规则 EMail: [A-Za-z0-9._%-]+'@'[A-Za-z0-9._%-]+'.'[A-Za-z]{2,4} ; 解析合法电子邮件地址 *marc.bloom@blo.blo.uk* 时，我们会失败，因为 *blo.blo.uk* 将被贪婪规则组件 [A-Za-z0-9._%-]+ 识别，因此 '.'[A-Za-z]{2,4} 将没有剩余的输入字符。正则表达式模式没有这个问题，因为输入字符串 *blo.blo.uk* 将被正则表达式 [A-Za-z0-9._%-]+\.[A-Za-z]{2,4} 的两个部分巧妙地共享。幸运的是，事实证明，这种复杂的回溯（如在正确的 PEG 规则中使用的）在解析中很少需要。

PEG 元素的程序化和模板实现

理想的 C/C++ PEG 实现既接近 PEG 语法又具有运行时效率。这既可以通过普通的“C”代码实现，也可以通过 C++ 模板实现。C++ 模板被证明更灵活，而普通的 C 代码在程序员错误的情况下麻烦更少，因为模板的错误消息仍然难以解码。规则 S: 'C' ; 具有以下程序化实现

typedef const unsigned char* Iterator;

inline bool Char(Iterator& p,int c) { return *p==c?(++p,true) : false;}

bool S(Iterator& it){return Char(it,'C');}

以及以下模板实现

template<int CHARVALUE>
    struct Char{
        template<typename It>
        static bool Matches(It& p) { return *p==CHARVALUE?(++p,true):false;}
    };
struct S{
   typedef Char<'C'> rule;
   template<typename It>
   static bool Matches(It& p)      { return rule::Matches(p); }
};

下表概述了所有 PEG 构造的程序化和模板实现

In ( p, 'a', 'z', 
    'A', 'Z', '0', '9' )

In<'a', 'z', 'A', 'Z', 
    '0', '9'>::Matches(p)

OneOfChars ( p, ':', ';', '/' )

OneOfChars<':', ';', 
 '/'>::Matches(p)

String ( p,'f','o','r' )

String<'f', 'o', 
  'r'>::Matches(p)

( pSave=p, e1(p) && e1(p) )|| 
( p=pSave, false )

And<e1,e2>::Matches(p)

( pSave=p, e1(p))
|| ( p=pSave, e2(p) )
|| ( p=pSave, false )

Or<e1,e2>::Matches(p)

e ( p ) ; return true;

Option<e>::Matches(p)

while ( e(p) ) {} return true;

OptRepeat<e>::Matches(p)

if ( !e(p) ) {return false;}
while ( e(p) ) {} return true;

PlusRepeat<e>::Matches(p)

pSave=p; int i;
for ( i=0; i<=HIGH; i++ ) {
  if ( !e(p) ) { break; }
}
return i>=LOW ? true: 
   ( p=pSave,false );

For<LOW,HIGH>::Matches(p)

( pSave=p, e(p) )
?( p=pSave,true ):
( p=pSave, false )

Peek<e>::Matches(p)

( pSave=p, e(p) )
? ( p=pSave,false ) :
( p=pSave,true )

Not<e>::Matches(p)

++p

Advance<1>::Matches(p)

请注意，构造 . 和 e{LOW,HIGH} 不是最初提议的 PEG 元素的一部分，而是我添加的。应用于电子邮件 PEG 识别器规则，我们得到以下模板实现

bool MatchesEMail(openend_iterator& it)
{
  using namespace peg_templ;
  C c;

  typedef In<'A','Z','a','z'>                     Alpha;
  typedef In<'A','Z','a','z','0','9'>             Alnum;
  typedef Or<Alnum,OneOfChars<'.','_','%','-'> >  EMailChar;
  typedef And<For<2,4,Alpha >,Not<EMailChar > >   EMailSuffix;
  typedef And<
            PlusRepeat<EMailChar>,
            Char<'@'>,
            PlusRepeat<Or< Or<Alnum,OneOfChars<'_','%','-'> >,
                           And<Char<'.'>,Not<EMailSuffix> >
                       >
            >,
            Char<'.'>,
            EMailSuffix
          > EMail;

  return EMail::Matches(it,&c);
}

请注意，EMail::Matches(it,&c) 有两个参数（与上表相反）。第一个是迭代器，第二个是指向解析上下文的指针。如果要在解析期间执行某些操作，此解析上下文是必需的。

输入迭代器

解析器读取要解析的源。不同源的存储介质、编码和输入结束指示符可能不同。在大多数情况下，存储介质是文件或字符串。字符编码可以是 ASCII、UTF-8 或许多其他 Unicode 编码之一。输入结束可以通过特殊终止符的存在或与输入结束指针进行比较来检测。

在大多数情况下，检查每个输入位置是否到达输入末尾是不必要的。大多数语法只期望可能的输入字符的一个子集。如果我们知道输入由一个特殊字符（例如 '\0'）终止，我们可以使用如下起始规则：S: TopRule '\0';。

如果我们使用模板参数 Iterator，我们可以通过提供合理的迭代器实现来应对所有上述可能性。我们的 PEG 实现仅使用以下迭代器操作

下表显示了输入迭代器的两个示例模型

typedef const unsigned 
      char* peg_openend_iterator;

struct peg_begend_iterator{
   peg_begend_iterator(const 
        char* p=0,const char* pEnd=0)
      :m_p((const unsigned char*)p),
       m_pEnd((const unsigned 
                char*)pEnd){}
   int  operator*()const{
      return m_p==m_pEnd?
         (INT_MIN+1):*m_p;
   }
   peg_begend_iterator& 
          operator++(){
      if(m_p<m_pEnd)++m_p;
      return *this;
   }
   unsigned const char* m_p;
   unsigned const char* m_pEnd;
};

为什么性能很重要

C++ 编译器的解析器花费的编译时间不到 20%。但是，有许多解析应用程序不需要复杂的后处理，速度确实很重要。例如，开发环境的自动完成支持、C/C++ 源文件的预处理、从大型 XML 文件中提取项目。

解析效率低下的主要原因有两个

• 回溯
• 不必要抽象的运行时开销

在递归下降解析中，可以通过重写语法来避免具有相同开头的替代项，从而避免回溯。这种技术称为左因子分解，将在本系列下一篇文章中展示。在 YACC（UNIX 解析器生成器）使用的 LR 解析（准确地说是 LALR 解析）中，通过内部使用堆栈来存储等待进一步处理的符号，从而避免了回溯。众所周知，使用优化语法的手写递归下降解析器和 YACC 等工具是性能最好的。但对于普通用户来说，手写解析器和编译器生成工具都不是理想的，前者因为它们需要太多工作，后者因为它们在大多数情况下生成难以理解和维护的代码。使用解析表达式文法（PEG），情况可能会改变，因为 PEG 将易于理解的递归下降技术与高效实现的可能性结合起来，而且与原始语法非常接近。因此，我比较了三种 PEG 实现和一个手动优化解析器的运行时效率。我将算术表达式语法作为测试用例，因为这样的语法可以写成不需要回溯的方式。所有测试的解析器都必须解析表达式 132*( firstOccurance + x2*( 1001/N55 )+19 )，该表达式重复直到填满 1000000 个字符的缓冲区。下表给出了结果。

结果表明，模板化和过程化的 PEG 实现非常接近手写优化解析器。它们还表明，使用始终检查输入结束条件的迭代器是有代价的。

关注点

解析表达式文法（Parsing Expression Grammars）这个术语是由 Bryan Ford [1] 提出的。他还指出，这种带回溯的递归下降解析是常见的做法。他展示了只需极少的规则即可定义一个强大的解析框架。他没有依赖于消除具有相同开头（所谓的左因子分解）的替代方案的文法转换，而是发明了一种解析器，该解析器记忆已走过的路径，并为任何 PEG 文法实现了线性解析时间（packrat 解析器）。

PEG 的一个重要优势在于不需要单独的扫描器。在使用扫描器进行解析时，将解析任务分为低级部分（扫描）和高级部分（实际解析）。扫描器通常跳过空白和注释，读取数字、运算符和标识符等项目，并返回一个整数值以指示它发现了什么。扫描器在某些情况下减少了回溯的必要性。另一方面，它引入了一个从理论角度来看从未必要的抽象层次，并且由于缺乏上下文信息而可能导致问题。一个典型的例子是模板实例化中的闭合尖括号（> 符号）。如果您使用 >> 一次关闭两个模板实例化（必须使用 > > 代替），您会收到编译器错误，因为扫描器将 >> 识别为移位运算符，这是一个在不使用扫描器时不会出现的问题。有趣的是，Christopher Diggins [2] 在本网站上展示了他的 YARD 解析器，他没有提及 Bryan Ford 的工作，但完全使用了 PEG 的思想，包括无扫描器解析。这当然是因为这些思想“不胫而走”。

历史

• 2005 年 4 月：初版。
• 2005 年 4 月：修正了“PEG 与正则表达式”章节 （感谢 Gary Feldman）。

参考文献

1. 解析表达式文法，Bryan Ford，麻省理工学院，2004 年 1 月 [^]
2. 使用 YARD 解析器的正则表达式分词器，Christopher Diggins，2004 年 12 月 [^]