Это грамматика LL (1) грамматика?

Question

Это грамматика LL (1)? Будет ли проблемой то, что S может быть как E/S, так и E?

S -> E / S 
S -> E
E -> letter 
E -> ‘ S ’

Может ли он получить ‘a / e / ‘g / s’ ’ / q, как это?

S =>  E / S 
  => ‘S’ / S 
  => ‘E / S’ / S 
  => ‘a / S’/ S
  => ‘a / E / S’ / S
  => ‘a / E / ‘E / S’’ / S
  => ‘a / e / ‘g / s’’ / q

Answer 1

Напомним, что грамматика G равна LL(1) тогда и только тогда, когда A → u и A → v являются отдельными произведениями в G, выполняются следующие условия:

1. Для нет терминал a do u и v получают строки, начинающиеся с a.
2. Не более одного из u и v получают пустую строку λ
3. Если u ⇒* λ, то v не выводит никаких строк, начинающихся с терминала в FOLLOW(A).

Второе и третье условия тривиальны, потому что никакая последовательность терминальных и нетерминальных символов не выводит пустую строку в вашей грамматике. Теперь рассмотрим произведения S → E / S и S → E. Можете ли вы найти два вывода S ⇒ E / S ⇒* au и S ⇒ E ⇒* av, где a является терминалом, который нарушает первое условие? Этот вопрос, очевидно, домашнее задание, поэтому я оставлю вам ответ на этот вопрос.