Находить LL(1) грамматику?

Question

Как найти грамматику LL(1) для языка:

L = a^m bⁿ c^{m + n}

Где m и n элементы натуральных элементов? Моя контекстно-свободная грамматика:

S → AB

A → acA | переменный ток

B → bcB | До нашей эры

Может ли кто-нибудь сказать мне, если я на правильном пути?

редактировать: мой новый CFG

S → aSc | В

B → bBc | До нашей эры

Однако я думаю, что у меня может быть ошибка относительно LL(1) в том, что оба вывода B оба начинаются с b..это правильно?

РЕДАКТИРОВАТЬ Спасибо, я думаю, что я получил это:

S → aSc | В

B → bBc | лямбда

Answer 1

Есть две основные проблемы с вашей грамматикой:

1. В настоящее время вы можете генерировать некоторые строки не на языке. Например, ваша грамматика может генерировать acacbcbc, чего нет в языке.

2. Ваша грамматика не LL(1), потому что у вас есть многочисленные ПЕРВЫЙ / ПЕРВЫЙ конфликты. Например, пара произведений A → acA и A → ac начинаются с a, поэтому, учитывая нетерминал A и символ a, вы не можете определить, какую продукцию применить.

Как подсказка, строки в вашем языке - это в точности строки вида a^m bⁿ cⁿ c^m. Другими словами, попробуйте посмотреть, можете ли вы генерировать ma спереди и mc сзади, а затем переключаться и генерировать nb, соответствующие n c. Возможно, вы захотите сначала найти грамматику для^m c^m и посмотреть, сможете ли вы ее адаптировать.

РЕДАКТИРОВАТЬ для новой грамматики: это выглядит намного лучше! Тем не менее, у вас все еще есть ПЕРВЫЙ / ПЕРВЫЙ конфликт в производстве

B → bBc

а также

B → bc

Кроме того, ваша грамматика не может генерировать строки ac или ε. Вы должны быть в состоянии решить обе эти проблемы, устранив конфликт FIRST/FIRST. Подсказка: как вы можете заменить второе производство на то, которое не позволяет генерировать персонажей?

Надеюсь это поможет!