文法&& LL解析器

Question

所以我有一個家庭作業，我已經花了2個小時試圖找出爲什麼這個語法將不與LL解析器工作：

<A> → a <B> 
<A> → a b <C> 
<B> → b d <D> 
<C> → d <E> 
<D> → m n 
<E> → x y 

可能有人請點我在正確的方向？我知道一個LL可能被絆倒的方式之一是，如果它遇到一個無限循環，我不相信它在這裏。

感謝

Answer 1

我相信，通過LL解析器你的意思是LL（1）語法分析器（一個LL解析器與1前瞻）

對於語法是由LL（1）語法分析器語法分析，它必須是LL（1）。語法必須遵守的一些事情是LL（1），如果它破壞其中之一，則稱爲LL（1）衝突。

• FIRST/FIRST衝突：

  對於每一個非末端，每條生產必須具有不相交的第一盤。 （第一組是一組可以開始在源自該受試者的句子的所有的終端。）

  EG：在上面的例子中，非終端具有兩個產生：

  <A> -> a <B> 
  <A> -> a b <C> 
  

  第一組每個作品如下：

  FIRST(a <B>) = {a} 
  FIRST(a b <C>) = {a} 
  

  你可以很清楚地看到這兩組相交。這是一個問題，因爲在LL語法分析器中，如果到達A處在堆棧中的點，並且要讀取的下一個符號是'a'，那麼解析器不知道是選擇<A> -> a <B>還是<A> -> a b <C>。

• FIRST/FOLLOW衝突：

  這發生時，對於一個特定的非終端A; FOLLOW(A)和FIRST(A)相交，並且A是NULLABLE。你的例子中不會出現這種特殊的衝突。

有關FIRST更多詳細信息，請與空的，我會

有關這些衝突的更多細節，以及一些示例，請參閱the Wikipedia page on LL(1) Conflicts。