Разработка компиляторов
LALR(1)-анализатор
Таблицы LR(1)-анализатора могут оказаться очень большими, ведь даже маленькая грамматика нашего примера привела к автомату с двенадцатью состояниями. Таблицы меньшего размера можно получить путем слияния любых двух состояний, которые совпадают с точностью до символов входной строки (lookahead symbols).
Пример. Рассмотрим грамматику G1 с правилами:
S -> AA A -> aA A -> b
Пополним эту грамматику правилом S' -> S.
Для этой грамматики мы получим следующие состояния:
0: {[S'->.S, $], [S->.AA, $], [A->.aA, a], [A->.aA, b], [A->.b, a], [A->.b, b]} 1: {[S'->S., $]} 2: {[S'->A.A, $], A->.aA, $], [A->.b, $]} 3: {[A->a.A, a], [A->a.A, b], [A->.a.A, a], [A->.a.A, b], [A->.b, a], [A->.b, b]} 4: {[A->b., a], [A->b., b]} 5: {[S->AA. $]} 6: {[A->a.A, $], [A->.aA, $], [A->.b, $]} 7: {[A->b., $]} 8: {[A->aA.,a], [A->aA.,b]} 9: {[A->aA.,$]}
Граф переходов выглядит так:
