..ᠭ쥢, ..祭   "᭮ 樨"  ᥭ,1991

                          

   1.   A.Aho,   R.Sethi,   J.Ullman   Compilers:   principles,
techniques, and tools. Addison-Wesley,  Reading,  MA,  1986.  -
ᮢ६ 祡,  ஬ ஡   ⥬  
;  ,  ᮦ, ࠪ᪨ 㯥.
   2.  A.Aho,   J.Ullman   Principles   of   compiler   design.
Addison-Wesley, Reading, MA, 1977. -    ।
饩 .
   3. ., .쬠  ᨭ⠪᪮ ,  ॢ
 樨. .1,2 - .:, 1978. -   ᢥ頥  
᪨ ᯥ ᬠਢ ।  ᮤন  
 ᭮, ⭮  砫 70- .
   4. .  ஢ ஢  ஢  
⥫ 設. - .:, 1975. -  ⮩ ⥫쭮,  
᪮쪮 ॢ襩  ᭮  㤥  ࠪ
᪨ ᠬ;   ।饩   㤠筮 
  㣠.
   ᯮ ᢥ ᮤঠ    㣨 ,
襤  ᪮ 몥,     ᫮
""  "࠭", ਬ,
   5. .. ஥஢  ஢  ஢.
- .:  ⨪,1984.


..ᠭ쥢, ..祭   "᭮ 樨"  ᥭ,1991
ਠ  樨 1. 모  ࠬ⨪. ⥩訩 .

   䠢 -   ⢮ ᨬ. ⨥  ᨬ  
।. 窠 ᨬ  0,1,2  뢠    "012"
( 012). 㣨 祭:
        R
       x    -     楯窠 x  ᨬ  ⭮ 浪
        n
       x    -     楯窠 x, ७ n ࠧ
       x*   -     楯窠 x, ७ 0   ࠧ
       x+   -     楯窠 x, ७ 1   ࠧ
       xy   -     楯 (⥭) 楯祪 x  y
       |x|  -      (᫮ ᨬ) 楯窨 x
       e    -      楯窠
      ᨬ 㤥   ᠬ  ᨬ.
㪢 x,y,z,u,v,w,t 㤥 ਬ    祭  楯祪.
⢮  楯祪   ⮢  ⢠  E  ⢥
 १ E*.  -  ⢮ E*.  ਬ  
                     n n
: , ᪨, { 0 1 | n >= 0 }.

  :
 - ᫨  楯窨;
 - ᠢ ணࠬ-ᯮ⥫,  砥    室
楯 ᨬ  뤠 ⢥ "", ᫨ 楯窠  ਭ
  ""  ⨢ 砥;
 -   堭 ஦ - ࠬ⨪.

⮡  ࠬ⨪, ॡ 㪠:
 - ⢮ ᨬ 䠢 ( ନ  ᨬ)  E.
   㤥   묨 ᨬ 䠢  ࠬ;
 - ⢮ ନ ᨬ ( ᨬ),  
   ᥪ饥  E  ᯥ樠쭮 뤥 砫 ᨬ
   S. 㤥   ய묨 㪢;
 - ⢮ ࠢ 뢮,  ।  ࠢ  ⠭
    楯祪.  ࠢ ⮨   楯祪  (
   , x  y), 祬 x  ᮤঠ  ࠩ   
   ନ;  砥,  楯 x   뢮 
      y. 뢮 楯祪 몠 稭   ନ
    S. ࠢ ࠬ⨪  㤥  뢠    x : y.
   ( 㯮ॡ  x ::= y  x -> y)

 ண, । ⨥ 뢮 楯窨:
 - S - 뢮 楯窠;
 - ᫨ xyz - 뢮 楯窠   ࠬ⨪   ࠢ
   y:t,  xtz - 뢮 楯窠;
 - ।塞 ࠬ⨪  ⮨  뢮  楯祪,
   ᮤঠ ⮫쪮 ନ ᨬ.

ਬ:
        )  S : e              ) S : e
            S : 0S1               S : (S)
                                  S : SS

 ᮪饭  ਭ ᯮ짮 ᨬ "" -  "|".
⪠ ଠ  । ਬ஢:

        )  S : e | 0S1        ) S : e | (S) | SS

 ᫮ ਬ:

        )  S  : aSBC | abC
            CB : BC
            bB : bb
            cC : cc
            bC : bc 
                               n n n
 ࠬ⨪ ஦  a b c (⥫⢮ ⮣ 䠪
- ࠦ).

ࠬ⨪  ᢮ । ࠧ  ..  .    뫠
ᠭ "᪠" ଠ    몠.    ࠪ⨪
ਬ ⠪ 㣠 ଠ ,  ࠤ樮  뢠
ଠ묨 ଠ - (). ନ   
뢠   ᨬ 䠢,  ନ -  
  㣫 ᪮ <>. ਬ, ࠬ⨪ 楫  ᥫ  
    :

  <᫮> : <> | <> <᫮>
  <> : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

᪮ 㯫.    ࠬ⨪ -
 몠   ᠬ? ⢥ - . 襭 - ࠦ.

ᬮਬ  ⥩ 䬥᪨ :

  <㫠> : (<㫠>) | <᫮> | <㫠><><㫠>
  <>    : + | *

祬 "3+5*2"  㫮?  ਢ  ᫥⥫쭮
८ࠧ 楯祪 (⠪ 뢠 "ࠧ"  "뢮"):

    <㫠> : <㫠>               <><㫠> :
                <㫠><><㫠><><㫠> :
                <᫮>  <><㫠><><㫠> :
                3        <><㫠><><㫠> :
                3        +     <㫠><><㫠> :
                3        +     <᫮>  <><㫠> :
                3        +     5        <><㫠> :
                3        +     5        *     <㫠> :
                3        +     5        *     <᫮>   :
                3        +     5        *     2

   饭 稥 뢮 (楯窨 ८ࠧ) 㤥 
뢠   <㫠>::3+5*2. 設⢮ ࠬ⨪  
 ᪮쪮 ࠧ 뢮    ⮩  楯窨  
몠. ன 㣮 뢮  楯窨 "3+5*2" - ࠦ.
   ᫨   뢮 楯窨 ࠢ ࠬ⨪ ਬ
 ⮫쪮  ᠬ  ନ, ,  祭 
 뢮 楯窨. 筮 । ࠢ 뢮.  
뢮 ஥  ।饬 ਬ?
   ࠧ 믮塞  楯祪      ..  "ॢ
ࠧ" ( ॢ 뢮).  ࠤ樨  ॢ  ࠦ
" ":

                           <㫠>
                         /       \    \
                <㫠>         \    <㫠>
                /   |    \         \       |
        <㫠> <> <㫠> |       |
              /     |      |       |       |
             |      |      |       |       |
          <᫮> <> <᫮> <> <᫮>
             |      |      |       |       |
             3      +      5       *       2

ᮢ ॢ  ⢨ ()  㧫 (祭 ନ
  ନ),    ⢨.  㧫
(ନ) 뢠 ﬨ.   "ॢ",  "७
ॢ", ,  㦤   ।.
       ॢ ࠧ  뢠 ࠧ 뢮
( ॢ  䨪஢  冷  ਬ  ࠢ).  ,
 묨 ( ࠢ묨) 뢮    ॢﬨ  ࠧ  
楯祪  筮 ᮮ⢥⢨ (ࠦ).
   ᫨    ⮩  楯窨  ࠧ   ࠧ
ॢ ࠧ (,     ᠬ,  ந,    ࠧ
ࠢ 뢮), ࠬ⨪ 뢠 筮.  ᠭ
ࠬ⨪ 筠 (祬? - ࠦ).      ᠬ
   筮 ࠬ⨪:

  <㫠> : <> | <><><㫠>
  <>    : (<㫠>) | <᫮>
  <>    : + | *

  ॢ ࠧ? - ࠦ. ॢ ࠧ  
।   楯窨 몠. ,  ,  
楯窠 "3+5"  "㫮".    ⨢  訬
(⨢)   ᫥ 室 : 3+5  ⫨稥
 5*2   ࠦ.        ਮ
権,  ࠬ⨪:

      <㫠> : <> | <㫠> + <>
      <>    : <> | <> * <>
      <> : (<㫠>) | <᫮>

    樨 ⠭  ? - ࠦ.

   ஬ ਢ筮     䬥᪨    (..
"䨪᭮", ..   樨  ࠭),  ப
࠭ "䨪᭠" ( ⭠ ᪠) ଠ  
,  ன  ᯮ ᫥ ࠭. ਬ:

         2+3      2 3 +
         2*3+4    2 3 * 4 +
         2*(3+4)  2 3 4 + *

 ⭮ ᪮  ᪮  ॡ,  祭 
 祭  ᫨  ᯮ짮 ⥪ ᥫ -  
ࠦ.

   ॢ   몠  㣮 뢠 ࠭樥  
樥.    䨪   ९ 
䨪   ࠭ 浪 ᫥ ᥫ  (
⥫⢮ - ࠦ),   樨      
䨪᭮  䨪  ᫥ 뤥  ,
  䨪᭮ ଥ  ࠭     
᫥  .  ॢ ࠭  䨪  
४ᨢ     ணࠬ  ॢ  .  
᫥ ࠢ ࠬ⨪  樨     
 ᬮ ᫥ ࠢ ਢ  ᫥饬 ࠣ:

             CompForm() {
               CompForm()
               ...

믮 ண, 筮 ,   . ஡
  - ⮣,  楯窨       ࠢ  
ࠢ 稭   ନ (,  ࠬ
 ४ᨢ).
   ᫨ ࠭  ४:

    <㫠> : <>    | <>< ><㫠>
    <>    : <> | <><㬭 ࠧ><>
    < >          : + | -
    <㬭 ࠧ>  : * | /

 ᠭ ஡ 祧,  ४ᨢ    
㤥 ,    㤭  (  ॢ
ࠧ 㤥 ᮮ⢥⢮ 楯窥 "5-3-2"?  -  ࠦ).
᪨,  ८ࠧ  ࠬ⨪,        冷
ᢥ⪨ 権. ࠤ樮 樨  ਮ 믮
 ᫥ ࠢ (,  樨  樠⨢),
 ⮫쪮  ᠭ ࠬ⨪ । 樨  
樠⨢.
       ஡ ,     
  ᨬ 樨 {} " 0     ࠧ".  
ਬ  祭 ࠬ⨪      
 ४ᨨ:

      <㫠> : <> { < > <㫠> }
      <>    : <> { <㬭 ࠧ> <> }

ᠭ  ⮩ ࠬ⨪ ४ᨢ  ⠪  
 룫拉 :

        char *infix, *postfix; /* 㪠⥫  室  室
                                   楯窨 */

        CompForm() {  /* ஢  */
         register char sign;
          CompTerm();
          while ( (sign = *infix) == '+' || sign == '-' ) {
            ++infix;
            CompTerm();
            *postfix++ = sign;
            *postfix++ = ' ';
          }
        }
        CompTerm() {  /* ஢     */
         register char sign;
          CompEl();
          while ( (sign = *infix) == '*' || sign == '/' ) {
            ++infix;
            CompEl();
            *postfix++ = sign;
            *postfix++ = ' ';
          }
        }
        CompEl  () {  /* ஢  */
          if ( *infix == '(' ) {
            ++infix;
            CompForm();
            if ( *infix++ != ')' ) error();
          } else {
            if ( !isdigit(*infix) ) error();
            while ( isdigit( *infix ) ) *postfix++ = *infix++;
            *postfix++ = ' ';
          }
        }

   ᯮ짮   ᠭ  孨  
 ४ᨢ ᪠. 室 楯   ᬠਢ
᫥ ࠢ, ॢ 뢮 室 ᢥ  (..   
砫쭮 ନ <㫠>).
   㭪 error   㦨   뢮  ᮮ饭  
⮬,  । 楯窠  室    䬥᪨
. ᫨   祭  室 楯窨  뤠
ᮮ饭  訡, ,   楯窠 饭.  ਢ
 ਬ  室   䬥᪨   楯祪,
᪠ ஬ - ࠦ.
   ᫨ ࠧ 楯窨-ணࠬ ᮯ஢  ॢ 
 㣮 ।⠢  쭥襣 믮,   
 ᯮ ( 襬 砥 - ᫥ 祭),  
,  ணࠬ .

                       ࠦ:

1.   뢠 ࠬ⨪a,     ࠬ
⨪ 筮?
-  S : e | 0 S 0 | 1 S 1
-  S : 0 S 1 | 0 1
 - S : S S '+' | S S '*' | 'a'
 - S : '+' S S | '-' S S | 'a'
 - S : S '(' S ')' S | e
 - S : 'a' S 'b' S | 'b' S 'a' S | e
 - S : 'a' | S '+' S | S S | S '*' | '(' S ')'

2.   筮 ࠬ⨪:
 - ⭠ ᪠(䨪᭠)  䬥᪮ 
 - 䨪᭠ 䬥᪮ 
 - 䬥᪮ ࠦ  楫 ⠭,  ६,
    権 '+', '-', '*', '/'  㭠୮ 樨 '-'
 - 樠⨢ ᯨ᮪ , ࠧ 묨
 - ࠢ樠⨢ ᯨ᮪ , ࠧ 묨
 - ਬ᪨ 

3. ,   ᫠, 뢠 ࠬ⨪
   n : 1 1 | 1 0 0 1 | n 0 | n n
  3. ஦   ࠬ⨪   ᫠
 ६?

4. ,  ࠬ⨪

   stmt : IF expr THEN stmt
        | IF expr THEN stmt ELSE stmt
        | OTHER

  筮. ८ࠧ    ࠬ
⨪, 뢠 ,  ஬ ELSE ᮮ⢥ 襬
⮬ THEN.
5.  ࠭祭 ᫥   ࠬ⨪, ⮡ 
    ४ᨢ ᪠ 뫮 ?
6.  ࠬ⨪  ᫥ 몮:
        2
       n              m n m n
   ) 0          )  a b a b    ) xx,  x -  楯窠
                                     㫥  .

                ࠦ  ணࠬ஢:

1. ।  ⠪, ⮡    ᪠  訡
   (..  ஦ ࠬ⨪) 楯祪.
2.       ⥯  (ࠢ
   樠⨢  "^"  訬 ਮ⮬).
3. ।    .
4.     "㭠 ", ⮡  室
    楯窨 ⨯ -(-a*b+c) ⠫  ⨬묨   ࠢ쭮
   ஢. 窨  --a, a+-b, 筮 ,  
    ᪠!

5.   ਬ᪨  -> ࠡ᪨ 
6.   ࠡ᪨  -> ਬ᪨ 

 䨪᭮ ଥ      樨  ।
࠭, ਬ, 1+2*3 뢠   +  1  *  2  3  .
(  ଠ  뫠 । .㪠ᥢ祬   
稫  "᪮").

7. ᫨ 祭 , ᠭ  䨪᭮  ,
   ᬠਢ   ࠧ ᫥ ࠢ.
8.    䨪᭠  -> 䨪᭠.
9.     䨪᭮ ( 䨪᭮)
     䨪.   ࠢ 㤮 ᬠਢ
   室 䨪 ( 䨪) ? -  
   ᪮ ⠪ ॢ    ,  ⮬  
   :
   -  䨪᭮  ᪠ "譨" ᪮;
   - "譨" ᪮  ᪠.

                -  ਠ  樨 1 -
