在深入探讨LALR(1)解析器之前,假设读者对LL(1)解析有一定的了解。如果需要深入了解LL(1)解析,可以参考相关的教程。此外,对PCK有一定的了解也是必要的。LALR(1)解析是一种与LL(1)解析相反的工作方式,它从叶子节点到根节点构建语法树,使用输入的标记来引导解析过程。与之相对,LL(1)解析器从根节点到叶子节点构建语法树,使用语法规则来引导解析。在LALR(1)/LR的情况下,输入决定了使用哪个规则,解析器将其与语法进行比较。在LL(1)/LL的情况下,语法规则告诉使用哪个规则,解析器将其与输入进行比较。
LALR(1)解析器的工作原理可能会让人感到困惑,尤其是对于初学者来说。幸运的是,了解LALR(1)算法的具体细节并不是使用它的先决条件。如果不是这样,大多数人可能会感到无从下手。尽管如此,还是需要从某个地方开始。以下是LALR(1)解析与LL(1)解析的比较:
LALR(1)解析器可以解析更大范围的上下文无关文法(CFG)。在识别能力方面,它比LL(1)解析器更强大。LALR(1)解析器可以是左递归或右递归。甚至鼓励使用左递归,因为它不会占用太多的栈空间。使用LALR(1)解析器时,不需要事先对语法进行因式分解。
然而,LALR(1)解析器也有一些缺点。它的学习曲线比使用LL(1)解析器稍微陡峭一些,因为它更复杂。生成表格的算法对于普通人来说几乎是无法理解的,无论有多少注释。它不适用于自然的树遍历。相反,它从底部向上构建树。由于算法的工作方式,错误识别不如LL(1)解析器那样及时。
基于以上分析,建议是:如果可能的话,使用LL(1)解析器;如果需要额外的解析能力,那么只使用LALR(1)解析器。PCK提供了这两种解析器。其他使用LALR(1)算法的解析器生成器包括YACC和Gold Parser。
要使用代码,首先需要构建代码。将pckw(以及支持的程序集)添加到路径中,然后开始。创建一个XBNF语法文件:
expr = expr "+" term | term;
term = term "*" factor | factor;
factor = "(" expr ")" | int;
add = "+";
mul = "*";
lparen = "(";
rparen = ")";
int = '[0-9]+';
然后将其转换为PCK规范:
pckw xlt expr.xbnf expr.pck
接下来,使用PCK规范生成一个标记器/词法分析器:
pckw fagen expr.pck ExprTokenizer.cs /namespace Demo
最后,使用相同的PCK规范文件生成一个LALR(1)解析器:
pckw lalr1gen expr.pck ExprParser.cs /namespace Demo
现在将这些文件包含到项目中,并引用Demo命名空间。添加对程序集pck的引用。在Main()例程中添加以下代码(如果这是一个控制台应用程序):
C#
var parser = new ExprParser(new ExprTokenizer("3*(4+7)"));
这将创建一个新的解析器和标记器,用于解析表达式3*(4+7)。
如果想要流式访问预转换的解析树,可以调用解析器的Read()方法,这与Microsoft的XmlReader非常相似:
C#
while (parser.Read())
{
switch (parser.NodeType)
{
case LRNodeType.Shift:
case LRNodeType.Error:
Console.WriteLine("{0}: {1}", parser.Symbol, parser.Value);
break;
case LRNodeType.Reduce:
Console.WriteLine(parser.Rule);
break;
}
}
然而,这并没有利用修剪或转换解析树的优势。在许多情况下,它也比解析树本身更难使用。幸运的是,获取解析树真的很容易:
var tree = parser.ParseReductions(); // 如果想要修剪树,请传递true。
Console.WriteLine(tree);
这将返回一个节点,其子节点代表解析树。每个节点都有关于解析元素的所有信息。在语法中被压缩的节点不会出现在解析树中。除非解析器上的ShowHidden为true,否则隐藏的节点不会出现在解析树中。