60

是否有一个很好的在线资源，其中包含一些主要解析算法（LL(1)、LR(1)、LR(0)、LALR(1)）的语法集合？我发现许多属于这些家族的单独语法，但我不知道有人写过大量示例语法的好资源。

有人知道这样的资源吗？

4

4 回答 4

39

来自维基百科的例子

法学硕士(1)

语法

S -> F
S -> ( S + F )
F -> a

输入

( a + a )

解析步骤

S -> "(" S "+" F ")"
  -> ( "F" + F ) 
  -> ( "a" + F ) 
  -> ( a + "a" )

左路(0)

语法

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1

输入

1 + 1

解析步骤

need to build a parser table and traverse through states.

LR(1)

语法

S’ -> S S 
S  -> C C 
C  -> c C | d

输入

cd

解析步骤

large table

LALR

语法

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

输入

xxzxx

解析步骤

traverse large parser table

您可能还想看看

于 2011-07-04T20:34:20.667 回答
24

Parsing Techniques - A Practical Guide有几个几乎每种语法类型的例子（即每种类型可能有六个左右）。您可以购买第 2 版书籍，尽管第 1 版可在作者网站上以 PDF 格式免费获得（靠近链接底部）。

作者还有一些测试语法，他与第二版的代码示例捆绑在一起，可以在这里找到。

注意：所有这些语法都很小（不到几十条规则），因为这显然是一本出版的书。

于 2011-08-20T20:05:42.800 回答
2

我不希望您找到大量以这种方式组织的语法。主办方会得到什么回报？

您可能有机会做的是找到对应于每个系列的解析器生成器（例如，LL(1)），然后查找该解析器生成器的输入实例，所有这些都将是 LL(1)定义。例如，ANTLR 的语法都是 LL(k) 的不同版本，具体取决于您选择的 ANTLR 版本（ANTLR 版本的描述会告诉它接受什么 k）；Bison 语法都是 LALR(1) [忽略最近的 GLR 选项]。如果您访问我的网站（参见 bio），您会看到一个几乎与上下文无关的语法列表（也就是说，不在您描述的任何类中）。

编辑：请注意@Bart Kier 的说明，即 ANTLR 可以将特定 k 的语法显式标记为 LL(k)。

于 2011-06-30T08:19:11.640 回答
1

大多数 yacc 及其克隆或替换（如 btyacc、hyacc、bison）的安装都有测试套件。这些测试套件中的语法共同构成了一个示例列表。我假设 LL 解析器生成器也是如此。但我对他们了解不多。既然提到了 ANTLR，那么我也可能会指出，快速搜索将在 ANTLR https://github.com/antlr/grammars-v4下显示以下大型示例存储库所以，我想这也算是一个答案。

于 2020-01-05T07:11:28.403 回答