LL(1)，LR(1)，LR(0)，LALR(1)文法的例子？

Question

对于一些主要的解析算法(LL(1)，LR(1)，LR(0)，LALR(1))，是否有很好的在线资源来收集语法？我已经找到了许多属于这些家族的单独的语法，但我不知道有人编写了大量示例语法的好资源。

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

Answer 1

对于几乎每种类型的语法，Parsing Techniques - A Practical Guide都有几个示例(即每种类型可能有六个左右)。你可以购买第二版，尽管第一版可以在作者的website上免费获得(接近链接的底部)。

作者还提供了一些测试语法，这些语法与第二版中的代码示例捆绑在一起，可以在here上找到。

注意:所有这些语法都很小(少于几十条规则)，因为这显然是一本出版的书。

Answer 2

来自维基百科的例子

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 tool
• antlr works - >download<
• Parser table generation from ocw mit
• From parsing to code genration ocw mit
• additional examples

Answer 3

我不期望你能找到一大堆这样组织起来的文法。组织者会得到什么回报？

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

编辑:注意@Bart Kier的澄清，ANTLR可以显式地将特定k的语法标记为LL(k)。