Определения грамматика, является ли LL с помощью дизъюнктного тестом

Question

У меня есть три грамматик:

А -> Ab | b | CBB

B -> aB | ba | aBb

C -> aaA | b | Cab

мне нужно «определить, является ли [они] LL грамматик, выполнив дизъюнктный тест, показывающий первые наборы каждых ОРЗ каждого нетерминала.

Это то, что я до сих пор ...

а -> авы | B | С

первый (Ab) = а

первый (б) = б

первых (С) = Aaa = а

Это тот, с которым я столкнулся. Правильно ли я делал CBB? Если это так, я бы сказал, что они пересекаются &, правило не проходит тест. (справа?)

B -> aB | ba | ABB

первый (Ab) = а

первый (BA) = B

первый (ABG) = а

Они пересекались &, таким образом, это правило не проходит тест.

C -> aaA | b | Cab

первый (ааа) = а

первых (б) = б

первый (Cab) = C

Они не пересекались &, таким образом, это правило проходит

Answer 1

Точки теста, чтобы увидеть, если, глядя на первый терминал, вы можете указать, какое правило использовать (требование для LL). Его довольно очевидно для B, что есть 2 правила, которые могут применяться для терминала a; его также довольно очевидно, что каждое правило для C начинается с другого терминала. И вы можете видеть, что возможные первые терминалы для C (и, следовательно, CBB) перекрываются для других правил для A.

Итог: выглядит хорошо (хотя, если вы остановились на одном терминале для CBB и случилось с выбором c, вы пришли бы к неверному выводу).

Answer 2

Я считаю, что FIRST устанавливает для правил A {a}, {b} и {a, b, c}. Грамматика не LL, потому что она не проходит тест на попарное рассогласование из-за наличия хотя бы одного пересечения. На самом деле в этом случае есть два пересекающихся терминала: a и b.