如何确定语言是否为LL（1）LR（0）SLR（1） [英] How to determine whether a language is LL(1) LR(0) SLR(1)

问题描述

有一个简单的方法来确定语法是LL1，LR0，SLR1 ...只是从语法上查看，而不进行任何复杂的分析？

实例：要决定一个BNF语法是LL1，你必须首先计算第一和跟随集合 - 这在一些情况下可能非常耗时。

有人有一个想法如何做到这一点更快？
任何帮助真的会感激！

解决方案

首先，您无法判断语言是否为检查语法的LL（1），您只能对语法本身发表声明。对于存在LL（1）语法的语言，完全有可能写出非LL（1）语法。

>

• 您可以为语法编写一个解析器，并让程序首先计算，然后为您跟踪集合和其他属性。




• 检查语法并寻找违反的语法各种语法类型的约束。例如：LL（1）允许正确但不是左递归，因此，包含左递归的语法不是LL（1）。 （对于其他语法属性，你将不得不花费一些高质量的时间与定义，因为我现在不记得任何东西在我的头顶部：）

Is there a simple way to determine wether a grammar is LL1, LR0, SLR1... just from looking on the grammar without doing any complex analysis?

For instance: To decide wether a BNF Grammar is LL1 you have to calculate First and Follow sets first - which can be very time consuming in some cases.

Has anybody got an idea how to do this faster? Any help would really be appreciated!

解决方案

First off, a bit of pedantry. You cannot determine whether a language is LL(1) from inspecting a grammar for it, you can only make statements about the grammar itself. It is perfectly possible to write non-LL(1) grammars for languages for which an LL(1) grammar exists.

With that out of the way:

• You could write a parser for the grammar and have a program calculate first and follow sets and other properties for you. After all, that's the big advantage of BNF grammars, they are machine comprehensible.

• Inspect the grammar and look for violations of the constraints of various grammar types. For instance: LL(1) allows for right but not left recursion, thus, a grammar that contains left recursion is not LL(1). (For other grammar properties you're going to have to spend some quality time with the definitions, because I can't remember anything else off the top of my head right now :).

这篇关于如何确定语言是否为LL（1）LR（0）SLR（1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！