LL(1), LR(1), LR(0), LALR(1)语法的例子是什么？

Question

是否有一个在线资源，包含一些主要解析算法（LL(1), LR(1), LR(0), LALR(1)）的语法集合？我找到了很多属于这些族群的单个语法，但是我不知道是否有一个好的资源，其中有人编写了一大批示例语法。

有没有人知道这样的资源？

- templatetypedef

---

这些是解析算法而非文法。你的意思是需要一种类型的解析器还是另一种语法的示例？ - Hogan

从技术上讲，LL(1)等实际上是文法族。以它们命名的解析算法是一种可以解析该语言族中任何文法的算法。 - templatetypedef

@Ira Baxter- 我目前正在教授编译器课程，当我想展示各种解析算法时，经常需要从其他来源中借鉴例子语法。在这些类别中创建非平凡的语法很棘手（但可行），而要制作符合 LR(1) 但不是 LALR(1) 或符合 LALR(1) 但不是 SLR(1) 的语法则极为困难。我希望能找到符合这些描述的真实世界的语法示例，以便我能专注于呈现材料而不是调整语法。 - templatetypedef

@Prashant Bhate，也许它消失了是因为你太想要它了。 - Bart Kiers

以下是我的个人GitHub存储库链接，其中包含4个LL(1)语法，一个不是LL(1)的LR(0)语法，一个不是LR(0)的SLR(1)语法和一个不是SLR(1)的LR(1)语法。所有示例都可以通过在任何*.nix类似操作系统的终端中键入“make”来编译和运行。 - OrenIshShalom

Answer 1

维基百科上的例子：

LL(1)

文法

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

输入

( a + a )

解析步骤

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

LR(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

您可能还想看看

• Parsing Simulator工具
• antlr works - 下载>
• 来自ocw mit的解析器表生成
• 从解析到代码生成ocw mit
• 附加示例

- Prashant Bhate

---

请问如何证明语法是LR(0)或SLR(1)？ - Katia

@katia- 你可能想查看斯坦福大学编译器课程的网站http://cs143.stanford.edu，其中包含许多讲座幻灯片和手册，详细介绍了如何完成这项任务。第二个问题集和期中考试（以及它们的解决方案）详细说明了这一点。 - templatetypedef

我不相信所给的语法是LR(0)。在状态[S -> E .]，[E -> E . + B]中，我们有一个移位/规约冲突。我们需要使用一个向前看符号来确定是将S -> E . 规约为$ lookahead，还是继续移位。通过使用S的通用FOLLOW集解决了这个冲突，使得语法成为SLR而不是LR(0)。 - Chris Smowton

我同意@ChrisSmowton。 - Jiang Xiang

@ChrisSmowton，语法确实是LR（0）。为了创建Items DFA，通常会添加规则S-> E＃（其中＃是输入的结尾），因此提到的状态包含[S-> E。＃]，[E-> E。+ B]，并且没有冲突，但有两个不同的移位（其中一个是接受操作）。 - dodecaplex

你的LR（1）示例是带以下表格的LR（0）计算。 状态0-8。 开始状态：0。 Gotos S'：0→8; S：0→1，1→7; C：{0, 1}→2，2→4，3→5。 移位c：{0,1,2,3}→3，d：{0,1,2,3}→6。 在4上减少{S⇐CC}，在5上减少{C⇐cC}，在6上减少{C⇐d}，在7上减少{S'⇐SS}。 接受{⇐S'}的8。 此外：“cd”不符合语法，但“cdddd”符合。 - NinjaDarth

Answer 2

《解析技术 - 实用指南》中有几个例子（即每种类型大约半打左右）涉及几乎每种类型的语法。您可以购买第二版书籍，尽管第一版可在作者的网站上以PDF形式免费获取（链接底部附近）。

作者还提供了一些测试语法，这些语法与第二版的代码示例一起打包，可以在此处找到。

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

- Jason Moore

Answer 3

我不指望你会有意地找到一个大型的语法集合以此方式组织。组织者能得到什么回报呢？

你可能有机会找到与每个家族相对应的解析器生成器（例如LL(1)），并寻找该解析器生成器的输入实例，所有这些实例都将根据定义是LL(1)。例如，ANTLR的语法都是各种版本的LL(k)，具体取决于您选择的ANTLR版本（ANTLR版本的描述将说明它接受哪个k）；Bison语法都是LALR(1) [忽略最近的GLR选项]。如果您访问我的网站（请参见个人简介），您将看到一系列几乎都是无上下文的语法（也就是说，不属于您描述的任何类别）。

编辑：请注意@Bart Kier的澄清，ANTLR可以明确地标记特定k的语法。

- Ira Baxter

---

尝试使用解析器生成器是一个好建议。使用ANTLR，您可以手动设置向前查看，例如：options { k=1; }表示LL(1)，或者默认的options { k=*; }表示LL(k)。 - Bart Kiers

@Bart Kiers：我的认识是旧版本的ANTLR不能够灵活地处理k>1和k=*。所有版本都支持显式声明吗？不过，这仍然很有趣。我认为最新版的ANTLR使用了特定于语法规则的向前搜索来自动判断向前搜索是什么。但是，我并不是ANTLR专家。 - Ira Baxter

我相信在 ANTLR v3 中添加了无限的向前看 k=*。ANTLR v2.x 始终有一个固定的 k。这只是我随口说出的，稍后我会查看我的 ANTLR 参考资料，如果我错了，我会进行更正。但我非常肯定这是正确的。 - Bart Kiers

Answer 4

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

- Rock Brentwood