C# 3.0 的解析表达式文法支持 第1部分 - PEG Lib和解析器生成器

• 下载 PEG Explorer 和源代码 - 591.59 KB

引言

这是系列文章的第一部分，涵盖了解析技术 解析表达式文法。本部分介绍了 C# 3.0 的支持库和解析器生成器。该支持库由 PegCharParser 和 PegByteParser 类组成，用于解析文本和二进制源，并支持用户定义的错误处理、解析时的直接求值、解析树生成和抽象语法树生成。使用这些基类可以生成快速、易于理解和扩展的解析器，它们与宿主 C# 程序良好集成。

底层的解析方法——称为 解析表达式文法 [1][2][3] ——相对较新（首次描述于2004年），但已经有很多实现。解析表达式文法（PEG）可以很容易地用任何编程语言实现，但特别适合具有丰富表达式语法的语言，如函数式语言和功能增强的命令式语言（如 C# 3.0），因为 PEG 概念与相互递归函数调用、短路布尔表达式和内联定义的函数（lambda）有着密切的关系。

解析领域的一个新趋势是将解析器集成到宿主语言中，以便文法表示法和宿主语言实现之间的语义鸿沟尽可能小（Perl 6 和 boost::sprit 是这一趋势的先行者）。在追求这一目标时，解析表达式文法特别适用。早期的文法实现起来并不那么容易，以至于一条文法规则可能导致几十行代码。在某些解析策略中，文法规则和实现代码之间的关系甚至丢失了。这就是直到最近才使用生成器来构建解析器的原因。

本文展示了如何利用 C# 3.0 的 lambda 功能实现解析表达式文法的支持库，从而使 PEG 技术解析变得简单。使用此库时，PEG 文法被映射到一个 C# 文法类，该类继承了 PEG 基类的基本功能，并且每个 PEG 文法规则都被映射到 C# 文法类中的一个方法。使用此库实现的解析器应该快速（只要 C# 编译器尽可能内联方法），易于理解和扩展。此库还支持错误诊断、解析树生成和语义动作添加。

PEG，尤其是这个库，最显著的特点是占用空间小，没有任何管理开销。

本文主要解释PEG框架，并研究具体的应用示例。其中一个示例应用程序是PEG解析器生成器，它生成C#源代码。PEG解析器生成器是唯一一个手动编写的示例解析器，所有其他示例解析器都是由解析器生成器生成的。

目录

• 引言
• 解析表达式文法教程
  • 解析表达式文法基础
  • 解析表达式文法特点和惯用法
  • 将语义动作集成到 PEG 框架中
  • 解析表达式文法揭秘
• 解析表达式文法实现
  • PEG 的通用实现策略
  • 映射到 C#1.0 的解析表达式文法
  • 映射到 C#3.0 的解析表达式文法
• 解析表达式文法示例
  • Json 检查器（仅识别）
  • Json 树（构建树）
  • 基本编码规则（直接求值 + 构建树）
  • 科学计算器（构建树 + 求值树）
• PEG 解析器生成器
  • 使用 PEG 实现的 PEG 生成器
  • PEG 解析器生成器文法
  • PEG 解析器生成器对语义块的处理
• 透视解析表达式文法
  • 解析表达式文法调优
  • PEG 解析与其他解析技术的比较
  • 将 LR 文法转换为 PEG 文法
• 未来发展

解析表达式文法教程

解析表达式文法是一种可执行文法。执行 PEG 文法意味着匹配输入字符串的文法模式会相应地推进当前输入位置。不匹配的处理方式是回到先前的输入字符串位置，然后解析可能继续尝试其他选项。以下小节将详细解释 PEG，并介绍基本的 PEG 构造，这些构造已被作者扩展以支持错误诊断、直接求值和树生成。

解析表达式文法基础

以下 PEG 语法规则

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

引入了一个称为非终结符 **EnclosedDigits** 和一个包含两个备选项的右侧。

第一个备选项（[0-9]+）描述了一串数字，第二个（'(' EnclosedDigits ')'）描述了括号中的内容。以字符串 ((123))+5 作为输入执行 EnclosedDigits 将会匹配成功，并将输入位置移到 +5 之前。

此示例还展示了递归定义的潜力，因为 **EnclosedDigits** 一旦识别到开括号，就会使用自身。下表显示了对其他一些输入字符串应用上述文法的结果。**|** 字符是一个人工字符，用于可视化匹配前后的输入位置。

对于熟悉正则表达式的人来说，可以将解析表达式文法视为一种广义的正则表达式，它总是匹配输入字符串的开头（正则表达式前缀为 ^）。正则表达式由一个表达式组成，而 PEG 由一组规则组成；每条规则都可以使用其他规则来帮助解析。起始规则匹配整个输入，并使用其他规则匹配输入的子部分。在解析过程中，始终有一个当前输入位置，从该位置开始的输入字符串必须与 PEG 文法的其余部分匹配。与正则表达式一样，PEG 支持后缀运算符 * + ?、点 . 以及用 [] 包围的字符集。

PEG独有的前缀运算符是 & (窥视) 和 ! (非)，它们用于向前查看而不消耗输入。PEG中的备选项不是用 | 分隔，而是用 / 分隔，表示备选项严格按顺序尝试。PEG文法之所以强大，同时又可能占用大量内存，是因为它支持无限回溯，这意味着在备选项失败的情况下，输入位置可以回溯到任何先前访问过的输入位置。关于PEG的详细解释可以在维基百科 [2] 中找到。下表概述了本文描述的库类所支持的PEG构造（以及一些自创的扩展）。以下术语被使用：

本库支持的扩展 PEG 构造列于下表
（| 表示输入位置，斜体如 *name* 表示占位符）

PegNode CreaFuncName(ECreatorPhase phase, PegNode parentOrCreated, int id)
{
     if (phase == ECreatorPhase.eCreate || phase == ECreatorPhase.eCreateAndComplete)
     { // create and return the custom node; if phase==ECreatorPhase.eCreateAndComplete
       // this will be the only call
     }else{
      // finish the custom node and return parentOrCreated; one only gets here
      // after successful parsing of the subrules 
     }
}

解析表达式文法特点与惯用法

PEG 在某些方面与正则表达式类似：PEG 应用于输入字符串可以解释为一种模式匹配过程，它将输入字符串的匹配部分分配给文法规则（很像正则表达式中的组），并在不匹配时回溯。PEG 和正则表达式之间最重要的区别在于，PEG 支持递归，并且 PEG 模式是贪婪的。与大多数其他传统语言解析技术相比，PEG 令人惊讶地不同。最显著的区别在于：

• 解析表达式文法是确定性的，永不歧义，从而消除了大多数其他解析技术的问题。歧义意味着相同的输入字符串可以使用给定文法的不同规则集进行解析，并且没有策略说明应该使用哪些相互竞争的规则。在大多数情况下，这是一个严重的问题，因为如果未检测到，它会导致相同输入的解析树不同。缺乏歧义是 PEG 的一个巨大优点。但是，PEG 规则中备选项的顺序很重要，这需要一些时间来适应。
  例如，以下 PEG 规则 rel_operator: '<' / '<=' / '>' / '>='; 永远无法成功识别 <=，因为会选择第一个备选项。
  正确的规则是：rel_operator: '<=' / '<' / '>=' / '>';
• 解析表达式文法是无词法分析器的，而大多数其他解析器将解析任务分为低级的词法解析阶段（称为词法分析）和高级阶段（即解析）。词法解析阶段只解析数字、标识符和字符串等项，并将信息作为所谓的标记呈现给解析器。这种划分有其优点和缺点。它在某些情况下避免了回溯，并使得区分关键字和标识符等变得容易。大多数词法分析器的弱点在于词法分析器内部缺乏上下文信息，因此给定的输入字符串总是产生相同的标记。这并不总是可取的，例如在 C++ 中，输入字符串 >> 会引起问题，它可以是右移运算符，也可以是两个模板括号的闭合。
• 解析表达式文法可以回溯到输入字符串开头的任意位置。PEG 不要求必须将要解析的文件完全读入内存，但它禁止释放文件中已解析的任何部分。这意味着，预计将解析到末尾的文件，在解析开始之前应完全读入内存。幸运的是，内存不再是稀缺资源。在直接求值场景中（语义操作在识别到相应语法元素后立即执行），回溯也可能导致问题，因为已执行的语义操作在大多数情况下不容易撤销。因此，语义操作应放置在不再可能发生回溯，或者回溯将指示致命错误的点。PEG 解析中的致命错误最好通过抛出异常来处理。
• 对于许多常见问题，PEG 框架中存在惯用的解决方案，如下表所示：

//to avoid
[3]prod: val S ([*/] S val S)*;
[4]val : [0-9]+ / '(' S expr ')' S;
//to prefer
[3]prod: val ([*/] S val)*;
[4]val: ([0-9]+ / '(' S expr ')') S;

SingleCharacter: !['\\] InputCharacter

(!./FATAL<"end of input expected"> )

GenericQuote<'"',(!'"' .)*,'"'>

<= / <

//expect a symbol
'('  expr  @')'
//same as
'('  expr  (')'/FATAL<"')' expected"> );
	

//poor error handling
[4]object:   '{' S members?  @'}' S;
[5]members:   (str/num)(',' S @(str/num))*;
//better error handling
[4]object: '{' S (&'}'/members) @'}' S;
[5]members: @(str/num)(',' S @(str/num))*; 
	

PEG 惯用法应用于实际文法问题

大多数现代编程语言都基于文法，这些文法几乎可以通过主流的解析技术 (LALR(1) 解析) 进行解析。这里的重点是“几乎”，这意味着通常存在一些文法规则需要文法框架之外的特殊处理。PEG 框架可以更好地处理这些特殊情况，这将在 C++ 和 C# 文法中展示。

例如，C# 语言规范 V3.0 对其 cast-expression/parenthized-expression 消歧规则有以下措辞

A sequence of one or more tokens (§2.3.3) enclosed in parentheses is considered 
the start of a cast-expression only if at least one of the following are true:
    1) The sequence of tokens is correct grammar for a type, 
       and the token immediately following the closing parentheses is 
       the token ~, the token !, the token (, an identifier (§2.4.1), 
       a literal (§2.4.4), or any keyword (§2.4.3) except as and is.
    2) The sequence of tokens is correct grammar for a type, but not for an expression.

这可以用 PEG 表达为

cast_expression: 	       
/*1)*/     ('(' S   type   ')' S &([~!(]/identifier/literal/!('as' B/'is' B) keyword B)
/*2)*/	/  !parenthesized_expression   '(' S type ')' ) S   unary_expression;
B: ![a-zA-Z_0-9];
S: (comment/whitespace/new_line/pp_directive )*;

C++标准对其表达式语句/声明消歧规则有以下措辞：

An expression-statement ... can be indistinguishable from a declaration ... 
In those cases the statement is a declaration.

这可以用 PEG 表达为

statement: declaration /  expression_statement;

将语义动作集成到 PEG 框架中

PEG 文法只能识别输入字符串，它只给你两个结果：一个布尔值表示匹配成功或失败，以及一个指向匹配字符串部分末尾的输入位置。但在大多数情况下，文法只是给输入字符串一个结构的一种方式。然后，这个结构被用来将输入字符串与一个含义（语义）相关联，并根据这个含义执行语句。在解析过程中执行的这些语句称为语义动作。PEG 文法的可执行特性使得语义动作的集成变得容易。假设文法符号序列为 e1 e2，并且在识别 e1 后应该执行语义动作 es_，我们只需得到序列 e1 es_ e2，其中 es_ 是宿主语言的一个函数。

从文法角度看，es_ 必须符合与 e1、e2 或任何其他 PEG 组件相同的接口，这意味着 es_ 是一个返回 bool 值的函数，其中 true 表示成功，false 表示失败。语义函数 es_ 可以在使用（调用）es_ 的规则中局部定义，也可以在文法的全局环境中定义。将语义函数、into-variables、辅助数据值和辅助函数打包，然后形成一个语义块。

语义动作在 PEG 文法中面临一个大问题，即回溯。在大多数情况下，语义函数（例如，计算算术子表达式的结果）执行后，不应再发生回溯。在这种情况下，防止回溯的最简单方法是将任何回溯尝试视为致命错误。本文介绍的 FATAL<msg> 构造会中止解析（通过引发异常）。

将语义动作嵌入到文法中，可以对解析的构造进行直接求值。一个典型的应用是在解析阶段逐步计算算术表达式。直接求值速度快，但限制很多，因为它只能使用当前解析点的信息。因此，在许多情况下，嵌入式语义动作用于在解析过程中收集信息，以便在解析完成后进行处理。

收集到的数据可以有多种形式，但最重要的一种是树。优化解析器和编译器会将语义操作推迟到解析阶段结束，在解析过程中只创建物理解析树（我们的 PEG 框架通过前缀 ^ 和 ^^ 支持树生成）。然后，树遍历过程会检查和优化树。最后，树在运行时被解释，或者仅用于生成虚拟或实际机器代码。最重要的求值选项如下所示：

Parsing -> Direct Evaluation
	-> Collecting Information during Parsing
		-> User defined datastructure
			->User defined evaluation
		-> Tree Structure
			->Interpretation of generated tree
			->Generation of VM or machine code

在 PEG 实现中，树生成必须通过删除回溯恢复点之后构建的树部分来应对回溯。此外，当 Peek 或 Not 产生式处于活动状态时，不应创建任何树节点。在此实现中，这是通过 And、Peek、Not 和 ForRepeat 产生式的实现中感知树生成的代码来处理的。

解析表达式文法揭秘

以下示例文法也取自维基百科关于 PEG 的文章 [2]（但符号略有不同）。

<<Grammar Name="WikiSample">>
Expr:    S Sum;
Sum:     Product  ([+-] S Product)*;
Product: Value ([*/] S Value)*;  
Value:   [0-9]+ ('.' [0-9]+)? S / '(' S Sum ')' S;
S:       [ \n\r\t\v]*;
<</Grammar>>

在将文法应用于输入字符串期间，每个文法规则都从某个父文法规则调用，并匹配父规则匹配的输入字符串的子部分。这会生成一个解析树。文法规则 Expr 将算术表达式 2.5 * (3 + 5/7) 与以下解析树相关联：

Expr<
	S<' '>

	Sum<
		Product<
			Value<'2.5' S<' '>>
			'*'          //[*] see text 
			S<' '>
			Value<

				'(' 
				S<''> 
				Sum<
					Product<Value<'3' S<' '>>
					'+' 
					S<' '> 
					Product< Value<'5' S<''>> '/' S<''> Value<'7' S<''>> >

                                >
                        >
               >
	>
>

上述解析树不是物理树，而是在解析过程中存在的隐式树。PEG 解析器的自然实现是将每个文法规则与一个方法（函数）关联起来。文法规则的右侧对应于函数体，规则右侧的每个非终结符都映射到一个函数调用。当调用规则函数时，它会尝试将当前输入位置的输入字符串与规则的右侧进行匹配。如果成功，它会相应地前进输入位置并返回 true，否则输入位置不变，结果为 false。因此，上述解析树可以视为堆栈跟踪。上述解析树中标有 [*] 的位置对应于函数堆栈 Value<=Product<=Sum<=Expr，其中函数 Value 位于堆栈顶部，函数 Expr 位于堆栈底部。

上述解析过程仅匹配输入字符串，否则匹配失败。但在此解析过程中添加语义动作并不困难，只需在适当位置插入辅助函数即可。例如，算术表达式的 PEG 解析器可以在解析过程中计算表达式的结果。这种直接求值不会显著减慢解析过程。使用上面列出的变量赋值和语义块，可以得到以下用于算术表达式的增强 PEG 文法，它直接求值表达式结果并将其打印到控制台。

<<Grammar Name="calc0_direct">>
Top{ // semantic top level block using C# as host language
  double result;
  bool print_(){Console.WriteLine("{0}",result);return true;}
}
Expr:    S Sum   (!. print_ / FATAL<"following code not recognized">);
Sum
{  //semantic rule related block using C# as host language 
	double v;
	bool save_()  {v=  result;result=0; return true;}
	bool add_()   {v+= result;result=0;return true;}
	bool sub_()   {v-= result;result=0;return true;} 
  	bool store_() {result= v; return true;}
}	:     
	Product save_
                ('+' S Product add_
		/'-' S Product sub_)* store_		;
Product
{ //semantic rule related block using C# as host language 
	double v;
	bool save_()  {v=  result;result=0; return true;}
	bool mul_()   {v*= result;result=0; return true;}
	bool div_()   {v/= result;result=0;return true;} 
	bool store_() {result= v;return true;}	
}	: 
	Value  save_
		('*' S Value mul_
		/'/' S Value div_)* store_		;
Value:   Number S / '(' S Sum ')' S	;
Number
{ //semantic rule related block using C# as host language 
	string sNumber;
	bool store_(){double.TryParse(sNumber,out result);return true;}
}
	:  ([0-9]+ ('.' [0-9]+)?):sNumber store_	;
S:	 [ \n\r\t\v]*					;
<</Grammar>>

在许多情况下，解析时的即时求值是不够的，需要一个物理解析树或抽象语法树（简称 AST）。AST 是一个精简到基本节点的解析树，从而节省空间并提供更适合求值的视图。这种物理树通常需要至少是输入字符串内存空间的 10 倍，并将解析速度降低 3 到 10 倍。

以下 PEG 文法使用符号 ^ 表示抽象语法节点，符号 ^^ 表示解析树节点。下文给出的文法还增强了错误处理项 Fatal< errMsg>。Fatal 会立即退出解析过程，结果为失败，但输入位置设置为发生致命错误的位置。

<<Grammar Name="WikiSampleTree">>
[1] ^^Expr:   S Sum (!./FATAL<"end of input expected">) ;
[2] ^Sum:     Product  (^[+-] S Product)*               ;
[3] ^Product: Value (^[*/] S Value)*                    ;  
[4] Value:    Number S / '(' S Sum ')' S  /
                 FATAL<"number or  ( <Sum> )  expected">;
[5] ^^Number: [0-9]+ ('.' [0-9]+)?                      ;
[6] S:        [ \n\r\t\v]*                              ;
<</Grammar>>

有了这个文法，算术表达式 2.5 * (3 + 5/7) 将会产生以下物理树：

Expr<

  Product<
    Number<'2.5'>
    <'*'>
    Sum< Number<'3'>; <'+'> Product<Number<'5'><'/'>Number<'7'> >>

  >
>

有了物理解析树，可以实现更多的求值选项，例如，可以在优化树之后为虚拟机生成代码。

解析表达式文法实现

在本章中，我将首先逐一展示如何实现所有 PEG 构造。这将用伪代码表示。然后我将尝试在 C#1.0 和 C#3.0 中为这些基本 PEG 函数找到最佳接口。

PEG 的通用实现策略

PEG 的自然表示是带有回溯的自顶向下递归解析器。PEG 规则实现为函数/方法，它们在需要时相互调用，并在匹配成功时返回 true，在不匹配时返回 false。回溯的实现方式是在调用解析函数之前保存输入位置，如果解析函数返回 false，则将输入位置恢复到保存的位置。

如果输入位置只在所有其他情况下的成功匹配后才向前移动，那么回溯可以限制在 PEG 序列构造和 e<min,max> 重复中。在下面的伪代码中，我们使用字符串和整数变量、短路条件表达式（使用 && 表示 AND，使用 || 表示 OR）和异常。s 代表输入字符串，i 指代当前输入位置。bTreeBuild 是一个实例变量，当设置为 false 时，它会阻止树构建操作。

if i<length(s) && s[i]=='\u03A0'
     {i+= 1; return true;}
else {return false;}

if i+2<length(s) && s[i]=='a' && s[i+1]=='b' 
      { i+= 2; return true; }
else {return false; }

			
if    i+2<length(s) && toupper(s[i])=='A' && toupper(s[i+1] =='B' 
     { i+= 2; return true; }
else {return false; }

if i+1<length(s) && (s[i]=='a'|| s[i]=='b')
     {i+= 1; return true;}
else {return false;}

if i+1<length(s) && s[i]>='a' && s[i]<='z'
     {i+= 1; return true;}
else {return false;}	

if i+1<length(s) 
     {i+=1;return true;} 
else {return false;}

if i<length(s) && ExtractBitsAsInt(s[i],7,8)==3 
     {i+=1;return true;}
else {return false;}

int i0= i; 
TreeState t=SaveTreeState();
if e1() && e2() 
      {return true;}
else  {i=i0; RestoreTreeState(t);return false;}

return e1() || e2();

return e() || true;

while e() {} return true;

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

	

int c,i0=i; 
TreeState t=SaveTreeState();
for(c=0;c<high;++c){if !e(){ break;} }
if c<low    { i=i0; RestoreTreeState(t); return false;}
else        {return true;}

int i0=i; 
bool bOld= bTreeBuild; bTreeBuild= false;
bool b= e();
i=i0; bTreeBuild= bOld;
return b;

int i0=i; 
bool bOld= bTreeBuild; bTreeBuild= false;
bool b= e();
i=i0; bTreeBuild= bOld;
return !b;

		

PrintMsg(message); 
throw PegException();

PrintMsg(message); return true;

int i0=i;
bool b= e();
variableName= s.substring(i0,i-i0);
return b;

int i0=i;
if i<length(s) {v= ExtractBitsAsInt(s[i],3,5);++i;return true;}
else           {return false;}

TreeState t=SaveTreeState();
AddTreeNode(...)
bool b= e();
if !b  {RestoreTreeState(savedState);}
return b;

TreeState t=SaveTreeState();
AddTreeNode(..)
bool b= e();
if !b {RestoreTreeState(savedState);}
else {TryReplaceByChildWithoutSibling();}
return b;

解析表达式文法映射到 C#1.0

在 C#1.0 中，我们可以将 PEG 运算符 CodePoint,Literal, Charset, Any, FATAL, 和 WARNING 映射到基类中的辅助函数。但是其他 PEG 构造，如 Sequence, Repeat, Peek, Not, Into 和树构建，不能轻易地外包给库模块。整数和的文法

<<Grammar Name="IntSum">>
Sum:    S [0-9]+  ([+-] S [0-9]+)* S 	;
S:	 [ \n\r\t\v]*			;
<</Grammar>>

导致以下 C#1.0 实现（PegCharParser 是一个未显示的基类，包含字段 pos_ 和方法 In 和 OneOfChars）

class InSum_C1 : PegCharParser 
{
	public InSum_C1(string s) : base(s) { }
	public bool Sum()//Sum:    S [0-9]+  (S [+-] S [0-9]+)* S 	;
	{
	    S();
	    //[0-9]+
	    if( !In('0', '9') ){return false;}
	    while (In('0', '9')) ;
	    
	    for(;;){//(S [+-] S [0-9]+)*
	        int pos= pos_;
	        if( S() && OneOfChars('+','-') && S() ){
	            //[0-9]+
	            if( !In('0', '9') ){pos_=pos; break;}
	            while (In('0', '9')) ;
	        }else{
	            pos_= pos; break;
	        }
	    }
	    S();
	    return true;
	}
	bool S()//S:	 [ \n\r\t\v]*			;
	{
	    while (OneOfChars(' ', '\n', '\r', '\t', '\v')) ;
	    return true;
	}
}

要执行文法，我们只需调用上述类的 Sum 方法。但我们不能对这个解决方案感到高兴和满意。与原始文法规则相比，上述类 InSum_C1 中的 Sum 方法庞大，并且其循环和辅助变量的使用相当令人困惑。但这也许是 C#1.0 中最好的可能。许多传统解析器生成器甚至会产生更糟糕的代码。

解析表达式文法映射到 C#3.0

PEG 运算符，如 Sequence, Repeat, Into, Tree Build, Peek 和 Not，可以被视为接受函数作为参数的运算符或函数。在 C# 中，这映射到一个带有委托参数的方法。例如，Peg Sequence 运算符可以实现为一个接口为 public bool And(Matcher pegSequence); 的函数，其中 Matcher 是以下委托 public delegate bool Matcher();。

在较旧的 C# 版本中，将函数作为参数传递需要一些代码行，但 C#3.0 改变了这一点。C#3.0 支持 lambda 表达式，它们是语法开销非常小的匿名函数。Lambda 表达式使得 PEG 在 C# 中的函数式实现成为可能。PEG 序列 e1 e2 现在可以映射到 C# 术语 And(()=>e1() && e2())。()=>e1()&& e2() 看起来像一个普通的表达式，但实际上是一个功能齐全的函数，具有零参数（因此 ()=>）和函数体 {return e1() && e2();}。有了这个功能，整数求和的文法

<<Grammar Name="IntSum">>
Sum:    S [0-9]+  ([+-] S [0-9]+)* S 	;
S:	 [ \n\r\t\v]*			;
<</Grammar>>

导致以下 C#3.0 实现（PegCharParser 是一个未显示的基类，包含方法 And、PlusRepeat、OptRepeat、In 和 OneOfChars）

class IntSum_C3 : PegCharParser
{
   public IntSum_C3(string s) : base(s) { }
   public bool Sum()//Sum:    S [0-9]+  (S [+-] S [0-9]+)* S ;
   {
      return 
         And(()=>

            S()
         && PlusRepeat(()=>In('0','9'))
         && OptRepeat(()=> S() && OneOfChars('+','-') && S() && PlusRepeat(()=>In('0','9')))
	 && S());
   }
   public bool S()//S:	 [ \n\r\t\v]*			;
   {
      return OptRepeat(()=>OneOfChars(' ', '\n', '\r', '\t', '\v'));
   }
}

与 C#1.0 实现相比，这个解析器类是一个巨大的改进。我们消除了所有循环和辅助变量。正确性（与文法规则的一致性）也更容易检查。方法 And、PlusRepeat、OptRepeat、In 和 OneOfChars 都在 PegCharParser 和 PegByteParser 基类中实现。

下表显示了本文提供的基本库中可用的大多数 PEG 方法。

表达式文法示例

以下示例展示了 PegGrammar 类在所有支持用例中的用法

1. 仅识别：结果只有匹配或不匹配，如果出现不匹配则会发出错误消息。
2. 构建物理解析树：结果是一个物理树。
3. 直接求值：解析时执行语义动作。
4. 构建树，解释树：遍历并求值生成的树。

JSON 检查器（仅识别）

JSON (JavaScript Object Notation) [5][6] 是一种适用于序列化/反序列化程序数据的交换格式。与 XML 相比，它轻量级，因此是解析技术的一个很好的测试候选者。此处介绍的 JSON 检查器在文件不符合 JSON 文法时会给出错误消息和错误位置。以下 PEG 文法是 json_check 的基础。

<<Grammar Name="json_check" 
	  encoding_class="unicode"  encoding_detection="FirstCharIsAscii"
	  reference="www.ietf.org/rfc/rfc4627.txt">>
[1]json_text:		S top_element expect_file_end			;
[2]expect_file_end:	!./ WARNING<"non-json stuff before end of file">;
[3]top_element:		object / array  /
			FATAL<"json file must start with '{' or '['">	;
[4]object:  		'{' S (&'}'/members)  @'}' S		;
[5]members: 		pair S (',' S pair S)*				;	
[6]pair:		@string S @':' S value				;
[7]array:  		'[' S (&']'/elements)  @']' S		;
[8]elements: 		value S (','S  value S)*			;
[9]value:    		@(string / number / object / 
				array / 'true' / 'false' / 'null')	;
[10]string:	 	'"' char* @'"'					;
[11]char:  		escape / !(["\\]/control_chars)unicode_char	;
[12]escape:		'\\' ( ["\\/bfnrt] / 
			'u' ([0-9A-Fa-f]{4}/FATAL<"4 hex digits expected">)/
			     FATAL<"illegal escape">);
[13]number:		'-'? int frac? exp?				;
[14]int:		'0'/ [1-9][0-9]*				;
[15]frac:		'.' [0-9]+					;
[16]exp:		[eE] [-+] [0-9]+				;
[17]control_chars:	[#x0-#x1F]					;
[18]unicode_char:	[#x0-#xFFFF]					;
[19]S:  		[ \t\r\n]*					;


<</Grammar>>

上述文法到 C#3.0 的转换是直接的，并生成以下代码（仅复制了前 4 条规则的转换）。

public bool json_text()    
	{return And(()=>    S() && top_element() && expect_file_end() );}
public bool expect_file_end()  
{ return   
      Not(()=> Any() )
   || Warning("non-json stuff before end of file");
}
public bool top_element()    
{ return   
      @object()
   || array()
   || Fatal("json file must start with '{' or '['");
}
public bool @object()    
{
   return And(()=>  
     Char('{')
  && S()
  && (    Peek(()=> Char('}') ) || members())
  && (    Char('}') || Fatal("<<'}'>> expected"))
  && S() );
}

JSON 树（构建树）

通过对 JSON 检查器文法进行一些修改，我们得到了一个为 JSON 文件生成物理树的文法。为了使 JSON 值 true、false、null 具有唯一的节点，我们添加了相应的规则。此外，我们添加了一条匹配字符串内容（不带引号的字符串）的规则。这给了我们以下文法：

<<Grammar Name="json_tree" 
	  encoding_class="unicode"  encoding_detection="FirstCharIsAscii"
	  reference="www.ietf.org/rfc/rfc4627.txt">>
[1]^^json_text:		(object / array)				;
[2]^^object:  		S '{' S (&'}'/members) S @'}' S			;
[3]members: 		pair S (',' S @pair S)*				;	
[4]^^pair:		@string S ':' S value				;
[5]^^array:  		S '[' S (&']'/elements) S @']' S		;
[6]elements: 		value S (','S  @value S)*			;
[7]value:    		@(string / number / object / 
				array / true / false / null)		;
[8]string:	 	'"' string_content '"'				;
[9]^^string_content: ( '\\' 
                           ( 'u'([0-9A-Fa-f]{4}/FATAL<"4 hex digits expected">)
                           / ["\\/bfnrt]/FATAL<"illegal escape"> 
                           ) 
                        / [#x20-#x21#x23-#xFFFF]
                        )*	;
[10]^^number:        '-'? '0'/ [1-9][0-9]* ('.' [0-9]+)? ([eE] [-+] [0-9]+)?;
[11]S:  		[ \t\r\n]*					;
[12]^^true:		'true'						;
[13]^^false:		'false'						;
[14]^^null:		'null'						;


<</Grammar>>

下表左侧显示了 JSON 输入文件，右侧显示了我们的解析器库的 TreePrint 辅助类生成的树。

{
   "ImageDescription": {
      "Width":  800,
      "Height": 600,
      "Title":  "View from 15th Floor",
      "IDs": [116, 943, 234, 38793]
    }
}

json_text<
  object<
    pair<
      'ImageDescription'
      object<
        pair<'Width' '800'>
        pair<'Height' '600'>

        pair<'Title' 'View from 15th Floor'>
        pair<'IDs' array<'116' '943' '234' '38793'>>
      >
    >
  >
>

基本编码规则（直接求值 + 构建树）

BER（基本编码规则）是 ASN.1 数据编码最常用的格式。像 XML 一样，ASN.1 用于表示分层数据，但与 XML 不同，ASN.1 传统上以紧凑的二进制格式编码，BER 是其中一种格式（尽管是最不紧凑的一种）。互联网标准 SNMP 和 LDAP 是使用 BER 作为编码的 ASN.1 协议的示例。以下用于将 BER 文件读取为树状表示的 PEG 文法使用语义块来存储进一步解析所需的信息。这种使用在解析过程中读取的数据来解码下游数据的动态解析是二进制格式解析的典型特征。下文所示的 BER 文法规则 [4] 表达了以下事实：

1. BER 节点由 Tag Length Value（缩写为 TLV）三元组组成，其中 Value 要么是原始值，要么是 TLV 节点列表。
2. 标签标识元素（类似于 XML 中的开始标签）。
3. Tag 包含一个标志，指示元素是原始的还是构造的。构造意味着有子节点。
4. 长度要么是 Value 的字节长度，要么是特殊模式 0x80（只允许带有子元素的元素），在这种情况下，子序列以两个零字节 (0x0000) 结束。
5. 值要么是一个原始值，要么——如果设置了构造标志——是一个 Tag Length Value 三元组序列。TLV 三元组序列在 TLV 三元组的 Length 部分给出的长度用尽时结束，或者在长度为 0x80 的情况下，在达到结束标记 0x0000 时结束。

<<Grammar Name="BER" encoding_class="binary"
          reference="http://en.wikipedia.org/wiki/Basic_encoding_rules"
          comment="Tree generating BER decoder (minimal version)">>
{
   int tag,length,n,@byte;
   bool init_()     {tag=0;length=0;           return true;}
   bool add_Tag_()  {tag*=128;tag+=n;          return true;}
   bool addLength_(){length*=256;length+=@byte;return true;}
}
[1] ProtocolDataUnit: TLV;
[2] ^^TLV:  init_
     ( &BITS<6,#1> Tag ( #x80  CompositeDelimValue  #0#0 / Length CompositeValue )
     / Tag Length PrimitiveValue
     );
[3] Tag: OneOctetTag / MultiOctetTag / FATAL<"illegal TAG">;
[4] ^^OneOctetTag:   !BITS<1-5,#b11111> BITS<1-5,.,:tag>;
[5] ^^MultiOctetTag: . (&BITS<8,#1> BITS<1-7,.,:n> add_Tag_)* BITS<1-7,.,:n> add_Tag_;
[6] Length :   OneOctetLength / MultiOctetLength 
             / FATAL<"illegal LENGTH">;
[7] ^^OneOctetLength: &BITS<8,#0> BITS<1-7,.,:length>;
[8]^^MultiOctetLength: &BITS<8,#1> BITS<1-7,.,:n> ( .:byte addLength_){:n};
[9]^^PrimitiveValue: .{:length} / FATAL<"BER input ends before VALUE ends">;
[10]^^CompositeDelimValue: (!(#0#0) TLV)*;
[11]^^CompositeValue
{
     int len;
     PegBegEnd begEnd;
     bool save_()  {len= length;return true;}
     bool at_end_(){return len<=0;}
     bool decr_()  {len-= begEnd.posEnd_-begEnd.posBeg_;return len>=0;} 
}
	:  save_ 
           (!at_end_ TLV:begEnd 
                (decr_/FATAL<"illegal length">))*;


<</Grammar>>

科学计算器（构建树 + 求值树）

这个计算器支持基本的算术运算 + - * /，内置的单参数函数如 'sin'、'cos' 等，以及变量赋值。计算器期望每行一个表达式和赋值。它作为一个两步解释器工作，首先构建一个树，然后评估该树。这个计算器的 PEG 语法可以通过 PEG Grammar Explorer 附带的解析器生成器转换为 PEG 解析器。求值器必须手动编写。它的工作原理是遍历树并在访问节点时评估结果。

计算器的文法是

<<Grammar Name="calc0_tree">>
[1]^^Calc:  ((^'print' / Assign / Sum) 
            ([\r\n]/!./FATAL<"end of line expected">)
            [ \r\n\t\v]* )+ 
            (!./FATAL<"not recognized">); 
[2]^Assign:S ident S '=' S Sum;           
[3]^Sum:   Prod  (^[+-] S @Prod)*;
[4]^Prod:  Value (^[*/] S @Value)*;  
[5] Value: (Number/'('S Sum @')'S/Call/ident) S;
[6]^Call:   ident S '(' @Sum @')' S;
[7]^Number:[0-9]+ ('.' [0-9]+)?([eE][+-][0-9]+)?;
[8]^ident: [A-Za-z_][A-Za-z_0-9]*;
[9] S:	    [ \t\v]*;
<</Grammar>>

PEG 解析器生成器

使用 PEG 实现的 PEG 生成器

库类 PegCharParser 和 PegByteParser 旨在手动构建 PEG 解析器。但无论如何，强烈建议在实现之前先在纸上写出文法。我编写了一个小型解析器生成器（使用 PegCharParser），它将“纸上”的 Peg 文法转换为 C# 程序。当前版本的 PEG 解析器生成器只生成 C# 解析器。它针对大型字符集和大量字面备选项进行了优化。未来版本将生成 C/C++ 和其他语言的源代码，并进一步支持调试、跟踪和直接执行文法，而无需将其转换为宿主语言。但即使是当前版本的 PEG 解析器生成器也相当有用。

在 表达式文法示例 一章中介绍的所有示例都是用它生成的。PEG 解析器生成器是一个生成语法树的 PEG 解析器示例。它将 PEG 文法作为输入，验证生成的语法树，然后编写一组 C# 代码文件，这些文件实现了 PEG 文法描述的解析器。

PEG 解析器生成器文法

本文附带的 PEG 解析器生成器期望一组按照 解析表达式文法基础 一章描述编写的文法规则。这些规则必须以头部开头，并以尾部结束，如以下 PEG 文法中所述：

<<Grammar Name="PegGrammarParser">>
peg_module:              peg_head peg_specification peg_tail;
peg_head:                S '<<Grammar'\i B S  attribute+ '>>';
attribute:               attribute_key S '=' S attribute_value S;
attribute_key:           ident;
attribute_value:         "attribute value in single or double quotes";
peg_specification:       toplevel_semantic_blocks peg_rules;
toplevel_semantic_blocks:semantic_block*;
semantic_block:          named_semantic_block / anonymous_semantic_block;
named_semantic_block:    sem_block_name S anonymous_semantic_block;
anonymous_semantic_block:'{' semantic_block_content '}' S;
peg_rules:               S peg_rule+;
peg_rule:                lhs_of_rule ':'S  rhs_of_rule ';' S;
lhs_of_rule:             rule_id? tree_or_ast? create_spec? 
                         rule_name_and_params 
                          (semantic_block/using_sem_block)?;
rule_id:                 (![A-Za-z_0-9^] .)* [0-9]+ (![A-Za-z_0-9^] .)*;
tree_or_ast:             '^^'/'^';
create_spec:             'CREATE' S '<' create_method S '>' S;
create_method:           ident;
ident:                   [A-Za-z_][A-Za-z_0-9]*;
rhs_of_rule:             "right hand side of rule as described in 
                                %22#Parsing" expression="" grammars="" basics"="">Parsing Expression Grammars Basics";
semantic_block_content:  "semantic block content as described in 
                                "%22#Parsing" expression="" grammars="" basics"="">Parsing Expression Grammars Basics";
peg_tail:   '<</GRAMMAR'\i; S '>>';

<</Grammar>>

文法的头部包含 HTML/XML 风格的属性，用于确定生成的 C# 文件的名称和输入文件属性。C# 代码生成器使用以下属性：

所有其他属性均视为注释。以下示例标头中的属性 reference

<<Grammar Name="json_check" 
	  encoding_class="unicode"  encoding_detection="FirstCharIsAscii"
	  reference="www.ietf.org/rfc/rfc4627.txt">>

被视为注释。

PEG 解析器生成器对语义块的处理

语义块被转换为局部类。语义块中的代码必须是类体中预期的 C# 源代码，除了可以省略访问关键字。解析器生成器在必要时预置一个 internal 访问关键字。顶级语义块的处理方式与局部语义块不同。

顶层语义块在文法的构造函数中创建，而局部语义块在每次调用关联规则方法时创建。在局部语义块中无需定义构造函数，因为解析器生成器会创建一个带有一个参数的构造函数，该参数是对文法类的引用。以下示例展示了一个包含顶层和局部语义块的文法片段及其到 C# 代码的转换。

<<Grammar Name="calc0_direct">>
Top{ // semantic top level block 
  double result;
  bool print_(){Console.WriteLine("{0}",result);return true;}
}
...
Number
{ //local semantic block 
	string sNumber;
	bool store_(){double.TryParse(sNumber,out result);return true;}
} :  ([0-9]+ ('.' [0-9]+)?):sNumber store_	;

这些语义块将被转换为以下 C# 源代码：

class calc0_direct : PegCharParser 
{
   class Top{ // semantic top level block 
      internal double result;
      internal bool print_(){Console.WriteLine("{0}",result);return true;}
   }
   Top top;

   #region Constructors
   public calc0_direct(): base(){ top= new Top();}
   public calc0_direct(string src,TextWriter FerrOut): base(src,FerrOut){top= new Top();}
   #endregion Constructors
  ...
  class _Number{ //local semantic block  
	internal string sNumber;
	internal bool store_(){double.TryParse(sNumber,out parent_.top.result);return true;}
        internal _Number(calc0_direct grammarClass){parent_ = grammarClass; }
        calc0_direct parent_;
   }
        public bool Number()    
        {
             var _sem= new _Number(this);
	...
}

通常，多个文法规则必须使用相同的局部语义块。为了避免代码重复，解析器生成器支持 using SemanticBlockName 子句。名为 SemanticBlockName 的语义块应该在第一个文法规则之前、与顶层语义块定义在同一位置进行定义。但由于此类块在规则的 using 子句中被引用，因此它被视为局部语义块。

局部语义块也支持析构函数。析构函数被转换为 IDispose 接口，析构函数代码被放置到相应的 Dispose() 函数中。由解析器生成器生成的文法规则函数将被包含在一个 using 块中。这使得即使在存在异常的情况下，也能在规则结束时执行清理代码。以下示例取自 Python 2.5.2 示例解析器。

Line_join_sem_{
      bool prev_;
      Line_join_sem_ (){set_implicit_line_joining_(true,out prev_);}
      ~Line_join_sem_(){set_implicit_line_joining_(prev_);}
}
...
[8] parenth_form:         '(' parenth_form_content @')' S;
[9] parenth_form_content 
    using Line_join_sem_:   S expression_list?;
...
[17]^^generator_expression: '(' generator_expression_content @')' S;
[18]generator_expression_content
    using Line_join_sem_:   S expression genexpr_for;

Line_join_sem 语义块开启和关闭 Python 的隐式行连接（Python 是面向行的，但允许在括号中的构造内换行，例如 (...) {...) [...]。上述文法片段的 Line_join_sem 语义块和规则 [8] 被翻译为：

class Line_join_sem_ : IDisposable{
   bool prev_;
   internal Line_join_sem_(python_2_5_2_i parent)
   { 
      parent_= parent; 
      parent_._top.set_implicit_line_joining_(true,out prev_);
   }
   python_2_5_2_i parent_;
   public void Dispose(){parent_._top.set_implicit_line_joining_(prev_);}
}
public bool parenth_form_content()    /*[9]   parenth_form_content 
                                              using Line_join_sem_:    S expression_list?;*/
{
    using(var _sem= new Line_join_sem_(this)){
       return And(()=>    S() && Option(()=> expression_list() ) 
     );            
}

透视解析表达式文法

解析表达式文法缩小了形式文法与在函数式或命令式编程语言中实现文法之间的语义鸿沟。因此，PEG 特别适用于手动编写的解析器，以及将文法非常紧密地集成到编程语言中的尝试。如 [1] 所述，构成 PEG 框架的元素并非全新，而是手动实现解析器时众所周知且常用的技术。使 PEG 框架独一无二的是基本元素的选取和组合，即：

当回溯频繁发生时，PEG 文法可能会导致严重的性能损失。这就是为什么一些 PEG 工具（所谓的 packrat 解析器）会记忆已经读取的输入和相关规则。可以证明，适当的记忆化即使在发生回溯和无限前瞻时也能保证线性解析时间。另一方面，记忆化（保存已访问路径的信息）有其自身的开销，并且在一般情况下会影响性能。限制回溯的更好方法是重写文法，以减少回溯。这将在下一章中展示。

PEG 文法的基础思想并非全新，其中许多思想经常用于手动构建解析器。只有在支持和鼓励回溯以及无限前瞻方面，PEG 才与大多数早期解析技术有所不同。无限前瞻和回溯的最简单实现要求在解析开始之前将输入文件读取到内部内存中。这在现在不是问题，但在内存资源稀缺的早期是不可接受的。

解析表达式文法调优

一组文法规则可以识别给定的语言。但是相同的语言可以用许多不同的文法来描述，即使在相同的形式主义（例如 PEG 文法）中也是如此。文法修改可用于实现以下目标：

[1]^^string: 
  '"' ('\\' ["'bfnrt\\])/!'"' .)* '"';

[1]^^string:   '"'(escs/chars)* '"';
[3] ^^escs:  ('\\' ["'bfnrt\\])*;
[4] ^^chars: (!["\\] .)*;

'/*'  (!'*/' . )*  
('*/' / 
 FATAL<"comment not closed before end"> 
);

'/*'  
( (!'*/' .)*  '*/' 
/ FATAL<"comment not closed before end"> 

);

[10]string:   '"' char* '"'	;
[11]char: escape 
      / !(["\\]/control)unicode 
      /!'"' FATAL<"illegal character">;
[12]escape:   '\\' ["\\/bfnrt];
[17]control   [#x0-#x1F];
[18]unicode:  [#x0-#xFFFFF];

[10]string: 
'"' 
( '\\'["\\/bfnrt] 
/ [#0x20-#0x21#0x23-#0x5B#0x5D-#0xFFFF] 
/ !'"' FATAL<"illegal character">

     )*
'"';

[1] if_stat:   
   'if' S '('expr')' stat /
   'if' S '('expr')' stat 'else' S stat;

[1] if_stat: 
   'if' S '(' expr ')' stat 
             ('else' S stat)?;

备注
[1] 通过语法分组文法元素可以获得更具信息性的树节点，从而简化后处理。在上述示例中，通过将连续的非转义字符分组为一个语法单元来改进对字符串内容的访问。
[2] 错误消息提供的源引用位置很重要。在 C 语言注释未闭合直到输入结束的示例中，错误消息应在注释开始处给出。
[3] 减少调用深度意味着函数调用内联，因为在我们的 PEG 实现中，每个规则都对应一个函数调用。这种转换只应在热点进行，否则会失去文法的表达性。此外，一些激进的内联编译器可能会为您进行这种内联。减少调用深度可能值得商榷，但左因子化肯定不是。它不仅提高了性能，而且还消除了潜在的破坏性回溯。当将语义动作嵌入到 PEG 解析器中时，在许多情况下不应再发生回溯，因为撤销语义动作可能很繁琐。

PEG 解析与其他解析技术的比较

目前使用的大多数解析策略都基于上下文无关文法的概念。（接下来的 50 行解释紧密遵循维基百科上关于上下文无关文法的材料 [3]）上下文无关文法由一组规则组成，类似于 PEG 解析器的一组规则。但上下文无关文法与 PEG 文法的解释方式大相径庭。主要区别在于上下文无关文法是非确定性的，这意味着

1. 上下文无关文法中的备选项可以任意选择
2. 非终结符可以任意顺序替换（替换意味着用非终结符的定义替换规则右侧的非终结符）。通过从起始规则开始，并以所有可能的顺序选择备选项和替换非终结符，我们可以生成由文法描述的所有字符串（也称为由文法描述的语言）。

S : 'a' S 'b' | 'ab'; 

我们可以生成以下语言字符串：

ab, aabb, aaabbb,aaaabbbb,...

使用 PEG 我们无法生成语言，我们只能识别输入字符串。相同的文法被解释为 PEG 文法

S: 'a' S 'b' / 'ab';

将识别以下任何输入字符串：

ab
aabb
aaabbb
aaaabbbb

事实证明，上下文无关文法的非确定性特性，虽然对于生成语言来说必不可少，但在识别输入字符串时可能会成为问题。如果一个输入字符串可以通过两种不同的方式解析，我们就会遇到歧义问题，这是解析器必须避免的。非确定性的另一个结果是，上下文无关的输入字符串识别器（解析器）必须选择一种策略来替换规则右侧的非终结符。要识别输入字符串

1+1+a

S: S '+' S | '1' | 'a';

S '+' S -> 
(S '+' S)  '+' S -> 
(('1') '+' S) '+' S -> 
(('1') '+' ('1')) '+' S -> 
(('1') '+' ('1')) '+' ('a')

这被称为最左推导。或者我们可以使用以下替换：

S '+' S -> 
S '+' (S  '+' S) -> 

S '+' (S '+' ('a')) -> 
S '+' (('1') '+' ('a')) -> 
('1') '+' (('1') '+' ('a'));

这被称为最右推导。最左推导解析策略称为 LL，而最右推导解析策略称为 LR（LL 和 LR 中的第一个 L 代表“从左解析输入字符串”，但谁会尝试从右解析呢？）。大多数使用的解析器要么是 LL，要么是 LR 解析器。此外，用于 LL 解析器和 LR 解析器的文法必须遵守不同的规则。LL 解析器的文法绝不能使用左递归规则，而 LR 解析器的文法则优先于右递归规则使用直接左递归规则。例如，C# 文法就是为 LR 解析器编写的。因此，局部变量列表的规则是：

local-variable-declarators: 
  local-variable-declarator 
| local-variable-declarators ',' local-variable-declarator;

如果我们要将此文法与 LL 解析器一起使用，那么我们必须将此规则重写为：

local-variable-declarators: 
   local-variable-declarator  (',' local-variable-declarator)*;

回到原始上下文无关规则

S: S '+' S | '1' | 'a';

并将其解释为 PEG 规则

S: S '+' S / '1' / 'a';

我们不必进行替换或/和选择解析策略来识别输入字符串

1+1+a

我们只需遵循 PEG 的执行规则，它将转换为以下步骤：

1. 将输入位置设置为输入字符串的起始位置
2. 选择起始规则的第一个备选项（此处为： S '+' S）
3. 将输入与序列 S '+' S 的第一个组件进行匹配
4. 由于第一个组件是非终结符 S，因此调用此非终结符。

这显然会导致无限递归。因此，规则 S: S '+' S / '1' / 'a'; 不是有效的 PEG 规则。但几乎任何上下文无关规则都可以转换为 PEG 规则。上下文无关规则 S: S '+' S | '1' | 'a'; 转换为有效的 PEG 规则：

S: ('1'/'a')('+' S)*;

以下章节之一将展示如何将上下文无关规则转换为 PEG 规则。

下表比较了主流的解析器类型。

上表将 PEG 的通用性和强大性评为“非常高”的原因是 PEG 运算符 & (窥视) 和 ! (非)。实现这些操作并不困难，但大量使用它们会影响解析器性能，早期的解析器作者因为隐含的成本而小心翼翼地避免使用此类功能。

谈到运行时性能，上述解析器策略之间的差异并不那么清晰。LALR(1) 解析器可以非常快。LL(1) 解析器（预测解析器）也是如此。当使用 LL(*) 和 PEG 解析器时，运行时性能取决于文法实际使用的前瞻量。特殊版本的 PEG 解析器（Packrat 解析器）可以保证线性运行时行为（这意味着输入字符串长度加倍只会使解析时间加倍）。

LR 解析器与 LL 或 PEG 解析器之间的一个重要区别是，LR 解析器始终是表驱动的。因此，手动编写的解析器在大多数情况下要么是 LL 解析器，要么是 PEG 解析器。表驱动解析将解析置于一个黑盒中，只允许有限的用户交互。对于一次性的、明确定义的解析任务来说，这不是问题，但如果经常更正/改进和扩展文法，则不理想，因为对于表驱动解析器来说，更改文法意味着完整的表和代码重新生成。

将 LR 文法转换为 PEG 文法

大多数流行编程语言的规范都附带适合 LR 解析器的文法。LL 和 PEG 解析器不能直接使用此类文法，因为它们存在左递归规则。左递归规则在 LL 和 PEG 解析器中是被禁止的，因为它们会导致无限递归。LR 文法的另一个问题是它们经常使用具有相同开头的备选项。这在 PEG 中是合法的，但会导致不必要的回溯。下表显示了从 LR 文法转换为 PEG 文法时必要的文法转换。

// s1, s2 are terms which are not
//left recursive
// and not empty
A: A t1 | A t2 | s1 | s2;

A: (s1 | s2) (t1 | t2)*

A: B t1 | s1 ;
B: A t2 | s3 ; 

// we substitute B by its right hand side
A: (A t2 | s3) t1 | s1; 
//Eliminate immediate left recursion
A: (s3 t1 | s1) (t2 t1)* ...;

A: s1 t1 | s1 t2;

A: s1 (t1 | t2);

以下示例展示了将“C”文法的一部分从 Kernighan 和 Ritchie 的“C”书中描述的 LR 文法转换为 PEG 文法（符号 S 用于表示空白符扫描）。

declarator: pointer? direct_declarator;

declarator: pointer? direct_declarator;

direct_declarator:
   identifier 
| '(' declarator ')' 
| direct_declarator '[' constant_expression? ']'
| direct_declarator '(' parameter_type_list ')'
| direct_declarator '(' identifier_list? ')';

direct_declarator: 
 (identifier / '(' S declarator ')' S)
 (   '[' S constant_expression? ']' S
   / '(' S parameter_type_list ')' S
   / '(' S identifier_list? ')' S
  )*;

pointer: 
   '*' type_qualifier_list?
|  '*' type_qualifier_list? pointer;;

pointer: 
   '*' S type_qualifier_list? pointer?

parameter_type_list: 
   parameter_list 
|  parameter_list ',' '...';

parameter_type_list: 
   parameter_list (',' S '...')?;

type_qualifier_list: 
   type_qualifier
|  type_qualifier_list type_qualifier;

type_qualifier_list: 
   type_qualifier+;

parameter_declaration:
   declaration_specifiers declarator
|  declaration_specifiers abstract_declrator?;

parameter_declaration: 
   declaration_specifiers 
      (declarator / abstract_declarator?);

identifier_list:
   identifier
|  identifier_list ',' identifier;

identifier_list: 
   identifier S 
      (',' S identifier)*;

未来发展

计划中的系列文章包括以下部分：

历史

• 2008年10月：初始版本
• 2008年10月：小幅更新
  • 改进了语义块支持（using 子句，IDispose 接口）
  • 新增示例解析器 Python 2.5.2

参考文献

[1] 解析表达式文法，Bryan Ford，麻省理工学院，2004年1月 [^]
[2] 解析表达式文法，Wikipedia.en [^]
[3] 上下文无关文法，Wikipedia.en [^]
[4] ITU-T X.690: BER、CER 和 DER 规范，国际电信联盟 [^]
[5] RFC 4627: JavaScript 对象表示法 (JSON) 的 application/json 媒体类型 [^]
[6] JSON 简介 [^]