ОТВЕТЫ К УПРАЖНЕНИЯМ                 

sm_book.jpg (20496 bytes)

Поиск по номерам упражнений:

1.1. 1.2. 1.3. 1.4. 1.5. 1.6
2.1. 2.2. 2.3. 2.4. 2.5. 2.6.
3.1. 3.2. 3.3. 3.4. 3.5. 3.6.
3.7. 3.8. 3.9. 3.10. 3.11. 3.12.
4.1. 4.2. 4.3. 4.4. 4.5.  
6.1. 6.2. 6.3. 6.4. 6.5.  

 

1.1. 

  'Joe''s Pizza is "cute"'
  "Joe's Pizza is ""cute"""

На начало

1.2. 

  '-'16 0

На начало

 

1.3.

(a) e1 sX sX ; (b) e1 tX e2 tX e3 ; (c) t1 e2 or e1 t2 .

На начало

 

1.4.

(a) tX превращается в b ; (b) неудача; (c) e6 превращается в A(B) , e4 превращается в C D ; (d) неудача.

На начало

 

1.5. 

  Add { 
     (eX) '0' = eX;
     (eX) eY's'= <Add (eX) eY>'s'; }

На начало

 

1.6. 

  Addb {
     (eX'0')(eY s1) = <Addb (eX)(eY)> s1;
     (eX'1')(eY'0') = <Addb (eX)(eY)>'1';
     (eX'1')(eY'1') = 
            <Addb (<Addb (eX)('1')>)(eY)>'0';
     (eX)(eY) = eX eY; }

На начало

 

2.1. 

  $ENTRY Go { = <Job> }
  Job { = <Prout 'Please enter a line'>
          <Job1 <Card>>; }
  Job1 {
     0  = <Prout 'Good-bye!'>;
     eX = <Prout 'The translation is:'>
          <Prout <Trans-line eX>>
          <Job>; }

На начало

 

2.2. 

  (a) Sum-1            and         '#SUM_1 '
  (b) Sum'-'1          and         '#SUM -#1 '
  (c) as above
  (d) (9'+'25)'()'     and         '(#9 +#25 )#(#)'

На начало

 

2.3. 

  * Conv-xx, conversion of a file typed for Input
  * into a file for Xxin.
  * Call: refgo conv-xx+reflib  file-name
   
  $ENTRY Go { = 
         <Xxout (<Arg 1>) <Input <Arg 1>>>; }
  $EXTERN Input,Xxout;

На начало

 

2.4. 

  Merge { s1 s2 = 
        <Implode <Explode s1> <Explode s2>>; }

На начало

 

2.5. 

  (a)
      7  6 8  5  4    9    3 2  10      11    1
      eA ( t2 )  (  Sunday ) ( s.Day  s.Night )

Переменная  eA (No.7) является закрытой. 

  (b)
    1    3   2  4  5 7    9   8     10   6  11
    ( e.Word )  e1 ( ( e.Word ) e.Transl )  e2

No.3 является закрытым, No.4 открытым вхождением, No.9 повторным, No.11 закрытым. 

  (c) 
     1 8   9  10  7  6  2  11  12  13  4  5  3  
     ( e1 '+' e2 '+' e3 )  e1  '+' e2  (  e3 )

No.5 является закрытым, No.6 повторным, No.8 открытым, No.10 закрытым, No.11 и No.13 повторными.

На начало

 

2.6. 

  (a) ('di' left_arrow eA)('f' left_arrow t1)('ident' left_arrow eB)
  (b) ( left_arrow e1)('d' left_arrow sX)('iffi' left_arrow e2) ('ent' left_arrow e3)
  (c) Failure
  (d) ( left_arrow e1)( left_arrow e2)(A B C left_arrow e3)
  (e) (A(A B) left_arrow e1)((C) left_arrow eX)(D left_arrow e2)

На начало

 

3.1.

Второй знак уничтожения появится в ответе: 

  #Crocodile

Для выдачи сообщения в предложение следует вставить: 

  ()'#'e2 = <Prout 'Extra delete signs!'> 
               <Prout '#'e2>;

между предложениями 2 и 3.

На начало

 

3.2. 

  Cut {
     (e1)(e2) = <Cut1 (()e1) (()e2)>; }
   
  Cut1 {
     ((e.R1) tX e1) ((e.R2) tX e2) =
            <Prout (e.R1 tX)(e.R2 tX)>
            <Cut1 (()e1) (()e2)>;
     ((e.R1) tX e1) ((e.R2) tY e2) =
            <Cut1 ((e.R1 tX) e1) ((e.R2 tY) e2)>;
     eZ = ; }

На начало

3.3. 

  Equal {
     (sX e1) (sX e2) = <Equal (e1) (e2)>;
     ((e.T1)e1) ((e.T2)e2) = 
         <Equal1 <Equal (e.T1)(e.T2)> (e1)(e2)>;
     () () = T;
     (e1) (e2) = F; }
   
  Equal1 {
     T eA = <Equal eA>;
     F eA = F; }

На начало

3.4. 

  F { 
     sX e1 = <F1 sX()e1>;
      = <Prout 'No repeated symbols'>; }
   
  F1 {
     sX(e2)sX e1 = sX e2 sX;
     sX(e2)sY e1 = <F1 sX(e2 sY) e1>;
     sX(e2) = <F e2>; }

На начало

3.5.

При неявной рекурсии: 

  Isect {
     (sX e1)(e2 sX e3) = sX <Isect (e1)(e2 e3)>;
     (sX e1)(e2) = <Isect (e1)(e2)>;
     ()(e2) = ; }

Без применения неявной рекурсии: 

  Isect {
     (sX e1) eI (sX e2) = sX <Isect (e1)(eI e2)>;
     (sX e1) eI (sY e2) =  
            <Isect (sX e1) eI sY (e2)>;
     (sX e1) eI () = <Isect (e1) (eI)>;
     () eI (e2) = ; }

 

ЗАМЕЧАНИЕ: Был использован "закрытый'' формат функции Isect , который обеспечивает память еще для одного выражения, вначале пустого. Если бы форматом функции был Isect (e1)e2> , необходимо было бы ввести некоторую вспомогательную функцию.

На начало

3.6.

2c + t , где t = 1, если одна строка является началом другой. А при таком определении: 

  * Precedence-conservative
  * <Prec eC(e1)(e2)> == T(e1)(e2)
  *                   == F(e1)(e2)
  * where eC is the common part of e1 and e2.
  Prec {
     eC ()(e2) = T(eC)(eC e2);
     eC (e1)() = F(eC e1)(eC);
     eC (t1eX)(t1eY) = <Prec eC t1 (eX)(eY)>;
     eC (t1eX)(t2eY) = 
         <Addc eC <Pre-term t1 t2>(t1eX)(t2eY)>;}
   
  Addc { eC sT(eX)(eY) = sT(eC eX)(eC eY); }

время составляет c + t.

На начало

 

3.7. 

  String {
     e1 s2 = <String e1> s2;
      = T;
     e1(e2) = F e1(e2); }
   
  Pal { eX = <Pal1 ()eX()>; }
  Pal1 {
     (eL) s1 e2 s1 (eR) =
             <Pal1 (eL s1) e2 (s1 eR)>;
     (eL)(eR) = T eL eR;
     (eL) eI (eR) = F eL eI eR; }

На начало

3.8. 

  Fact {sN = <Loop F(1) I(1) N(sN)>; }
   
  Loop {
     F(sF) I(sN) N(sN) = <* sN sF>;
     F(sF) I(sI) N(sN) = 
           <Loop F(<* sI sF>) I(<+ sI 1>) N(sN)>;
        }

На начало

3.9. 

  * Recursive definition
  Reverse {
     s1 e2 = <Reverse e2> s1;
      = ; }
   
  *Iterative definition
  Reversei { eX = <Revit ()(eX)>; }
   
  Revit {
     (eR)(s1 e2) = <Revit (s1 eR)(e2)>;
     (eR)() = eR; }

На начало

3.10.

См. функцию Pprout в reflib .

На начало

3.11. 

  * Multibracket Backtracking
  Mback {
    [e1(e2 ^e3)e4] = <Mback [e1 ^(e2 e3)e4]>;
    [.e1  ^e2.] = e1 e2; };

Функция достигает результата ,перемещая указатель обратно к началу выражения. Тот же результат может быть получен при перемещении указателя вперед.

На начало

3.12.

(a) 

  * Call: <Tree [.  ^sX.]>
  * where sX is the root node.
   
  Tree {
  *1. A leaf. Jump over.
    [e1 ^sX'.'e2] = <Tree [e1 sX'.' ^e2]>;
  *2. A node with subtree. Enter it.
    [e1 ^sX(eT) e2] = <Tree [e1 sX( ^eT)e2]>;
  *3. A 'hanging' node. Generate subtree.
    [e1 ^sX e2] = <Tree [e1 ^<Subtree sX> e2]>;
  *4. Up the tree.
    [e1(e2 ^)e3] = <Tree [e1(e2) ^e3]>;
  *5. End of work
    [.e1 ^.] =  e1; }

(b) Все те узлы, обработка которых завершена, находятся в левой мультискобке, причем в формате sX(eS) , где eS является обработанным поддеревом для sX . Те узлы, обработка которых уже начата, но не завершена, также находятся в левой мультискобке, но в формате 

  sX)( ,

поскольку левая круглая скобка, следующая за sX, представляется инвертированной парой скобок. Поэтому указанное выше предложение 3 модифицируется как: 

  *3. A 'hanging' node. See whether repeated.
    [e1 ^sX e2] =  <Tree1 
        (<Rep sX[. ^e.ML(e1 ).]> )(sX e2)e.MR>;

Две новые функции определяют следующим образом: 

  * See whether the subtree was already built
  Rep {
  *1. Repeated node found.
    sX [e1 ^sX(eS) e2] = 
                Yes(eS) <Mback [e1 ^sX(eS) e2]>;
  *2. A different symbol.
    sX [e1 ^sY e2] = <Rep sX [e1 sY ^e2]>;
  *3. Enter a parenthesis
    sX [e1 ^(e2)e3] = <Rep sX [e1( ^e2)e3]>;
  *4. Exit a parethesis
    sX [e1(e2 ^)e3] = <Rep sX [e1(e2) ^e3]>;
  *5. End of work.
    sX [.e1 ^.] = No e1; }
   
  Tree1 {
  *1. Repeated node. Cope subtree.
    (Yes(eS)e1)(sX e2)e.MR = 
             <Tree (e1)(sX(eS) e2)e.MR>;
  *2. New node. Compute subtree.
    (No e1)(sX e2)e.MR = 
             <Tree (e1)(<Subtree sX> e2)e.MR>;
        }

На начало

4.1. 

  Addop {
     e1 s.Op e2, '+-': eX s.Op eY =
              (e1) s.Op e2;
    e1 = <Prout 'No additive operations'>; }

На начало

4.2. 

  Less {
    (e1) e2, <- e1 e2>: '-'eZ = T;
    (e1) e2 = F;
    eA = <Less <Format eA>>; }
   
  Lesseq {
    (e1) e2, <- e2 e1>: '-'eZ = F;
    (e1) e2 = T;
    eA = <Lesseq <Format eA>>; }
   
  Format {
    '-'s1 e2 = ('-'s1) e2;
    '+'s1 e2 = (s1) e2;
    s1 '-'e2 = (s1) '-'e2;
    s1 '+'e2 = (s1) e2;
    s1 e2 = (s1) e2; }

На начало

4.3. 

  S123 {
     eA 1 e1, e1: 
             {eB 2 e2, e2:
                      {eC 3 eD = T;
                       eC = F };
              eB = F };
     eA = F }

На начало

4.4. 

  Fa {
     e1 sX sY e2, 
         <Less sY sX>: T, 
         <Less 100 <+ sX sY>>: T = sX sY;
     e1 = <Prout 'No such pair'>; 
     }
  Fb {
     e1 sX sY e2, <Less sY sX>: T,
          <Less 100 <+ sX sY>>:
          {T = <Prout 'It is greater'>;
           F = <Prout 'It is not greater'>; 
          };
     e1 = <Prout 'No such pair'>; 
      }

На начало

4.5. 

  * Dictionary is stored as DICT
  $ENTRY Go { = 
            <Br 'dict='<Xxin 'DICT'>>
   	 <Prout 'Type in additions'>
            <Addition <Input>> ;
             }
   
  
  Addition {
      =   <Prout 'No additions. Go ahead.'> 
          <Job>;
     eX = <Prout 'OK. Go ahead.'> 
          <Xxout ('DICT') eX<Cp 'dict'>>
          <Br 'dict='eX<Dg 'dict'>>
          <Job>;
            }
  $EXTRN Input,Xxout,Xxin;
    ...  etc. as before

На начало

6.1. 

  Fun-n {
    sN eA = <Mu <Implode 'Fun'<Symb sN>> eA>; }

На начало

6.2.

Вставьте между третьим и четвертым предложениями: 

  '*'e1 = <Prout 'Error: no upgrade of 'e1>;

На начало

6.3. 

  (a) '*'((Add) (35)16)
  (b) '*'((Up) ('*V'((F) ('*VE'1)'*VE'2)) '*V!'('*E'3))
  (c) <Comp 'A*B'>

(d)   Невозможно. Это эквивалентно <Dn 'A*B'> , а ни одно выражение не становится активным, будучи погруженным в метакод. Сравнить с Упражнением 6.4(b).

На начало

6.4. 

  (a)  51
  (b)  'A*B'

На начало

6.5.

Следует модифицировать две функции: 

  Check-end {
        = <Prout 'End of session'>;
     '*'Error = <Job>;
     eX = <Out <Ev-met eX>>; }
   
  Out {
     0 eX = <Prout 'The result is:'>
            <Prout <Up eX>> <Prout> <Job>;
     1 eX = <Prout 'Result depends on unknowns'>
            <Prout> <Job>;
     2 eX = <Prout 'Recognition impossible'>
            <Prout 'View field in metacode:'>
            <Pprout eX> <Error eX>;
       }
  $EXTRN Pprout,Error;

На начало