且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

如何确定语言是否为LL(1)LR(0)SLR(1)

更新时间:2023-10-24 18:02:52

首先,您无法判断语言是否为检查语法的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 :).