带有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?

谢谢

推荐答案

1. FIRST(U$)的意思是在U$的派生中可能是第一个符号集".显然，如果U可以派生空字符串，则$必须是该集合的一部分.输入结束标记$确保我们不必担心FIRST集中的ε. (如果我们使用LR(k)而不是LR(1)，我们将使用k结束标记，以使FIRSTk中的所有字符串都具有长度k.

1. FIRST(U$) means "the set of symbols which could be first in a derivation of U$". Clearly, if U 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 the FIRST sets. (If we were doing LR(k) instead of LR(1), we would use k end markers so that all the strings in FIRSTk had length k.

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