parsing - LR(1) 语法：如何分辨？支持/反对的例子？

Question

我目前正在查看 GNU Bison 来解析程序代码（或者实际上是扩展使用 Bison 来执行此操作的程序）。我知道 Bison 只能（或：最好）处理 LR(1) 语法，即一种特殊形式的上下文无关语法；而且我实际上也（相信）理解上下文无关和 LR(1) 语法的规则。

但是，不知何故，我对 LR(1) 语法的概念缺乏很好的理解。以 SQL 为例。SQL 包含——我相信——一种上下文无关的语法。但它也是 LR(1) 语法吗？我怎么知道？如果是，什么会违反 LR(1) 规则？

Answer 1

LR(1) 意味着您可以通过知道所有将被减少的标记加上它们后面的一个标记来选择适当的规则来减少。AND在布尔查询和BETWEEN操作中没有问题。例如，以下语法是 LL(1)，因此也是 LR(1)：

expr ::= and_expr | between_expr | variable
and_expr ::= expr "and" expr
between_expr ::= "between" expr "and" expr
variable ::= x

我相信整个 SQL 语法比 LR(1) 还要简单。可能是 LR(0) 甚至 LL(n)。

Answer 2

我的一些客户使用我的 LALR(1) 解析器生成器创建了 SQL 和 DB2 解析器，并成功使用了多年。他们发给我的语法是 LALR(1)（除了按您想要的方式解决的 shift-reduce 冲突）。对于纯粹主义者 - 不是 LALR(1)，但在实践中工作正常，不需要 GLR 或 LR(1)。你甚至不需要更强大的 LR(1)，AFAIK。

我认为解决这个问题的最好方法是找到一个 SQL 语法和一个好的 LALR/LR(1) 解析器生成器，看看你是否得到冲突报告。我记得一个 SQL 语法（有点过时）是 LALR(1)，可以在这个下载中找到：http: //lrstar.tech/downloads.html

LRSTAR是一个 LR(1) 解析器生成器，它会给你一个冲突报告。如果您无法解决冲突，它也是 LR(*)。