while n = 0 or n = 1

do геad (n) do;

В процедуре предполагается, что строка из нулей и единиц заканчивается каким-либо другим целым числом.

3.7. ргос fixed point = void :

begin char in; read (in);

bool dig: = false;

if in = " + " or in = " - "

then read (in)

if digit (in) then dig: = true;

read (in)

while digit (in)

do read (in) od;

if in = ". " then error else read(in)

if digit (in)

then dig : = true ; read (in)

while digit (in) do read (in) od;

if not dig then error fi

3.8. Процедуры digit и error предполагаются. ргос train = void : begin rollingstock in;

read (in); if in = engine then read (in) else error ti;

if in = engine then read(in)

if in = truck else error

white in = truck do read(in) od;

if in =/= guards van

then error

3.9. Единственно возможным является массив строк.

3.10. Для обозначения этих двух видов можно использовать логическую переменную. Преимущество - исключаются переполнения от рекурсии, недостаток - всякий раз, когда действия компилятора для этих двух видов отличаются, переменную необходимо проверять.

Глава 4

4.1. а) Детерминированный, так как с обозначает середину строки, а вторую половину можно согласовать с первой с помощью стека.

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

в) Детерминированный по причинам, аналогичным изложенным в п. (а).

г) Детерминированный {см. п. (в)).

д) Недетерминированный, поскольку нельзя узнать, снимать ли «0» из стека для каждой считанной «1» или только для каждой второй считанной «1».

4.2. а) Воспользуйтесь леммой подкачки и предположите, что язык контекстно-свободный. Для достаточно большого k строку

akbkck

можно записать в виде

uvwxy

где \vwx\<k, \vx\ # 0 и для i>0 строка

uvwxy

также находится в языке. Допустим, что i=0, тогда uwy

находится в языке. Но uwy образуется из uvwxy путем исключения v и х, и так как \vwx\<k, v и х вместе не могут содержать множества а, b и с (т. е. vwx не может простираться по kb). Поэтому uwy должна все же содержать ka или kc, но не может содержать ka. b и с, поскольку \vx\# 0. Поэтому она не может включать равное число a, b и с и не находится в языке. Таким образом, возникает противоречие, и язык оказывается не контекстно-свободным.

б) Воспользуйтесь леммой подкачки и предположите, что язык контекстно-свободный Для достаточно большого простого числа k p = ak

можно выразить как uvwxy где \uwx\ <k, \vx\# 0 и для i>0

uvwxy

находится в языке. Такие строки имеют длину р + где р - длина uwy, a / - длина vx, которая не является нулем. Не все эти длины представляют собой простые числа. Например,

P + Pl

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

4.3. ргос Е-void : begin t;

end;

ргос Т= void: begin F;

ргос F= void: begin if in = "(" then read (in); E; if in =

then read (in) else error и elif identifier (in) then read (in) else error fi end;

ргос U = void : begin if in = " x "

then read (in); F U

end;

ргос G = void : begin if in = + then read (in); Т; G

4.4. а) Это следует из 2. . .

б) Любая s-грамматика удовлетворяет 1 и 2.

в) Преобразование можно осуществить с помощью правил грамматики, непрерывно заменяя самые левые нетерминалы до тех пор, пока не будет получена q-грамматика.

4.5. S есть начальный символ в каждом случае:

S->OS11

S->OS

S->1T

S->e

T->0S

T->e

3. S->1T S->0U T->0X

U->1X

T->1UU

U->0TT

X->S X->e

4.6. Правила для Е и Т не позволяют грамматике стать LL( 1)-грамматикой

Е->ТХ Х-> + ТХ Х->Е T->FY Y->xFY

4.7. Нет, так как х является направляющим символом в этих двух правилах для S.

4.8. Предложение, генерированное LL(1)-грамматикой, не может иметь два левосторонних вывода, так как иначе это означало бы, что два альтернативных правила для какого-либо нетерминала имеют общий направляющий символ.

4.9. См. табл. У.1. 4.10.См. табл. У.2.