如何判断一种语言是否为 LL(1) LR(0) SLR(1) [英] How to determine whether a language is LL(1) LR(0) SLR(1)

问题描述

有没有一种简单的方法可以判断一个语法是 LL(1)、LR(0)、SLR(1)... 只看语法而不做任何复杂的分析?

Is there a simple way to determine whether a grammar is LL(1), LR(0), SLR(1)... just from looking on the grammar without doing any complex analysis?

例如:要确定 BNF 语法是否为 LL(1)，您必须计算 First 和 Follow 集 - 在某些情况下这可能很耗时.

For instance: To decide whether a BNF Grammar is LL(1) you have to calculate First and Follow sets - which can be time consuming in some cases.

有人知道如何更快地做到这一点吗?任何帮助将不胜感激！

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

推荐答案

首先，有点迂腐.您无法通过检查语法来确定 语言 是否为 LL(1)，您只能对 语法 本身进行陈述.完全可以为存在 LL(1) 语法的语言编写非 LL(1) 语法.

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.

顺便说一句:

• 您可以为语法编写一个解析器，并让一个程序为您先计算并遵循集合和其他属性.毕竟，这是 BNF 语法的一大优势，它们是机器可理解的.

• 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.

检查语法并查找违反各种语法类型的约束.例如:LL(1) 允许右递归但不允许左递归，因此包含左递归的文法不是 LL(1).(对于其他语法属性，您将不得不花一些时间在定义上，因为我现在不记得其他任何事情了:).

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屋！