0

考虑命题逻辑的以下语法：

<A> ::= <B> <-> <A> | <B> 
<B> ::= <C>  -> <B> | <C> 
<C> ::= <D>  \/ <C> | <D> 
<D> ::= <E>  /\ <D> | <E> 
<E> ::= <F> | -<F>
<F> ::= <G> | <H>
<G> ::= (<A>)
<H> ::= p | q | r | ... | z

连接词的优先级是：-、/\、/、->、<->。

还考虑了关联性，例如p\/q\/r应该与 相同p\/(q\/r)。其他连接物也是如此。

我假装在 java 中制作了一个预测性的自上而下的解析器。我在这里没有看到歧义或直接左递归，但不确定我是否只需要考虑这是一个 LL(1) 语法。也许是非直接左递归？

如果这不是 LL(1) 语法，那么根据我的意图转换它所需的步骤是什么？

4

1 回答 1

3

这不是 LL(1)。原因如下：

LL(1) 文法的第一条规则是：

一个文法 G 是 LL(1) 当且仅当A --> C | DG 有两个不同的产生式时，以下条件成立：

  1. 对于没有终端a，C 和 D 都派生以 开头的字符串a。

这条规则是，这样在解析这段代码时就不会发生冲突。当解析器遇到 a(时，它不知道要使用哪个产生式。

你的语法违反了第一条规则。同一个产生式右边的所有非终结符，即所有的 Cs 和 Ds，最终都归约为 G 和 H，因此它们都派生出至少一个以 开头的字符串(。

于 2013-12-19T19:55:21.690 回答