Путаница в поиске первой и последующей левой рекурсивной грамматики

Question

Недавно я столкнулся с проблемой поиска первого и последующего

S->cAd
A->Ab|a

Здесь я путаюсь с первым из A, который является правильным {a}, {empty,a}, поскольку в производстве A есть рекурсия слева. Я запутался, стоит ли включать пустую строку в первый из A или нет. Любая помощь будет принята с благодарностью. ------------- --------------- отредактирован

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

S->SA|A
A->a

Мне нужно доказать, что эта грамматика не в LL(1) с использованием таблицы синтаксического анализа, но не могу сделать, потому что я не получил 2 записи в одной ячейке.

Answer 1

Во-первых, вам нужно удалить левую рекурсию, ведущую к

S -> cAd
A -> aA'
A' -> bA' | epsilon

Затем вы можете рассчитать

FIRST(A) = a         // as a is the only terminal nderived first from A.

EDIT :-

На ваш второй вопрос

S -> AS'
S' -> AS' | epsilon
A -> a

FIRST(A) = a
FIRST(S) = a
FIRST(S') = {a,epsilon}.

Идея удаления левой рекурсии перед вычислением FIRST() а также FOLLOW() можно узнать здесь.

Answer 2

Грамматика не является LL(1), если она имеет левую рекурсию, но после удаления левой рекурсии вы можете применить синтаксический анализ LL(1).