2

我过去已经实现了递归下降和类似 PEG 的解析器，您可以在其中执行以下操作：

Path -> Segment+
Segment -> Slash Name
Segment -> /
Name -> /\w+/
Slash -> /
  • whereSegment+表示“匹配一个或多个Segment”
  • 并且有一个普通的旧正则表达式用于匹配一个或多个单词字符\w+

您通常如何使用 LR 语法/解析器完成同样的事情？我见过的所有 LR 解析器的例子都是非常基础的，比如解析1 + 2 * 3, or (())()，其中的模式非常简单，似乎不涉及“一个或多个”功能（或者零个或多个 with *，或者可选 with ?） . 您通常如何在 LR 解析器中做到这一点？

或者LR解析首先需要词法分析阶段（即LR解析器需要终端和非终端“令牌”）。希望有一种方法可以在没有这样两个阶段的情况下进行 LR 解析。LR 解析器的定义谈到了我一直在阅读的书籍/网站中的“输入字符”，但随后您会不经意/巧妙地看到如下一行：

语法的终端符号是词法扫描器在输入流中找到的多字符符号或“标记”。

它就像什么，扫描仪是从哪里来的。

4

3 回答 3

2

您当然可以为一种语言编写无扫描仪语法，但在大多数情况下它不会是 LR( 1 )，因为当标记是单个字符时，前瞻的 1 个标记并不多。

通常，LALR(1) 解析器生成器（如 bison）与扫描器生成器（如 flex）结合使用。

于 2015-04-26T06:19:04.720 回答
1

每当您有一个解析器在令牌流上运行时，总会有一个问题是什么产生了令牌流。对于大多数解析器生成器，标记的语法规范和词法规范是分开的，主要是因为解析器生成器和词法生成器的操作方式不同。

将正则表达式运算符添加到“语法”很方便。但是它们并没有扩展上下文无关语法的力量。

在语法中使用类似正则表达式的运算符有 3 种选择。

1）在整个语法中一致地在字符级别使用它们。如果您这样做，您的解析器将使用作为单个字符的标记进行操作。这对于大多数解析器生成器来说可能效果不佳，因为大多数解析器生成器的决定仅基于下一个输入流标记，在这种情况下，是单个字符。要完成这项工作，您要么需要一个回溯解析器，要么需要一个通过替代解析空间尝试多条路径的解析器；LR 和 LL 解析器不这样做。如果您不介意 GLR 基于每个字符的额外开销，则可以使用无扫描仪 GLR 解析器。（此外，如果在字符级别操作，您可能已经明确指定了空格和注释语法）。

2) 将它们用作单个标记字符序列的规范（如在 OP 的“名称 -> /w+/”中）。在这种形式中，您最终要做的是编写与语法集成的词汇标记规范。然后可以将语法处理为两部分：词汇规范和更传统的 BNF。这个想法与许多词法分析器和解析器生成器兼容；它仍然没有改变表现力。

3) 仅对语法元素使用正则表达式运算符。这些很容易转化为传统的 BNF 语法规则：

  Path -> Segment +

相当于：

  Path -> Segment 
  Path -> Path Segment

经过这样的转换，结果与大多数解析器生成器兼容。这留下了如何指定语法标记的词法句法的问题。

您可以实现结合 1) 和 2) 的混合方案，这似乎是 OP 所做的。

于 2015-06-19T14:31:08.363 回答
0

一些 LR 解析器生成器的 BNF 语法中允许使用正则表达式。 LRSTAR 9.1允许使用正则表达式。Yacc 和 Bison 不允许在 BNF 语法中使用正则表达式。

词法标记应在词法文法中指定，与 BNF（解析器）文法分开。在解析器看到它们之前已经定义了标记，这使解析器的工作变得更加轻松。

PEG 不会强迫您将词汇符号与语法符号分开，从而产生一些严重的问题，例如在某些情况下需要无限前瞻。

于 2017-03-20T23:07:38.550 回答