带有epsilon生产的LR(1)解析表 [英] LR(1) parsing table with epsilon productions
问题描述
我在使用包含epsilon生产的语法为LR(1)解析器构建项目集时遇到麻烦.例如,给定以下语法(其中eps代表epsilon)
I'm having trouble building the collection of sets of items for LR(1) parsers with a grammar containing epsilon productions. For example, given the following grammar (where eps stands for epsilon)
S -> a S U
U -> b
| eps
State0为
S' -> .S, $
S -> .a S U, $
从State0中移动"a"会得到以下状态,我们称其为State2
Moving with 'a' from State0 would give the following state, let's call it State2
S -> a .S U, $
S -> .a S U, $/???
为了对State2的第二项进行前瞻,我需要计算FIRST(U $).我知道FIRST(U)= {'b',eps}.我的第一个问题是:State2的第二项的前瞻是$和'b'?由于U可以是eps,因此我的大脑告诉我也可以将$用作预示符,而不仅仅是'b'.如果FIRST(U)只是{'b'},那就只是'b'.正确吗?
In order to have the lookahead for the second item of State2 I need to calculate FIRST(U$). I know that FIRST(U) = {'b', eps}. My first question is: the lookaheads of the second item of State2 are $ and 'b'? Since U can be eps, my brain tells me that I can have $ as a lookahead as well, not just 'b'. It would have been just 'b' if FIRST(U) would have been just {'b'}. Is that correct?
第二个问题:在某个时候,我将处于以下状态
Second question: at some point I will have a state as the following one
S -> a S .U, $
U -> .b, $
U -> .eps, $
我在这里做什么?我是否需要随eps一起移动并设置项目U -> eps., $
?如果我将另一个终端(即X -> .eps, a/$
)作为预行怎么办?如果我搬家,最后得到一组X -> eps., $
的形式,我会减少吗?
What do I do here? Do I need to move with eps and have a set with the item U -> eps., $
? What if I have another terminal as lookahead, i.e. X -> .eps, a/$
? And if I move, ending up having a set of the form X -> eps., $
, do I reduce?
还有更多:我需要在解析表中插入eps作为符号吗?
And more: do I need to insert eps in the parse table as a symbol?
谢谢
推荐答案
-
FIRST(U$)
的意思是在U$
的派生中可能是第一个符号集".显然,如果U
可以派生空字符串,则$
必须是该集合的一部分.输入结束标记$
确保我们不必担心FIRST
集中的ε. (如果我们使用LR(k)而不是LR(1),我们将使用k
结束标记,以使FIRSTk
中的所有字符串都具有长度k
.
FIRST(U$)
means "the set of symbols which could be first in a derivation ofU$
". Clearly, ifU
can derive the empty string,$
must be part of this set. The end-of-input marker$
ensures that we never have to worry about epsilons in theFIRST
sets. (If we were doing LR(k) instead of LR(1), we would usek
end markers so that all the strings inFIRSTk
had lengthk
.
与U →
(或者如果您坚持要与U → ε
)关联的项目为U → •
.换句话说,它是可还原的,并应在匹配的超前行为上引发减少动作.
The item associated with U →
(or with U → ε
if you insist) is U → •
. In other words, it is reducible and should trigger a reduce action on matching lookahead.
ε
不是符号;我们仅使用它(有时)使空字符串可见.但是空字符串为空.
ε
is not a symbol; we only use it (sometimes) to make the empty string visible. But the empty string is empty.
这篇关于带有epsilon生产的LR(1)解析表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!