LL(1) 到 LR(1) 的转换

LL(1) to LR(1) Transformation

提问人:Fiery Phoenix 提问时间:10/25/2016 最后编辑:Fiery Phoenix 更新时间:11/3/2016 访问量:617

问:

我最近为这个 LL(1) 语法编写了一个递归下降解析器(它生成了 XML 的一小部分):

document ::= element EOF
element ::= < elementPrefix
elementPrefix ::= NAME attribute elementSuffix
attribute ::= NAME = STRING attribute
attribute ::= EPSILON
elementSuffix ::= > elementOrData endTag
elementSuffix ::= />
elementOrData ::= < elementPrefix elementOrData
elementOrData ::= DATA elementOrData
elementOrData ::= EPSILON
endTag ::= </ NAME > 

我已将语法从这个简单的 EBNF 语法转换为 LL(1):

document  ::=  element
element   ::=  start_tag (element | DATA)* end_tag | empty_tag
start_tag ::=  < NAME attribute* >
end_tag   ::=  </ NAME >
empty_tag ::=  < NAME attribute* />
attribute ::=  NAME = STRING

现在,我正在编写一个识别相同语法的shift-reduce解析器。我意识到每个 LL(1) 语法也是 LR(1)。然而,我的教授告诉我,为上述 LL(1) 语法编写一个 shift-reduce 解析器“可能不方便”。这让我认为在开始编写解析器代码之前,我需要将其转换为 LR(1)。

假设使用上面的 LL(1) 语法编写 LR(1) 解析器确实不是一个好主意,我该如何将其转换为 LR(1)?我需要做些什么才能使它更适合手动编码的 LR(1) 解析器?

补遗:标记为 、 、 、 、 、 和 。NAMESTRINGDATA></></=

11/3/16 更新:

显然,转型是没有必要的。语法已经在 LR(1) 中,经过更多研究后,我能够确认它。我现在已经完成了两个解析器的实现,我感谢所有能够提供帮助的人!

XML 解析 无关语法

评论

1赞 Ira Baxter 10/27/2016
为什么不方便呢?
1赞 Fiery Phoenix 10/27/2016
@IraBaxter 那么我上面的语法适合用于手动编码 shift-reduce 解析器吗?
1赞 Ira Baxter 10/27/2016
“每个 LL(1) 语法都是一个 LR(1) 语法”。是的。为方便起见,您可以提取 Kleene 星形子表达式,并使用递归将它们转换为单独的规则。
1赞 CoronA 10/27/2016
您(或其他任何人)能否解释一下您希望如何手动编写 LR-Parser?将 LR-Items 写在纸上,然后将所有过渡复制到过渡表中?然后尝试找到一个产生最小状态的 LR 语法。这需要很多经验和一点运气——我认为没有办法系统地做到这一点。
1赞 CoronA 10/28/2016
你的语法已经是 LR(1),所以问题可能应该是:“我怎样才能将不方便的 LR(1) 语法转换为方便的语法”。而且没有解决方案,特别是因为手动编写 LR 解析器非常罕见。教授可能指出了你的 EBNF 语法已经是 LR(1) 的事实——它的可读性要好得多,并且会产生一个更方便的语法树。

答: 暂无答案