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

Question

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

A -> aB |б |CBB

B -> aB |ба |aBb

C -> aaA |б |caB

Мне нужно "определить, являются ли [они] грамматики LL, выполняя попарно непересекающийся тест, показывая первые наборы каждой RHS каждого нетерминала....

A -> aB | b | CBB

first (aB) = a

first (b) = b

first (CBB) = aaA = a

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

B -> aB | ba | aBb

first (aB) = a

first (ba) = b

first (aBb) = a

Они пересекаются, и поэтому правило не проходит тест.

C -> aaA | b | caB

first (aaA) = a

first (b)= b

first (caB) = c

Они не пересекаются и, таким образом, правило проходит

Answer 1

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

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

Answer 2

Я полагаю, что ПЕРВЫЙ набор для правил А равен {a}, {b} и {a, b, c}.Грамматика не является LL, потому что она не проходит тест парного дизъюнкта из-за наличия хотя бы одного пересечения.На самом деле в этом случае есть две пересекающиеся клеммы, a и b.