如何找到递归语法的 FIRST 和 FOLLOW 集? [英] How to find FIRST and FOLLOW sets of a recursive grammar?
问题描述
假设我有以下 CFG.
Suppose I have the following 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 集,我想我可以按如下方式完成.
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屋!