Глава 5

(S - начальный символ)

начальный символ)

5.1. а) S->aYc Y->Ybb Y->b

б) Е->Е+Т Е->Т Т ->TxF Т -> F F->X

F->(E)(E -

в) P->D = S P->S D->*S D->x

S->D (Р - начальный символ)

5.2. а) Признак LR(1) отсутствует, так как грамматика неоднозначна. Ее можно заменить на E->E + i

E->i

б) Это - не LR(1)-грамматика, так как язык нельзя разобрать детерминированно. Соответствующей LR(1)-грамматики не существует.

в) Построив таблицу разбора, можно показать, что грамматика обладает признаком LR(0), а поэтому и признаком LR(1).

5.5. См. табл. У.З. Это- SLR(l)-грамматика.

5.4. Грамматика не обладает признаком LR(1), так как при чтении d с semi в качестве предварительно просматриваемого символа неизвестно, нужно ли приводить к DEC-LIST или нет. Эквивалентной SLR(l)-грамматикой является следующая:

PROGRAM->begin d semi X end X->d semi X Y->semi s Y

Y->E См. табл. У.4.

5.5. См. табл. У.5.

5.6. Грамматика не обладает признаком LR(1), так как язык нельзя разобрать детерминированно. Невозможно, например, на основании проделанного анализа и одного последующего символа определить, требуется ли 01 приводить к S.

5.7. а) Нет. б) Нет.

5.8. Это - не LR(l)-грамматика, так как при чтении «1» с последующим символом «:» 1(1)-анализатор не знает, выполнять приведение с помощью правила (4) или нет. Этой проблемы можно избежать, если во время лексического анализа заменить последовательность «: = » одним символом.

5.9. Ошибки могут быть обнаружены на более ранней стадии разбора (в смысле выполненных приведений, а не считанных символов) при меньшем числе действий приведения и большем числе показаний ошибок в таблице разбора.

5.10. Стеки можно объединить, так как нет таких действий в разборе, которые добавляли бы или исключали элемент из одного стека, и не делали этого по отношению к другому. Строго говоря, стек символов не требуется.

5.11. Каждый регулярный язык соответствует детерминированному конечному автомат), из которого можно получить lr(1)-таблицу разбора.

Таблица У.3

6 7 8 9 10 11 12 13 14

PROGRAM X Y begin semi d s end HALT S2

S7 S10 S7 SI0 S13

R2 R5

R5 R4

Таблица У.5

F ITEM ,

t \

HALT S3

S6 S7

7 R2

8 S9

S8 S10

R3 R3

9 R4 R4 10 I R5 R5

Глава 6

6.1. После идентификатора следует печать. Однако каждый знак операции следует помещать в стек и удалять из него и печатать после TERM или FACT

6.2. Е->Е+Т

Е-><А1>Е - Т

6.3. Нет.