当前位置：文江博客话题详情

如何判断一个文法是LL(1)、LR(0)还是SLR(1)？

发布于 2024-12-21 04:53:03 字数 146 浏览 1 评论 0原文

如何识别文法是 LL(1)、LR(0) 还是 SLR(1)？

任何人都可以使用这个例子或任何其他例子来解释它吗？

X → Yz |一个
Y → bZ | ε
Z → ε

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

执笔绘流年 2024-12-28 04:53:03

要检查语法是否为 LL(1)，一种选择是构造 LL(1) 解析表并检查是否有任何冲突。这些冲突可以是

第一/第一冲突，其中必须为非终结/终结对预测两个不同的产生式。
FIRST/FOLLOW 冲突，其中预测了两种不同的产生式，一种表示应采用某些产生式并将其扩展为非零数量的符号，另一种表示应使用一种产生式来指示某些非终结符最终应扩展为空字符串。
FOLLOW/FOLLOW 冲突，其中指示非终结符最终应扩展为空字符串的两个产生式相互冲突。

让我们通过为每个非终结符构建 FIRST 和 FOLLOW 集来尝试一下您的语法。在这里，我们得到：

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}

我们还知道 FOLLOW 集合是

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

由此，我们可以构建以下 LL(1) 解析表：

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

由于我们可以构建没有冲突的解析表，因此语法为 LL(1)。

为了检查语法是 LR(0) 还是 SLR(1)，我们首先为该语法构建所有 LR(0) 配置集。在这种情况下，假设 X 是起始符号，我们得到以下结果：

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

由此，我们可以看到语法不是 LR(0)，因为状态 (1) 中存在移位/归约冲突。具体来说，因为我们有移位项 X → .a 和 Y → .，所以我们无法判断是移动 a 还是减少空字符串。更一般地说，没有 ε-产生式的文法是 LR(0)。

然而，这个文法可能是SLR(1)。为了看到这一点，我们使用特定非终结符的前瞻集来增强每次归约。这返回了这组 SLR(1) 配置集：

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

状态 (1) 中的移位/归约冲突已被消除，因为我们仅在前瞻为 z 时进行归约，这不会与任何其他项冲突。

To check if a grammar is LL(1), one option is to construct the LL(1) parsing table and check for any conflicts. These conflicts can be

FIRST/FIRST conflicts, where two different productions would have to be predicted for a nonterminal/terminal pair.
FIRST/FOLLOW conflicts, where two different productions are predicted, one representing that some production should be taken and expands out to a nonzero number of symbols, and one representing that a production should be used indicating that some nonterminal should be ultimately expanded out to the empty string.
FOLLOW/FOLLOW conflicts, where two productions indicating that a nonterminal should ultimately be expanded to the empty string conflict with one another.

Let's try this on your grammar by building the FIRST and FOLLOW sets for each of the nonterminals. Here, we get that

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}

We also have that the FOLLOW sets are

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

From this, we can build the following LL(1) parsing table:

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

Since we can build this parsing table with no conflicts, the grammar is LL(1).

To check if a grammar is LR(0) or SLR(1), we begin by building up all of the LR(0) configurating sets for the grammar. In this case, assuming that X is your start symbol, we get the following:

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

From this, we can see that the grammar is not LR(0) because there is a shift/reduce conflicts in state (1). Specifically, because we have the shift item X → .a and Y → ., we can't tell whether to shift the a or reduce the empty string. More generally, no grammar with ε-productions is LR(0).

However, this grammar might be SLR(1). To see this, we augment each reduction with the lookahead set for the particular nonterminals. This gives back this set of SLR(1) configurating sets:

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

The shift/reduce conflict in state (1) has been eliminated because we only reduce when the lookahead is z, which doesn't conflict with any of the other items.

回复收藏 0 原文

怼怹恏 2024-12-28 04:53:03

如果没有 FIRST/FIRST 冲突，也没有 FIRST/FOLLOW 冲突，则您的语法是 LL(1)。

FIRST/FIRST 冲突的示例：

S -> Xb | Yc
X -> a 
Y -> a

仅通过查看第一个输入符号“a”，您无法知道是否应用产生式 S -> 。 Xb 或 S -> Yc，因为“a”位于 X 和 Y 的第一个集合中。

FIRST/FOLLOW 冲突的示例：

S -> AB 
A -> fe | ε 
B -> fg

仅看到第一个输入符号“f”，您无法决定是否应用产生式 <代码>A-> fe 或 A -> ε，因为“f”既在 A 的 FIRST 集合中，又在 A 的 FOLLOW 集合中（A 可以解析为 ε/empty，B 解析为 f）。

请注意，如果您没有 epsilon 产生式，则不会出现 FIRST/FOLLOW 冲突。

If you have no FIRST/FIRST conflicts and no FIRST/FOLLOW conflicts, your grammar is LL(1).

An example of a FIRST/FIRST conflict:

S -> Xb | Yc
X -> a 
Y -> a

By seeing only the first input symbol "a", you cannot know whether to apply the production S -> Xb or S -> Yc, because "a" is in the FIRST set of both X and Y.

An example of a FIRST/FOLLOW conflict:

S -> AB 
A -> fe | ε 
B -> fg

By seeing only the first input symbol "f", you cannot decide whether to apply the production A -> fe or A -> ε, because "f" is in both the FIRST set of A and the FOLLOW set of A (A can be parsed as ε/empty and B as f).

Notice that if you have no epsilon-productions you cannot have a FIRST/FOLLOW conflict.

回复收藏 0 原文

诗化ㄋ丶相逢 2024-12-28 04:53:03

简单回答：如果关联的 LL(1) 解析表的每个表项中至多有一个产生式，则称该文法是 LL(1)。

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    --------------------------------------------

由于 [S,b] 包含两个产生式，因此对于选择哪个规则会产生混乱。因此它不是 LL(1)。

一些简单的检查来查看语法是否为 LL(1)。
检查 1：语法不应保留递归。
示例：E --> E+T。不是 LL(1)，因为它是左递归。
检查2：语法应该是左因子分解的。

当两个或多个语法规则选择共享公共前缀字符串时，需要进行左分解。
示例：S-->A+int|A。

检查3：语法不应含糊不清。

These are some simple checks.

Simple answer:A grammar is said to be an LL(1),if the associated LL(1) parsing table has atmost one production in each table entry.

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    --------------------------------------------

As [S,b] contains two Productions there is a confusion as to which rule to choose.So it is not LL(1).

Some simple checks to see whether a grammar is LL(1) or not.
Check 1: The Grammar should not be left Recursive.
Example: E --> E+T. is not LL(1) because it is Left recursive.
Check 2: The Grammar should be Left Factored.