65.9K
CodeProject 正在变化。 阅读更多。
Home

Pck/LALR(1): 一种 LR 分析算法

honey the codewitch
starIconstarIconstarIconstarIconstarIcon

5.00/5 (2投票s)

2019年8月14日

CPOL

3分钟阅读

viewsIcon

6793

downloadIcon

114

Pck 的一部分 LALR(1) 解析算法

pckw

引言

好了，我终于完成了。LALR(1) 解析器支持现在已加入 PCK。

背景

这个背景假设至少对 LL(1) 解析有一定的了解。如果您需要学习它，您可以参考我的关于创建 LL(1) 解析器的教程。 这也假设对 PCK 有一些了解。

LALR(1) 解析是一种解析形式，与 LL(1) 解析相比，它的工作方式几乎是“由内而外”的；它从叶子到根构建树，并使用输入标记指导解析。 与 LL(1) 解析器相比，后者从根到叶构建树，并使用语法来指导解析。 在 LALR(1)/LR 情况下，输入告诉我们使用哪个规则，解析器将其与语法进行比较。 在 LL(1)/LL 情况下，语法告诉我们使用哪个规则，解析器将其与输入进行比较。

听起来令人困惑？ 一开始是有点。 幸运的是，LALR(1) 算法的细节对于使用它来说并不重要。 如果是的话，大多数人都会倒霉！

话虽如此，我们必须从某个地方开始。 这是与 LL(1) 解析相比，LALR(1) 解析的结果

  • LALR(1) 解析更大的 CFG 语法子集。 在它可以识别的内容方面，它比 LL(1) 强大得多。
  • LALR(1) 可以是左递归或右递归。 甚至鼓励左递归，因为它不占用那么多堆栈空间。
  • 语法在使用之前不需要分解

以下是 LALR(1) 解析的缺点

  • 与使用 LL(1) 解析器相比，学习曲线略高，因为它更复杂。
  • 对于凡人来说，生成表的算法几乎不可能理解，无论有多少注释。
  • 它不适合自然树遍历。 相反，它从下往上构建树。
  • 由于算法的工作方式，错误识别不如 LL(1) 那么快。

这是我的建议，鉴于以上：如果可以，请使用 LL(1) 解析器，或者仅当您需要它带来的额外解析能力时才使用 LALR(1) 解析器。 PCK 两者都提供。

使用 LALR(1) 算法的其他解析器生成器包括 YACC 和 Gold Parser。

Using the Code

首先，我们需要先构建代码才能使用它。 将 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 规范并使用它来生成一个 tokenizer/lexer

pckw fagen expr.pck ExprTokenizer.cs /namespace Demo

最后，获取相同的 pck 规范文件并使用它来生成一个 LALR(1) 解析器

pckw lalr1gen expr.pck ExprParser.cs /namespace Demo

现在将这些文件包含在您的项目中，并引用 Demo 命名空间。 添加对程序集 pck 的引用。 在某个地方添加以下代码，如果这是一个控制台应用程序，则可能在您的 Main() 例程中

var parser = new ExprParser(new ExprTokenizer("3*(4+7)"));

这将在表达式 3*(4+7) 上创建一个新的解析器和 tokenizer。

如果您想要对预转换的解析树进行流式访问，您可以在循环中调用解析器的 Read() 方法，非常像 Microsoft 的 XmlReader

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(); // pass true if you want the tree to be trimmed.
Console.WriteLine(tree);

这会返回一个以其他节点作为子节点的节点，表示解析树。 每个节点都包含有关已解析元素的所有信息。 语法中折叠的节点不在解析树中。 隐藏的节点不在解析树中，除非解析器上的 ShowHidden 为 true。

您还可以在运行时创建解析器，就像使用 LL(1) 解析器一样。 您不必生成代码。

为此，您必须引用 pck、pck.cfg、pck.fa 和 pck.lalr1 程序集

// we need both a lexer and a CfgDocument. 
// we read them from the same file.
var cfg = CfgDocument.ReadFrom(@"..\..\..\expr.pck");
var lex = LexDocument.ReadFrom(@"..\..\..\expr.pck");
// create a runtime tokenizer
var tokenizer = lex.ToTokenizer("3*(4+7)", cfg.EnumSymbols());
// create a parser
var parser = cfg.ToLalr1Parser(tokenizer);

这段代码执行与生成的代码等效的操作，而实际上不生成任何代码。 生成 LALR(1) 表和 FA tokenizer 可能需要一些时间，因此建议预先生成。 此外，从上面的内容来看，设置显然更加复杂。

历史

  • 2019 年 8 月 14 日 - 首次提交
© . All rights reserved.