提问人:Fiery Phoenix 提问时间:10/25/2016 最后编辑:Fiery Phoenix 更新时间:11/3/2016 访问量:617
LL(1) 到 LR(1) 的转换
LL(1) to LR(1) Transformation
问:
我最近为这个 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) 解析器?
补遗:标记为 、 、 、 、 、 和 。NAME
STRING
DATA
>
<
/>
</
=
11/3/16 更新:
显然,转型是没有必要的。语法已经在 LR(1) 中,经过更多研究后,我能够确认它。我现在已经完成了两个解析器的实现,我感谢所有能够提供帮助的人!
答: 暂无答案
评论