如何构建递归下降解析器
4.00/5 (10投票s)
学习如何实现递归下降解析器，并提供JSON和整数表达式求值器的示例
引言
递归下降解析可能是最常见的解析形式。它是实现手工编写解析器的标准选择。本文旨在教你如何构建它们。
概念化这个混乱的局面
解析被用于无数的软件产品中，它涉及将结构化文本分解成有意义的“短语”，这些“短语”被你的代码用来实现某种功能。具体是什么功能取决于你解析的内容。在我们的示例中，我们有一个JSON解析器，其功能涉及构建一个规范化JSON数据树，以及一个表达式解析器，其功能涉及在运行时评估一个整数表达式并返回结果。
设计阶段：构建语法和规划解析器
实现解析器有几个步骤，从规划到实现。第一步是为你将要解析的内容设计“语法”。使用EBNF或其变体来定义它可能会有所帮助。我使用XBNF（我自己的EBNF变体）来编写语法，但只要它易于理解，你使用什么形式都无关紧要。然后我们将使用这个语法作为我们的设计模板，它将指导我们创建解析器。
我们JSON解析器的语法如下
Json<start>= Object | Array;
Object= "{" [ Field { "," Field } ] "}";
Field= string ":" Value;
Array= "[" [ Value { "," Value } ] "]";
Value<collapsed>= string |
number |
Object |
Array |
Boolean |
null ;
Boolean= true|false;
number= '\-?(0|[1-9][0-9]*)(\.[0-9]+)?([Ee][\+\-]?[0-9]+)?';
string= '"([^\n"\\]|\\([btrnf"\\/]|(u[A-Fa-f]{4})))*"';
true= "true";
false= "false";
null= "null";
lbracket<collapsed>= "[";
rbracket<collapsed>= "]";
lbrace<collapsed>= "{";
rbrace<collapsed>= "}";
colon<collapsed>= ":";
comma<collapsed>= ",";
whitespace<hidden>= '[\n\r\t ]+
同时，我们表达式解析器的语法如下
Term<start,type="int">= Factor { ("+"|"-") Factor };
Factor<type="int">= Unary { ("*"|"/") Unary };
Unary<type="int">= ("+"|"-") Unary | Leaf;
Leaf<type="int">= integer | "(" Term ")";
add="+";
sub="-";
mul="*";
div="/";
lparen="(";
rparen=")";
integer='[0-9]+';
whitespace<hidden>='\s+';
如果你理解EBNF和可能的XBNF，JSON语法应该相当明显。你可以在我之前的任何解析器生成器项目中阅读有关XBNF的信息，所有这些项目都使用XBNF作为输入格式。与我的其他解析器项目不同，我们不会为XBNF语法机器生成代码。我们将再次手动实现它，只需将语法作为指导来帮助我们编写代码。
请注意，上面我用TitleCase名称标记了语法的非终结符元素，用camelCase名称标记了终结符元素。如果你不理解终结符和非终结符，这在这里并不重要。基本上，非终结符由终结符和其他非终结符组成，而终结符仅表示输入流中的单个“平面”词素。非终结符可以分解为它们的组成部分，而终结符是原子/不可分的。同样，你不需要真正理解这部分，但如果你理解了会更好。
有了语法之后，下一步应该是决定是使用词法分析器/扫描器，还是实现无扫描器解析器。使用词法分析器/扫描器可以使解析更容易，但需要额外的手动编写代码或额外的构建步骤来生成扫描器代码。
你可能想知道词法分析器/扫描器到底做什么。简而言之，它接收文本输入流并在其中查找模式。每个不同的模式都关联着一个“符号ID”，它告诉你它是哪种模式（例如，它是一个数字、一个字符串，还是一个左括号或右括号等？）此信息以一系列“令牌”的形式返回，令牌包含符号ID、匹配文本的值以及令牌在输入流中的行、列和位置信息。然后解析器使用这些符号ID来决定接下来要解析什么。解析器并不真正关心令牌值，只关心令牌符号ID。总结一下，值是匹配的字面文本，而符号ID是与该类型文本片段关联的数字“代码”。
我们为什么要使用词法分析器/扫描器？词法分析器/扫描器可以将词法分析和语法分析作为独立步骤分离，从而大大简化解析。如果没有词法分析器/扫描器，这两个步骤会合并到解析例程中，这会使它们变得复杂。
为什么不使用词法分析器/扫描器？词法分析器/扫描器没有上下文信息，因此它们不能根据文本在输入中出现的位置有条件地返回不同的符号。因此，它们的匹配能力不如无扫描器解析器。然而，实际上，这几乎从来不是问题。你很少会遇到需要根据上下文区分终结符的情况。但是，你会在像Python这样的语法中遇到它，因为该语言语法中存在有意义的和无意义的空白。在这些情况下，你可以手动编写一个单独的词法分析器/扫描器，或者简单地将扫描器部分直接集成到解析代码本身中。你可能不想使用它的另一个原因是对于非常简单的语法。
本文提供的代码中包含一个无扫描器的JSON解析器以及一个整数表达式解析器，后者确实使用了词法分析器。我们也可以同样容易地为JSON使用扫描器/词法分析器，但我希望演示这两种技术。
如果你决定使用词法分析器，通常使用像Rolex这样的工具来生成它会比手动编写容易得多。我已将Rolex二进制文件包含在解决方案文件夹中，以便可以从扫描器/词法分析器规范文件重建ExpressionParser项目。
JSON解析器
JSON解析器是一个简单的解析器，它读取JSON输入并将其解析成一个对象模型，使用IDictionary<string, object>表示JSON对象，使用IList<object>表示JSON数组。
表达式解析器
表达式解析器是另一个简单的解析器，它读取整数表达式并计算结果，返回一个整数。解析表达式时要注意的一个问题是运算符优先级。例如，“乘”之类的因子比“加”之类的项具有更高的优先级。我们必须在语法中将这些不同的运算符分开，以强制执行优先级。请注意语法中Term是如何由Factors组成的，而Factor是如何由Unaries组成的，Unaries又是由Leaves组成的。这就是我们建立优先级的方式。如果我们将所有运算符都放在同一个非终结符声明下，那么就没有运算符优先级了。当我们访问下一节中的代码时，这会变得更清楚。
编写这个混乱的程序
为了编写递归下降解析器，我们将为语法中“=”号左侧出现的几乎每个构造都创建一个例程。这些例程将根据需要调用其他例程进行解析。这就是递归下降解析的工作原理。
public sealed class JsonParser : IDisposable
{
const int _TabWidth = 4;
readonly IEnumerator<char> _input;
bool _isEnd;
int _line;
int _column;
long _position;
JsonParser(IEnumerable<char> input)
{
_input = input.GetEnumerator();
_line = 1;
_column = 1;
_position = 0L;
}
bool _NextInput()
{
if (_isEnd)
return false;
if(!_input.MoveNext())
{
_isEnd = true;
return false;
}
++_position;
switch(_input.Current)
{
case '\n':
_column = 1;
++_line;
break;
case '\r':
_column = 1;
break;
case '\t':
_column += _TabWidth;
break;
default:
++_column;
break;
}
return true;
}
public static object Parse(IEnumerable<char> input)
{
if (null == input)
throw new ArgumentNullException("input");
using (var p = new JsonParser(input))
{
if (!p._NextInput())
return null;
// we only accept arrays or objects at the top level
switch (p._input.Current)
{
case '{':
return p._ParseObject();
case '[':
return p._ParseArray();
}
p._ThrowExpecting("Expecting object or array");
}
return null;
}
public void Close()
{
_input.Dispose();
}
void IDisposable.Dispose()
{
Close();
}
// Object= "{" [ Field { "," Field } ] "}";
IDictionary<string,object> _ParseObject()
{
_SkipWhiteSpace();
if ('{' != _input.Current)
_ThrowExpecting("Expecting {");
if (!_NextInput())
_ThrowExpecting("Unterminated object");
var result = new Dictionary<string, object>();
while(!_isEnd && '}' != _input.Current)
{
// Field= string ":" Value;
_SkipWhiteSpace();
var key = _ParseString();
_SkipWhiteSpace();
if (':' != _input.Current)
_ThrowExpecting("Expecting :");
if (!_NextInput())
_ThrowExpecting("Unterminated field");
_SkipWhiteSpace();
result.Add(key, _ParseValue());
_SkipWhiteSpace();
if ('}' == _input.Current)
break;
else if (',' != _input.Current)
_ThrowExpecting("Expecting ,");
if (!_NextInput())
_ThrowExpecting("Unterminated object");
}
if ('}' != _input.Current)
_ThrowExpecting("Unterminated object");
_NextInput();
return result;
}
// Array= "[" [Value { "," Value } ] "]";
IList<object> _ParseArray()
{
_SkipWhiteSpace();
if ('[' != _input.Current)
_ThrowExpecting("Expecting [");
if (!_NextInput())
_ThrowExpecting("Unterminated array");
var result = new List<object>();
while (!_isEnd && ']' != _input.Current)
{
_SkipWhiteSpace();
result.Add(_ParseValue());
_SkipWhiteSpace();
if (']' == _input.Current)
break;
else if (',' != _input.Current)
_ThrowExpecting("Expecting ,");
if (!_NextInput())
_ThrowExpecting("Unterminated array");
}
if (']' != _input.Current)
_ThrowExpecting("Unterminated array");
_NextInput();
return result;
}
// Value<collapsed>= string | number | Object | Array | Boolean | null
object _ParseValue()
{
_SkipWhiteSpace();
switch(_input.Current)
{
case '\"':
return _ParseString();
case '{':
return _ParseObject();
case '[':
return _ParseArray();
case 't':
case 'f':
return _ParseBoolean();
case 'n':
_ParseNull();
return null;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '-':
case '.':
return _ParseNumber();
}
_ThrowExpecting("Unexpected character in JSON value");
return null; // doesn't execute
}
// Boolean = true | false
bool _ParseBoolean()
{
if('t'==_input.Current)
{
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('r' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('u' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('e' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
_NextInput();
return true;
}
if('f'==_input.Current)
{
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('a' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('l' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('s' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('e' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
_NextInput();
return false;
}
_ThrowExpecting("Expecting boolean");
return false; // doesn't execute
}
// null = "null"
void _ParseNull()
{
if ('n' == _input.Current)
{
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('u' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('l' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
if (!_NextInput())
_ThrowExpecting("Unterminated boolean");
if ('l' != _input.Current)
_ThrowExpecting("Unexpected character in boolean");
_NextInput();
return;
}
_ThrowExpecting("Expecting null");
}
// string= '"([^\n"\\]|\\([btrnf"\\/]|(u[A-Fa-f]{4})))*"';
string _ParseString()
{
if (_isEnd || '\"' != _input.Current)
_ThrowExpecting("Expecting \"");
if (!_NextInput())
_ThrowExpecting("Unterminated string");
var sb = new StringBuilder();
while(!_isEnd && '\"'!=_input.Current)
{
if('\n'==_input.Current)
_ThrowExpecting("Unterminated string");
if ('\\' == _input.Current)
{
if (!_NextInput())
_ThrowExpecting("Unterminated string");
switch (_input.Current)
{
case '/':
sb.Append('/');
break;
case '\\':
sb.Append('\\');
break;
case '\"':
sb.Append('\"');
break;
case 'b':
sb.Append('\b');
break;
case 't':
sb.Append('\t');
break;
case 'r':
sb.Append('\r');
break;
case 'n':
sb.Append('\n');
break;
case 'f':
sb.Append('\f');
break;
case 'u':
if (!_NextInput())
_ThrowExpecting("Unterminated string");
int ch = 0;
ch <<= 4;
ch |= _FromHexChar(_input.Current);
if (!_NextInput())
_ThrowExpecting("Unterminated string");
ch <<= 4;
ch |= _FromHexChar(_input.Current);
if (!_NextInput())
_ThrowExpecting("Unterminated string");
ch <<= 4;
ch |= _FromHexChar(_input.Current);
if (!_NextInput())
_ThrowExpecting("Unterminated string");
ch <<= 4;
ch |= _FromHexChar(_input.Current);
sb.Append((char)ch);
break;
default:
_ThrowExpecting("Unrecognized escape sequence");
break;
}
}
else
sb.Append(_input.Current);
_NextInput();
}
if (_isEnd || '\"' != _input.Current)
_ThrowExpecting("Unterminated string");
_NextInput();
return sb.ToString();
}
// number= '\-?(0|[1-9][0-9]*)(\.[0-9]+)?([Ee][\+\-]?[0-9]+)?';
double _ParseNumber()
{
if (_isEnd)
_ThrowExpecting("Expecting number");
var sb = new StringBuilder();
if ('-' == _input.Current)
{
sb.Append(_input.Current);
if (!_NextInput())
_ThrowExpecting("Unterminated number");
}
if (char.IsDigit(_input.Current))
{
sb.Append(_ParseDigits());
}
if ('.' == _input.Current)
{
sb.Append('.');
if (!_NextInput())
_ThrowExpecting("Unterminated number");
sb.Append(_ParseDigits());
}
if ('E' == _input.Current || 'e' == _input.Current)
{
sb.Append(_input.Current);
if (!_NextInput())
_ThrowExpecting("Unterminated number");
if ('-' == _input.Current || '+' == _input.Current)
{
sb.Append(_input.Current);
if (!_NextInput())
_ThrowExpecting("Unterminated number");
}
sb.Append(_ParseDigits());
}
return double.Parse(sb.ToString());
}
// [0-9]+
string _ParseDigits()
{
if (_isEnd || !char.IsDigit(_input.Current))
_ThrowExpecting("Expecting digits");
var sb = new StringBuilder();
sb.Append(_input.Current);
while (_NextInput() && char.IsDigit(_input.Current))
sb.Append(_input.Current);
return sb.ToString();
}
void _ThrowExpecting(string msg)
{
msg = string.Concat(msg,string.Format(" at line {0},
column {1}, position {2}", _line, _column, _position));
throw new Exception(msg);
}
byte _FromHexChar(char hex)
{
if (':' > hex && '/' < hex)
return (byte)(hex - '0');
if ('G' > hex && '@' < hex)
return (byte)(hex - '7'); // 'A'-10
if ('g' > hex && '`' < hex)
return (byte)(hex - 'W'); // 'a'-10
_ThrowExpecting("The value was not hex");
return 0; // doesn't execute
}
// whitespace<hidden>= '[\n\r\t ]+
void _SkipWhiteSpace()
{
while (!_isEnd && '\n'==_input.Current ||
'\r'==_input.Current || '\t'==_input.Current || ' '==_input.Current)
_NextInput();
}
}
这里我用粗体标出了所有处理语法组件解析的方法。其余代码是支持代码。关于支持代码，必须进行一些簿记以跟踪何时到达输入末尾，并记录行、列和位置信息。我们还有一个报告错误的帮助器，一个跳过空白的帮助器，以及一个将十六进制字符串转换为byte值的帮助器。注意我们有一个帮助器_NextInput()，它跟踪行、列和位置信息，并确定我们是否到达输入末尾。这很重要。当我们抛出错误时，我们需要报告错误在输入中发生的位置，因此我们必须在推进输入时始终更新我们的行、列和位置信息。我们还必须知道何时到达末尾，这样我们就不会在到达末尾后尝试读取更多输入。如果没有这个，当我们移动到输入末尾并尝试继续解析时，就会抛出异常。
静态Parse()方法通过使用指定的输入准备一个新的解析器实例来启动我们的解析，然后根据光标下的字符委托给适当的_ParseXXXX()方法。
在我们的_ParseXXXX()方法内部，我们处理该方法所代表的相应语法结构，例如_ParseObject()将解析JSON对象{ ... }，而_ParseArray()将解析JSON数组[ ... ]。
这有一些棘手的地方，尤其是解析字符串和数字，这会变得有些复杂。这是扫描器/词法分析器可以使它更容易的地方，但我们在这个解析器中没有使用它。否则，解析非终结符JSON元素只是委托给适当的方法，并跳过可能出现的空白。词法分析器/扫描器对于忽略空白和注释之类的东西特别有用，但是，我们在这里没有使用它，所以我们必须手动跳过空白（JSON中没有注释）。
请注意，每次我们解析某些内容时，每个方法都以检查*当前*输入字符开始，并在解析完我们刚刚解析的构造的末尾后离开该方法。这很重要，并且对于每个例程都必须保持一致。
现在我们将访问使用词法分析器/扫描器的ExpressionParser代码
public sealed class ExpressionParser : IDisposable
{
IEnumerator<Token> _input;
bool _isEnd;
void _ThrowExpecting(string msg)
{
msg = string.Concat(msg, string.Format(" at line {0},
column {1}, position {2}", _input.Current.Line,
_input.Current.Column, _input.Current.Position));
throw new Exception(msg);
}
ExpressionParser(IEnumerator<Token> input)
{
_input = input;
}
bool _NextInput()
{
if(!_input.MoveNext())
{
_isEnd = true;
return false;
}
return true;
}
public static int Parse(IEnumerable<char> input)
{
using (var p = new ExpressionParser(new ExpressionTokenizer(input).GetEnumerator()))
{
if (!p._NextInput())
p._ThrowExpecting("Empty expression");
return p._ParseTerm();
}
}
public void Close()
{
_input.Dispose();
}
void IDisposable.Dispose()
{
Close();
}
// Term<start,type="int">= Factor { ("+"|"-") Factor };
int _ParseTerm()
{
int result = _ParseFactor();
var done = false;
while (!_isEnd && !done)
{
switch (_input.Current.SymbolId)
{
case ExpressionTokenizer.add:
if (!_NextInput())
_ThrowExpecting("Unterminated expression");
result += _ParseFactor();
break;
case ExpressionTokenizer.sub:
if (!_NextInput())
_ThrowExpecting("Unterminated expression");
result -= _ParseFactor();
break;
default:
done = true;
break;
}
}
return result;
}
// Factor<type="int">= Unary { ("*"|"/") Unary };
int _ParseFactor()
{
int result = _ParseUnary();
var done = false;
while (!_isEnd && !done)
{
switch (_input.Current.SymbolId)
{
case ExpressionTokenizer.mul:
if (!_NextInput())
_ThrowExpecting("Unterminated expression");
result *= _ParseUnary();
break;
case ExpressionTokenizer.div:
if (!_NextInput())
_ThrowExpecting("Unterminated expression");
result /= _ParseUnary();
break;
default:
done = true;
break;
}
}
return result;
}
// Unary<type="int">= ("+"|"-") Unary | Leaf;
int _ParseUnary()
{
switch(_input.Current.SymbolId)
{
case ExpressionTokenizer.add:
if(!_NextInput())
_ThrowExpecting("Unterminated expression");
return _ParseUnary();
case ExpressionTokenizer.sub:
if(!_NextInput())
_ThrowExpecting("Unterminated expression");
return -_ParseUnary();
}
return _ParseLeaf();
}
// Leaf<type="int">= integer | "(" Term ")";
int _ParseLeaf()
{
int result;
switch(_input.Current.SymbolId)
{
case ExpressionTokenizer.integer:
result= int.Parse(_input.Current.Value);
_NextInput();
return result;
case ExpressionTokenizer.lparen:
if (!_NextInput())
_ThrowExpecting("Unterminated expression");
result = _ParseTerm();
if (ExpressionTokenizer.rparen != _input.Current.SymbolId)
_ThrowExpecting("Unterminated expression");
_NextInput();
return result;
}
_ThrowExpecting("Invalid token in expression");
return 0; // doesn't execute
}
}
在这里，我们使用词法分析器（上面粗体强调）来解析我们的表达式。看看我们的Parse()方法是如何创建词法分析器并通过将光标移动到第一个标记来“启动”它的。这与我们之前创建的无扫描器JSON的Parse()方法略有不同，但总体概念相同，只是我们处理的是标记而不是字符。词法分析器的API因你用于生成它的工具而异。此示例使用Rolex工具和词法分析器/扫描器API，它通过IEnumerable<Token>报告标记。如果你使用GPLEX之类的工具，读取标记的代码会看起来不同，但主要概念是相同的。
在我们的_ParseXXXX()方法中，你会发现我们经常对_input.Current.SymbolId进行switch操作。还记得我说过扫描器/词法分析器会将符号ID与文本片段关联起来吗？这个符号ID就是由上述SymbolId成员报告的。很多时候，我们并不关心实际的文本是什么——它通常可以从符号ID推断出来。例如，我们知道表示“add”的符号ID的文本总是“+”。Rolex将其词法分析器类上的每个SymbolId都设置为常量。我们在switch语句中使用这些常量来决定采取什么行动。
创建这些方法的流程是获取适当的语法定义，并基本“合成”其代码。我说“合成”是因为代码非常规则，理论上可以生成，但生成代码虽然可能，却会变得复杂。有一种非常常用且不那么复杂的方法可以在不进行代码合成的情况下机器生成解析器代码，它使用比下面更机械化、可能更“原始”的技术，但这超出了本文的范围。话虽如此，我们是手动创建这些代码的。对于人类来说相对容易，但对于计算机来说却很复杂。
基本上，当我们看到...|...时，这是一个交替，所以我们找出它是哪个替代方案（通常基于光标下的第一个令牌）并进行适当的解析。
当我们看到{ ... }（零个或多个）或{ ... }+（一个或多个）时，这表示一个循环。我们通常为此使用while循环。否则，当我们看到一个非终结符元素，例如Factor时，我们就会调用_ParseFactor()。
如果我们看到[ ... ]，这表示一个可选表达式。我们将其视为...|（一个没有最终替代方案的交替）。它基本上只是语法糖。
最后，当然，当我们看到终结符或非终结符时，我们要么解析终结符，要么委托给与非终结符对应的_ParseXXXX()方法。例如，当我们在语法定义中看到Factor时，我们知道要调用_ParseFactor()。
关于表达式的一点特别之处在于负数。请注意，我们的整数只是正数。表示像-10这样的东西是一个一元表达式，而不是一个叶子。-负责一元表达式。请参阅语法。此外，这允许使用+，它基本上是一个无操作——它什么也不做，但为了完整性而包含在内，因此+10是合法的。因为Unary会调用自身（请参阅语法），所以这允许像C#一样使用---10和+-+10。
使用这些解析器很简单
Console.WriteLine(ExpressionParser.Parse("(1+1+1)+5*2*2")); // reports 23
var json = @"{ ""foo"":""bar"", ""fubar"":1.2, ""fubaz"": [ {},true,false,null] }";
var j = JsonParser.Parse(json);
var d = j as IDictionary<string, object>;
Console.WriteLine(d.Count); // reports 3
有关生成Rolex词法分析器的更多信息，请参阅本文。
历史
- 2020年3月14日 - 初次提交