Разработка компиляторов

       

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.,$]}

Граф переходов выглядит так:



Содержание раздела