
                       ..

                           

                 

                           

                            1993



       ,
       
      1991-
1993  .     ,          
        
.
      "" 
:       ,  
,   .       
   ""    
 .       
                 
         .  
     .
                   
 ,        
.



 1.                                             6
  1.1.                6
  1.2.                                   7
 2.                                   11
  2.1.               13
  2.2.                                      14
  2.3.   
                              17
  2.4.   
                         20
  2.5.               22
  2.6.    LEX             27
 3.                                31
  3.1.                           31
  3.2. -            33
    3.2.1.   -                     33
    3.2.2.  FIRST  FOLLOW                         37
    3.2.3.  
                                 39
    3.2.4. LL(1)-                                 40
    3.2.5.                             41
    3.2.6.                                 43
    3.2.7.                                  44
    3.2.8.           46
    3.2.9.           48
  3.3.  -  -                49
    3.3.1.                                            49
    3.3.2. LR(k)-                                51
    3.3.3. LR                                     56
    3.3.4.    -             62
    3.3.5.           63
 4.                 64
  4.1.               64
  4.2.                                       64
  4.3.                          69
  4.4.                  72
  4.5.                    73
 5.                              74
  5.1.                     74
  5.2.                       76
  5.3.                                  79
    5.3.1.                    79
    5.3.2.                     80
    5.3.3.                   81
 6.            85
  6.1.            85
  6.2.   -2                             86
  6.3.                         90
 7.                98
  7.1.                98
  7.2.                                99
  7.3.                   102
  7.4.                                   103
  7.5.                                    104
  7.6.                           108
  7.7.            109
 8.                                      110
  8.1.                                         110
  8.2.                        113
  8.3.                                    122
  8.4.                                 124
  8.5.                             130
  8.6.    
                                    132
  8.7.                        143
  8.8.                           151
  8.9.    
                                     155
    8.9.1.                            155
    8.9.2.    -           158
    8.9.3.             165
 9.         169
  9.1.                                         169
  9.2.  Yacc                                        172
                                                 175

                       1. 

1.1.     

            
 .     ,    
      .    
       ,   
 ,    . 
               
.     , , 
,           
" " (, , -2,   ), 
    (,   
   ).  ,  
 ,          ,
,      .
           .
,   , -2        
IBM/PC   .
   ,        
         . 
        .  
       ,    
,   .     
   Intel-80X86.   
   8086, 80186, 80286, 80386, 80486, 80586
     ,  , 
  ,       ,  ,  
()   . ,    
 (   ).      
 Motorola 68010, 68020, 68030, 68040.
           
        .  
   CISC, RISC.   , 
Intel, Motorola, Sun, DEC,     
 RISC-.  ,      
                  
 .
,               
.    , , 
         (      
 ).         
 ,     - (Cray, CDC 
),        (,  IBM/RS-6000)  
   (,     I-
860).  ,             
           .   
    ,        
       ,
        
       .

1.2.  

         
  . 1.1.
            ()    ,
    ,    -
             .   
,               
,              
.             
   :          ,   
      ,   
 ,     .
            
      ,     
        .   
             (,  
  ).

      +-------------+   +-------------+ +-----------------+
      |  |-->|  | |+---------------+|
  |       |   +-------------+ ||   +||
 ---->|-------------|------------------>||    ||-+
      |     |                   ||      || |
      |     |                   |+---------------+| |
      +-------------+                   +-----------------+ |
            +-----------------------------------------------+
            v
 +-------------------+  +-------------+ +------------------+
 |     |->|  | |+----------------+|
 |             |  +-------------+ ||   ||
 |-------------------+----------------> ||  +      ||+
 | --   |                  ||   |||
 |   |                  |+----------------+||
 +-------------------+                  +------------------+|
           +------------------------------------------------+
           v
  +-------------+   +-----------++----------------------+
  |  |-->|||+--------------------+|
  |       |   +-----------+||    ||
  |-------------|--------------->||     ||-+
  |   |                || +   || |
  |   |                |+--------------------+| |
  +-------------+                +----------------------+ |
             +--------------------------------------------+
             v
     +----------------+    +--------------------------+
     |       |    |+------------------------+|
     |  |    ||      ||
     |   |    || (, -     ||
     |----------------|--->||  ,   .)||---+
     | -  |    |+------------------------+|   |
     +----------------+    +--------------------------+   |
             +--------------------------------------------+
             |  +-------------------------------------+
             v  v                                     |
     +-------------+   +-------------------------+    |
     |  |   |+-----------------------+|    |
     |-------------|-->||     ||    |
     |    |   || ( )||--> |
     |       |   |+-----------------------+|    |
     +-------------+   +-------------------------+    |
             +----------------------------------------+
             |
             v
     +-----------------------+     +-------------+
     |          |     |+-----------+|
     |-----------------------+---->||           ||
     |  ,      |     ||  ||
     |           |     ||     ||
     |   .|     |+-----------+|
     +-----------------------+     +-------------+

                       . 1.1

         ()  
(    ,             ,
  .).
      -  
.   ,        ,
       -  
.          LL(1)-
 (    -  ),  LR(1)-
    (LR(0), SLR(1), LALR(1)  ). 
                
 ,  LR(1) -   
   .
     
     .   
    ,    
.
        
 ,        -
  .            "-
",         ,  
 ,  ,   . 
           ,
         ,  
   () .
   ,         
,    .    
         
.                    
   ,     
 .      
       ,            
 .
               
.             /
     .        
        
 .     (
)     -.      
      
,  , ,   .
      .    
   -  -,  
.  -   
   .     
       ,    -  
   .    
    ,    
           
.          ,
     ,     ,   
    ..
,       -       .
            ,  
 (  ) .    
      ,  
 ,     ,
      
.      , 
     ,     ,  
   ,       
.
,                   
 ,   .    
                
     ,    
     ,               
 .

 2.  

     -   ,
          ,   
 ,   ,  ..   
       .     
        
,     -  ,      ,
   ().     
       .    , 
         
(   ).       -
    ('\'      
"...").
          .    
                (,      ,
,      ..),  ,
.                
  (      -).  
,    -    
.      (,  /1)  
          
     .
       
          :       
,       ,  
     , 
   ,    ,  
 ,         
   (,      ..).  
       .  
       (,    -
).      - ,   
(,       )       
 .       
    ,   
,       
     .     ,      
   ,   -  
,     . 
    -    
 (,     ..),       
,    .
                    
     ,        ,
    "  ".     (.
2.1)      , 
 (.  2.2)          
   ( ,   ,  
     " ", 
       ).    
     ,    
,           
             
            ,         
         (,
,    ..).            
       .

                             +------------------+
                             | .  |<-----+
                             +------------------+      |
                                      ^|               |
 +---------------------+              ||          +----------+
 | ,  | ... |           ||          |  |
 +---------------------+       ||          +----------+
           |                          |v               ^
           |    +---------+  +------------------+      |
           +--->|  |  | .  |------+
                +---------+  +------------------+
                       " "

      . 2.1                     . 2.2

           
 .    
       .         
  ,     ,      
    ,      
  ,         ,  
, .    ( ,
     )  
 .     
       
 ,   .

2.1.     

 T  -  .     T
      ( '<-' 
  ,  '<=' ):

  (1) {}  ( ) -    
T;

  (2) {a}  -     T   a<-
T;

  (3){} -        T  (e  -  
);

  (4)   P   Q -        T,  
   

     () P U Q (),

     () PQ (, ..  pq, p<-P, q<-Q),

     () P* (: P*={e} U P U PP U...;

  (5)               
 T.

,      T     ,
    {},   {e},   {a}    a<-T,
        
  ,   .
              
        ,    
   .    
 PP*      P+   ,   
,   .    
       *,       ,
,     U,            
   '|'.  ,  0|10*    (0|(1(0*))).
 ,     

d1 = r1
d2 = r2
.......
dn = rn

 di  -   ,   ri -  
   T U  {d1,d2,...,di-1}, ..  
      .  , 
 ri      , 
              
 .

  2.1.             
  

 -   

 =  (|)*
 = {a,b,...,z}
 = {0,1,...,9}

    -   

 = +
_ = .  | 
 = (  ( + | - |  )  ) | 
 =  _ 

,            
        ,    
.   :     
   ,   .
       
   .  ,  
   ,        
.

2.2.  

      ()  -    
M=(Q,T,D,Q0,F), 

  (1) Q -   ;

  (2) T -     ;

  (3) D  -   ,    QxT  
        Q      
  ;

  (4)  Q0<=Q  -        
;

  (5) F<=Q -   .

       ()   -    
M=(Q,T,D,q0,F), 

  (1) Q -   ;

  (2) T -     ;

  (3) D  -   ,     QxT  
  Q           
;

  (4) q0<-Q -    ;

  (5) F<=Q -   .

             
  ,     .     
      ,
     .   
         
 (. 2.3).

                    +-----------+
                    |  |
                    +-----------+
                          |
                          v
     +---------------------------------------+
     |                  | a | .............. |
     +---------------------------------------+
               
               
             

                       . 2.3

   ,   
        
.   (q0,w)   ,    
(q,e),  q<-F,   ( ).

                 |
                 v
               +---+
               | 1 |
               +---+
                 | 
       +------   v
       |       \---+ (,,"." +-----+
       |  | 2 |--------------->|| 3 ||
       |       /---\                +-----+
       +------   |. \ E
                 v   --------------------+
               +---+                     |
               | 4 |                     |
               +---+                     |
                 |                  |
       +-------  v                       |
       |       \---  ,   +-----+ |
       |  | 5 |------------>|| 6 || |
       |       /---              +-----+ |
       +-------  |E                      |
                 v                       |
               +---+                     |
               | 7 |<--------------------+
               +---\
             +,- |  \ 
                 v   \
               +---+  |
               | 8 |  |
               +---+  |
            |   /
       +-------  v  /
       |       \---/   +------+
       |  | 9 |--------->|| 10 ||
       |       /---           +------+
       +-------

                   . 2.4

     M         |-,
   :     ,  
      (q1,w1)   (q2,w2).
 |-+   |-*  - ,  ,    
-    |-. , 
  M       w,    (q0,w)|-*(q,e)  
   q<-F.    ,      (,
)   M,  (  L(M)),  
  ,   M. ..

L(M)={w | w<-T*  (q0,w)|-*(q,e)   q<-F}

              
,         , 
,   a,    p  q, 
    (q,a)->p.    
  (    ).

 2.2.           
. 2.4.

2.3.     
        .

            
     [1].  
 (  ) r   : (r)#. 
            
 :             
      "#",    ,  
 "#"    .
     ,   - 
,      -  "." (),
"U" (), "*" ().
    (  e-)  
       ,     ,    
    ,   ,    ,
 .
  ,    T - -, 
  :  nullable,  firstpos,  lastpos    followpos.
 nullable,  firstpos    lastpos      
,   followpos -     .   
,   nullable,    . 
followpos     .
  firstpos(n)        n  
       , 
        ,  
      n.  ,  lastpos(n)  
 ,       
,        n.  
 n,     (.. ,     n
  )         ,  
nullable(n)=true,     false.

  n      nullable(n)     firstpos(n)    lastpos(n)
---------------------------------------------------------
   |   true      |       0          |     0
--------+-------------+------------------+--------------
 i  |   false     |      {i}         |    {i}
--------+-------------+------------------+--------------
   U    | nullable(a) |   firstpos(a)    | lastpos(a)
 /   \  |    or       |    U             |    U
a     b | nullable(b) |   firstpos(b)    | lastpos(b)
--------+-------------+------------------+--------------
   .    | nullable(a) | if nullable(a)   |if nullable(b)
 /   \  |   and       | then firstpos(a) |then lastpos(a)
        |             |    U firstpos(b) |  U lastpos(b)
 a   b  | nullable(b) | else firstpos(a) |else lastpos(b)
--------+-------------+------------------+--------------
   *    |             |                  |
   |    |    true     |   firstpos(a)    |  lastpos(a)
   a    |             |                  |
--------------------------------------------------------

                           . 2.5

    nullable  firstpos 
 . 2.5.   lastpos  .

                    {1,2,3}.{6}
                         /   \
                {1,2,3}.{5} {6}#{6}
                     /   \             |   followpos
            {1,2,3}.{4} {5}b{5}       --------+-------------
                 /   \                   1    |    {1,2,3}
        {1,2,3}.{3} {4}b{4}              2    |    {1,2,3}
            /    \                       3    |      {4}
    {1,2}*{1,2}  {3}a{3}                 4    |      {5}
         |                               5    |      {6}
    {1,2}U{1,2}                          6    |       -
       /   \                          ----------------------
  {1}a{1} {2}b{2}
                    . 2.6              . 2.7

 2.3.  firstpos  lastpos   (a+b)abb#
   .  2.6.          
firstpos,   - lastpos.  ,      
     .
 i  - ,   followpos(i)      j
,       ...cd...,   
,   , ,    i  -    
 c,  j -  d.
 followpos         
    

  1.  n -     "." (),
a,b -   .        i,   
lastpos(a),            followpos(i)
 firstpos(b).

  2.  n -     "*" (), a -
  .             i,    
lastpos(a),            followpos(i)
 firstpos().

    2.3   followpos   .
2.7.
     followpos             
            
.

 2.1.      .

      Dstates  
.      . 
    firstpos(root),  root - 
    ,  - 
,  ,    "#".
  Dstates     
firstpos(root).

   while    T  Dstates do
       T;
      for    a<-T do
           a  T  
         p1,...,pi,   S=U followpos(pi)
                             i
          S    S   Dstates, 
            S  Dstates
         (. 2.8)
           Dtran  T  a  
         Dtran(T,a)=S.
      end;
   end;

  2.3  T={1(a),2(b),3(a)}. 
      . 2.9.      
    ,   
.  2.10.          
,   {1,2,3},        
  [1,2,3,6].

                         a: {1,2,3,4}  T={1(a),2(b),3(a)}

                         b: {1,2,3}       /    /     \
                                       v    v       v
                                      {1,2,3}      {4}

+------------+ +----+    a: {1,2,3,4}  T={1(a),2(b),3(a),4(b)}
|+----+      | |    |    b: {1,2,3,5}     /    /    |    |
||b   |      | |    |                    v    v     v    v
||----+------+-+>Sb |                   {1,2,3}    {4}  {5}
||{pb}|+----+| |----|
|+----+|a   || |    |    a: {1,2,3,4}  T={1(a),2(b),3(a),5(b)}
|      |----++-+>Sa |    b: {1,2,3,6}     /    /    |    |
|      |{pa}|| |    |                    v    v     v    v
|      +----+| |    |                   {1,2,3}    {4}  {6}
+------------+ +----+
                         a: {1,2,3,4}  T={1(a),2(b),3(a),6(#)}
                         b: {1,2,3}       /    /    |
                                         v    v     v
                                        {1,2,3}    {4}

      . 2.8                        . 2.9

         +--------------------b--------------------+
         |           +-----------a--------------+  |
     +-+ |       +-+ | +----a-----+             |  |
     |b| |       |a| | |          |             |  |
     V | V   a   V | V V   b      |       b     |  |
---->{1,2,3}--->{1,2,3,4}----->{1,2,3,5}----->[1,2,3,6]

                        . 2.10

2.4.     
         

       
,    [2].

 2.2.      .

 1.           
 :     S-F.

 2.             
 new (. 2.11):

  for   G   do
            G   , 
            s   t  G   
               ,   
             a  s  t 
             a        
             ;
            G  new   
            
        end;

             +---+              +-+  +-+
       +-----|s,t|-----+        |s|  |t|
       |     +---+     |        +-+  +-+
       |a             a|         |    |
       |     +---+     |         v    v
       +---->|   |<----+        +-+  +-+
             +---+              | |  | |
                                +-+  +-+
                    . 2.11

 3.   new=,   res=        4,
   2  :=new.

  4.                
 res            .
     '.  s -
. ,      a    M  
  t.  r -   t.  ' 
   a   r    a.        '  -
  ,          s0
  M,              '   -
   F.  ,        res  
       F,     
F.

 5.   '     , ..    d,
            
    ,      '.    
,    .

2.5.   

   ,       ,      
.         
   :      (
   )      (,
,    ..).     ,    
    .         
,      .    
-,         
      ,    
.   ,   
       :  
  ,              .  
       , ,
 .
                   
    .      -
   .    ,      -  
  .         
       :      
       -  
          
 -  , ,  ,   
        
 .         
    (.  7),    ,  
            
             
,       .        
      
 ,      
  .
    (,  /1   )  
      .
              
 .     ,  ,
 :

DO 10 I=1,25 
DO 10 I=1.25

      -    DO,   -
  .   ,         
  ,        
 .
    /1.    :

IF THEN THEN THEN = ELSE; ELSE ELSE = THEN 
DECLARE (ARG1, ARG2, ...., ARGn) ...

       ,      ")", 
,       DECLARE      
.              
       
   .
        .
    ,   
      , -      
       .
,         
   :

while (Insym<='9' & Insym>='0') do
 ...
end;

             
     :

while (Insym in ['0'..'9']) do
 ...
end;

            
.       
 [2].   LETTER,  DIGIT, BLANK,  SLESS  -  
 .    MAP,   
,  -  .   MAP
 :

      MAP['A']:=LETTER;
          ........
      MAP['z']:=LETTER;
      MAP['0']:=DIGIT;
           ........

      MAP['9']:=DIGIT
      MAP[' ']:=BLANK;
      MAP['<']:=SLESS;
          ........

      :

while (Map[Insym]=Digit) do
 ...
end;

        
.     ,      
 .

                                        +----------+
                    ------------------->|  |
      +---+ f  +---/     |  if |
      | i |--->|   |                    +----------+
      +---\    +---\    +---------------+
        |  \        ---------------->|  |
       n|   \                        +---------------+
        |    \                           ^ ^  ^
        |     \  f    t             | |  |
        v      --------------------------+ |  |
      +---+        t                     |  |
      |   |--------------------------------+  |
      +---+                                   |
       t|                                     |
        v                                     |
      +---+                      |
      |   |-----------------------------------+
      +---+
        |     
        v
+--------------------+
|   int |
+--------------------+

                         . 2.12

      ,    
 .  . 2.12    .
      
 ,   [3]:

 case 'i':
 if (cp[0]=='f' &&!(map[cp[1]] & (digit | letter)))
 {cp++; return IF;}
 if (cp[0]=='n' && cp[1]=='t'
  &&!(map[cp[2]] & (digit | letter)))
 {cp+=2; return INT;}

 cp  -    .    map 
  .
       , 
         
   .     ,      
    .   
   .
    ,   - 
   N (. 2.13).

   N         N
 +----------------+               +-------------------+
 |       |        |               |  # |            # |
 +----------------+               +-------------------+
          ^    ^                         ^   ^
          |    |              |   |
          |  (cp)           | 

       . 2.13                   . 2.14

       ,     
       N .  
       N   ,       
   (eof).       :
   .      
.        
.    ,  ,  , 
    ,         .
            
,     .      
   ,    
N  .          
 ,        N    
     .
       ,  
           .    
,       ,  
.         ,   
      '' 

'#' (. 2.14).

           
      '#'        
 ,       .
          (.  2.15).
              
  (   -          
).                 
   .       
   '#'   ,   
(,   '#'       ).
      ,        
          .     
     ,   
            
.        
.     ,      
  .

      +----------+                   +-----+
      |     N    |                   | N   |
      v          v                   v     v
 +------------------+           +-------------+
 |    |          |\n|           |    |     | #|
 +------------------+           +-------------+
          |   |   |         |      |  |
          |   |              |      |
          |                 |
   )   <        )  

                    . 2.15

           
   .     
    .

2.6.    LEX

         
      .    ,  
         () , 
   .    
     LEX,          
 . LEX-    :


%%
 
%%
 

      ,  
     .      LEX
  

p1 { _1 }
p2 { _2 }
...............
pn { _n }

   pi -   ,    _i -
 , ,    
  ,        pi  
.  LEX    .
               ,
   .    
     .
 ,  LEX, 
      .   
            
      ,        
 ,           
   pi.      _i. 
,  _i       
.     , ..   
  ,          
     ,               
 .      
       
     . 
        
 -   .         
   yylval.

 2.4.  . 2.16  LEX-.

%{ /*  LT,LE,EQ,NE,GT,
  GE,IF,THEN,ELSE,ID,NUMBER,RELOP 
   DEFINE   */ %}
 /* */
 delim  [ \t\n]
 ws       {delim}+
 letter   [A-Za-z]
 digit    [0-9]
 id       {letter}({letter}|{digit})*
 number   {digit}+(\.{digit}+)?(E[+\-]?{digit}+)?
 %%
 {ws}     {/*     */}
 if       {return(IF);}
 then     {return(THEN);}
 else     {return(ELSE);}
 {id}     {yylval=install_id(); return(ID);}
 {number} {yylval=install_num(); return(NUMBER);}
 "<"      {yylval=LT; return(RELOP);}
 "<="     {yylval=LE; return(RELOP);}
 "="      {yylval=EQ; return(RELOP);}
 "<>"     {yylval=NE; return(RELOP);}
 ">"      {yylval=GT; return(RELOP);}
 ">="     {yylval=GE; return(RELOP);}
 %%
 install_id(){/*,   ,
                    yytext,
                  yyleng,  
                    */
            }
 install_num(){/*   
                 */
             }
                       . 2.16.

     ,          %{    %},
 ,   . ,
       ,      
           lex.yy.c        
         
.        
.  . 2.16   install_id  install_num.
            
.             
 ,     .  ,
    -   delim.      
  {  \t\n},  ..        :  ,
    .   - ,
       ws.       -       
        -.
 delim     ,   
 ,     delim.
  letter   . 
[A-Za-z]           A    Z  
    a   z.         id  
  ,   LEX.
,    -  LEX, 
.
          number    '+'
   "   ", 
'?'    "    ".  
   ,       ,
   LEX  .  , 
    number     '\.', 
        ,      
,          .    e
 [+\-]       , 
     ,   [A-Z].
     ,    
    -,       .  ,  
        
.
    ,        %%.
      ,         ws,   ..
   ,     
,       .    ,  
    .
  ,   
 'if',      IF,   
 ,       
 'if'.      'then'
 'else'    .
 ,        id,    .
   yylval      ,   
 install_id.      
  3.1.     yylval        
lex.yy.c,     LEX,           
. yylval     ,
    , return(ID),  
   .
  install_id            
.       :
yytext   yyleng.   yytext -    
 ,  yyleng -   ,      .
,          
 yyleng ,   yytext.
          .  
   yylval    
 ,        - 
  relop.
, ,          
   'if',      
: 'if'   {id}     , 
, .    'if'   
,      .
              
  .
          '<=',       
   '<',        ,
    .   
      .

 3.  

3.1.    

 G=  - -  ,  N -
   , T -  
, P  -       S  - . 
,   uxv       uAv ( 
   uAv=>uxv),   A->x -      u    v  -
    (N  U T)*.  u1=>u2=>...=>un, 
,     u1    un,        
u1=>*un. ..:

  1) u=>*u    u,

  2)  u=>*v  v=>*w,  u=>*w.

, "=>+"       .
   G    S,  =>+
     L(G) - , 
G.   L(G)      G.
   w   L(G)      ,
 S=>+w.  w    G.
  S=>*u,     u      ,    u
        G.    -  
 ,   .
 ,       
         .
    .   S=>*u   
 ,   u  -      .
   .
    (V,E),  V 
  ,    E  -      
   ,                   
((v,e1),(v,e2),...,(v,en)).     ,    
 a   n ,      ,
   e1,  - ,    e2, 
..
      G=(N,T,P,S)  -    
  ,           
    N  U T  U {e}.    
   A,      -  X1,...,
Xn,  A->X1X2...Xn -   .
    D   
(   )   -  G(S)=(N,T,P,S),  
  :

  (1)   D  S;

  (2)     a<-T,  e;

  (3)     ;

  (4)  N - ,    
 X1,...,Xn  -            
,  N->X1...Xk -    P.

      ( -)  -  
 P=(Q,T,,d,q0,Z0,F), 

  (1)   Q    -             ,
          
;

  (2) T -   ;

  (3)  -    ;

  (4) d  -    -     Qx(T U
{e})x     Qx*, .. d:Qx(T
U {e})x -> {Qx*};

  (5) q0<-Q -    ;

  (6) Z0<-  - ,          
 ( );

  (7) F<=Q -   

 -    (q,w,u)<-QxT*x*,


  (1) q -    ;

  (2) w  -        ;  
   w     ;  w
e,  ,     ;

  (3) u  -   ;      u
   ;  u=e,  
 .

   - P     
 |-,   .  

  (q,aw,Zu)|-(q',w,vu)

   d(q,a,Z)  (q',v),  q, q'<-Q, a<-T U
{e}, w<-T*, Z<-, u,v<-*.
        -    P    
    (q0,w,Z0),    w<-T*,  ..  
       ,    
 ,    ,    
    Z0.   - 
  (q,e,u),  q<-F, u<-*.
,    w    -  P,  
(q0,w,Z0)|-*(q,e,u)       q<-F    u<-*.  ,
  (   )    P  (
L(P)),   ,   P.
      :   w
  -  P,    (q0,w,Z0)|-*(q,e,e).  
 .

3.2. -  

3.2.1.   -

         -  
 ,     . 
     (-)         
       .  3.1.
      
 .       ,
   S.        
       
 S->X1 X2 ...,      S. 
  ,     
X1,   ..,    ,        
 ,    ,  
  Y->a ....     
                  
 .

         S                  S                 S
                          / | \             / | \
                        X1 X2...           X1 X2...
                        /                 /   |
                      ...........       .............
                      /                 /     |
                     Y                 Y      |
                    /|\               /|\     Z
                   / ...             / ...   /|\
   a..........$   a...........$      a........b.......$
        )                )                  )
                         . 3.1

 .  3.2    ,
     .  
    .

                      +---------------+
                  | a | + | b | $ |
                      +---------------+
                              ^
                              |
           +-+    +----------------------+
           |X|    |  - | 
    |-|<---|    |--->
           |Y|    +----------------------+
           |Z|                |
           |-|                v
           |$|     +---------------------+
           +-+     |   |
                   +---------------------+

                         . 3.2

-     
,         .      
 ,     $ -  
,             .        
      $   .  
          $
 .   -    M[A,a],  A -
,  a -    $.
       ,      
 .     X -    
   a  -      .      
  .   .

1.   X=a=$,         
  .

  2.  X=a#$,   X    
     .

  3.   X -  ,       
M[X,a].             X,  
. , , M[X,a]={X->UVW},   X
      WVU {   U}.  ,
                    
   .   M[X,a]=error, 
    .
               
  .

 3.1.   .

repeat  X:=  ;
        if X -   $
        then if X=InSym
             then  X  ;
                  InSym:= ;
             else error()
             end
        else /*X = */
             if M[X,InSym]=X->Y1Y2...Yk
             then  X  ;
                  Yk,Yk-1,...Y1  
                 (Y1  );
                   X->Y1Y2...Yk
             else error() /*  M */
        end end
until X=$ /* */

                              . 3.3

    ,   
 S$,  (S -     ),   
 w$  (w -   ),   InSym  
    . ,  
 M     ,    .
3.3.

 3.1.    :

 E -> T E'
 E' -> + T E' | e
 T -> F T'                                           (*)
 T' -> * F T' | e
 F -> ( E ) | id

          
. 3.4.       -  .  
,     .

---------------------------------------------------
-|             
      |--------------------------------------------
 |  id  |   +    |   *    |  (   |  )  |  $
------+------+--------+--------+------+-----+------
  E   |E->TE'|        |        |E->TE'|     |
  E'  |      |E'->+TE'|        |      |E'->e|E'->e
  T   |T->FT'|        |        |T->FT'|     |
  T'  |      |T'->e   |T'->*FT'|      |T'->e|T'->e
  F   |F->id |        |        |F->(E)|     |
-----------------------------------------------------

                       . 3.4

----------------------------------
 |       | 
--------+-----------+-------------
$E      | id+id*id$ |
$E'T    | id+id*id$ | E->TE'
$E'T'F  | id+id*id$ | T->FT'
$E'T'id | id+id*id$ | F->id
$E'T'   |   +id*id$ |                               E
$E'     |   +id*id$ | T'->e                        / \
$E'T+   |   +id*id$ | E'->+TE'                   /     \
$E'T    |    id*id$ |                           T      E'
$E'T'F  |    id*id$ | T->FT'                   /|    / | \
$E'T'id |    id*id$ | F->id                   F T'  +  T  E'
$E'T'   |      *id$ |                         |       / |
$E'T'F* |      *id$ | T'->*FT'               id     /   |
$E'T'F  |       id$ |                              F    T'
$E'T'id |       id$ | F->id                        |   /|\
$E'T'   |         $ |                             id  * F T'
$E'     |         $ | T'->e                             |
$       |         $ | E'->e                            id
----------------------------------

              . 3.5                            . 3.6

     id+id*id        
 ,    . 3.5. 
            . 
    ,   ,
      , ..    
    .     
      ( ),
     .

    . 3.6.

3.2.2.  FIRST  FOLLOW.

             
    ,        G.  
,  FIRST     FOLLOW,         
    G,  , ,  .
,    ,  ,  , 
    .
 u  -    ,  FIRST(u)
-  ,    , 
 u.  u=>*e,  e   FIRST(u).
  FOLLOW(A)        A     
 a,       
  A          ,  ..  
 a  ,       S=>*uAav  
 u   v.  ,    A  a   
    ,    
e.     A             
 ,  $  FOLLOW(A).
   FIRST(X)          X
  .

  3.2.        FIRST      
.

   1.   X  - ,   FIRST(X) -  {X};  X -
,  FIRST(X)={}.

   2.        X->e,    e 
FIRST(X).

   3.       FIRST(X)   
    e:
         X   -             X-
       >Y1Y2...Yk,       a     FIRST(X),    
         i   a<-FIRST(Yi)     e     
       FIRST(Y1),...,FIRST(Yi-1), ..  Y1...Yi-1=>*e.   e
        FIRST(Yj)   j=1,2,...,k,  
       e   FIRST(X). , ,   FIRST(Y1)
           FIRST(X).    Y1  
       e,          FIRST(X),  
       Y1=>*e,   FIRST(Y2),  ..

  FIRST        X1X2...Xn    
 .

   1.  FIRST(X1X2...Xn)={}.

   2.     FIRST(X1X2...Xn)      e    
FIRST(X1).     e   FIRST(X2), 
e<-FIRST(X1),  e         FIRST(X3),      e
    FIRST(X1),      FIRST(X2),    ..
,   e  FIRST(X1X2...Xn),  e<-FIRST(Xi)
  i.

   FOLLOW(A)    A  
3.3.

 3.3.   FOLLOW(X)    X - 
.

   1.  FOLLOW(X)={}.

   2.  $  FOLLOW(S),  S -    $
-   .

   3.   e   A->uBv,    FIRST(v),
  e,   FOLLOW(B).

   4.                
 FOLLOW(X):  e     A->uB 
A->uBv,   FIRST(v)   e (.. v=>*e),   
FOLLOW(A)   FOLLOW(B).

 3.2. a   (*).  

 FIRST(E) =FIRST(T)=FIRST(F)={(,id}
 FIRST(E')={+,e}
 FIRST(T')={*,e}
 FOLLOW(E)=FOLLOW(E')={),$}
 FOLLOW(T)=FOLLOW(T')={+,),$}
 FOLLOW(F)={+,*,),$}

, id        FIRST(F)   3
  i=1,     FIRST(id)={id}     FIRST('(')={'('}  
    1.     3  i=1,   
  T->FT'  FIRST(T)   id  
.   2  FIRST(E')  e.
    1        FOLLOW    FOLLOW(E)
 $.     2,       F->(E), 
FOLLOW(E)          .      3,
    E->TE',   FOLLOW(E')    $  
  .     E'=>*e,         
FOLLOW(T).       E->TE',   2
 FOLLOW(T)    FIRST(E'),   e.

3.2.3.    

       
 G      ,   
  .   ,    A->u  -    
   a<-FIRTS(u).     A
 u,       a.  ,
 u=e   u=>*e.         A  u,
       FOLLOW(A)    
 $  $<-FOLLOW(A).

 3.4.    .

     A->u    1  2

   1.      a  FIRST(u)  A->u 
M[A,a].

   2.   e<-FIRST(u),  A->u  M[A,b]  
  b     FOLLOW(A).     e<-FIRST(u)    $<-
FOLLOW(A),  A->u  M[A,$].

   3.      error.

 3.3.    3.4   (*). 
FIRST(TE')=FIRST(T)={(,id},       
E->TE'  M[E,(]  M[E,id]   E->TE'.
     E'->+TE'  M[E',+] 
E'->+TE'.      E'->e  M[E',)]
 M[E',$]  E'->e,  FOLLOW(E')={),$}.
 ,     3.4,   
. 3.4.

3.2.4. LL(1)-

 3.4         M    
    .     M
      . ,  
    ,  M   
     .
,                  
   ,   LL(1).  L
    -,  L ,
    , 1 -      
          .
 ,   3.4   LL(1)- G
 ,        L(G) 
 .
LL(1)-         .
          
LL(1).    ,    G  LL(1)
    ,            A->u|v
 :

1)       a     u    v  
 ,   a;

  2)       u  v   
;

  3)    v=>*e,      u        ,
    FOLLOW(A).

     :

  -       LL(1)-,      
   

  (1) S =>* w A u => w v u =>* wx,

  (2) S =>* w A u => w z u =>* wy,

     FIRST(x)=FIRST(y),  ,     v=z.   
,         wAu      ,
    Au  (  $),        
,         A,    
 -   ,     w 
   .
,             LL(1)-,
 LL(1)-.
       ,
        LL(1).      
 :

 St -> if Ex then St
    | if Ex then St else St
    | Cont
 Ex -> ...

   ,      .  3.7.
   ,        LL(1).
,        LL-,  
.

                 St                              St
                /|\                             /| \
             /   |  \                        /   |    \
          /      St   \                   /      St   ...
       /        / \     \              /        / \  \
    /         /     \     \        /         /     \     \
if E then if E then S else S    if E then if E then S else S

                  )                            )

                          . 3.7

3.2.5.   

      
-        ,  
      .  
       LL(1)-
       LL(1)-.       
          
 .        . -
,              
 LL(1) , -,     
       
.
 ,        A
,      A=>+Au      u.
       
-,     .
   , ..    A->Au,
       .      A-
:

A -> Au1 | Au2 | ... | Aum | v1 | v2 | .... | vn

      vi    A.   A-
 

A -> v1A' | v2A' | .... | vnA'
A'-> u1A' | u2A' | .... | umA' | e

   A    ,   ,  
   .         
     ,         
,       .    
  3.5               
.

 3.5.   .

 1.     .
 2. for i:=1 to n do
       for j:=1 to i-1 do
            Aj->v1 | v2 | ... | vk -   
            Aj;
               Ai->Aju  
           Ai->v1u | v2u | ... | vkU;
       end;
            
        Ai;
       end

 (i-1)-         2   
   Ak->Alu,   kk.  
       (   i)       (  j)
          m    
  Ai->Amu,           m>=i.   ,   
    Ai-,  m 
i.
 3.5  ,          
(  A=>+A)  e- (  A->e).  ,
      e-            .
            e-
.

3.2.6.  

O       ,  ,   ,
            
 A,    A- ,  
    ,      , 
  .
  A->uv1   |  uv2  -    A-      
    ,     u,    ,
    uv1     uv2.     
,   A->uA'.        ,  
     u,        A'->v1      A'->v2.
   

 A -> u A'
 A' -> v1 | v2

 3.6.   .

    A     u, 
      .  u#e, .. 
   ,    A- A->uv1 |
uv2 | ... | uvn | z,  z -  ,  
 u, 

 A -> uA' | z
 A' -> v1 | v2 | ... | vn

  A'   -     .        
,         
 .

 3.4.     :

 St -> if Ex then St
    | if Ex then St else St
    | Cont
 Ex -> ...

     

 St  -> if Ex then St St'
     | Cont
 St' ->  else St | e
 Ex  -> ...

 ,   ,  ,  
LL(1),   . 3.8.

                 St
                / | \
              /   |   \                         St
            /     St    St'                   /  | \
          /      / \\                      /     |   \
        /       /   \ \                 /        St    St'
      /        /     \  St'        /          /  | \    \
    /         /       \   |     /          /     |  \     \
if E then if E then S else S if E then if E then S S' else S

                   )                           )

                               . 3.8

3.2.7.  

              -    
 ,       
   .     
   ,         
,  ,    
            .  
    ,    
. 3.9.   N  ,   
N->ui->*e (      ,  
 e!),      1.1   1.2.  
1.1  ,     
FOLLOW(N).    -   .      
   ,          
,  N.

 procedure N;{N -> u1 | u2 | ... | uk}
   begin if InSym<-FIRST(ui) { !}
         then if parse(ui)
              then exit(N->ui)
              else error()
              end
         else
    1:    N->ui =>* e 
       1.1 : if InSym<-FOLLOW(N)
                    then exit(N->e)
                    else error()
                    end;
       1.2:  exit(N->e)
    2:   N->ui =>*e
              error()
   end   end;
 procedure parse(u);
 { u   e!}
 begin v:=u;
       while v#e do
              {v=Xz}
              if X- a
              then if InSym<>a
                   then return(false)
                   end
              else {X- B}
                   B;
              end;
              v:=z
       end;
       return(true)
 end;
                . 3.9

3.2.8.     

 ,      
       . 
    ,      
 .        
 ,    .
         LL(1)-.         
     .

   1.     .

   2.       A->X1X2...Xn  
           ,  
X1,...,Xn.      ,         
,        s    ,  
 a,      t,    
   a,         
        t.        
 A,        A
     .              
    A,      t,
  "" A       s 
 t.  ,      s  t,  e,
    s  t,   .
     ,   
e       .
       
. ,  ,      
  . 3.10.

  +---+ T +---+ E'+-----+   +---+ + +---+ T +---+ E'+-----+
E:| 0 |-->| 1 |-->|| 2 ||E':| 3 |-->| 4 |-->| 5 |-->|| 6 ||
  +---+   +---+   +-----+   +---+   +---+   +---+   +-----+
                              |                        ^
                              |           e            |
                              +------------------------+

  +---+ T +---+ E'+-----+   +----+ + +----+ T +----+ E'+----+
E:| 7 |-->| 8 |-->|| 9 ||E':| 10 |-->| 11 |-->| 12 |-->||13||
  +---+   +---+   +-----+   +----+   +----+   +----+   +----+
                              |                           ^
                              |           e               |
                              +---------------------------+

                             51
     +----+  (  +----+  E  +----+  )  +------+
 F:  | 14 |---->| 15 |---->| 16 |---->|| 17 ||
     +----+     +----+     +----+     +------+
       |                                 ^
       |              id                 |
       +---------------------------------+
                        . 3.10

                   e
       +---------------------+            +---------+
       |                     |            |    T    |
       v                     |            v         |
     +---+   +  +---+  T  +-----+       +---+ +   +---+
 E': | 3 |----->| 4 |---->|| 5 || => E':| 3 |---->| 4 |
     +---+      +---+     +-----+       +---+     +---+
       |e                                 |e
       |         +-----+                  |      +-----+
       +-------->|| 6 ||                  +----->|| 6 ||
                 +-----+                         +-----+

              +-------+          +---------+
              |  T    |          |    +    |
              v       |          v         |   e
   +---+ T +---+ + +---+       +---+ T   +---+   +-----+
E: | 0 |-->| 3 |-->| 4 | => E: | 0 |---->| 3 |-->|| 6 ||
   +---+   +---+   +---+       +---+     +---+   +-----+
             |  e +-----+
             +--->|| 6 ||
                  +-----+
                           . 3.11

     +---------+                     +---------+
     |   +     |                     |   *     |
     v         |    e                v         |   e
   +---+ T   +---+     +-----+     +---+ F   +---+    +------+
E: | 0 |---->| 3 |---->|| 6 || T:  | 7 |---->| 8 |--->|| 13 ||
   +---+     +---+     +-----+     +---+     +---+    +------+

     +----+  (  +----+  E  +----+  )  +------+
 F:  | 14 |---->| 15 |---->| 16 |---->|| 17 ||
     +----+     +----+     +----+     +------+
       |                                 ^
       |              e                  |
       +---------------------------------+
                        . 3.12

   3.11       
E'.     E' .3.11   
E .  3.10.    .  3.11   E. ,
,               
      .          
   T  T'.     
. 3.12.
           
     -,         
           
.         
  E   :

procedure E; repeat T; until InSym<>PLUS;

3.2.9.    

        
            error().   
       
 .         
   .          
   .
              
    N          ,
   ,       
,             FIRST(N),    
FOLLOW(N).     N  
,   -  N  .
        ,    
         
   ()     ,
    .

3.3.  -  -

3.3.1. 

    -    -  
    ,      ()  
 ().       ""
 w       .      
 ,          
   ,       
    ,            
 ,         
  (. 3.13).

         S              S                     S
                                            / | \
                                           X1 X2...
                                          /   |
                                        .............
                                        /     |
                     Y                 Y      |
                    /|\               /|\     Z
                  / ...              / ...   /|\
   a.........$   a...........$      a........b.......$

        )                )                  )

                         . 3.13

 3.5.       ,
  . 3.14 ).  +b*c    
S,     . 3.14.).    
 . 3.14 ).
  a+b*c  ,    
      .  
 a,  b  c.     a   
 F  -      F->id,     F+b*c.
                
 b   c.         
  :

E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c->a+b*c
   ---    ---      -    -      -    -      -      -

          E -> E + T       +b*c             E
          E -> T           F+b*c            /+\
          T -> T*F         T+b*c           E   T
          T -> F           E+b*c           |   |\
          F -> id          E+F*c           T   T F
                           E+T*c           |   |  \
                           E+T*F           F   F   id
                           E+T             |   |    c
                           E               a   b

             )               )                )

                       . 3.14

       ,          
       , 
          
  ,   . 
         .    
,          
     A->v,          ,
      A->v   , 
       . , ,   3.5
 a   F  b  F,    F+F*c,  
    S.
,          z  -  
   A->v      z,        
   v ,          v    A
        
 z.  ,  S=>*uAw=>uvw,  A->v  ,
   u,      uvw.   w   
      .   ,
    ,    
      uvw     
 .     ,      
        .
        
  .   
        
,       w.   w  -    
 ,  w=Zn, n-  
    

S = Z0 => Z1 => Z2 => ... => Zn-1 => Zn =w.

         ,  
 Vn  Zn   Vn     
 An  -> Vn,   (n-1)-   
Zn-1.     , ..   Vn-1
 Zn-1    ,   
 Zn-2.  ,    ,    
 ,       
S,              
.   ,  
,     .
   ,     -
-     .

3.3.2. LR(k)-

   LR(k)  L ,   
-, R  -            
, k  -    ,    
    .   k ,   
1.
LR-    :

  - LR-  -        
 -;
- LR-     ;
-   LR-      
  ;
-   ,      LR-
,      ,  
    (
  LL).

                    +------------------------------+
                | A1 | ... | Ai | ... | An | $ |
                    +------------------------------+
                                 ^
                                 |
            +------+          +-------------+ 
     |  Sm  |<---------|     LR      |-------->
            |------|          |   |
            |  Xm  |          +-------------+
            |------|                 |
            | Sm-1 |                 |
            |------|            +--------+
            | Xm-1 |            |        |
            |------|            v        v
            | .... |        +---------------+
            |------|        | action | goto |
            |  S0  |        +---------------+
            +------+
                            . 3.15

  LR-   . 3.15.
   , , ,   
  ,           -    
.                
,            
.           
      .        
,       S0X1S1X2S2...XmSm (Sm
-     ).     Xi  -      
(   ),   Si - , 
.           ,
        ,      
           
            
     .    
          .    
          LR-
.
        :  (action) 
  (goto).            -  
,       LR-  
 .
-LR   -   ,   
 -   ,      -  
:

(S0 X1 S1 X2 S2 ... Xm Sm, Ai Ai+1 ... An $)

     

X1 X2 ... Xm Ai Ai+1 ... An

   ,    
   ,         .
   -        
,        .
           
 Ai            Sm.
    action[Sm,Ai]      Sm  
 Ai,      :

  1) shift S, ,  S - ,

  2) reduce A->w,     A -> w,

  3) accept, ,

  4) error, .

,           
, 

  1.   action[Sm,Ai]=shift S,     
,   

(S0 X1 S1 X2 S2 ... Xm Sm Ai S, Ai+1 ... An $)

         Ai,   
  S,     action[Sm,Ai].    
  Ai+1.

  2.   action[Sm,Ai]=reduce A->w,    
,   

(S0 X1 S1 X2 S2 ... Xm-r Sm-r A S, Ai Ai+1 ... An $)

 S=goto[Sm-r,A]  r -  w,    .
 goto   ,     G, -
       ,
    G.   
   2r   (r      r 
),         Sm-r.
          A  -    
 ,    S -   goto[Sm-r,A]. 
          .    LR-
  Xm-r+1  ...  Xm  -    
,    ,     w -
   ,    .
           LR-
,   ..          ,
   ,     , 
  ,    .

  3.  action[Sm,Ai]=accept,   .

  4.  action[Sm,Ai]=error,   , 
     .

      LR-.  LR- 
 .          
    .

 3.7.  LR-.

loop  S -    ;
     if action[S,InSym]=shift S'
     then  InSym   S'
            ;
            InSym 
           

     else if action[S,InSym]=reduce N->w
          then   
               2*|w| ;
                   
                S';
                   N, 
                 goto[S',InSym];
                 N->w
          else if action[S,InSym]=accept
               then return
               else error()
end  end  end  end;

      S0,   
w$, InSym      w$;     
       ,   
  accept,   error.

          +--------------------------------------+
          |-|     action       |  goto      |
          |  |------------------+------------|
          |      |  id   +  *   $   |  E  T   F  |
          |------+------------------+------------|
          |  0   |  S6              |  1  2  3   |
          |  1   |      S4     acc  |            |
          |  2   |      R2  S7  R2  |            |
          |  3   |      R4  R4  R4  |            |
          |  4   |  S6              |     5  3   |
          |  5   |      R1  S7  R1  |            |
          |  6   |      R5  R5  R5  |            |
          |  7   |  S6              |        8   |
          |  8   |      R3  R3  R3  |            |
          +--------------------------------------+

                        . 3.16

 3.6.   . 3.16   action  goto LR-
          
 +   *   3.5.    Si      
    i, Rj -    
j, acc - ,   - .
 goto[S,A]     A    ,
         A   S. 
  goto[S,A]   A.
   id+id*id      
    .  3.17. ,      LR-
             
  id.  S6      id 
 action  .  3.17          S6  
 .        : 
 id      S6        id
   .
         +,      
 6     +    F->id.  
    (        
).      
goto          F  -    3,  F    3
       .            ,
   .     
.

+---------------------------------------------------------+
||                |          | |
| |                       |              |         |
|--------+-----------------------+--------------+---------|
|        |0                      |id + id * id $|    |
| id     |0 id 6                 |   + id * id $| F -> id |
| F      |0 F 3                  |   + id * id $| T -> F  |
| T      |0 T 2                  |   + id * id $| E -> T  |
| E      |0 E 1                  |   + id * id $|    |
| E+     |0 E 1 + 4              |     id * id $|    |
| E+id   |0 E 1 + 4 id 6         |        * id $| F -> id |
| E+F    |0 E 1 + 4 F 3          |        * id $| T -> F  |
| E+T    |0 E 1 + 4 T 5          |          id $|    |
| E+T*   |0 E 1 + 4 T 5 * 7      |          id $|    |
| E+T*id |0 E 1 + 4 T 5 * 7 id 6 |             $| F -> id |
| E+T*F  |0 E 1 + 4 T 5 * 7 F 8  |             $| T -> T*F|
| E+T    |0 E 1 + 4 T 5          |             $| E -> E+T|
| E      |0 E 1                  |              |   |
+---------------------------------------------------------+

                         . 3.17

3.3.3. LR-

,         LR-,
 LR-.   -,  
LR-,            
   LR.
     LR,  ,    -
      -,      
     .        
,              ,  
   ,    ,    
   ,     ,    
.        
     LR-.      
      ,     
     ,          
       ,          
      .
               
     k    .  
    k=0   k=1.  ,   
  .  3.16      .  ,
            LR   ,
   k       , 
LR(k)-.
     LR(k)-. 
     G  -,
     S'    S'->S. 
      ,   ,
           
 .         
,       S'->S.
    LR(k)    k>=0,    


 (1) S' =>* uAw => uvw,
 (2) S' =>* zBx => uvy,
 (3) FIRST(w)=FIRST(y)

,  uAy=zBx (.. u=z, A=B  x=y).
     ,  uvw  uvy - 
   ,   FIRST(w)=FIRST(y) 
A->v -    ,        
 uvw,     A->v       
    uvy  uAy.   A  v  
w,   LR(k)    ,      FIRST(w)  
,      ,  uv  
    uA.          
       ,          
   .  , 
LR(k)  ,    .
    LL-   LR-  
.              LR(k),   
     , 
,          k 
 .     , 
   LL(k) ,    
 ,      k , 
    .   LL-  
 LR.        LR-
.
LR(1)      [A->u.v,a],    A->uv  -
 ,   a -     
$. "1"       , 
  .     
   [A->u.v,a],  v   e,   
[A->u.,a]             A->u    
      a.   
   A->u        a,
   [A->u.,a]  LR(1)    
 .
 ,   LR(1)- [A->u.v,a]  
   z,       S=>*yAw=>yuvw,
. z=yu   a -   w,  w  e  a 
$ (. 3.18).

                      S
                     /|\
                    / | \
                   /  A  \
                  /  /\   \
                 /  /  \   \
                y  u    v   a...
                 ----     ----
                   z       w

                  . 3.18

 ,   ,    
-  .

 3.7.  

 S -> BB
 B -> aB | b

     S=>*aaBab=>aaaBab.  
[B->a.B,a]        z=aaa,    
       y=aa,   A=B,  w=ab,   u=a,  v=B.
     S*=>BaB=>BaaB.  
  ,           Baa  
 [B->a.B,$].
     LR-      ,    
           ,
       .          
     ,        
.               
  ,  
,               
               
.
            LR(1)-
            G'  
- closure  goto.
    [A->u.Bv,a]   ,
            z.   
    S=>*yAax=>yuBvax,    z=yu.
,    vax        bw.
         B->q  
S=>*zBbw=>zqbw.   [B->.q,b]   z. 
 b    ,   v,   v
 e     vax=>*bw    b    a.  ..  b
 FIRST(vax).         
     ,  ..     ,  
 closure.
A   LR(1)-  .

 3.8.   LR(1)-.

          items,
   closure  goto.

function closure(I);/*I -  */
 begin repeat    [A->u.Bv,a]  I,
                 B->w  G'  
               b  FIRST(va), ,  [B->.w,b]
                I
          do  [B->.w,b]  I;
      until  I    ;
      return I;
 end;

       LR(0)        closure   
   FIRST(va).
 I  -    ,      
   z,    goto(I,X)  -    ,
    zX.

function goto(I,X);/*I -  ;
                     X -  */
 begin  [A->u.Xv,a]  I;
       J -   [A-uX.v,a];
      return closure(J)
 end;

              LR(1)-
     ,      C  -    
{closure({[S'->.S,$]})}.           
  goto()    . -
, goto(I,X)  -     
I   X.

procedure items(G'); begin C:={closure({[S'->.S,$]})};
      repeat     I  C
                     X
                 ,  goto(I,X)  
                    C
             do  goto(I,X)  C
      until  C      end;

 3.8.     3.5.

    E'-> E
 1) E -> E + T
 2) E -> T
 3) T -> T * F
 4) T -> F
 5) F -> id

         
 . 3.19.
              
,     
   (I0)   .   -    
         , ..   
    ,   ,   
 ,   .
 ,     LR(1)- 
          LR(1)-.  
    .

+-------------+ E  +-------------+ +  +-------------+
| I0          |--->| I1          |--->| I4          |
| E'-> .E,  $ |    | E'-> E.,  $ |    | E -> E+.T,$ |
| E -> .E+T,$ |    | E -> E.+T,$ |    | E -> E+.T,+ |
| E -> .T,  $ |    | E -> E.+T,+ |    | T -> .T*F,$ |
| T -> .T*F,$ |    +-------------+    | T -> .F,  $ |
| T -> .F,  $ | T  +-------------+    | T -> .T*F,+ |
| F -> .id, $ |--->| I2          |    | T -> .F,  + |
| E -> .E+T,+ |    | E -> T.,  $ |    | F -> .id, $ |
| E -> .T,  + |    | T -> T.*F,$ |    | F -> .id, + |
| T -> .T*F,+ |    | E -> T.,  + |    | T -> .T*F,* |
| T -> .F,  + |    | T -> T.*F,+ |    | T -> .F,  * |
| T -> .T*F,* |    | T -> T.*F,* |    | F -> .id, * |
| T -> .F,  * |    +-------------+    +-------------+
| F -> .id, * |       |                  F|   |  |
| F -> .id, + |-------+---+ +-------------+   |  |
+-------------+       | F | |               T |  | id
  |     +-------------+   | |                 |  +------+
+-+     | *               | |                 |         |
|       v                 v v                 v         |
| +-------------+    +-----------+      +-------------+ |
| | I7          |    | I3        |      | I5          | |
| | T -> T*.F,$ |    | T -> F.,$ |      | E -> E+T.,$ | |
| | T -> T*.F,+ |    | T -> F.,+ |      | E -> E+T.,+ | |
| | T -> T*.F,* |    | T -> F.,* |      | T -> T.*F,$ | |
| | F -> .id, $ |    +-----------+   *  | T -> T.*F,+ | |
| | F -> .id, + |<----------------------| T -> T.*F,* | |
| | F -> .id,*  |   id                  +-------------+ |
| +-------------+                                  +----+
|      | F |       id                              |
| id   |   +---------------------------------+     |
+------+----------------------------------+  |     |
       |                                  |  |     |
       v                                  v  v     v
 +-------------+ F                      +------------+
 | I8          |                        | I6         |
 | T -> T*F.,$ |                        | F -> id.,+ |
 | T -> T*F.,+ |                        | F -> id.,* |
 | T -> T*F.,* |                        | F -> id.,$ |
 +-------------+                        +------------+
                     . 3.19

 3.9.    LR .

  1.    LR(1)-  C={I0,I1,...,In}
 G'.

   2.   i       Ii.  
       i     
:

     )   [A->u.av,b]   Ii   goto(Ii,a)=Ij, 
 action[i,a]="shift j".  a - ;

     )   [A->u.,a]    Ii,  A#S',    
action[i,a]="reduce A->u";

     )       [S'->S.,$]        Ii,    
action[i,$]="accept".

   3.        i    
:   goto(Ii,A)=Ij,   goto[i,A]=j (  A -
).

   4.   ,      2   3, 
 "error".

    5.              
,      [S'->.S,$].    
    , ..   
               
  (   /,    /),
,       LR(1),    
 .

  ,     action  goto 
      3.10,    
 LR(1)-.  LR-,   
,   LR-.  
  action         
,    LR(1)-.

3.3.4.    -

      LR(1),    -
       ,   ,
       ,  
,       ( /),
    ,        
(   /).      ,   
    LR.

 3.9.        

if-then-else:

 St -> if Ex then St
       | if Ex then St else St
       | ...

   -   

                                 
              ... if Ex then St       else ... $

   ,    if Ex then St , 
   ,      .  
/.     ,     
else,      St -> if Ex then St 
  else,             St     
 if  Ex then  St else  St.      
,          , 
   LR(1).
              LR(1)-
 :

St -> CondSt | UnCondSt
CondSt -> IfThenSt | IfThenElseSt
FullSt -> IfThenElseSt | UnCondSt
IfThenElseSt -> if Ex then FullSt else St
IfThenSt ->if Ex then St

3.3.5.    

              .   
      , 
    s      A.
   ,     ,
    A.       
   goto[s,A]      .  
 A      . 
A  -     ,           
 ,  .  s - , ,
    end.
            
         
.        
      ,   
.

 4.   

      
 () ,    
   /   
.          .
                   
       (,      ,   
  ),   ,  ,    
 ,   .

4.1.     

           
   .       
           
(),                   
  ,      .
        a:=b*-
c+b*-c   . 4.1.

  .   4.2.               
       .   4.1.).     
                  
   .   . 4.2.)     
         (  )    
  .

4.2.  

 -     x:= y
op z,   x,y   z  - ,      
     .     op  -   
,            
,    .       
    .

                  :=                    :=
                  /\                    /\
                 /  \                  /  \
                a    +                a    +
                    / \                   / \
                   /   \                 |   |
                  *     *                 \ /
                 / \   / \                 *
                /   \ /   \               / \
               b    - b    -             /   \
                    |      |            b     -
                    |      |                  |
                    c      c                  |
                                              c
                       )                 )

                        . 4.1

                             66
         +------------+                    +------------+
 10      | := | | | | |                  0 | id | b |   |
         +------+---+-+                    |----+---+---|
                v   |                    1 | id | c |   |
         +--------+ |                      |----+---+---|
  9      | id | a | |                    2 | -  | 1 |   |
         +--------+ v                      |----+---+---|
         +------------+                  3 | *  | 0 | 2 |
  7      | +  | | | | |                    |----+---+---|
         +------+---+-+                  4 | id | b |   |
              +-+   +------------+         |----+---+---|
              |                  |       5 | id | c |   |
              v                  v         |----+---+---|
     +------------+      +------------+  6 | -  | 5 |   |
   3 | *  |   | | |  8   | *  | | | | |    |----+---+---|
     +----------+-+      +------+---+-+  7 | +  | 3 | 8 |
            v   |               v   |      |----+---+---|
     +--------+ |        +--------+ |    8 | *  | 4 | 6 |
   0 | id | b | |    4   | id | b | |      |----+---+---|
     +--------+ v        +--------+ v    9 | id | a |   |
     +------------+      +------------+    |----+---+---|
   2 | -  | | |   |  6   | -  | | |   |  10| := | 9 | 7 |
     +------+-----+      +------+-----+    +------------+
            v                   v
      +--------+          +--------+
   1  | id | c |     5    | id | c |            )
      +--------+          +--------+
                    )
                             . 4.2

       , 
          ().  
 "  "   ,    
   :          .
      -         
       ,         
      . ,
    x+y*z                  
 

 t1:=y*z
 t2:=x+t1

 t1  t2 - ,  .
                  
 ,     .      
        
.         
   . ,  

           if A>B then S1 else S2

    :

  t:=A-B
  JGT t,S2
     .....

  JGT   -        ,  
 .
       
        
.           ,
   ,      
 .

           t1 := -c           t1 := -c
           t2 := b * t1       t2 := b * t1
           t3 := -c           t5 := t2 + t2
           t4 := b * t3       a := t5
           t5 := t2 + t1
           a := t5

                )               )

                      . 4.3

       . 4.1  
            .   4.3.)      4.3.),
.
     -        
.           
         .   
   : ,     
.
 -         ,    
 op,  arg1,  arg2    result.    op    
.          x:=-y 
x:=y  arg2     .        (
" ")          arg2,  
result.            result
 .  . 4.4    a:=b*-c+b*-
c.      . 4.3..
    arg1, arg2  result -  
         ,    
.         
.
          , 
        ,      
     .         
            
: op,  arg1  arg2,     . 4.4.. 
arg1   arg2 -           (
,     ,      ),   
    (   ).    
       .  
        
  .
      -      ,    - 
       .       ,
          
arg1   arg2,      op   .
 . 4.4.   . 4.4..

+----------------------------++------------------------+
|   |op  |arg1 | arg2 |result||     | op | arg1 | arg2 |
|---+----+-----+------+------||-----+----+------+------|
|(0)| -  |  c  |      |  t1  || (0) | -  |  c   |      |
|(1)| *  |  b  |  t1  |  t2  || (1) | *  |  b   |  (0) |
|(2)| -  |  c  |      |  t3  || (2) | -  |  c   |      |
|(3)| *  |  b  |  t3  |  t4  || (3) | *  |  b   |  (2) |
|(4)| +  |  t2 |  t4  |  t5  || (4) | +  | (1)  |  (3) |
|(5)| := |  t5 |      |  a   || (5) | := |  a   |  (4) |
+----------------------------++------------------------+
         )                     ) 
                          . 4.4

        x[i]:=y
     ,           .  4.5.,
 x:=y[i]     . 4.5..

+------------------------+  +-------------------------+
|    | op  | arg1 | arg2 |  |     | op  | arg1 | arg2 |
|----+-----+------+------|  |-----+-----+------+------|
|(0) | []= |  x   |  i   |  | (0) | =[] |  y   |  i   |
|(1) | :=  | (0)  |  y   |  | (1) | :=  |  x   | (0)  |
+------------------------+  +-------------------------+
         ) x[i]:=y                  ) x:=y[i]
                       . 4.5

          , 
    .    
 .  ,   . 4.4.   
 ,     . 4.6.

+---------------+  +------------------------+
|    |  |  |     | op | arg1 | arg2 |
|----+----------+  |-----+----+------+------|
|(0) | (14) |   |  |(14) | -  |  c   |      |
|(1) | (15) |   |  |(15) | *  |  b   | (14) |
|(2) | (16) |   |  |(16) | -  |  c   |      |
|(3) | (17) |   |  |(17) | *  |  b   | (16) |
|(4) | (18) |   |  |(18) | +  | (15) | (17) |
|(5) | (19) |   |  |(19) | := |  a   | (18) |
+---------------+  +------------------------+

                     . 4.6

             ,   
,                 ,
    ,     
    .   
      .
            
   ,            
       .      
,   x,      ,
 x.         ,
     ,      
         arg1  arg2. - 
     .
            
    .    
      op, arg1    arg2.    
   .  ,    
   .      , 
        
             .  
       
 ,              
    .  ,   . 4.6 
   (14)   (16),      
 (15)  (17).

4.3.  

       
 .    
                
          
.             
 -           
- (  ,   ), 
       -  (  ,  
 ).
 ,    ( ) - 
     ,          
    .     .  4.1  
      :

        a b c - * b c * + :=

          
.           ,  
         
.             
      .
       ,   
. ,     

             := a + * b - c * b - c

                
  -    [4].    -      
'  '.    -  -
     .       
        
  ,              
.   (. 4.7).

     module M;
     var X,Y,Z: integer;
     procedure DIF(A,B:integer):integer;
        var R:integer;
        begin R:=A-B;
              return(R);
        end DIF;
     begin Z:=DIF(X,Y);
     end M.
                   . 4.7

      . 4.8.

    program 'M'
    var int
    var int
    var int
    procbody proc int int end int
       var int
       begin assign var 1 7 end
                    int int mi par 1 5 end par 1 6 end
             result 0 int var 1 7 end
             return
       end

    begin assign var 0 3 end int
          icall 0 4 int var 0 1 end int var 0 2 end end
    end
                  . 4.8

   :

program 'M'          
                 
var int             var X,Y,Z:integer;
var int           X,Y,Z  
var int          1,2,3    0
procbody proc       
int int end       ,  .
int                 4   0 
                    5, 6   1.
var int            R   7 
                  1
begin              
assign            
var 1 7 end         (R)
int                
int mi            
par 1 5 end       (A)
par 1 6 end       (B)
result 0            0
int                 
var 1 7 end       -  R
return            
end                

begin              
assign            
var 0 3 end        -  Z
int                
icall 0 4           DIF
int var 0 1 end    X  Y
int var 0 2 end
end               
end                

4.4.     

               
 .         
     (,  ),
  (   ,  ),        ..  
          .
   .  1)        
      ; 2)   
    .
  , ,   ,    
       -.  
-              
,  ,            
            .  
    ,     ..   , 
           
(, , ,    ,  ..).
          ,    
  . 4.9.

            
  
 +-----+            +----------------------------+
 |   --+--------+   | :             |
 |-----|        |   |----------------------------|
 |   --+----+   |   | :  |
 | ....|..  |   |   |   ()      |
 |-----|    |   |   |----------------------------|
 |   --+--+ |   +-->| : , ...   |
 +-----+  | |       |----------------------------|
          | +-->    |............................|
          |         |                            |
          |         |----------------------------|
          +-------->|                            |
                    +----------------------------+

                       . 4.9

            
    -        .    
            .   
   -  ,      
    . ,   
  ,   . 4.10.

                            /\
                          /    \
                        /        \
                      /            \
                    /                \
    /                    \
                /  \                     \
              /      \                     \
            /          \                     \
                         
                         
      +--------+   +--------+           +------+
      |        |<--+---     |<----------+---   |
      +--------+   +--------+           +------+

                      . 4.10

4.5.   

    ,  
               
 ,     .  ,  
      ,   
            .    
,        
  ,            
    .     ,  
 ,  .
         
     (    if,
for, while   ..),        . 
           
   (,    for  -  
 ,  ,   ,      
,    case  -      
..).       .
         
     (,   -
   ),  -  (, 
    ).

 5.   

5.1.    

       (-)
   P=(Q,T,,,,q0,Z0,F),  Q - 
, T  -   ,  -  
 ,    -      ,    -
   Qx(T  U  {e})x      
   Qx*x*, q0<-Q  -   ,
Z0<-  -        ,  F<-Q   -   
 .
       P     
(q,x,u,y),   q<-Q -  , x<-T*  -   
,  u<-*  -    ,  y<-*  -    
 ,        . 
(q,a,Z)    (r,u,z),        (q,ax,Zw,y)|-
(r,x,uw,yz)    x<-A*,  w<-*   y<-*.   
   |-   |-*.
  y          x,    (q0,x,Z0,e)|-
*(q,e,u,y)       q<-F     u<-*.    (
),         -    P
( t(P)),      {(x,y)|(q0,x,Z0,e)|-
*(q,e,u,y)    q<-F   u<-*}.   , 
-   P=(Q,T,,,,q0,Z0,F)   
(-),    :

  1)    q<-Q,  a<-T U  {e}   Z<-    (q,a,Z)
    ,

  2)  (q,e,Z)#{},  (q,a,Z)={}   a<-T.

 5.1.     .

    -          ,       ,
    .  
  :

 Q={q0,+,*,),$};
 T={,+,*,(,),$},  $ -  ;
 ={Z0,(,+,*};
 ={,+,*};

     . 5.1.

+------------------------------------------------+
|   |  Q  |   T   ||     *     |   Q  |       |
|----+-----+-------||------------+------+------- |
| Z0 | q0  |  ||     z      |  q0  |   |
| Z0 | q0  |   (   ||     z(     |  q0  |        |
| Z0 | q0  |   ||     z      |  |        |
|----+-----+-------||------------+------+------- |
|(   |  )  |       ||     e      |  q0  |        |
|+,* |  )  |       ||     e      |  )   | +,*    |
|----+-----+-------||------------+------+------- |
| +  |  *  |       ||     +*     |  q0  |        |
| *  |  +  |       ||     *+     |  q0  |        |
|| +,* |       ||  {+,*} |  q0  |        |
|----+-----+-------||------------+------+--------|
|+,* |  $  |       ||      e     |  $   | +,*    |
| Z0 |  $  |       ||      e     |      |        |
+------------------++----------------------------+
                  . 5.1

                             76
+--------------------------------+
|  ||     ||
|------+---------+---------+-----|
|Z0    |    q0   | a*(b+c)$|  a  |
|Z0    |    q0   |  *(b+c)$|     |
|Z0    |    *    |   (b+c)$|     |
|Z0*   |    q0   |   (b+c)$|     |
|Z0*(  |    q0   |    b+c)$|     |
|Z0*(  |    q0   |     +c)$|  b  |
|Z0*(  |    +    |      c)$|     |
|Z0*(+ |    q0   |      c)$|  c  |
|Z0*(+ |    q0   |       )$|     |
|Z0*(+ |    )    |        $|  +  |
|Z0*(  |    )    |        $|     |
|Z0*   |    q0   |        $|     |
|Z0*   |    $    |         |  *  |
|Z0    |    $    |         |     |
+--------------------------------+
                . 5.2

          
a*(b+c)    . 5.2.

5.2.   

      (  ,
: -)   Tr=(N,T,,R,S), 

  N -    ;

  T -   ;

   -   ;

  R -         A->u,  A1=v1,
A2=v2, ... , Am=vm,   :

     -  ,   v1, ..., vm,  
,    Bk  B<-N  B   v ( k -
  B  v),

     -   u          B,  
  Bk   v  ( )
   B;

  S -  ,    N.

A->u          ,  Ai  -  
 A   Ai=vi  -  ,   
 .     P   
       ,    G=(N,T,P,S)  
   Tr.   - Tr   
      ,   
  .     -    
.        n      (
 ),   A,       
 Ai.       ( )
  Ai        n.        
           
 Ai=vi,      n.
  t(Tr),      -   Tr,   
 {(x,y)|x       
 Tr   y  -     S  
  }.    Tr=(N,T,,R,S)  -  -,    (Tr)
    (-).

     5.2.          
,    0  1,  x  
sin, cos, +  *.    

                E -> E+T | T
                T -> T*F | F
                F -> (E) | sin(E) | cos(E) | x | 0 | 1

      E,  T    F    ,  
 1   2.   1     ,   
,  2   -      .
   -    E2.    
:

 d(f(x)+g(x))=df(x)+dg(x)                       dx=1
 d(f(x)*g(x))=f(x)*dg(x)+g(x)*df(x)             d0=0
 dsin(f(x))=cos(f(x))*df(x)                     d1=0
 dcos(f(x))=-sin(f(x))df(x)

   -:

 E -> E+T    E1=E1+T1             F -> cos(E) F1=cos(E1)
             E2=E2+T2                         F2=-sin(E1)*(E2)
 E -> T      E1=T1                F -> x      F1=x
             E2=T2                            F2=1
 T -> T*F    T1=T1*F1             F -> 0      F1=0
             T2=T1*F2+T2*F1                   F2=0
 F -> ( E )  F1=(E1)              F -> 1      F1=1
             F2=(E2)                          F2=0
 F -> sin(E) F1=sin(E1)
             F2=cos(E1)*(E2)

   sin(cos(x))+x   . 5.3.

 5.1.        
v    1,   t(Tr)  -.  
  [5].

  5.2.  T=({S,A},{a},{a,b},{S->A,AbAbA;A->a,a;A->aA,aA}.
    {an|n>=1},   {anbanban}.  
  .

   5.2.            
  - [5].

,  ,  .

.    - Tr=(N,T,,R,S)
 ,         A->u,v    R
      
 u  v      .

                               E  E1=sin(cos(x))+x
                              / \ E2=cos(cos(x))
           E1=sin(cos(x))    / + \  *(-sin(x)*(1))+1
           E2=cos(cos(x))   E     T
             *(-sin(x)*(1)) |     | T2=1
                            |     | T1=x
           T1=sin(cos(x))   |     |
           T2=cos(cos(x))   T     F F1=x
             *(-sin(x)*(1)) |     | F2=1
                            |     |
           F1=sin(cos(x))   |     |
           F2=cos(cos(x))   F     x
             *(-sin(x)*(1)) |
                            |
                      sin ( E ) E1=cos(x)
                            |   E2=-sin(x)*(1)
                            |
                            T   T1=cos(x)
                            |   T2=-sin(x)*(1)
                            |
                            F   F1=cos(x)
                            |   F2=-sin(x)*(1)
                            |
                      cos ( E ) E1=x  E2=1
                            |
                            T   T1=x  T2=1
                            |
                            F   F1=x  F2=1
                            |
                            x

                          . 5.3

,    -,    
   ( -).

  5.3.     Tr=(N,T,,R,S)   -     -.
  - P,  t(P)=t(Tr) [5].

   ,   ,    
,     -.

 5.4.   Tr=(N,T,,R,S)  -  
 -,        LL(k)-
.          {x$,y)|(x,y)<-t(Tr)}    
  - [5].
           -,
       LR(k)     
    -.

 5.3.   - T  

          S -> Sa, aSa
          S -> Sb, bSb
          S -> e, e

       LR(1)   ,      
    -,        

{(x$,y)|(x,y)<-t(Tr)} [5].

.  - Tr=(N,T,,R,S) , 
   R   A->u,v,  v<-N**.
 ,        
   ,     
.

 5.5.   Tr=(N,T,,R,S)  -  
    -,      
 LR(k)-.     {(x$,y)|(x,y)<-t(Tr)}
   - [5].

5.3.  

      
     ,   -,   
  .    , 
       
     -,            
     .

5.3.1.   

 G  - -:  G=(T,N,P,Z),   T,  N,  P,  Z,  -
,                 ,
 ,         
.    -     


p: X0 -> X1 ... Xn

   ,   G -   -,
..          ,      
      ,        
.
   X <- N U T   A(X) 
 X.    A(x)   . 
a(X) ,  a <- A(X).
         p  <-  P      F
 ,   :

a0 = fpa0(a1, ... , aj),

 ik <- [0,np] -    p,  ak - 
 Xik , .. ak <- A(Xik).
       ,   a0  ""  
a1,...,aj          a0    "    "
a1,...,aj.      j    ,
   ,   a0 "  
 ".
-,             
 ,         -  
 ,       
(AG).
   a(X0) ,     
 p:  X0 ->X1  ... Xnp   
a<0>=fa<0>(...).       a(Xi)  ,  
    p:X0 -> X1 ... Xi ... Xnp 
   a=fa(...), i <- [1,np]. 
       X      S(X),
  -  I(X).
 ,      
- ,  ..    ,        
 ,   .

5.3.2.   

      AG   , 
,  G,      
    G.      
     G.          
 ,   ,  
 .  ,      
 ,       
,        
-   .
             
,              ,
   .

5.3.3.    

              
          .
     ,        
            
.            
              ,
  ""   .        
       
         
      [].
      
             
       ,       
     .        
,   ""     
      ,    
      .    
          ,         
 .       
               
        
     (      
    )    
 .         ,  
            .
                
,      . 
,           -
      ,      
,     .
 ,        ,
           
,             
   .     
           
.             
.    ,      ,
 L-.
       .
      ,   
  [   ],     .      
 ,      (  ), 
        .    
   ,        [()],
       .  
[]  [()]    .
      .

  ::= 'ALPHABET'
          (  ) (  )
 ::= 
                   '::' [(  / ';')] '.'
 ::= (  / ',') ':' 
 ::= 'RULE'  'SEMANTICS'  '.'
 ::=  '::=' 
 ::= [(  )]
 ::= 
         | 
         | '('  [ '/'  ] ')'
         | '['  ']'
         | '[('  [ '/'  ] ')]'
 ::= [(  ])
              [(  ])
 ::= 
           | [  ] 
 ::=  ':=' 

 ::= 
           |   
 ::= 
        |   
 ::=  '<'  '>'
 ::=  '<'  '>'
 ::=  ':'
       |   '' ':'
       |   '' ':'
 ::= 
         |   
         |   
         |   
         |   

          
       .        
         
   .         
  .         
  .           
       .    
                 
,    .
          
       -  .
 "i  : " ,    
       i-      .
 "i  E :  " ,     
 ,      i-   
 .    "i  A  :  "  ,  
       
i-        (      
).
         ( 
).          
     (  )          
       (0 
  , 1      ..),  
           (
).         
  .     ,      
   :       
,    ,        
 ,     ,     
,     -    
   (. 5.4).

                             |
                            ...
                          .  N  .
                         .  / \  .
                        .  /   \  .
                       .  /\   /\  .
                      .  / /\ /\ \  .
                     .  /  -- --  \  .
                    ...N...........N...
                      /\           /\
                      --           --

                         . 5.4

           VAL
 .

      6.    

6.1.      

                
   .    
               
   ,   
   .
      ,   ,  
              ,  
 .     
      "".      
     

E={DS1,...DSn}.

   -    , 
  <,>:

DSi={<,>},

            
 (,    ,        
).
   DSi   DSj       "DSi
 DSj"     ,     DSi
          DSj  (    
      ),      .
   .      
  (. 6.1

                     +-------------+
                     |     |
                     |   |
                     | () |
                     +-------------+
               +---------+  |  +--------+
               |            |           |
         +-----------++-----------++-----------+
         |  ||  ||  |
         | ()    ||   ()  ||  ()   |
         +-----------++-----------++-----------+
             /|\            /|\         /|\

                            . 6.1

      :
-     ;
-          ;
-     ,   
  ;
-    .

      .     
         .    
      ,      
""  ,   "" .
    ,      
   ,    " " 
"  ".         
 (),   ,      
 (   )   (). 
          ,  
    ,         
  .
        
  -.          
   -2.

6.2.   -2

         ,    
  :   1)           
; 2)   ; 3) ; 4) 
.
""     -2  
    .      
            
     .            
  (from   M  import   X,Y,   ...;)      
 (import M;).

               
                    
+------------+        +------------+     +------------+
| MODULE M1; |        |   +----+   |     | MODULE X1; |
| EXPORT A1;-+--------+-->| A1 |---+--+  | IMPORT A1; |
| .........  |        |   +----+   |  |  |            |
+------------+        |            |  +--+------> A1  |
                      |            |     +------------+
+--------------+      |            |
| MODULE M2;   |      |            |     +------------+
| EXPORT       |      |   +----+   |     | MODULE X2; |
| QUALIFIED A2-+------+-->| M2 |   |     | FROM M2    |
| ............ |      |   +----+   |     | IMPORT A2; |
+--------------+      |     v      | +---+---->A2     |
                      |   +----+   | |   +------------+
                      |   | A2 |---+-+
                      |   +----+   |
+-----------------+   |            |
| MODULE M3;      |   |   +-----+  |
| EXPORT M31;-----+---+-->| M31 |  |     +-------------+
|  +-------------+|   |   +-----+  |     | MODULE X3;  |
|  | MODULE M31; ||   |   +-----+  |     | IMPORT A31; |
|  | EXPORT A31;-++---+-->| A31 |--+-----+--> A31      |
|  | ..........  ||   |   +-----+  |  |  +-------------+
|  +-------------+|   |            |  |
| ................|   |            |  |  +-------------+
+-----------------+   |            |  |  | MODULE X    |
                      |            |  |  | IMPORT M31; |
                      |            |  +--+---> A31     |
                      v            v     +-------------+

+-------------------+ v            v
| MODULE M4;        | |   +-----+  |
| EXPORT M41;-------+-+-->| M41 |  |     +-------------+
|  +---------------+| |   +-----+  |     | MODULE X4;  |
|  | MODULE M41;   || |      v     |     | FROM M41    |
|  | EXPORT        || |   +-----+  |     | IMPORT A41; |
|  | QUALIFIED A41;|+-+-->| A41 |--+-----+----> A41    |
|  | ..........    || |   +-----+  |  |  +-------------+
|  +---------------+| |            |  |  +--------------+
| ..................| |            |  |  | MODULE X     |
+-------------------+ |            |  |  | IMPORT M41;  |
                      |            |  +--+-->A41        |
                      |            |     +--------------+
+-----------------+   |    +----+  |
| MODULE M5;      |   |    | M5 |  |      +-------------+
| EXPORT          |   |    +----+  |      | MODULE X5;  |
| QUALIFIED M51;--+---+-+     v    |      | FROM M5     |
|  +-------------+|   | |  +-----+ |      | IMPORT M51; |
|  | MODULE M51; ||   | +->| M51 |-+------+-> M51.A51   |
|  | EXPORT A51;-++---+-+  +-----+ |      +-------------+
|  | ..........  ||   | |     v    |
|  +-------------+|   | |  +-----+ |
| ................|   | +->| A51 | |
+-----------------+   |    +-----+ |
+-------------------+ |    +----+  |
| MODULE M6;        | |    | M6 |  |      +-------------+
| EXPORT            | |    +----+  |      | MODULE X6;  |
| QULIFIED M61;-----+-+-+     v    |      | FROM M6     |
|  +---------------+| | |  +-----+ |      | IMPORT M61; |
|  | MODULE M61;   || | +->| M61 |-+------+--> M61.A61  |
|  | EXPORT        || |    +-----+ |      +-------------+
|  | QUALIFIED A61;|+-+-+     v    |
|  | ............  || | |  +-----+ |
|  +---------------+| | +->| A61 | |
| ..................| |    +-----+ |
+-------------------+ +------------+

                         . 6.2

       
   ,    -   
   ,      
    (M.X).
   ,       ,
               
     ,         
 .           
 .  6.2.      ,
        ( 
   ).        
  , integer, real, boolean, char, word, address,
proc,   true, false,  nil,  adr, tsize, cap,
small, chr, inc, dec, float, halt, hihg, odd, ord, trunc, val,
excl, incl, max, min, size, abs.
             
,    .   
 ,    -  (. 6.3).
        
,        .  
                
,        . 
:       
   .         
   ,     
      .       
     :     
      (    
     ).

               (  )
              +------------+
              |       |<-----   
              |------------|<-----   
              |  |        
              +------------+
                 |^   |
           ||   | 
        +--------+|   +-----------+
        | +-------+               |
        v |                v
  +------------------+      +-----------+
  |   |      |  |
  |------------------|      |-----------|
  | ................ |      | ......... |
  |                  |      |           |
  +------------------+      +-----------+

                    . 6.3

      ,   .
            (,
  ..),   ,     
:
Object -   :  , ,    
..;
Mode -  : , ,   ..;
Name -  ;
Type -    .

6.3.      

       ,
         "
 "           .  
      , ,  
    ,      
       . 
,              ,   
 ,         
     (. 6.4).

                        Env
                       ^   ^
                      /     \
                    Env     Env
                    ^^       ^^
                   /  \     /  \
                 Env  Env  Env Env

                     . 6.4

              
.                  
,     .    
    ,      
:
SET OF  T -      
T;
KEY K SET OF T -    
 T   K;
LIST OF T -      T;
KEY K  LIST OF T -    
 T   K;

      :

  Init(S) -     S;

  Include(V,S)  -      V      S;  
 ,       
  ;

  Find(K,S) -              K  
 S  NIL,       .

       ,    
:

for V in S do ;

 V           
 .     ,   
   ,   -   .
             -
  .            -
            -  
  .        
           
,       .     
    -2 (  
 ).

ALPHABET
Prog:: Env : key Name set of Element.

 .    Name.

Block :: Env : key Name set of Element;
         Kind : boolean;
         Pred : pointer to Block.

 Kind  true    false  . Env -
   . Pred  -   
.

Mod_Head :: Entry : pointer to Element;
            Imp_Set : set of Import_Pair;
            Mode:boolean.

Imp_Set  -         ;  
Import_Pair -        :  Imp_Name:Name  -  
  ,    Name_Set:Set  of  Name  -  
             ,         
,   Nil,   ; Entry  -
              ;   Mode    -    
 .

Import ::  Imp_Set : set of Name.

Imp_Set -   .

Export ::  Mode:boolean.

Mode -   .

From :: Qual : boolean; Name : NameType.

Qual :: Qual : boolean.
Ident_List :: Ident_Set : set of Name.
Type_Des :: Exit : pointer to Element.

Qual -    ; Name -  ,
          ;    Ident_Set   -    
; Exit -    .

RULE
Declaration ::= 'procedure' Ident [ Formal_Param ] ';'
                Block ';'
SEMANTICS
var Entry:pointer to Element;
Kind<5>:=true;
2:if Find(Val<2>,Env)<>Nil
  then Error("Identifire declared twice");
  end;
  Entry:=Include(Val<2>,Env);
  Entry@.Object:=ProcObject.

 ;           
; Entry  -        .  
     , - .

RULE
Declaration ::= 'module' Ident Mod_Head Block ';'
SEMANTICS
var M:Import_Pair;
    V:Element;
if Find(Val<2>,Env)<>Nil
then Error("Identifire declared twice")
end;
Entry<3>:=Include(Val<2>,Env);
Entry<3>@.Object:=LocalModuleObject;
Kind<4>:=false;
3: for M in Imp_Set<3> do Inc_Imp(M,Env<4>);
   end;
if (Mode<3>=NotQual) then
 for V in Entry<3>@.Exp_Set do Export(V,Env);
end end.

 ;              
.      , - .   
     -.    Imp_Set  -  
       .    
  -   ,            -   
 ,   -     
.              Nil,       
.      M -   
  M        (IMPORT  M),  
 Inc_Imp   M      ;  
    (FROM  M IMPORT  ...),   M  
          Inc_Imp      
    M ,  
         ;         
    -        ,      M
     .
    Mode                
,           
(EXPORT QUALIFIED  ...)   (EXPORT ...).  Export
     EXPORT   A1,A2,... 
        ,
  ;     Ai   -   ,      
 ;    , 
        
 .

RULE
Block ::= [( Declaration )] [ Block_St_Seq ] 'end' Ident
SEMANTICS
0:Init(Env<0>);
  Pred<0>:=@.

 Pred -    .

RULE
Mod_Head ::= [ Priority ] ';' [ ( Import ) ] [ Export ]
SEMANTICS
4E: Mode<4>:=NotQual;
Entry<0>@.Mode:=Mode<4>;
Mode<0>:=Mode<4>;
0:Init(Imp_Set<0>).

   .        
 .

RULE
Import ::= [ From ] 'import' ( Ident /',' ) ';'
SEMANTICS
var Tmp:Import_Pair;
0:Init(Imp_Set<0>);
1E: Qual<1>:=false;

3A:if Qual<1> then Include(Val<3>,Imp_Set<0>)
   else Tmp.Name_Set:=Nil;
        Tmp.Imp_Name:=Name<3>;
        Include(Tmp,Imp_Set)
   end;
if Qual<1> then
        Tmp.Name_Set:=Imp_Set<0>;
        Tmp.Imp_Name:=Name<1>;
        Include(Tmp,Imp_Set)
end.

   ,   Name<1> -   ,  
  .    Imp_Set<0> - 
    .      
    ,    -   
        .    
,            
  .

RULE
From ::= 'from'  Ident
SEMANTICS
Qual<0>:=true;
Name<0>:=Val<2>.

RULE
Export ::= 'export'  [ Qual ]  ( Ident /',' )
SEMANTICS
0: Init(Entry@.Exp_Set);
2: Mode<2>:=NotQual;
    Mode<0>:=Mode<2>;
3A: Include(Val<3>,Entry@.Exp_Set).

       ; 
      Exp_Set : Key
Name  Set   Of  Element      ,    
        M.V,
 M  -   ,    V  -      ,
      .

RULE
Qual ::= 'qualified'
SEMANTICS
Qual<0>:=Qualified

RULE
Declaration ::= 'var' ( Var_Decl ).

RULE
Var_Decl ::= Ident_List ':' Type_Des ';'
SEMANTICS
var V:Name;
for V in Ident_Set<1> do
   if (Find(V,Env)<>Nil)
   then Error("Identifire declared twice")
   end;
   Include(V,Env);
   V@.Object:=VarObject;
   V@.Type:=Exit<3>;
end.

V -         .    
    Ident_Set<1>  -
            
.

RULE
Ident_List ::= ( Ident /',' )
SEMANTICS
0:Init(Ident_Set<0>);
1A:Include(Val<1>,Ident_Set<0>).

RULE
Type_Des ::= Ident
SEMANTICS
var P:pointer to Block;
P:=Block@;
repeat
  Exit<0>:=Find(Val<1>,P@.Env);
  if P@.Kind then P:=P@.Pred
  end;
until (Exit<0><>NIL)or(not P@.Kind);
if (Exit<0>=NIL)
then Exit<0>:=Find(Val<1>,Env)
end;
if (Exit<0>=Nil) then Error("  ")
else if (Exit<0>@.Object<>TypeObject) then
         Error("Not type object"); Exit<0>:=Nil;
end  end.

   P -       
.       ,       .
     ,  ,       -  ,    
.       ,  
    .   , 
,   - .
          .
6.5.

          +--------------------+
          |                    |
          |          Block |  Env<--------+
          |           |                   |
          |           |                   |
          |        Dec_List               |
          |           |                   |
          |           |                   |
          |       Declaration             |
          |           |      \            |
          |           |        \          |
          |           |       Block       |
          | +---------+---------->Env     |
          v |         |                   |
+-----> Imp_Set | Mod_Head |           Exp_Set<-+
|                     | \                       |
|                     |   \                     |
|                  Imp_List \                   |
|                     |       \                 |
|          +--------------+   Export            |
|          |              |     |               |
|        Import         Import  |--------+      |
|         /| Imp_Set       |    |        |      |
|       /  |      ^        |    |        |      |
|    From  |      |        |   Ident   Ident    |
|     |    |      |        |    |        |      |
|     |    |      |        |    v        v      |
|<--Ident  |      |        |     ---------------+
|     +-------+   |   +--------+
|     |       |   |   |        |
|   Ident   Ident | Ident    Ident
|     |       |   |   |        |
|     v       v   |   |        |
|      -----------+   v        v
+------------------------------

                      . 6.5

 7.    

           
.  ,      
     :           .
           
 ,          , 
    .  ,  
       .
       .  ,
           (
 ),          
 (     ).        
     ,      
     (      
).         ,    
    , , -,
       ,     -  -
       .  
 (, )  (  )  
        ,      
 .     
               :     
,   ,   
.

7.1.     

    ,          
   :  ()  . 
            .  
     :  1)    
              
 ; 2)    ,   
    /     
              
.      
  ,          
 -   .      
              
      .

7.2.  

    (  
        ),  
              
    ,   
 .  7.1.       ,   -
.

 +---------------------------------------+
 |                                       |
 |---------------------------------------|
 | s | o | r | t |   |   |   |   |   |   |<----
 |---+---+---+---+---+---+---+---+---+---|
 | a |   |   |   |   |   |   |   |   |   |<----
 |---+---+---+---+---+---+---+---+---+---|
 | r | e | a | d |   |   |   |   |   |   |<----
 |---+---+---+---+---+---+---+---+---+---|
 | i |   |   |   |   |   |   |   |   |   |<----
 |---------------------------------------|
 |                                       |
 +---------------------------------------+

                  . 7.1

, ,  -,         
  ,          
 (     );
-,     ,         
      .   
              
.     .
       N.  
 h  (   ),    
      0<=h(id)<=N-
1, id - .    h(id) , 
 ,     .   ,
       ,      id    
,  ( )   
          .    
 ,     , 
id      h(id).    - 
,    -      .    
     h2(h).  
 :      ,    
,        
,        .      
    h3(h2),  ..  , hi=h2 
i>=2.   h2     [0,N-1]
           -.    
.

1) h2(i)=(i+1) mod N

   ()   .  
  ,         "",  
          
  - .

2) h2(i)=(i+k) mod N,  k  N  .

-    ,   
   ,  "".

3) h2(i)=(a*i+c) mod N - " ".

 c   N      ,  b=-1  p 
   p,   N, b  4,  N
  4   [6].            
:

type Pair=record Yes:boolean;
                 Point:integer
          end;
 function Search(id):Pair;
 var H,H0: integer;
 begin H:=h(id); H0:=h;
      loop if T[H]=id then return(true,H)
           elsif T[H]=Empty then return(false,H)
           else H:=h2(H);
           if H=H0 then return(false,NIL);
 end   end end end;

  :   (true,P),         
,  P  -      ;  (false,NIL),  
         ;
(false,P),    ,    
  P.
      
:

function Insert(id):integer;
 var P:Pair;
 begin P:=search(id);
      with P do
      if not Yes and Point<>NIL
      then T[Point]:=id;
      end;
      return(Point)
 end; end;

       - 
      .     
        
,        .  7.2.    
   -    (EOS).
       -         
       .  
           (.
7.3).

     +-------------------------------------
     |                  +------------------
     |                  |       +----------
     |                  |       |    +-----
     |                  |       |    |
     |                  |       |    +--------------+
     |                  |       |                   |
     v                  v       v                   v
----------------------------------------------------------+
  | s | o | r | t |EOS| a |EOS| r | e | a | d |EOS| i |EOS|
----------------------------------------------------------+

                          . 7.2

     +---+
   0 |   |
     |---|
     |...|
     |---|   +----------+   +--------+
   9 | --+-->| Idenp |--+-->|    | x |
     |---|   +----------+   +--------+
     |---|      v            v
     |...|      
     |---|   +------------+
  20 | --+-->| Idenp |  x |
     |---|   +------------+
     |---|      v
     |...|      
     |---|   +--------+   +--------+   +-------+
  32 | --+-->|    |  -+-->|    |  -+-->|   | x |
     |---|   +--------+   +--------+   +-------+
     |...|      v            v
     |---|       
 210 |   |

              . 7.3

7.3.     

           
.    -      
    .       
     ,      
  (. 7.3).
           (    
  NIL).         id  
   H(id)      
T[H].        :

type Element= record IdenP:integer;
                     Next:pointer to Element;
              end;
Pointer=pointer to Element
function Search(Id):Pointer;
 var P:Pointer;
 begin P:=T[H(Id)];
      loop if P=nil then return(nil)
           elsif IdenTab[P^.IdenP]=Id then return(P)
           else P:=P^.Next
 end  end; end;

IdenTab -  .    
   :

function Insert(Id):Pointer;
 var P,H:Pointer;
 begin P:=Search(Id);
      if P<>nil then return(P)
      else H:=H(Id); new(P);
           P^.Next:=T[H]; T[H]:=P;
           P^.Idenp:=Include(Id);
      end;
      return(P);
 end;

             |--|       +------+      +------+
      H----->| -+-x---->|      |----->|      |----->
             |--| | +-->+------+      +------+
             |  | | |
             |--| | +------------+
                  |   +------+   |
                  +---|      |---+
            P-------->+------+

                         . 7.4.

   Include               
.   . 7.4.

7.4.  .

      ,     
.       :   
    .   
   .

1.      s     H.
       
    .          
 ord,            
    .

2.   H,   ,    ,  ..
   0   m-1,   m -      ,
,     H  m.
  ,           ,
 ,   ,   
,          .    
   .
    H  -     
.          
  H   q. ..  H0=0, Hi=q*Hi-
1+ci   1<=i<=k, k  -  .  q=1  
 .      ci
  q*Hi-1         2.         
   .
 Hashpjw,    [1], , 
 H=0.      c     H   4 
    c.  -    
H   1,    4     24  , 
    2   H      0    
  ,  1.

 #define PRIME 211
 #define EOS '\0'
 int Hashpjw(s)
 char *s;
 { char *p;
 unsigned H=0, g;
 for (p=s; *p != EOS; p=p+1)
  {H=(H<<4)+(*p);
    if (g = H & 0xf0000000)
       {H=H^(g>>24);
       H=H^g;
  }    }
 return H%PRIME;
 }
         . 7.5

7.5.   

       
   .      ,         
        (,
),  ..        '<',
,       .  
   ,     ,
 .      ,  
(   )    (   )  .
          ,      ,
       ,      ,
   ;    , 
   .        .
7.6.

        +---------------+
 TP --->|    |    |    -+--->Ident
        +-/----\--------+
         /      \
        v        v
      Left     Right

            . 7.6

        :

function SearchTree(Id,TP):Pointer;
 begin if Id=TP^.Ident then return(TP)
       elsif IdTP^Ident
          then return(Search_tree(Id,TP^.Right))
       else return(nil)
 end   end;

    

function Insert_tree(Id,TP):Pointer;
 function fill(var P):Pointer;
 begin if P=nil then
         P:=new(Element);
         P^.Ident:=include(Id);
         P^.Left:=nil; P^.Right:=nil;
         return(P);
       else return(Insert_tree(Id,P))
 end   end;
 begin if Id=TP^.Ident then return(TP)
       elsif Id|   | -+----->|   | -+---->|   |   |
         +------+      +------+     +-------+
             T1           T2           Tn

                   . 7.11

7.7.     

            
       .
      ,  ,      ,
     ,  
 -   .  
,   ,      ,  
        
.          
,       ,
           ,
,       .  
,           
   ,     ,    
       .    ,  
          (,  
       ,     
      ,   
       
 ).         
      , 
   . ,  -, 
                
          .    
        
 ,       , 
     ,        
       
.         ,  ,  .
,      -2    
  .     
""         .    
, ,     
        .

 8.  

    -      
       .     
         
  .       ,    
       ,     
:     (  ,  
),       ,         (

) .  ,      
: ,       
   , ,  ,  
 (,   )     
        .      
                 
    .
 -             
 .  ,        
      ,   
                 
 .            
                
,     ,      ,    
  .
           
         
           
.

8.1.  

           
   ,        
  Motorola 68020.

      :

  D -     ;

   -     ;

  POST  -  -    ()+:  
       
         
;

  PRE -  -   -():    
         
  ,           
  ;

  DIRECT -       :  
         ADDREG+INDEXREG*SCALE
+ADDRDISP -      +  
   ,         SCALE+
;

  INDPPRE  -  -    :  (ADDREG+INDEXREG*
SCALE+ADDRDISP)+INDEXDISP  -        
 ,     +    
  ;

  INDPOST -  -    :  (ADDREG+ADDRDISP)
+INDEXREG*SCALE+INDEXDISP  -        
 ,    +  
,    SCALE +  , 
 ;

  DIRPC -     PC (  ):  
   PC+INDEXREG*SCALE+ADDRDISP;

  INDPREPC -  -    PC:  (PC+INDEXREG*  SCALE+
ADDRDISP)+INDEXDISP -   ,   INDPRE,    
   PC;

  INDPOSTPC -  -  PC: (PC+ADDRDISP)+INDEXREG
*SCALE+INDEXDISP   ,    INDPOST,      
   PC;

  ABS - ;

  IMM -  .

      :

  MOVEA ,  -     
    ;

  MOVE 1,2  -         1
    2;

  MOVEM   , -     
   ;

  MOVEM ,   -   
    ;

  LEA ,   -        
 ;

  MUL ,D  -      
     D    
D;

  ADD ,D -       
   D     D;

  SUB ,D  -       
    D    
D;

  CMP ,D  -        D    
         ,    
   ,    D
 ;

  TST  -     ,  
  ;

  BNE   -       NE  (  )  
  ;

  BEQ    -          EQ  ()  
  ;

  BLE   -     LE (  )
   ;

  BGT   -          GT  ()  
  ;

  BLE   -     KE (  )
   ;

  BLT   -          LT  ()  
  ;

  BR  -     ;

  JSR  -        ;

  JMP  -     ;

  RTD    -      
 ;

  LINK A,    -        
 ,         
                
;

  UNLK A  -          
  .

8.2.   

         
  (, ,   ),  
      (      
)       . 
        (  )  
     ,   
.    ,       
             -   
       .  
  . 8.1.

       PROCEDURE P1;                          +----+
          VAR V1;                         P2  | V2 |
          PROCEDURE P2;                       |----|
             VAR V2;                          |....|
             BEGIN P2;                        |----|
                   V1:=...                P2  | V2 |
                   V2:=...                    |----|
             END P2;                      P1  | V1 |
          BEGIN P2;                           +----+
          END P1;

           . 8.1                        . 8.2

                
 ,      .  8.2.    
 P2,         
      P2        
   P1,       P2.  
,     
   .
        
:         . 
            ,
    ;     
         
        (,    ,    
     -       ""  
  ).           
,      ,      
 .

8.2.1.     

                                  
                +-----------------+<---------+
                |      |          |
                |         |          |
                |-----------------|          |
         |        |<--+      |
     |-----------------|   |Disp  |
      +--|  BP   |<--+- BP  |
             |  |-----------------|   |      |
             |  |    |   |Disp  |
             |  |-----------------|   |      |
             |  | .  |<--+      |
             ||-+-----------------+-|<-------+
             |  |      |
             |  |         |
             |  |-----------------|  LP
           +-+--|  LP   |<----+D
           | |  |-----------------|     |e
 | |  |        |     |l
| |  |                 |     |t
    | |  |-----------------|     |a
           | +->|  BP   |-----+
           v    +-----------------+
                  .................   

                       . 8.3

,         , 
   . 8.3.
  ,            
   BP (Base  pointer),     
 .     
LP (Link  Pointer).      BP  LP  
      , 
   .    
   BP ,     -   
,        
BP.
       
-.            
,      ,  
:

         
     JSR A

 JSR  A   SP,  PC  
       A.  
         ,    
   . 8.4.   BP,    ,
    .

              +---------------+
              |  |<---SP
              |---------------|
              |. |
             |+---------------+--|
              |    |
              |       |
              |---------------|    LP
           +--| LP  |<-------
           |  |---------------|
 |  |      |
|  |               |
    |  |---------------|  BP
           |  | BP  |<----
           v  |---------------|
              |...............|

                   . 8.4

            
       ,  
 -          (
).     :

          
       MOVE BP,LP
       SUB Delta,LP
       JSR A

 Delta  -       
   .     ,
  . 8.5.

                 +------------------+
                 |     |
                 |------------------|
                 | .   |
              |--+------------------+--|
                 |       |
                 |          |
                 |------------------|  LP
             +---|  LP    |<---+
             |   |------------------| D  |
   |   |                  | e  |
  |   |         | l  |
      |   |                  | t  |
             |   |------------------| a  |
             |   |  BP    |<---+
             v   |------------------|
                 | ................ |

                        . 8.5

              
 

         MOVE -Delta(BP),LP

       .
        1-  ,  
    ,      1-    
 .
    ,    ,  
  :

           
       MOVE (LP),LP /* ,  
                   */
       JSR A

           
.      

       MOVE -Delta(BP),LP

                
.

     :

       LINK BP,- 
       MOVEM -(SP)

 LINK BP,    :

       MOVE BP,-(SP)
       MOVE SP,BP
       ADD - ,SP

 MOVEM    .
       ,
  . 8.3.

                    
 :

       MOVEM (SP)+,D0-D7,A0-A7
       UNLK BP
       RTD  

 MOVEM      .  
  ,     . 8.6.

         +-----------------+<--SP
  |        |
  |-----------------|
         |  BP   |<--BP
         |-----------------|       +------------------+
         |    |       |     |<---SP
         |-----------------|       |------------------|
         | .  |       | .   |
      |-----------------------|    +------------------+
             .................     ..................
               . 8.6               . 8.7

     UNLK BP,   
 :

         MOVE BP,SP
         MOVE (SP),BP
         ADD #4,BP /*4 -  */

  ,   . 8.7.
,      RTD  _,
  

         ADD _, SP
         JMP -_(SP)

       ,      
.
       , 
          
   .

8.2.2.    

       .  -
   (DISPLAY)    ,  
      .
i-            
   i-  .  
         
 BP.       
      .      
       ()
.       (i) i- 
        
   .      DISPLAY[i]  
        
i-  .

                                  
                                   <------+
               |       |       |  
               |          |       |  
               |------------------|       |  
        |         |       |  
    |------------------|       |
     +--|  BP    |<-- BP <-+
            |  |------------------|       | |
            |  |     |       | |
            |  |------------------|       | |
            |  | .   |       | |
            |  |------------------|<------+ |  DISPLAY[i]
            |  |       |         |  ---------+
            |  |          |         +------*    |
            |  |------------------|            ---------+
            |  |        |
            |  | DISPLAY[i]       |
            |  |------------------|
  |  |         |
 |  |                  |
     |  |------------------|
            +->|  BP    |
               |------------------|
               |..................|

                     . 8.8

      DISPLAY[i]   ,
         
               .
          
. 8.8.          
(  ),     .

     |----------------------|<-------------------------+
        |       |             |
        |----------------|             |
        |        |                             |
        |----------------|  BP                         |
  +-----|  BP  |<-----                       |
  |     |----------------| BP   |
  |     |            x---+--------->             |
  |     |  .......| BP 1-   |
  |     |            x---+--------->                   |
  |     |----------------|                             |
  |     |   |                             |
  |     |----------------|                             |
  |     |     |                             |
  |  |--+----------------+--|<-------------------------+
  |     |       |
  |     |----------------|
  |     |        |
  |     |----------------|
  +---->|  BP  |
        |----------------|
        |         |
        |----------------|
        |   |
        |----------------|
     |--+     +--|

                          . 8.9.

    -   
( 8.9).      .   
            
  .           
              BP
 .
         
 .  ,     
(,  )       .    
    -     ,  
               
       ,           
        .  
                   
.
        
           
. ,  ,    -2    
      ,         
     .   
      "" ,   
    ,    
       .

8.3.  

   ,        
          .   
          
      
(  )               .  
      ,  
       -.
,         -      
   .      
    Table,     
()   :
-   -  ;
-   - ;
-    -   ;
-   -  ;
-     -   .

 IncTab    ()   
,      .
 LevelTab  -    , 
        (.  .
4.9).
        
 :  DISP    
   (   ),  SIZE - .
       

    RULE
    DeclPart ::= ( Decl )
    SEMANTICS
             Disp<1>:=0;
    1A:      Disp<1>:=Disp<1>+Size<1>;
             Size<0>:=Disp<1>.

          
(. 8.10).

                DeclPart | Size <----------+
                        /|\                |
                      /  |  \              |
                    /    |    \            |
                  /      |      \          |
                /        |        \        |
             Decl       Decl     Decl      |
                  Disp----->Disp--------->Disp
                + Size    + Size        + Size
                   ^         ^             ^
                   |         |             |

                        . 8.10

 ,     ,    
.        
:

     RULE
     Decl ::= 'VAR' TypeDes
     SEMANTICS
     var Entry:Tablentry;
     0:  Entry:=IncTab;
         Size<0>:=((Table[VAL<2>]+1) DIV 2)*2;
             {     }
         Table[Entry]:=Disp<0>+Size<0>.

           
  :

RULE
TypeDes ::= 'REC' ( TypeDes ) 'END'
SEMANTICS
var Disp:word;
    Temp:Tablentry;
0:  Entry<0>:=IncTab;
    Disp:=0;
2A: begin Temp:=IncTab;
          Table[Temp]:=Disp;
          Disp:=Disp+Table[Entry<2>]+1) div 2)*2;
          {     }
     end;
     Table[Entry<0>]:=Disp.

8.4.  .

           
.      ADDRESS - 
,        68020.    
   ,   . 
     68020      ,    
          ADDRESS,  
 :

Register=
   (D0,D1,D2,D3,D4,D5,D6,D7,A0,A1,A2,A3,A4,A5,A6,SP,NO);
AddrType=record
   AddrMode:(D,A,Post,Pre,Direct,IndPre,IndPost,
             DirPC,IndPrePC,IndPostPC,Abs,Imm);
   Addreg,IndexREG:Register;
   IndexDisp,AddrDisp:cardinal;
   Scale:1..8;
end;

   NO ,     
  .
             
:       
;         
   6.
          ,  
        
    5;    
   ""               
    .    
       
              
  VarTail,         -  
       Variable.     ,
       ( 
Number      -    ,  - 
-):

RULE
Variable ::= VarMode Number Number VarTail
SEMANTICS
var Temp:integer;
    AddrTmp1,AddrTmp2:AddrType;

3: if (Val<2>=0) then {   }
      Address<4>.AddrMode:=Abs;
            Address<4>.AddrDisp:=0;
   else {   }
        Address<4>.AddrMode:=Direct;
        if (Val<2>=Level) then
           {    }
           Address<4>.Addreg:=A6
        elsif (Val<2>=Level-1) then
             {    }
             Address<4>.Addreg:=A5;
        else Address<4>.Addreg
                 :=GetFree(RegSet);
             with AddrTmp1 do
                  AddrMode=Direct;
                  Addreg=A5;
                  IndexReg=No;
                  AddrDisp=0;
             end;
             Emit2(MOVEA,AddrTmp1,Address<4>.Addreg);
             AddrTmp1.Addreg;=Address<4>.Addreg;
             AddrTmp2.AddrMode=A;
             AddrTmp2.Addreg=Address<4>.Addreg;
             for Temp:=Level-Val<2> do
                  Emit2(MOVEA,AddrTmp1,AddrTmp2)
        end  end;
           if (Val<2>=Level) then
              Address<4>.AddrDisp:=Table[Val<3>]
           else Address<4>.AddrDisp:=Table[Val<3>]
                +Table[LevelTAB[Val<2>]].
   end     end.

 GetFree         (
 ,     )       
    RegSet  Block. 
Emit2    .     
 -   ,       
Address         (    
         
   '()';         
   ).     
    (6),      -  
   ,               
   LOCALSize    
(!).
       ,   
              
:

RULE
Variable ::= VarMode Number Number VarTail
SEMANTICS
var Temp:integer;
3: if (Val<2>=0) then {   }
      Address<4>.AddrMode:=Abs;
      Address<4>.AddrDisp:=0;
   else {   }
        Address<4>.AddrMode:=Direct;
        if (Val<2>=Level) then
           {    }
           Address<4>.Addreg:=A6;
           Address<4>.AddrDisp:=Table[Val<3>]
         else with Address<4> do
              AddrMode=IndPost; Addreg:=NO; IndexREG:=NO;
              AddrDisp:=DispLAY[Val<2>];
              IndexDisp:=Table[Val<3>]
   end   end  end.

      .  
  (Number -  -  ):

RULE
VarTail ::= 'FIL' Number VarTail
SEMANTICS
if (Address<0>.AddrMode=Abs) then
   Address<3>.AddrMode:=Abs;
   Address<3>.AddrDisp
     :=Address<0>.AddrDisp+Table[Val<2>];

else Address<3>:=Address<0>;
     if (Address<0>.AddrMode=Direct)
     then Address<3>.AddrDisp
          :=Address<0>.AddrDisp+Table[Val<2>]
     else Address<3>.IndexDisp
          :=Address<0>.IndexDisp+Table[Val<2>]
end  end.

         
 AddrDisp,     -  IndexDisp. 
, ,          
     - .
               
   (. 8.11):

                    VarTail | Disp---------------+
                            |                    |
                           / \                   |
                         /     \                 |
                       /         \               |
           +--------Number     VarTail | Disp <--+
           |                                     ^
           |              Table                  |
           |            |-------|                |
           +----------->| Disp  |----------------+
                        |-------|

                          . 8.11

      .  -
    :

VarTail ::= 'ARR' Number Typexpr VarTail

  Number  -          ;
Typexpr -   .     ,
 -,     ,
       ,     
Typexpr,          .  
         GetAddr  
   .

      VarTail  :
                  IndPre or Direct    (IndPost or Abs) or
                  IndexReg=NO         ((Direct or IndPre)
                                       & (IndexReg<>NO))
---------------------------------------------------------
ElSize<3>=    | AddrDisp<4>:=       |AddrDisp<4>:=
   1,2,4,8    |  AddrDisp<0>        |-Left<2>*ElSize<3>
AddrMode<3>=D | -Left<2>*ElSize<3>  |AddrMode<4>:=IndPost
              | Addreg<4>:=Addreg<0>|Addreg<4>:=
              | IndexReg<4>:=       |if Addreg<0> 
              |    Addreg<3>        |then Addreg<0>
              | AddrMode<4>:=IndPost|else GetAddr
              | Scale<4>:=ElSize<3> |IndexReg<4>:=
              |                     |   Addreg<3>
              |                     |Scale<4>:=ElSize<3>
              |                     |-------------------
              |                     |LEA Address<0>,
              |                     |    Address<4>
---------------------------------------------------------

---------------------------------------------------------
ElSize<3>    | AddrDisp<4>:=       | AddrDisp<4>:=
  <>1,2,4,8  |  AddrDIP<0>-        | -Left<2>*ElSize<3>
AddrMode<3>=D|  Left<2>*ElSize<3>  | AddrMode<4>:=IndPost
             | Addreg<4>:=Addreg<0>| Addreg<4>:=
             | IndexReg<4>:=       | if Addreg<0> 
             |    Addreg<3>        | then Addreg<0>
             | Scale<4>:=1         | else GetAddr
             | AddrMode<4>:=IndPost| IndexReg<4>:=
             |---------------------|  Addreg<3>
             | MUL ElSize<3>,      | Scale:=1
             |     Addreg<3>       |-------------------
             |                     | LEA Address<0>,
             |                     |     Address<4>
             |                     | MUL ElSize<4>,
             |                     |     IndexReg<4>
---------------------------------------------------------

---------------------------------------------------------
ElSize<3>=    |AddrDisp<4>:=       | AddrDisp<4>:=
   1,2,4,8    |AddrDisp<0>-        | -Left<2>*ElSize<3>
AddrMode<3><>D|Left<2>*ElSize<3>   | AddrMode<4>:=IndPost
              |Addreg<4>:=Addreg<0>| Addreg<4>:=
              |IndexReg<4>:=GetFree| if Addreg<0> 
              |AddrMode<4>:=IndPost| then Addreg<0>
              |Scale<4>:=ElSize<3> | else GetAddr
              |--------------------| IndexReg<4>:=GetFree
              |MOVE Address<3>,    | Scale<4>:=ElSize<3>
              |     IndexReg<4>    |-------------------
              |                    | LEA Address<0>,
              |                    |     Address<4>
              |                    | MOVE Address<3>,
              |                    |      IndexReg<4>
--------------------------------------------------------

---------------------------------------------------------
ElSize<3>     |AddrDisp<4>:=       | AddrDisp<4>:=
 <>1,2,4,8    |AddrDisp<0>-        | -Left<2>*ElSize
AddrMode<3><>D|Left<2>*ElSize<3>   | AddrMode<4>:=IndPre
              |Addreg<4>:=Addreg<0>| Addreg<4>:=
              |IndexReg<4>:=GetFree| if Addreg<0> 
              | AddrMode<4>:=IndPre| then Addreg<0>
              | Scale<4>:=ElSize<3>| else GetAddr
              |--------------------| IndexReg<4>:=GetFree
              |MOVE Address<3>,    | Scale<4>:=1
              |      IndexReg<4>   |----------------
              | MUL ElSize<3>,     | LEA Address<0>,
              |     IndexReg<4>    |     Address<4>
              |                    | MOVE Address<3>,
              |                    |      IndexReg<4>
              |                    | MUL ElSize<3>,
              |                    |     IndexReg<4>
--------------------------------------------------------

 ""             
,       ( "
"       6    5,
            
 ).
MaxReg -        ,  
       .        
    :   ,   MaxReg,
   ,   -  .
 GetAddr        
.     :

RULE
VarTail ::= 'ARR' Number Typexpr VarTail
SEMANTICS
Size:integer;
Flag:boolean;
AddrTmp1,AddrTmp2:AddrType;
Flag:= ((Address<0>.AddrMode=IndPre)
      or (Address<0>.AddrMode=Direct))
      and (Address<0>.IndexReg=NO);
Size:=Table[Val<2>];

if (Address<3>.AddrMode=D)
then IndexReg<4>:=Addreg<3>
else IndexReg<4>:=GetFree;
end;
AddrMode<4>:=IndPre;

if Flag then
   Address<4>.AddrDisp
      :=Address<0>.AddrDisp
        -Table[Val<2>]*Size;
   Addreg<4>:=Addreg<0>;
else Address<4>.AddrDisp:=
        -Table[Val<2>]*Size;
     if (Address<0>.Addreg<=MaxReg)
     then Addreg<4>:=Addreg<0>
     else Addreg<4>:=GetAddr;
end  end;

if (Size in [2,4,8])
then Address<4>.Scale:=Size)
else Address<4>.Scale:=1;
end;
AddrTmp1.AddrMode:=D; AddrTmp1.Addreg:=IndexReg<4>;
if Flag then Emit2(LEA,Address<0>,Address<4>) end;
if (Address<3>.AddrMode<>D)
then Emit2(MOVE,Address<3>,AddrTmp1);
end;
AddrTmp2.AddrMode:=IMM; AddrTmp2.AddrDisp:=ElSize<3>;
if not (Size IN [1,2,4,8])
then Emit2(MUL,AddrTmp2,AddrTmp1);
end.

8.5.   

     
         . 
       
  .
     68020        ,
       
(              
""):

  1)            ()     
      ,   
    ,      
     ;
  2)          "",   ..   
          
(, ,       
..).
         
      .  ,
              
.8.12.

                      2
                      R          V
           +-----------------------------+
      |   R | ADD A1,A2 | ADD A2,A1 |
    |-----+-----------+-----------|
    A1     |   V | ADD A1,A2 | MOVE A1,R |
           |     |           | ADD A2,R  |
           +-----------------------------+

                       . 8.12

   ,  R -   , V - 
-   .     
     .       
  :

RULE
IntExpr ::= 'PLUS' IntExpr IntExpr
SEMANTICS
if (Address<2>.AddrMode<>D)
   and (Address<3>.AddrMode<>D) then
       Address<0>.AddrMode:=D;
       Address<0>.Addreg:=GetFree(RegSet);
       Emit2(MOVE,Address<2>,Address<0>);
       Emit2(ADD,Address<2>,Address<0>);
else if (Address<2>.AddrMode=D) then
        Emit2(ADD,Address<3>,Address<2>);
        Address<0>:=Address<2>);
     else Emit2(ADD,Address<2>,Address<3>);
          Address<0>:=Address<3>);
end  end.

8.6.     
       

                 
 .      
             
,   -.
            
 ,     
. ,      ,  
            
.

                            |
                           / \
                       R1 /\  \
                          --  /\
                          R2 /\ \
                             -- /\
                            Rn /\ \
                               --  \
                                   /\LR
                                 L/\/\R
                                  ----

                            . 8.13

    ,              
           -,   
   . 8.13.        
 LR   n .   L  nl
,    R  - nr  .  nl=nr,  
 L     nl    
   n+1-  .    nr  (=nl)    
    R.    ,    
    n+nl+1.
 nl>nr,        L      nl
.       R         nr=lr

         . 8.14                 . 8.15

  2)         l1  l2, 
         l1 
l2   l1+1,  l1=l2.
     ,      
      .
     
.

  :

  1)    .

  2)       ,  
      ,  , 
  -          (    
          R).   
          ,
  ,             
      R (.  8.15).    
    .

    :

  1)       -            1,    
   LOAD X,R,  R - ,  
,   X -   ,     (.
8.16.);

  2)            -    
 0,    

   
 Op X,R

   R -  ,    ,  X - 
,   ,  Op - , 
  (. 8.16.);

  3)          
      ,    


    
    
  Op R+1,R

 R  - ,     ,  
Op,  ,   (. 8.17 )).

    R                R             R                R
    |                |             |                |
   / \              / \           / \              / \
  /   \R         R /   \        R/   \R+1      R+1/   \R
 X    /\          /\    X       /\   /\          /\   /\
(0)   --          --   (1)      --   --          --   --
    )               )            )               )

          . 8.16                   . 8.17

                
,    

    
    
  Op R,R+1
  MOVE R+1,R

         ,    
      (   
                 
 )(. 8.17 )).
   ,     
 .         
         , 
,   -        
              .
, ,   :  
   ,      
 .

RULE
Expr ::= IntExpr
SEMANTICS
Reg<1>:=1; Left<1>:=true.

RULE
IntExpr ::= Term AddOp IntExpr
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Reg<1>:=if Label<1> < Label<3>
            then Reg<0>+1
            else Reg<0>;
Reg<3>:=if Label<1> < Label<3>
            then Reg<0>
            else Reg<0>+1;
Code<0>:=if Label<1>=0
        then Code<3>||Code<2>
             ||Code<3>||","||Reg<0>
        else if Label<1> < Label<3>
        then Code<3>||Code<1>||Code<2>||
             Reg<0>+1||","||
             Reg<0>
        else Code<1>||Code<3>||Code<2>||
             Reg<0>||","||Reg<0>+1
             ||"MOVE"||Reg<0>+1
             ||","||Reg<0>.
IntExpr ::= Term =>
              Left<1>:=Left<0>; Code<0>:=Code<1>;
              Label<0>:=Label<1>; Reg<1>:=Reg<0>.

RULE
Term::= Factor MultOp Term
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Reg<1>:=if Label<1> < Label<3>
            then Reg<0>+1
            else Reg<0>;
Reg<3>:=if Label<1> < Label<3>
            then Reg<0>
            else Reg<0>+1;

Code<0>:=if Label<1>=0
        then Code<3>||Code<2>

             ||Code<3>||",""||Reg<0>
        else if Label<1> < Label<3>
        then Code<3>||Code<1>||Code<2>||
             Reg<0>+1||","||
             Reg<0>
        else Code<1>||Code<3>||Code<2>||
             Reg<0>||","||Reg<0>+1
             ||"MOVE"||Reg<0>+1
             ||","||Reg<0>.

RULE
Term ::= Factor
SEMANTICS
Left<1>:=Left<0>; Code<0>:=Code<1>;
Label<0>:=Label<1>; Reg<1>:=Reg<0>.

RULE
Factor ::= Ident
SEMANTICS
Label<0>:=if Left<0> then 0 else 1;
Code<0>:=if not Left<0> then
   "LOAD"||Reg<0>||","||Val<1>
        else Val<1>.

RULE
Factor ::= ( IntExpr )
SEMANTICS
Left<2>:=Left<0>; Code<0>:=Code<2>;
Label<0>:=Label<2>; Reg<2>:=Reg<0>.

RULE
AddOp ::= '+'
SEMANTICS
Code<0>:="ADD".

RULE
AddOp ::= '-'
Code<0>:="SUB".

RULE
MultOp ::= '*'
SEMANTICS
Code<0>:="MUL".

RULE
MultOp ::= '/'
SEMANTICS
Code<0>:="DIV".

                         Expr
                           |
                        IntExpr
                         / |  \  Left=true
                       /   |    \Label=2
                    /      |      \Reg=1
            Term         AddOp      IntExpr
           / | \  Left=true|          /  | \  Left=false
          /  |   \Label=1   |        /    |   \Label=2
         /   |     \Reg=2   |      /      |     \
        /    |       \      +    /        |       \
   Factor MultOp    Term      Factor   MultOp   Term
 |Left=true |       |Left=false |Left=true |     |Left=false
 |Label=0   |       |Label=1    |Label=0   |     |Label=1
 |Reg=2     *       |Reg=3      |Reg=1     *     |Reg=1
Ident             Ident       Ident          Factor
 A                  B            C            | Left=false
                                              | Label=1
                             -----------------  Reg=1
                           /|\
                         (  |  )
                         IntExpr
                          / | \  Left=false
                        /   |   \Label=1
                      /     |     \Reg=1
                  Term    AddOp IntExpr
               |Left=true   |        | Left=false
               |Label=0     |        | Label=1
               |Reg=2       +        | Reg=1
            Factor                 Term
               |Left=true            | Left=false
               |Label=0              | Label=1
               |Reg=2                | Reg=1
             Ident                 Factor
               D                     | Left=false
                                     | Label=1
                                     | Reg=1
                                   Ident
                                     E

                    . 8.18.

    A*B+C*(D+E)  
. 8.18.      :

 LOAD E,R1
 ADD D,R1
 MUL C,R1
 LOAD B,R2
 MUL A,R2
 ADD R2,R1

         
.           ,  
         
     [9].
         ,   
 .     
   . 8.19.
    ,   ,
   -   ,          
,    +1,    .   
           ,  
      ,     ,
         ,  
   .

                  | ^
                  | | Label
                 / \
               /     \
             /         \
    Left=0 /Label-->Left\
          /\             /\ Reg<0>:=if (Left<0>=Label<0>)
         /  \           /  \           &(Left<0>#0)
        /    \         /    \       then Label<0>+1
       /      \       /\    /\      else Label<0>
      /        \     /  \  /  \
      ----------     ----  ----

                  . 8.19.

          
:

RULE
Expr ::= IntExpr
SEMANTICS
Code<0>:=Code<1>; Left<1>:=true.
RULE
IntExpr ::= Term AddOp IntExpr
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Code<0>:=if Label<3> > Label<1> then
           if Label<1>=0 then
              Code<3>||Code<2>||Code<1>
              ||","||Label<3>
           else Code<3>||Code<1>||Code<2>||
                Label<1>||","||Label<3>
        else if Label<3> < Label<1> then
                Code<1>||Code<3>||Code<2>||
                Label<1>||","||Label<3>||
                "MOVE"||Label<3>||","||
                Label<1>
        else {Label<3>=Label<1>}
                Code<3>||"MOVE"||Label<3>||
                ","||Label<3>+1||Code<1>||
                Code<2>||Label<1>||","||
                Label<1>+1.

RULE
IntExpr ::= Term
SEMANTICS
Left<1>:=Left<0>; Code<0>:=Code<1>;
Label<0>:=Label<1>.

RULE
Term ::= Factor MultOp Term
SEMANTICS
Left<1>:=true; Left<3>:=false;
Label<0>:=if Label<1>=Label<3>
          then Label<1>+1
          else Max(Label<1>,Label<3>);
Code<0>:=if Label<3> > Label<1> then
           if Label<1>=0 then
              Code<3>||Code<2>||Code<1>
              ||","||Label<3>
           else Code<3>||Code<1>||Code<2>||
                Label<1>||","||Label<3>
        else if Label<3> < Label<1> then
                Code<1>||Code<3>||Code<2>||
                Label<1>||","||Label<3>||
                "MOVE"||Label<3>||","||
                Label<1>
        else {Label<3>=Label<1>}
                Code<3>||"MOVE"||Label<3>||
                ","||Label<3>+1||Code<1>||
                Code<2>||Label<1>||","||
                Label<1>+1.

RULE
Term ::= Factor
SEMANTICS
Left<1>:=Left<0>; Code<0>:=Code<1>;
Label<0>:=Label<1>.

RULE
Factor ::= Ident
SEMANTICS
Label<0>:=if Left<0> then 0 else 1;
Code<0>:=if Left<0> then Val<1>
        else "LOAD"||Val<1>||"R1".

RULE
Factor ::= ( IntExpr )
SEMANTICS
Left<2>:=Left<0>; Code<0>:=Code<2>;
Label<0>:=Label<2>.

RULE
AddOp ::= '+'
SEMANTICS
Code<0>:="ADD".

RULE
AddOp ::= '-'
SEMANTICS
Code<0>:="SUB".

RULE
MultOp ::= '*'
SEMANTICS
Code<0>:="MUL".

RULE
MultOp ::= '/'
SEMANTICS
Code<0>:="DIV".

               
,        ,  
,        .  
,      .    -
,         
       ,    
   .
  A*B+C*(D+E)    :

 LOAD E,R1 -  E  1 
 ADD D,R1 -  D  E     1 
 MUL C,R1 -  C  D+E    1 
 MOVE R1,R2 -     R2
 LOAD B,R1-  B  1 
 MUL A,R1 -  A  B    1 
 ADD R1,R2 -  A*B  C*(D+E)     2
             

     ,  
,        .
    ,       
         (
).

8.7.   

   ,         ,
       ,         
,   ,    
 ,   :

A & B  if A then B else False,

A v B  if A then True else B.

           
 ,  ,   ,    
       .      
     ,      
     (,    ),  
 ,        
  (,  -2 ,  
    ),    
             (,   ).
        
        ,
          .  
        
(     "      ").
        
 .
      
 :

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>:=False; TrueLab<1>:=True.

RULE
BoolExpr ::= BoolExpr '&' BoolExpr
SEMANTICS
FalseLab<1>:=FalseLab<0>; TrueLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>.

RULE
BoolExpr ::= BoolExpr 'V' BoolExpr
SEMANTICS
TrueLab<1>:=TrueLab<0>; FalseLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>.

RULE
BoolExpr ::= F
SEMANTICS
GOTO FalseLab<0>.

RULE
BoolExpr ::= T
SEMANTICS
GOTO TrueLab<0>.

 ,         
      NodeLab.   ,
    . 8.20.

         TrueLab                    TrueLab
       FalseLab\                  FalseLab\
           / | \\                      /| \\
          / / \ \\                    // \ \\
         / / & \ \\                  // V \ \\
        / /     \ \\                //     \ \\
FalseLab /       \ \TrueLab  TrueLab/       \ \TrueLab
        /         \FalseLab        /         \ FalseLab
TrueLab<-------NodeLabel      FalseLab<---NodeLabel

                    . 8.20.

       
   (),    
       :  
       ,      F  
    GOTO      FalseLab<0>,  
 T  - GOTO    TrueLab<0>. , 
 F  V (  F &  T &  T )  V T   
  ,   . 8.21  8.22.:

                 F V ( F & T & T ) V T
                 | FalseLab=False
                 1 TrueLab=True
                /
TrueLab=True   / V \
FalseLab=2    /     \  FalseLab=False
              F      2 TrueLab=True
                    / \
     TrueLab=True  / V \
    FalseLab=3    /     \
                 /       \
                 4        3
                / \       |
TrueLab=5      / & \      T
FalseLab=3    /     \   TrueLab=True
             /       \  FalseLab=3
             F        5
                     / \
      TrueLab=6     / & \                   1: GOTO 2
     FalseLab=3    /     \   TrueLab=True   2:
                  /       \  FalseLab=3     4: GOTO 3
                  T        6                5: GOTO 6
                           |                6: GOTO True
                           T                3: GOTO True

              . 8.21                      . 8.22

           
   :        
           
,      True   False,    
  true  false,  .  ,
          (  )
 ,      ( 
)      ,   GOTO True    GOTO
False.

  1.            
     ,      
       ,      
             ,   ..
    True   ,    T,  
   False   F.
     .

  2.             
   FalseLab  TrueLab   
   GOTO  TrueLab,      
,    GOTO  FalseLab,      
.
           .
   1,   BoolExpr ::= F
 BoolExpr  ::= T,      .
       n>1.      
     . 8.23

                         | FalseLab0
                         | TrueLab0
                        / \
                       / & \
FalseLab1=FalseLab0   /     \  FalseLab2=FalseLab0
TrueLab1=NodeLab2    /       \ TrueLab2=TruLab0
                    /\       /\
                   /  \     /  \
                   ----     ----

                             147
                         | FalseLab0
                         | TrueLab0
                        / \
                       / V \
FalseLab1=NodeLab2    /     \  FalseLab2=FalseLab0
TrueLab1=TruLab0     /       \ TrueLab2=TruLab0
                    /\       /\
                   /  \     /  \
                   ----     ----

                     . 8.23

              
      GOTO
FalseLab1,              
 GOTO  FalseLab0 (=FalseLab1).      
 ,       
GOTO TrueLab1  (=NodeLab2).       
,       GOTO
FalseLab0 (=FalseLab2).       ,  
      GOTO TrueLab0 (=TrueLab2).
 -  .
   1    ,   
       TrueLab=True 
FalseLab=False.
      :

BoolExpr ::= Ident
SEMANTICS
 else GOTO FalseLab<0>>;

, ,       
:

1: if Ident=T then GOTO True else GOTO 2
2:
4: if Ident=T then GOTO 5 else GOTO 3
5: if Ident=T then GOTO 6 else GOTO 3
6: if Ident=T then GOTO True else GOTO 3
3: if Ident=T then GOTO True else GOTO False

       
    .

  3.        ,  
  ,      
 .
,      TrueLab 
FalseLab,                
FalseLab,   TrueLab       
.   ,    FalseLab,   
TrueLab,            .  
,              
TrueLab       FalseLab,             
 .    ,
 .
     :

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>:=False; TrueLab<1>:=True;
Sign<1>:=false.

RULE
BoolExpr ::= BoolExpr & BoolExpr
SEMANTICS
FalseLab<1>:=FalseLab<0>; TrueLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>;
Sign<1>:=false; Sign<3>:=Sign<0>.

RULE
BoolExpr ::= BoolExpr V BoolExpr
SEMANTICS
TrueLab<1>:=TrueLab<0>; FalseLab<1>:=NodeLab<3>;
FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>;
Sign<1>:=true; Sign<3>:=Sign<0>.

RULE
BoolExpr ::= not BoolExpr
SEMANTICS
FalseLab<1>:=TrueLab<0>; TrueLab<1>:=FalseLab<0>;
Sign<1>:=not Sign<0>.

RULE
BoolExpr ::= F
SEMANTICS
GOTO FalseLab<0>.

RULE
BoolExpr ::= T
SEMANTICS
GOTO TrueLab<0>.

RULE
BoolExpr ::= Ident
SEMANTICS
if Sign<0>
then  else GOTO FalseLab<0>>
else  else GOTO TrueLab<0>>;

   Sign   . 8.24.

false |          true |        false |      true |
     or              or             and         and
     /\              /\             /\          /\
    /  \            /  \           /  \        /  \
   /    \          /    \         /    \      /    \
true   false    true  true     false false  false true

              true |        false |
                   |              |
                  not            not
                   |              |
                   |              |
                 false          true

                      . 8.24

      ,  else-
         .    
,    4.

 4.    ,  
           FalseLab
 ,      ,    
Sign      true,   ,   
       TrueLab 
,      ,     Sign
 false.
          
   :

RULE
BoolExpr ::= Ident
SEMANTICS
if Sign<0>
then >
else >.

   ,          

   :

RULE
BoolExpr ::= Ident
SEMANTICS
;
if Sign<0> then >
else >.

       ,  
 ,    (beq 
=, bne    <>,  bge    >=    ..),      sign
     true,   (bne
 =, beq  <>, blt  >=  ..),   sign 
 false.
   .    A  AND  (B  OR  C)
    . 8.25. 
(NOT((A=B)OR(C<>D)))AND(not((EH)))     
  . 8.26.

              TST A                      CMP A,B
              BEQ False                  BEQ False
              TST B                      CMP C,D
              BNE True                   BNE False
              TST C                      CMP E,F
              BEQ False                  BGE False
        True:                            CMP G,H
       False:. . .                       BGT False
                                    True:
                                   False:

                . 8.25            . 8.26

8.8.   

        
   .
1.             
 ,        
                
.       .
       0. 
       1.
2.         
       .    
  ( ,    ,
   'op';       
)    ,     op.  
 ,     op   ,      
             
,      -       
  ,     
               
      .         
:               
     ,   
 .        ,
    ,   op (. 8.27).

                |<-----| op |<-------|
               / \                  / \
              /   \                /   \
       +---->/\   /\<-----+ +-----/\   /\---+
       |    /  \ /  \     | |    /  \ /  \  |
       |    ---- ----     | |    ---- ----  |
       |                  +-+---------------+
       +--------------------+

                        .8.27

             
.    :
Table -   ;     
   (Count)        , 
          
(Last);
OpTable -      ,   
   (Addr -     , List -
 );

      :

NodeType =
 record Left  --   ;
        Right --   ;
        Comm  --     ;
        Flag --  ,   
                  ;
        Varbl -- ,    ;
        VarCount --  ;
 end;

         (    
LisType),    OpTable[Op],      
. 8.28.

           |<------------|<-------------|<---------| | Op
          / \           / \            / \         OpTable
         /   \         /   \          /   \
        /\   /\       /\   /\        /\   /\
       /  \ /  \     /  \ /  \      /  \ /  \
       ---- ----     ---- ----      ---- ----

                        . 8.28

                   
      .    Entry
 Variable        .
  Val    Op      .    Node
 IntExpr   Assignment       
NodeType  .

RULE
Assignment ::= Variable IntExpr
SEMANTICS
Table[Entry<1>].Count:=Table[Entry<1>].Count+1.
{   }

RULE
IntExpr ::= Variable
SEMANTICS
with Node<0>^ do with Table[Entry<1>] do
  if Last<>NIL
     {     }
        and Last^.VarCount = Count then
     {        }
     Flag:=true;
     {  -   }
     Comm:=Last;
     {     }
   else Flag:=false;
   end;
   Last:=^Node<0>; {  
                     }
   VarCount:=Count; {  }
   Varbl:=true; { - }
end end.

RULE
IntExpr ::= Op IntExpr IntExpr
SEMANTICS
var L:pointer to Listype; {  }
if Node<2>^.Flag and Node<3>^.Flag then
   {  ,   -   }
   L:=OpTable[Val<1>];
   {       }
   while L<>nil do
      if (Node<2>=L^.Left)
          and (Node<3>=L^.Right)
           {      }
      then exit
      else L:=L^.List;{  }
   end end
else L:=nil; {  }
end;

with Node<0>^ do
  Varbl:=false; {   }
  Comm:=L;
  {      nil}
  if L<>nil then
     Flag:=true; { }
     Left:=Node<2>;
     {     }
     Right:=Node<3>;
     {     }
  else Flag:=false;
  {        }
  {       ,
        }
       new(L);
       L^.Addr:=^Node<0>;
       L^.List:=OpTable[Val<1>];
       OpTable[Val<1>]:=L;
end end.

          
    .   
,       .
1.        
    (,  ,   
)  ,             
.   ,           ,
         .  
 ,    .
2.      .     
.        ,    
      ,   
,             
             .
   ,      +
              
         .   
   MOVE ,      
   :      
 ,     .

8.9.     
       

8.9.1.  

   ,   ,   
                
      . 
       ,
   .
        "  ":
     "", 
         ,  
    ""      
.    ,    
   .

                    :=
                     |
               -------------
              /             \
             +               +
            / \            /   \
           /   \          /     \
     const(a) const(x)   @       const(5)
                         |
                         |
                         +
                       /    \
                      /      \
                     +         @
                    / \        |
                   /   \       |
            const(b)  const(y) +
                              / \
                             /   \
                      const(i)  const(z)

                      . 8.29

 .  8.29          
a:=b[i]+5,   a,b,i  -    ,    
 x,y,z      .
   b       .
0-     const         
    ,   
      .    '@'
       
     ,    ,    
.

+------------------------------------------------------+
|-|              |   ||
||                     | |         |
|---+---------------------+----------------------------|
| 1 |   const(c)          |   MOV #c,Ri           | 2  |
|   |                     |   Reg->Const          |    |
|---+---------------------+-----------------------+----|
| 2 |        :=           | MOV Rj,c(Ri)          | 4  |
|   |        /  \         |                       |    |
|   |       /    \        |                       |    |
|   |       +    reg(j)   |                       |    |
|   |     /   \           | Stat->':=' '+' Reg    |    |
|   |reg(i)  const(c)     |             Const Reg |    |
|---+---------------------+-----------------------+----|
| 3 |          @          | MOV c(Rj),Ri          | 4  |
|   |          |          |                       |    |
|   |          +          |                       |    |
|   |         / \         |                       |    |
|   |        /   \        |Contents -> '@' '+' Reg|    |
|   |   reg(j)  const(c)  |             Const     |    |
|---+---------------------+-----------------------+----|
| 4 |        +            |   ADD #c,Ri           | 3  |
|   |       / \           |                       |    |
|   |      /   \          |                       |    |
|   |  reg(i)  const(c)   |Reg -> '+' Reg Const   |    |
|---+---------------------+-----------------------+----|
| 5 |       +             | ADD Rj,Ri             | 2  |
|   |      / \            |                       |    |
|   |     /   \           |                       |    |
|   | reg(i)  reg(j)      |   Reg -> '+' Reg Reg  |    |
|---+---------------------+-----------------------+----|
| 6 |      +              | ADD c(Rj),Ri          | 4  |
|   |     / \             |                       |    |
|   |    /   \            |                       |    |
|   |reg(i)    @          |                       |    |
|   |          |          |   Reg -> '+' Reg '@'  |    |
|   |          +          |     '+' Reg Const     |    |
|   |        /   \        |                       |    |
|   |    reg(j)  const(c) |                       |    |
|---+---------------------+-----------------------+----|
| 7 |         @           |   MOV (R),R           | 2  |
|   |         |           |                       |    |
|   |        Reg          |   Reg -> Contents     |    |
+------------------------------------------------------+
                         . 8.30

----------[stat]----------------------------------
|2          :=                                   |
|         /    \                                 |
|        +       \                               |
|      /   \       \                             |
|reg(Ra) const(x)    \                           |
|const(a)              \                         |
|  ------------------[reg(Rb)]------------------ |
| | 4                     +                    | |
| |                      / \                   | |
| |                     /   const(5)           | |
| |                    /                       | |
| | ---------------[reg(Rb)]------------------ | |
| | | 7                @                     | | |
| | |                  |                     | | |
| | | -------------[reg(Rb)]---------------- | | |
| | | |6               +                   | | | |
| | | |              /    \                | | | |
| | | |             /       \              | | | |
| | | | ------[reg(Rb)]----   \            | | | |
| | | | |4        +       |     @          | | | |
| | | | |        / \      |     |          | | | |
| | | | |       /   \     |     |          | | | |
| | | | | reg(Rb) const(y)|     +          | | | |
| | | | | const(b)        |    / \         | | | |
| | | | -------------------    / \         | | | |
| | | |                       /   \        | | | |
| | | |                  reg(Ri)  const(z) | | | |
| | | |                  const(i)          | | | |
| | | -------------------------------------- | | |
| | ------------------------------------------ | |
| ---------------------------------------------- |
--------------------------------------------------

                        . 8.31

 .8.30       
.         :    
       - . 
      ,    
,            .      
  ,     
  .     .   8.31       
   . 8.29   . 8.30.  
   ,     ,
            .  
    . 
    :

   MOVE b,Rb
   ADD #y,Rb
   MOVE i,Ri
   ADD z(Ri),Rb
   MOV (Rb),Rb
   ADD #5,Rb
   MOVE a,Ra
   MOV Rb,x(Ra)

  ,                 (
)             
   .   ,
       .
       ,    
                       
 ,  . .    
 .
        
 ,      
 [10,11].       [12],
               
  ,        
                    
(   ,        [13,14])
     .    
       ,        
  .

8.9.2.    T-

         
   .  ,   
   ( ).  ,
  , T-.
,         ,   
  ( , ). 
              
      .   
     .   
    .

 T-   ,     
A,        
.            a1...an
     .      ,
       ai...ak  
a1...an,   -  ai...ak.   
             
     ,        
       ,     ,
    .
       ,  ,  
     .      
        .
,       
   ,       
.    ,            
   .   Titem      8.1  
      (..      
 ).  Tterminal -    
,  Tproduction -    .

           r[i]={A->aiV1...Vm}
          |       /\
          |     /    \
          | 1 /\      /\m
          | /    \  /    \
|---------|----------------|-----|
          ai      l[i]

            . 8.32

 8.1:
var
   a:array[1..n] of Tterminal;
   r:array[1..n] of set of Tproduction;
   l:array[1..n] of INTEGER;
   (* l[i] -  a[i]-*)
   h:Titem;
   (*    ,  
       *)
begin (*   *)
   i   a[i]- l[i];
  (*    *)
  for i:=n downto 1 do
    for    A -> a[i] y  P do
     if l[i]>0 then
      j:=i+1;
     if l[i]>1 then   (*  a[i]  *)
        h:=[A->a[i].y];
        repeat  (*  a[i]y  a[i]..a[i+l[i]-1]*)
           h=[A->u.Xv]
          if   X  T then
            if X=a[j]   then j:=j+1  else exit end
          else (* X  N *)
            if  X->w  r[j] then j:=j+l[j] else exit end
          end;
          h:=[A->uX.v]; (*    *)
        until j=i+l[i];
      end (*l[i]>1*);
      end (*l[i]>0*);
      if j=i+l[i] then r[i]:=r[i]+{(A->a[i]y)} end
    end (*for*);
    (*    *)
    while   C->A  P , 
             (A->w)  r[i]
             (C->A)  r[i]
    do  r[i]:=r[i]+{(C->A)}
    end
  end; (* for i *)
  ,   (S->w)  r[1]
end

     .  8.32.    r[i]
  O(|P|). ,      
  O(n).

       .  8.29.      
     :

:= + a x + @ + + b y @ + i z 5

 .  8.33       .  
     8.9.3.

+-----------------------------+
|||       |
|        |     | ()  |
|--------+-----+--------------|
|  :=    |  14 | 2(22)        |
|   +    |  2  | 4(5)    5(6) |
|   a    |  0  | 1(2)         |
|   x    |  0  | 1(2)         |
|   +    |  9  | 4(16)   5(17)|
|   @    |  8  | 7(13)        |
|   +    |  7  | 5(15)   6(11)|
|   +    |  2  | 4(5)    5(6) |
|   b    |  0  | 1(2)         |
|   y    |  0  | 1(2)         |
|   @    |  3  | 3(6)    7(7) |
|   +    |  2  | 4(5)    5(6) |
|   i    |  0  | 1(2)         |
|   z    |  0  | 1(2)         |
|   5    |  0  | 1(2)         |
+-----------------------------+

          . 8.33

 G -  T-.    z  L(G) 
  .      ,
       ,      
.        .    
              
 ,       G.
      PARSE.    
        MATCHED,
      ,    
 .      - 
                  
.          ,
           
8.1. ,              
.
    ,       ,  
 :

  PTnode=^Tnode;
  Tnode=record
    op:Tterminal;
    son:array[1..MaxArity] of PTnode;
    rules:set of Tproduction
  end;

      8.1.

 8.2:
var root:PTnode;
 procedure PARSE(n:PTnode);
  procedure MATCHED(n:PTnode; h:Titem);
  var matching:boolean;
  begin
    h=[A->u.Xvy], v= v1 v2 ... vm,
    m=Arity(X)
    if X in T then (*   *)
     if m=0 then                        (*if l[i]=0*)
        if X=n^.op                     (*if X=a[j]*)
        then return(true) else return(false) end
     else (* m>0 *)                     (*if l[i]>0*)
      if X=n^.op then                  (*if X=a[j]*)
        matching:=true;
        for i:=1 to m do               (*j:=j+l[j] *)
         matching:=matching and       (*until j=i+l[i]*)
                    MATCHED(n^.son[i],[A->uXv'.vi v"y])
        end;
        return(matching)               (*h:=[A->uX.v]*)
      else return(false) end
     end
    else (*X in N*)   (*   *)
        if  n^.rules   X->w in
        then return(true) else return(false) end
    end
  end (* match *)
 begin (*PARSE*)
   for i:=Arity(n^.op) downto 1 do  (*for i:=n downto1*)
     PARSE(n^.son[i]) end;
   n^.rules:={};
   for   A->bu  P ,  b=n^.op do
     if MATCHED(n,[A->.bu])        (*if j=i+l[i]*)
     then n^.rules:=n^.rules+{(A->bu)} end
   end;
   (*    *)
   while   C->A  P , 
           (A->w)  n^.rules
               (C->A)  n^.rules
   do n^.rules:=n^.rules+{(C->A)}
   end
 end;(*PARSE*)
 begin
 (*   *)
         z;
   root:=   ;
 (*    *)
   PARSE(root);
   ,   S->w  root^.rules;
 end

       z, 
    .    T-
,       
   .
 8.1    8.2  ""      ,  
          ,  -
,    .    
            .
,        
.  8.30       8.2      
 ,   .   
       :  "",  
-,     "",       
 Match  .   Match     
   .     
    ,    op  -      
,   op-list -    ,   - 
 N.       op-list  ""  
       ,    
   ,    N->w, 
w -      ,      
  .        Match,      
      ,  
     .              
.     Pattern  (  )
    - Match.

Rule
Stat ::= Expr ':=' Expr

     2.   
            Match   ,
, <'+' Reg Const>  .

Semantics
Match<2>:=<'+' Reg Const>:
Match<3>:=;
Pattern<0>[1]:=Pattern<2>[1]&Pattern<3>[1].

Rule
Expr ::= '+' Expr Expr

,   , :

  (4) Reg -> '+' Reg Const

  (5) Reg -> '+' Reg Reg

  (6) Reg -> '+' Reg '@' '+' Reg Const.

  Match             
           >, .
            ,      
          
 Match        
<'+' Reg Const> (  2,3,6)   Reg.

Semantics
Match<2>:=;
Match<3>:=>;
P:=Pattern<2>&Pattern<3>;
if Match<0>   <'+' Reg Const>  i- 
Pattern<0>[i]:=Pattern<2>[1]&Pattern<3>[1];
if Match[0]  Reg  j- 
Pattern<0>[j]:=(Pattern<2>[1]&Pattern<3>[1])
              |(Pattern<2>[2]&Pattern<3>[2])
              |(Pattern<2>[3]&Pattern<3>[3]);
  Pattern<0>  false.

Rule
Expr ::= '@' Expr

,   , :

  (3) Reg -> '@' '+' Reg Const

  (7) Reg -> '@' Reg

,   Match        
      <'+' Reg Const>
( 3)   ( 7).
            ,      
          
 Match     <'@' '+' Reg Const>
(  6)  Reg.

Semantics
Match<2>:=<<'+' Reg Const>,Reg>;
if Match<0>  <'+' Reg Const>  i- 
Pattern<0>[i]:=Pattern<2>[1];
if Match<0>  Reg  j- 
Pattern<0>[j]:=Pattern<2>[1]|Pattern<2>[2];
  Pattern<0>  false.

Rule
Expr ::= Const
Semantics
if Pattern<0>  Const  j- 
Pattern<0>[j]:=true;
  Pattern<0>  false.

   . 8.29    , 
 .  8.34.   M   Match, P  - Pattern,  C  -
Const, R - Reg.

8.9.3.     

T-,       ,    
.       
,       .
              ,
   /  .
           
         ,  
,       ,      ,
             
 .        
,   -   T-.

  M=<':=' '+' R C R> :=
  P=              |
                -------------   M=<<'+' R C>,
               /             \     <'+' R R>,
             +               +     <'+' R <'@' '+' R C>>
            / \            /   \P=
           /   \          /     \
     const(a) const(x)   @       const(5)
M=  M=>
               '+' R C>> |       P=
P=  P=     |
                         |
                         |M=<<'@' '+' R C,
  M=<'+' R C>,           |   <'@' R>>
    <'+' R R>,           |P=
    <'+' R <'@' '+' R C>>|
  P=              +
                        /  \
                       /    \
  M=<<'+' R C>        /      \   M=<<'@' '+' R C,
     <'+' R R>       +        @     <'@' R>>
     <'+' R <'@'    / \        | P=
      '+' R C>>    /   \       |
  P=       /     \      |
          const(b)    const(y) | M=<<'+' R C>,
      M=    M=,
      P=    <'@''+'R C>>+    <'+' R <'@' '+' R C>>
                   P=  / \P=
                             /   \
                       const(i)  const(z)
                      M=  M=>
                      P=  P=

                      . 8.34

,      n   
p:A::=z0 X0 z1...Xk zk,  zi  T*  0<=i<=k  Xj  N 
1<=j<=k.     n        n1,...,nk,   
     X1,...,Xk.     
      .  
              
UndefinedValue. ,     
   n1,...,nk  n .  
A.a:=f(Xi.b,Xj.c,...)  1<=i,j<=k
  p,   

n.a:=f(ni.b,nj.c,...),

    p   a  A 
 n.        , 
    .    
       undefined,      
    .
      8.2      ,
       .    
    ,    ,  
       . 
,     ,    
:

  PTnode=^Tnode;
  Tnode=record
    op:Tterminal;
    son:array[1..MaxArity] of PTnode;
    nonterm: array[Tnonterminal] of record
   CostAttr      : ADDRESS;
   Production    : Tproduction;
       end
    OperatorAttributes: ...
  end;

  PARSE  

begin for i:=Arity(n^.op) downto 1 do
    PARSE(n^.son[i]) end;
    for  A  N do WITH n^.nonterm[A]
      CostAttr:=UndefinedValue;
      production:=Undefined;
    end;
    for   A->bu  P ,  b=n^.op do
      if MATCHED(n,[A->.bu]) then
        (A,n,(A->bu));
        (A,n^.nonterm[A].CostAttr);
        if (A->bu) ,   
            A then
          (n^.nonterm[A].CostAttr)
          n^.nonterm[A].production:=(A->bu)
        end
      end
    end;
(*    *)
    while   C->A  P, 
          ,      A
    do
      (C,n,(C->A));
      (C,n^.nonterm[C].CostAttr);
      if (C->A) is better then
        (n^.nonterm[C].CostAttr)
        n^.nonterm[C].production:=(C->A)
      end
    end
  end;

             ""   ,
  ,   
,          .
  ,    
         , 
.      
 ,      
    .    
p:A::=z0 X0  z1...Xk zk,       n, 
   A,       
 n1,...,nk     X1,...,Xk.  
    ni,    
Xi.

 9.    

              ()
               
.  ,         ,      
,         .  
          . 
,       . 
   ,  :   Yacc. 
    LL(1)-  L-
,         -  LALR(1)-    S-
 .

9.1.  

      ("")  
 :

 - ;
 -  ;
 -  ;
 - ;
 -  ;
 -  ;
 -  .

      ,    
               
 .
      ,   -
 .      
    ,      (  ),
      .         
             
,       ,      
 .          
   ,       
 .
         
               
    .      
   .
          ,
    .
             ,
          .  
     .
         
         .      
      -.
           ,
      .   
        [],
       ().
           (
/). ,

 A ::= B [ C ] ( D ) ( E / ',' )

            
.
          
 .     -  ,
            
 (  ),    ,    
 ()        
   ( ).    
      (  ,    
)   0 (   ). 
        ,  
      .  
 ,   N,     N, 
  ,   N.
               
              
.         ,
    ,    
  , , ,    A, B,
E, M.
  A              
   ,     
 ().   B       
    ,    
   ().   M    
    ,    
   ().  E    
  ,    ,        [],
.        
   . 9.1.

                         +---+
                         | A |<---------------+
                         +---+                |
                           |                  |
            +------------------------------+  |
            |       |             |        |  |
            v       v             v        v  |
  +---+   +---+   +---+         +---+   +---+ |  +---+
->| B |-->| X |-->| X |-->...-->| X |-->| X |--->| C |-
  +---+   +---+   +---+         +---+   +---+    +---+
    |       ^       ^             ^       ^
    |       |       |             |       |
    +-------------------------------------+

                  . 9.1

.    .
  D ::= 'd' =>
           $0.y:=$0.x+1;.

  A  ::= B (C) [D] =>
           $2.x:=1;
        2M:$2.x:=$2.x+1;
           $3.x:=$2.x;
        3E:$3.y:=$3.x;
        3 :writeln($3.y);.

 WRITELN        C  C-
,   D .     
   .

9.2.  Yacc

    Yacc     
LALR(1),          ()  .  
    :

 %{
  -
 %}
 %token   
 %%
   
 %%
  -

- (      %{  %} 
)   - ( #include
 #define),      .   - 
   ( ) .
      ,    
Yacc-         (#define).  
,            
      .

    

- : _1 {  1}
            | _2  {  2}
            |...
            | _n  {  n}
            ;

       -      
  .             
   .   
         $$, 
      -    $1, $2
,...,           
,    .    
        
  $$=.         
      
  .
         ,
  .            
   :

  -       /      
,    ;

  -     /    
.               
   ,   
   .

  , 

 %left '+' '-'

 +   -,        
   .            
   

 %right '^'

        (..
       
):

 %nonassoc '<'

,      ,   
.             
.
             
               
,    .     
      s     A->w,
 ,      
s     ,   .
    .
      
   .    ,   
      ,      
  :

%prec 

            
 ,    .
Yacc         ,      
  .
          
    " "  A->error w.
  error   -       Yacc.     
 ,     ,  
         error, 
 :          
,        , 
         [A-> . error
w].           error, 
      .
   w  ,    .      
   ,      ,  
   .
 w   ,      
   w.   w    , 
    .



1.   Aho A., Sethi R., Ullman J. Compilers: principles,
techniques and tools. N.Y.: Addison-Wesley, 1986.
2.    .    
 . .: , 1975.
3.   Fraser C.W., Hanson D.R. A Retargetable compiler for
ANSI C.// SIGPLAN Notices. 1991. V 26.
4.    .., .., ...
   (
)//  ..:  
, 1987. . 50-63.
5.    .,  .   ,
  . .: , 1978.
6.    .    . . 1.
 . .: , 1976.
7.    ..,  ..  
.     . .: ,
1971.
8.   - ..,  ..  
 //  . 1962. . 146. N 2. .
263-266.
9.    ..    
     //2 . 
"    ". 1983. .
104-105.
10.  Emmelman H.,Schroer F.W.,Landweher R. BEG-a
generator for efficient back-ends// ACM SIGPLAN. 1989.
V.11. N 4.p.227-237
11.  Aho A.U.,Ganapathi M.,Tjiang S.W. Code generation
using tree matching and dynamic programing// ACM Trans.
Program. Languages and Systems.1989. V.11.N 4.
12.  A. Bezdushny, V. Serebriakov. The use of the parsing
method for optimal code generation and common
subexpression elimination//Techn. et Sci. Inform. 1993.
V.12. N.1. P.69-92.
13.  Graham S.L., Harrison M.A., Ruzzo W.L. Am improved
context-free recognizer// ACM Trans. Program. Languages
and Systems. 1980. N.2.
14.  Harrison M.A. Introduction to formal language
theory. Reading, Mass.: Addison-Wesley, 1978.
