如何找到FIRST和FOLLOW集的递归语法？ [英] How to find FIRST and FOLLOW sets of a recursive grammar?

问题描述

假设我有以下CFG。

A -> B | Cx | EPSILON
B -> C | yA
C -> B | w | z

现在，如果我尝试找到

FIRST(C) = FIRST(B) U FIRST(w) U FIRST(z)
         = FIRST(C) U FIRST(yA) U {w, z}

也就是说，我要进入一个循环。
因此，我假设我必须将它转换为一个立即向左递归的形式，我可以做如下。

That is, I'm going in a loop. Thus I assume I have to convert it into a form which has immediate left recursion, which I can do as follows.

A -> B | Cx | EPSILON
B -> C | yA
C -> C | yA | w | z

现在，如果我尝试计算FIRST集，我想我可以按如下方式完成。 / p>

Now if I try to calculate FIRST sets, I think I can get it done as follows.

FIRST(C) = FIRST(C) U FIRST(yA) U FIRST(w) U FIRST(z)
         = { y, w, z } // I ignore FIRST(C)
FIRST(B) = FIRST(C) U FIRST(yA)
         = { y, w, z }
FIRST(A) = FIRST(B) U FIRST(Cx) U FIRST(EPSILON)
         = { y, w, z, EPSILON }

我在那里纠正吗？

但是即使我在那里，我仍然遇到一个问题，当我尝试从此语法计算FOLLOW集。

But even if I'm right there, I still run into a problem when I try to calculate FOLLOW sets from this grammar.

FOLLOW(A) = { $ } U FOLLOW(B) U FOLLOW(C)

我从第二条规则得到FOLLOW（B），从第三条规则得到FOLLOW（C）但现在要计算FOLLOW（B），我需要FOLLOW（A）（从第一个语法规则），所以我再次陷入一个循环。

I get FOLLOW(B) from 2nd rule and FOLLOW(C) from 3rd rule. But now to calculate FOLLOW(B), I need FOLLOW(A) (from 1st grammar rule) so again I'm stuck in a loop.

任何帮助？
提前感谢！

Any help? Thanks in advance!

推荐答案

由于FIRST和FOLLOW（通常）是递归的，要解决的方程组;可以使用简单的增量算法来实现该解决方案，该算法包括重复应用所有的右侧，直到在一个周期中没有集合改变。

Since FIRST and FOLLOW are (normally) recursive, it's useful to think of them as systems of equations to be solved; the solution can be achieved using a simple incremental algorithm consisting of repeatedly applying all the right hand sides until no set has changed during a cycle.

因此，让我们采用FOLLOW给定的语法：

So let's take the FOLLOW relation for the given grammar:

A → B | Cx | ε
B → C | yA
C → B | w | z

我们可以直接导出方程：

We can directly derive the equations:

FOLLOW(A) = FOLLOW(B) ∪ {$}
FOLLOW(B) = FOLLOW(A) ∪ FOLLOW(C)
FOLLOW(C) = FOLLOW(B) ∪ {x}

所以我们最初将所有跟随集设置为{}，

So we initially set all the follow sets to {}, and proceed.

第一轮：

FOLLOW(A) = {} ∪ {$} = {$}
FOLLOW(B) = {$} ∪ {} = {$}
FOLLOW(C) = {$} U {x} = {$,x}

第二轮：

FOLLOW(A) = {$} ∪ {$} = {$}
FOLLOW(B) = {$} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

第三轮：

FOLLOW(A) = {$,x} ∪ {$} = {$,x}
FOLLOW(B) = {$} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

第四轮：

FOLLOW(A) = {$,x} ∪ {$} = {$,x}
FOLLOW(B) = {$,x} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

在这里我们停止，因为在最后一轮没有改变。

Here we stop because no changes were made in the last round.

这个算法必须终止，因为有有限数量的符号，每个轮只能添加符号到步。这不是最有效的技术，虽然它在实践中通常是足够好的。

This algorithm must terminate because there are a finite number of symbols, and each round can only add symbols to steps. It is not the most efficient technique, although it is generally good enough in practice.

这篇关于如何找到FIRST和FOLLOW集的递归语法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！