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

              ਠ  樨 3. Lex  㣨.

   Lex - ணࠬ  樨 ᪠஢ (᪨ 
஢). 室  ᮤন ᠭ ᥬ  ନ  ॣ
 ࠦ. ⮬ ࠡ LEX'a    ணࠬ
 몥 ,  ⠥ 䠩 yyin (筮    ⠭
)  뤥   ᫥⥫쭮 ᨬ (ᥬ),
ᮮ⢥騥 ॣ ࠦ.
   ᬮਬ ᯮᮡ  ॣ  ࠦ    室
몥 Lex'. 䠢 Lex' ᮢ   䠢⮬  ᯮ㥬
.   䠢, ⢥,  ।⠢  ॣ୮
ࠦ   ᨬ. 樠 ᨬ (  ⮬  ᫥
+-*?()[]{}|/\^$.<> ) 뢠 ᫥  ᯥ樠쭮  䨪
\. ஬ ⮣, ਬ  ࠤ樮  ᯮᮡ  ஢
ᨬ  몥 C.   楯窨        窨:
ਬ:
      "" \  -  ᯮᮡ ஢ ᨬ 
     \n \t \007 "continue"
    ᨬ:
     [0-9]  [0123456789] -  
     [A-Za-z]               -  㪢
     [^0-7]                 -  ᨬ, ஬ . 
     .                      -  ᨬ, ஬ \n
ࠬ⨪   ॣ ࠦ ( 浪  뢠
ਮ):
    <> : <>*         - ७ 0   ࠧ
    <> : <>+         - ७ 1   ࠧ
    <> : <>?         - 易⥫ ࠣ
    <> : <><>       - ⥭
    <> : <>{m,n}     - ७  m  n ࠧ
    <> : <>{m}       - ७ m ࠧ
    <> : <>{m,}      - ७ m   ࠧ
    <> : ^<>         - ࠣ  砫 ப
    <> : <>$         - ࠣ    ப
    <> : <>|<>      -   ࠦ
    <> : <>/<>      - ࢮ ࠦ, ᫨    ᫥
                         ஥
    <> : ()          - ᪮, ᯮ  㯯஢
ਬ:
    [A-Za-z]([A-Za-z0-9]{0,7}) - 䨪 ()  몥 C
    ^#" "*define               - 砫 #define       몥 C
ணࠬ  室 몥 Lex ⮨    ⥩,  ࠧ
 ᨬ %%:
   ᠭ
   %%
   ࠢ
   %%
   ணࠬ
   ᠭ ᮤন । ᨬ  (ᨬ
)  :
 
᫨  ᫥饬 ⥪   ॣ୮  ࠦ  砥
{},     . ᫨ ப ᠭ 
稭  ஡  祭  ᪮ %{ ...  }%,    
   室 䠩.
   ࠢ ᮤন ப 
 {}
 -  ࠣ ணࠬ    C,    믮
⮣,   㦥  楯窠,  ᮮ⢥  .
⢨, 㪠  砫 ࠧ  ࠦ, 믮
 砫 ࠧ. Lex   뤥  
楯  室 ⮪. ᫨ ᪮쪮 ࠢ   楯
 , ਬ ࢮ ࠢ. ,   ࠧ
 ᫥騬 ࠢ  楯窨 "123"  㤥 ਬ 
 ࠢ,   楯窨 "123." - :
   [0-9]+
   (\+|\-)?[0-9]+
   (\+|\-)?[0-9]+"."[0-9]+
᫨    ࠢ  㤠 ਬ, 室 ᨬ 
 ᪮஢  yyout. ᫨  ⥫쭮,     ࠢ
 , ਬ, ப:
   .  {/* 祣   */}
   \n { }
    ணࠬ  ᮤঠ ந ⥪   C  
楫   室 䠩. 筮    뢠
㭪 yywrap(),  ।,    ⨦
⮬⮬  室 䠩. 㫥 頥 祭
ਢ  襭 ࠧ, 㫥 -   த  (।
த, ⢥,   -  䠩  
yyin).
    ⠡    yylex(). ⮬ ४
 ࠡ (ந室   㭪樨 yylex()), ᫨  
 ⢨ 믮  return (१  yylex()  㤥
ᮢ  㪠  )  ⨣  䠩  
祭 yywrap() ⫨筮  0 (१ yylex()  㤥  ࠢ
0).
   ࠤ樮 ਬ 室 ணࠬ   Lex'  -  
᫠ ᫮  ப  䠩:

   /*****************  । *********************/

   /* NODELIM 砥  ᨬ, ஬ ࠧ⥫ ᫮ */
NODELIM     [^" "\t\n]
            int l, w, c;    /* ᫮ ப, ᫮, ᨬ */

%% /********************  ࠢ ***********************/

                { l=w=c=0;          /* 樠 */      }
{NODELIM}+      { w++; c+=yyleng;   /*  */              }
\n              { l++;              /* ॢ ப */     }
.               { c++;              /* ⠫ ᨬ */  }

%% /*******************  ணࠬ **********************/

main() { yylex(); }

yywrap() {
  printf( " Lines - %d  Words - %d Chars - %d\n", l, w, c );
  return( 1 );
}

    ⢨  ࠢ  ᯮ짮  ᯥ
樠 樨  㭪樨 Lex':
   yytext    - 㪠⥫  ⮦⢫  楯  ᨬ,
               ନ஢ 㫥;
   yyleng    -  ⮩ 楯窨
   yyless(n) -  ᫥ n ᨬ 楯窨 ⭮  
               室 ⮪;
   yymore()  -  ᫥騥 ᨬ    yytext  ᫥
               ⥪饩 楯窨
   yyunput(c)-   c  室 ⮪
   ECHO      - ஢ ⥪ 楯  yyout

   ࠦ:     몥  ॣ  ࠦ  LEX'
᫥騥 ॣ ⢠:
   - ਩ 
   - ਩ ᪠
   - ⢥ ⠭ 
   - 楫 ⠭  ( 0, 12, -3, 0xFF )

   ணࠬ  Lex',  ⠥  ᫮  ७ᠬ
 室 ⮪:

NODELIM [^, :\.;\n\-\]
HYPHEN  [\-\]
%%
{NODELIM}+{HYPHEN}\n{NODELIM}+ { printf ("%s\n",yytext); }
{NODELIM}*                   { /* 易⥫쭮 */ }
. | \n                       { }
%%
yywrap() { return(1); }
main() { yylex(); }

   ᫨  易⥫쭮 ࠢ  ।饩  ணࠬ,
ணࠬ -० 㤥 ࠡ,  ⥫쭮 ,
᪮  ⮬ 堭 맮  ⢨  㤥  뢠
  ᨬ (   ᫮).
      뢠 㤮   室  
⢨  ନ ᪮쪨 ࠧ ﭨ (..  ࠧ  
 ⮬⮢)   ४祭     㣮.  
⮬ 砥   ﭨ ᫥ ᫨    ᯥ
쭮 ப %Start,  । ࠦﬨ 뢠   ᮮ
饣 ﭨ  㣫 ᪮. ४祭   
ﭨ 믮    BEGIN. ਬ, ᫥
 ணࠬ 㤠 ਨ  ணࠬ   C  (out  -
 , in - ):

%Start out in
%%
                { BEGIN out; }
<out>"/*"       { BEGIN in;  }
<out>.|\n       { printf("%s",yytext); }
<in> "*/"       { BEGIN out; }
<in> .|\n       { }
%%
yywrap() { return(1); }
main() { yylex(); }

    맮 ணࠬ Lex   UNIX  ᫥    
"lex _室_䠩". 室 䠩   "lex.yy.c".

ࠦ  ணࠬ஢:
1.   ணࠬ      Lex',         
   ࠭-ணࠬ  ᫮ DOUBLE PRECISION  REAL.
2.  ணࠬ  Lex',  뢮   祭
     ⥪ ᫮, 稭騥   㪢.
3.  ணࠬ  Lex'   㤠  ਥ  
   ணࠬ  C,  㤥 뢠   
    ਥ  ஢ "/*"  ᨬ
   ⠭.

                        ஥ LEX.

    ⠥ 㤨  ,      ॠ
 ᪠஢,  ⮣ 㦤  ᫥,    UNIX'
᪠ ணࠬ LEX ஥  ⠪.
      ॣ  ࠦ  r1,  ...  rn  ᫮
ந ନ஢  ⮬, ⥬,  ᫥
ꥤ 祭 ⮬, ᮧ   砫쭮  
ﭨ  e-室  砫 ﭨ    ॣ୮
ࠦ. (祭 ⮬ 㤥 ᯮ ࠦ r1|
r2|...rn). ਬ,  ࠦ a, abb, a*b+, 㤥 ஥
᫥騩 ⮬:

       e  Ŀ a ¿
  >Ĵ1>Ĵ2                    a
Ŀ        
     e  Ŀ a Ŀ b Ŀ b ¿
 0 >Ĵ3>Ĵ4>Ĵ5>Ĵ6        abb
                 
      <a   <b
      e    ¿
  >Ĵ7>Ĵ8                   a*b+
           b 

    뤥 ᥬ  室 楯窨  ਬ 
 ஢  ஢  ନ஢
 . ⫨稥 ⮨  ⮬,  稥  ⥪饬 ⢥
ﭨ 筮 ﭨ   ᭮   
 ⮬ -  ᪫祭,  楯窠   த
    ᥬ.  ⮬  砥  ᫥  
ᥬ  ᮮ⢥饥  ॣ୮ ࠦ ( 筮,
  室  ࠦ,  ஥  뫮  ᠭ    
⥪  室 LEX-ணࠬ)  த  .
     蠥, ᫨  ⥪饣 ⢠  
ﭨ   室  । ᨬ  室 楯窨.
쪮 ⥯   ᯮ ᫥  
ᥬ,  믮  ᮮ⢥饥    ⢨,  
"譨" ᬮ७ ᨬ   室  楯,  ⠭
⮬  砫쭮 ﭨ  த  ᫥饩 
ᥬ.  ஥    ⮬    樨   楯窨
aaba... ன ᫥騥 ⢠ ﭨ:

Ŀ a Ŀ a Ŀ b Ŀ a Ŀ
0,1,3,7>Ĵ2,4,7>Ĵ7>Ĵ8>Ĵstop
            
             a(a)         aab(a*b+)

 १ 㤥 ᯮ ᥬ aab,  ⢥ ॣ
୮ ࠦ a*b+.
   ନ஢ , 祭  ஥   
ନ஢  ⠪   ᯮ짮   뤥
ᥬ. ,   ﭨ    ᮮ⢥  
ﭨ . ᫨  ⢮ ᮤন    ﭨ
,  ᫥  ᮮ⢥饥   (筮)  
ﭨ ,  ॣ  ࠦ. ਬ   ᬮ
७  ਬ   ஥ ᫥騩 :

        Ŀ
        ﭨ    a    b   .ࠦ
        Ĵ
         0,1,3,7   2,4,7  8        -       
         2,4,7       7    5,8             
         8           -    8        a*b+    
         7           7    8        -       
         5,8         -    6,8      a*b+    
         6,8         -    8        abb     
        

   ࠦ:  諮 樨 뫠 । 奬  
   ॣ୮ ࠦ, ᮤঠ饣 樨 *,  |,
᪮  ⥭. ࠭  奬    ॣ
ࠦ, ᪠ LEX':
   1. +, ?, {m,n}, {m}, {m,};
   2. ^P, P$ ( 砫    ப);
   3. 1/P2  (P1,   ᫥ 2).

   ࠦ: ⢥    ,  ।⠢騥
, 뤥騩 ᥬ, :
   ﭨ s   - 楫 ᫮   1..᫮ ﭨ,
   㭪 室 - f:(s,c)->s,
   .ࠦ -  楫  ᮬ  1..᫮ ﭨ
        (  -  ॣ୮ ࠦ  
          ﭨ ⮬,   묨).
    㭪樨 室   ⠡ 祭 䥪⨢
 窨 ७ ᪮,  ॡ ᫨誮  .  (
 ⮬ ⨯筮 ᪠  ᮤঠ 100-500 
ﭨ, 室 䠢 - 256 ᨬ.  25-250 , 
㥬  ⠪ ⠡,  ਥ .)
   । 筮 ,      
ᯮᮡ ࠭ 㭪樨 室. 㬥,   
  "⨯筮" 㭪樨 f.


                   ॣ .

   ᬮਬ  ᪠ ॣ୮ ⢠ R    楯窥
ᨬ L. (    砥  ॠ樨  
஢,    ।⢥   ᬠਢ
 ᮢ  쬠 ୠ. , ਬ,  ⥬ UNIX
  ࠩ   ணࠬ  襭 ⮩  :
grep, egrep, fgrep - Get Regular Expression Pattern.)
    , 祢, ⭠  ਭ 
窨 L ॣ୮  (.*)(R)(.*)      襭
஥ ନ஢  ନ஢  
 ⮬  ਬ   楯窥 L.   ⮬⮢
? ⢥  "筮,  ନ஢,  ..    ࠡ⠥
॥",  饬 砥, ७. ஡ 砥   ⮬,
  ᥬ⢠ ॣ ࠦ,   
 ﭨ 쭮  ᯮ樠쭮    
ࠦ,   ६  ᫮ ﭨ , 祭 
  ॣ୮ ࠦ,          .
(ਬ ⠪ ᥬ⢠ - ࠦ  ।饩 樨). 
  ਬ   ᪠  ॣ
 , 뢠 ॣ묨 ࠦﬨ  쬠  㬥
७ .
    ⠪ ਫ  䥪⨢ 祬      
 ⠪ 뢠 "" 孨.  ᭮   
ᠬ ,   㠫쭠  cache-.  ⮬  砥
 ந   ᬮ 楯窨, 祬  
  cache- ⮫쪮 室     楯窨
ﭨ  室 . -,    ਤ㬠  
,    ⮤ 㤥  䥪⨢    (让,
ॡ騩  ६  ᫥ ,   ஬  ॠ쭮
ᯮ 讥 ⢮).
   ࠦ: த㬠 ⠫ ॠ樨  ""  ᪠
ॣ୮ ࠦ.


                        楯窨.

   祭 १, ਬ   ᪠ ப
R ( 砩 ॣ୮ ࠦ)    ᫥⥫쭮
ᨬ  L    宩  १:      ॡ   ६
O(|L|+|R|) + ६ ஥ ,      ᫥
⥫쭮⥩   ⬠,     襬  砥
ॡ O(|L|*|R|). 쬠  १, 뢠  
⭮ ᫮ ⮤  ⮫ ୮ .
   ࠦ: ,        ॣ୮
ࠦ (.)*r1r2...rn(.)*  ஢ n+1 ﭨ.
    ⢥  - ਤ㬠 ⮫   䥪⨢
 ᪠ ப,   ॡ騩  㤮  
஥ .   襭 -  --
   ।ࠡ⪠:  ࠧ ᪠ R[1:k]  ⠪ 
뢠  㭪  ⮢  f[i]  -    ᠬ   
ᮡ⢥ 䨪 楯窨 R[1:i], ᮢ饣  砫 R.
㣨 ᫮ f[i]=j 1<=i<=k, ᫨  ⮫쪮 ᫨ j (0<=j<i) -
ᨬ쭮, ⠪  R[1:j] = R[i-j+1:i]. ਬ:

        Ŀ
            1  2  3  4  5  6 
        Ĵ
         R  a  b  a  b  a  c 
        Ĵ
         f  0  0  1  2  3  0 
        

/* ᫥ 㭪樨 ⮢ f[1..k]  楯窨 r[1..k] */
    for( s=0, f[1]=0, i=1; i<k; i++ ) {
        while( s>0 && r[i+1]!=r[s+1] ) s=f[s];
        f[i+1] = r[i+1]==r[s+1] ? ++s : 0;
    }

ࠦ:
 - ,  ணࠬ ࠢ쭮  㭪 f;
 - ,  ६ ࠡ ணࠬ O(k).

:
/*  楯窨 r[1..k]  楯窥 l[1..n] */
    for( s=0, i=1; i<=n; i++ ) {
        while( s>0 && l[i]!=r[s+1] ) s=f[s];
        if( l[i]==r[s+1] ) if( ++s == k ) return YES;
    }
    return NO;

ࠦ:
 - ,  ணࠬ ࠢ쭮  宦 R  L;
 - ,  ६ ࠡ ணࠬ O(k+n);
 - ᯮ 㭪 ⮢ f, । , 騩
     ࠦ (.)*r1r2...r(.)*  ६ O(k).

    -  ᪠  ᫮    
⢠  楯窥 ᨬ.   ⮣  ன  ,
 뢠  ஬  (ॢ稪      "⢮
ணࠬ஢  " ⠪  ॢ  ନ  trie  -  
।  tree  retrieval:  -  ⭮襭   
, ⠪   ॢ).   ⢠ { if, else,  endif,
end } 룫廊 ⠪:

            i Ŀ f ¿
         >Ĵ1>Ĵ3
                
         e Ŀ n Ŀ d ¿ i Ŀ f ¿
        0>Ĵ2>Ĵ4>Ĵ6>Ĵ8>Ĵ10
                       
                 l Ŀ s Ŀ e ¿
               >Ĵ5>Ĵ7>Ĵ9
                          

 - । 㭪 ⮢  ⢥ 㧫 ,
 - ।  ᫥ 㭪樨 ⮢  ६
   O(᫮ 設 ),
 - ।   ᪠   祢 ᫮,
   ᯮ騩 㭪 ⮢,
 - ᯮ 㭪 ⮢,  ।    
   ஥ 쭮   ࠦ (.)*(W1|...Wn)(.)*

     䥪⨢ (-      ⨯
ਫ)  ५ Boyer  Moore    70-  
.  - ࠢ ᨬ 楯窨  ࠧ ࠢ-.
ᮢ ।  ᨬ   筮  
ଠ樨  ⮣, ⮡  ।  ࠧ    ᫥饣
ࠢ ࠧ  ᪮쪮  ᨬ  ।.  ,  ਬ
筮 ᥣ  ࠢ, ⮡ 㡥,  ப
"ࠪ"  ᮤন  楯窥 "ࠪ":

        ࠪ
        ࠪ
           ࠪ

   ࠦ:   BM  .
   ࠦ  ணࠬ஢:  ⭮  ணࠬ
᪮쪮 ⬮ ᪠ ப    १  
᪮  ࠡ. ⮢     ࠧ  
ப ࠧ筮   ࠧ த - ਬ, ⥪⮢ 
 䠩, 砩 ᫥⥫쭮 㫥     
..

                -  ਠ  樨 3 -
