XML 的这个子集是否有 LL(1) 文法？

Question

我将使用以下 EBNF 语法为 XML 的一个虚构子集创建一个解析器：

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

以上是语法'as is'，没有任何改动。 这是我将其转换为 LL(1) 的尝试：

DOCUMENT         ::=    ELEMENT EOF 
ELEMENT          ::=    PREFIX > ELEMENT_OR_DATA END_TAG
                      | PREFIX />
PREFIX           ::=    < NAME OPT_ATTR 
ELEMENT_OR_DATA  ::=      OPT_ELEMENT ELEMENT_OR_DATA 
                        | OPT_DATA ELEMENT_OR_DATA 
                        | epsilon
OPT_ELEMENT      ::=    ELM_LIST | epsilon
ELM_LIST         ::=    ELEMENT  | ELEMENT ELM_LIST
OPT_DATA         ::=    DATA_LIST | epsilon
DATA_LIST        ::=    DATA | DATA DATA_LIST
END_TAG          ::=    </ NAME >
OPT_ATTR         ::=    ATTR_LIST | epsilon
ATTR_LIST        ::=    ATTRIBUTE | ATTRIBUTE ATTR_LIST
ATTRIBUTE        ::=    NAME = STRING 
EOF              ::=         &$

这是原始版本的 LL(1) 版本吗？如果不是，我哪里出错了？如果是这样，有没有办法 'simplify' 不改变意思？我不相信我有最简单的版本。

希望这是清楚的。

Answer 1

LL(1) 解析器无法仅通过查看下一个标记来为 ELEMENT 的两个规则选择正确的规则。根据语法，解析器应该尝试第一个规则： ELEMENT ::= PREFIX > ELEMENT_OR_DATA END_TAG 如果它不起作用，它必须从递归（回溯）中 return 才能尝试第二条规则： ELEMENT ::= PREFIX />

问题是两条规则都从相同的 "object" 前缀开始。在这种情况下，它甚至是 "worse" 因为它不是终端。

当然，这不是 LL(1) 文法。让我们尝试构建一个。

我们首先通过删除 TAG 来简化原始语法： DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTE* > (ELEMENT | DATA)* </ NAME > ELEMENT ::= < NAME ATTRIBUTE* /> ATTRIBUTE ::= NAME = STRING

下一步是拆分 ELEMENT 的规则以获得第一个标记，这将有助于解析器 select 正确的规则。 DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTE* ELEMENT1 ELEMENT1 ::= > (ELEMENT | DATA)* </ NAME > ELEMENT1 ::= /> ATTRIBUTE ::= NAME = STRING

现在解析器可以成功开始解析元素了。它 "postpones" 决定它是扩展元素还是短元素，并将此问题委托给 ELEMENT1 规则。后者可以通过检查下一个标记是 > 还是 />.

来确定正在解析的元素类型。

让我们继续改造： DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTES ELEMENT1 ELEMENT1 ::= > ELEMENT_OR_DATA </ NAME > ELEMENT1 ::= /> ELEM_OR_DATA ::= ELEMENT ELEM_OR_DATA ELEM_OR_DATA ::= DATA ELEM_OR_DATA ELEM_OR_DATA ::= epsilon ATTRIBUTES ::= NAME = STRING ATTRIBUTES ATTRIBUTES ::= epsilon

我们刚刚用正确的 LL 语法替换了 *-operator。最后一个语法仍然有一些问题：前两个 ELEM_OR_DATA 规则可能 "confuse" 解析器，因为它无法猜测要应用哪一个（与我们一开始讨论的问题类似）。

让我们通过给解析器一个提示来解决这个问题： DOCUMENT ::= ELEMENT EOF ELEMENT ::= < ELEMENT0 ELEMENT0 ::= NAME ATTRIBUTES ELEMENT1 ELEMENT1 ::= > ELEMENT_OR_DATA </ NAME > ELEMENT1 ::= /> ELEM_OR_DATA ::= < ELEMENT0 ELEM_OR_DATA ELEM_OR_DATA ::= DATA ELEM_OR_DATA ELEM_OR_DATA ::= epsilon ATTRIBUTES ::= NAME = STRING ATTRIBUTES ATTRIBUTES ::= epsilon

我们拆分了 ELEMENT1 并在第一个 ELEM_OR_DATA 规则中使用了 ELEMENT0。现在假设 DATA 是一个标记，解析器可以通过仅查看下一个标记轻松地确定应用哪个规则。

XML 的这个子集是否有 LL(1) 文法？

Do I Have an LL(1) Grammar for This Subset of XML?

xml

grammar

parsing

context-free-grammar