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

Question

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

L = а ^м б ^п с ^{т + п}

где т и п являются элементами из натуральных? Мой контекстно-свободная грамматика:

S → AB

→ АСА | ac

B → bcB | bc

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

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

S → Asc | B

B → bBc | bc

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

EDIT Спасибо, я думаю, что я получил его:

S → Asc | B

B → bBc | лямбда

Answer 1

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

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

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

В качестве подсказки, строки на русском языке являются именно струны образуют ^м б ^п с ^п с ^м. Другими словами, попробуйте посмотреть, можете ли вы создать m a's на передней панели и m c на задней панели, а затем переключить и сгенерировать n b в соответствии с n c. Возможно, вам захочется найти грамматику для ^m c ^m и посмотреть, можете ли вы ее приспособить.

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

B → Bbc

и

B → Ьс

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

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