Неоднозначная грамматика с LL (1) parse

Question

У меня возникли проблемы с этим. Я должен переписать следующую грамматику, чтобы заставить ее работать с анализом LL (1)

S → существительное | существительное и существительное | M, существительное и существительное

M → M, существительное | существительное

Первая проблема, которую я заметил, что грамматика была рекурсивной в производстве с заголовка M и исправить его, как этот

M → существительного Newpro

Newpro →, существительное Newpro

Но потом я заметил, что производство с заголовком S неоднозначно, но я не знаю, как это исправить, я попытался «разложить» существительное, но на самом деле я не уверен.

Вы можете мне помочь?

Благодарим за ответы.

Answer 1

Ваш отказ от рекурсии M является неполным - вы забыли правило NewPro → & epsilon;

После того, как вы добавите это, у вас осталась проблема S, что не является двусмысленным, но требует факторинга слева. Поскольку FIRST (M) & subseteq; FIRST (S), вам нужно сначала заменить M на S:

S → существительное | существительное и существительное | существительное Newpro, существительное и существительное

, а затем вы можете лево-фактор, который просто, в

S → S существительное '
S' → & эпсилон; | и существительное | NewPro, существительное и существительное

Теперь у вас есть проблема в том, что эта грамматика LL (4), но не LL (1), так как вам нужно 4 маркера для поиска конца последовательности NewPro. Это гораздо труднее решить, но это может быть исправлено.Сначала вам нужно потянуть , noun, в NewPro:

S '→ & epsilon; | и существительное | NewPro и существительное
NewPro →, существительное, | , Существительное Newpro

, а затем влево-фактор Newpro:

Newpro →, существительное Newpro '
Newpro' →, | Newpro

, а затем подставить в Newpro ':

Newpro' →, | , Существительное Newpro '

и левый фактор это тоже:

Newpro' →, Newpro '' Newpro '→ & эпсилон; | существительного Newpro '

Давать окончательная грамматика:

S → S существительное'
S»→ & эпсилон; | и существительное | NewPro и существительное
NewPro →, существительное NewPro '
NewPro' →, NewPro ''
NewPro '' → & epsilon; | существительное Newpro «

Что LL (1) и может быть использован непосредственно или немного упрощен путем замены Newpro обратно в S» и переименовании правила, чтобы избавиться от «-suffixes:

S → A существительного
A → & epsilon; | и существительное | , существительное B и существительное
B →, C
C → & epsilon; | существительное B