ࡱ> ilqrjk`!) ;]Iפ5Ì7N;gxڽyLG߲+rEE=7UT.PQ};fL9KDY!e 2Xl>npY'-VS lc 4˖ ɒ2 )% +#$]%zbG(BAPB$}9zy"dhtIɴ}2 9/f3$U^D\V̗a] V"ZVW :BBl)Be#搙=3١N4tϾ&6g 'pEjm-h+l8d!Xܮ%ЗsߊhWWÿsJX_7K%wnUIRG7h(n=(KUa9z.̉q`;G䃹9 IYhq2"G@ g. zpF({Wg`+[A DA7|Tk=zu\BeyN F @ $ a[gk| -ZnF?hIɌ+Ch @_o]UXө1@9AnS+{VBvPɥU9![\aǂ,zM^EaY ;-;FTP^F\9H'=t}fMrAalbs:q0l&Wl+aEJJ=BՆ-}09:t{jE62m"6ܪp;J{轂ȵowWɿ7h#c5.aX7pe.@>l꠷/Zx|@i Gd# R} >L~ތ?#yy%4,&-L6;8$8A? c@Gx;UƝ{ \_WEƿs,Xkt:ID}ID}AD}!hz?jUo|됪 fAh}:v?D @ʍdF,@Vj ntqxCfX+' 5Xb|Mؤ-v3}O hsX,@O9=s}݉<-i;;|*zb}fGW% 'Sx5ԝ*L-|>v%",Ge(,%+.A%BZ'4 wPǺz2>pPY9J]Ov%!ٴ>rbZww3}5dVkñ|`mح/'s?ف45=~5*|se:i{!d SIвGkcv,2۱J5֭UVMg'_]m Mnho67mn2^V}Eǟ(%7:2pp b^dRqD˓JS0w4Uhjowu',(   &2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery*2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery/ 00DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 0?"0DWingdings MSn0:A 0? C.  @n?" dd@  @@``  C'(7.-O." aR )*$+' .)),,2$ ;]Iפ5Ì71 0e0e     A@  A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|ES"@8*ʚ;r1ʚ; g4mdmd :A 0ppp@ <4!d!dL$ 0<4ddddL$ 0g4CdCd :A 0p@ pp<4BdBdL$ 080___PPT10 ? %?A Tokenizing Machine:Tokenizing Machine Continued& :Tokenizing Machine Continued& Type BL_Tokenizing_Machine_Type is modeled by ( buffer : string of character ready_to_dispense : boolean ) constraint & Initial Value (empty_string, false)2Z      ":Tokenizing Machine Continued& Operations m.Insert (ch) m.Dispense (token_text, token_kind) m.Is_Ready_To_Dispense () m.Flush_A_Token (token_text, token_kind) m.Size (),  s$A State-Transition View'Tokenizing BL ProgramsBToken Types KEYWORD IDENTIFIER CONDITION WHITE_SPACE COMMENT ERROR& 7 7%A Very Useful Extension&Another Useful Extension) How Does Insert Work?+ The Specification of Insert, An Important Math Operation(Other Math DefinitionswOK_STRINGS = {s: string of character (IS_KEYWORD (s))} union {s: string of character (IS_IDENTIFIER (s))} union {s: string of character (IS_CONDITION_NAME (s))} union {s: string of character (IS_WHITE_SPACE (s))} union {s: string of character (IS_COMMENT (s))} PREFIX (s_set) = {x: string of character (there exists y: string of character (x * y is in s_set))}Tx   >PREFIX Examples.s_set = { abc } PREFIX (s_set) = {  ,  a ,  ab ,  abc } s_set = { abc ,  de } PREFIX (s_set) = {  ,  a ,  ab ,  abc ,  d ,  de }- :Tokenizing Machine: ImplementationObvious Representation Text buffer_rep Boolean token_ready Insert (ch)? check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep], ch), and set self[token_ready] accordingly append ch at end of self[buffer_rep] L$ $ . hTokenizing Machine: Implementation Continued& Dispense (token_text, token_kind)? set token_text to all but the last character of self[buffer_rep] set token_kind to the value of WHICH_KIND (token_text) set self[token_ready] to false&##,  /hTokenizing Machine: Implementation Continued& *How do we  check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep], ch) ? How do we determine  WHICH_KIND (token_text) ? How do we do these things quickly?$0Making Decisions QuicklyKeep track of the  state of the buffer by adding one field to the representation: Text buffer_rep Boolean token_ready Integer buffer_state >S:S$1Possible Buffer StatesHow many interestingly different buffer states do you think there may be? Let s start enumerating them& $i S20Buffer States Continued& Initial state (empty buffer) How many states after inserting the first character?  B ,  D ,  E ,  I ,  P ,  T ,  W ,  n ,  r ,  t , identifier (any other letter) white_space (  ,  \n ,  \t ) comment ( # ) error (any other character) <RZZZR30Buffer States Continued& RHow many states after inserting the second character?  BE ,  DO ,  EL ,  EN ,  IF ,  IN ,  IS ,  PR ,  TH ,  WH ,  ne ,  ra ,  tr , identifier (any other id character) white_space (  ,  \n ,  \t ) comment (any other character but  \n ) error (any character that cannot start a new  good token) 6664vA State Transition Diagram: Transitions Out of  empty Only5Structure of Body of Insert6A Simplified ViewWBuffer States EMPTY_BS ID_OR_KEYWORD_OR_CONDITION_BS WHITE_SPACE_BS COMMENT_BS ERROR_BS(JJ7The State Transition Diagram8Useful Private FunctionsIs_White_Space_Character (ch) Is_Digit_Character (ch) Is_Alphabetic_Character (ch) Is_Identifier_Character (ch) Can_Start_Token (ch) Id_Or_Keyword_Or_Condition (t) Buffer_Type (ch) Token_Kind (bs, str)/ !#9:;<=@X ` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@(?n<d@ `7 `2@`7``2 n?" ddH@ f @`PR    @ ` ` p>>  z   (     <" .  T<d" .  <"U_ .  Td">& .  N"P .  <"{ .  C xl?d?"mU .  6 "`  T Click to edit Master title style! !$  0 " "  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6h "@  B*  6lh "@`  h D*  6 h "` h D*B  s *޽h ? 13 Default Design%     k (  T +  "+bb P@ # "Dwoh  s *"PP  Bd" P@bb P 0  # "Nyh  s *"P    Bd"P 0 z   <" a*h   s *"    f?d?"+)   < ?"pP  T Click to edit Master title style! !   0 " `    W#Click to edit Master subtitle style$ $  6@ "`p   F*  6 "`p   H*  6p "`  H*B  s *޽h ? 13* 0 :(    08  P   h \*   0:     ^* d  c $ ?    0X  @  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6,h `P   \*   6h `  h ^* H  0޽h ? ̙3380___PPT10.TP( \H(  \ \ 0pY P    B*  \ 0     D*  \ 6 `P   B*  \ 6x `   D* H \ 0޽h ? ̙3380___PPT10.Tpx  %    (    N8c?"0@  N 8c?"P@  Nh ?"  BCode Generator  6h ` mTranslator Architecture(L ` P  #  @  Th ?" l @  :Parser  T 8c?"` P    Th ?"`vj = Tokenizer  B   ZD8c?"0B   ZD8c?" B   ZD8c?" B   ZD8c?"P  Th ?"p  X"string of characters (source code)##  Th ?"p   Fstring of tokens  Th ?"q   Fabstract program  Tdh ?"p  V string of integers (object code)!!H  0޽h ? 3333N  jNbN0^`| M(  |~ | s *, `   j | BGjJ?l |  `xaxa1?h2  JAnother great machine! 00F X 0& |  X0&N X & | X &R | "B=ChDE\Ff@@@1 Og "(4EK%K5Q=W-] hhW_K?K?QE. 04@` &R | "B5ChDE\Ff@@@1 #w(_4GF/KKQW]'hghWKKQ5F5.-04@`X    | BCDE4F>1MM.Ew]otg_XPH@@8"@3@K8\0n 8H_Q. .E\-M]|y\(tQ4mM  @`  )N  0P   |  0P N  0P   |  0P   | B=CWDEF1##WwnL4# %==QWQQ4wg_OG7(HL@` P *  | B/C4DEHFR1' '##(#(444.(#'// &(@`. ]  | BCDE4F>1      @` = z | JBCDEpFz1        :<@`\ =y  | BDCWDEF1##<nL4#~fW ?Q?WnQQ4$<D<HL@` 0P * | B0C4DEHFR1 # #0( #(444.(# &(@`j   | B'CDE4F>1  '     @`  z | JB'CDEpFz1'       ' :<@`\ y  | BOCDEF1'#/O @}   | BHCDEF1(H(0.@@ @ K  | BCDE@FJ1 4 W08H_gw]w4wW@"$@` + N    |     | B7CDE8FB1.Qt 77t/Q'./' @`   | BCDEF1 @` '  | BCDEF1 @` '  | BCDEF&``1@`' ( FN  8  |  8 H2 | C 1  H2 | C 13 8 H2 | C 1  H  | C 1a  H !| C 1 n  N s .  "| s .  #| BC#DE$F.ࠀ1  #@`   N s .  $| s . R %| "B7C)DE\Ff17))))))###''// / //77704@`  N s   &| s   '| B_CKDEFࠀ1&&?W___W#OGO#O)G.?474747:7@/@(F(@(F KKKFFF@:4)#  /?NP@`s   (| BC DEF1  @   )| BC DEF 1   @   *| BCDEF 1   @   +| BCDE<FF@1   $@`  " ,| B8CDEDFN1 ((0080(( $(@` . " -| B CDEDFN1 $(@`   N s (  .| s (  /| BC#DE$F.ࠀ1  #@` (  N s (  0| s ( R 1| "B8C)DE\Ff18)0)0)0)()() # ##  04@`  N s   2| s   3| BgCKDEFࠀ1&&(# #) .(404040:0@8@8F@@@F@KHKPKWF_F_Fg@g:g4g)g#g_W P@8(NP@`s   4| BC DEF1 @   5| BC DEF 1 @   6| BCDEF 1   @   7| BCDE<FF@1   $@`  " 8| B/CDEDFN1'/'$(@`  " 9| BCDEDFN1$(@` ( F F   :| F   N F   ;| F  Z <| *B CDEFࠀ1888"@\GGO_o?wPmy5Ms\\l?(W"  h:t%wGK@tG@@0(8"rt@`  N F W  =| F W  >| B*CDEF@1oo   "**n h]]WK@:.|(l#U(MMM =-  wg WG(84 @KWht (8@GOgwgoowztnnnnnhhntzzz-t=nMhUc\WdQtQ|QQ]cntz@`F W N =  ?| = : @| BGC(DEPFZ`@ 1G(/#'' 7/' ''###((/(G(*,@` A| B'CDE(F2`@ 1  ' @`Cj B| B CDE$F.`@ 1  @`=] C| BCDE$F.`@ 1   @`E] D| B/CDE@FJ`@ 1'/'' /   "$@`  N iM  E| iM L F| B CnDE`Fh1  .:FW]cnnfnGicWL@4#/' 14@Q   N i M  G| i M N  jG  H|  jG LN  fG  I|  fG H2 J| C 1 fG N2 K| S 1, NA H L| C 1& N0  M| BCDE$F.1 'W@` j" N i M  N| i M 2 O| CɛENGH06=JQQ1 w`T7(ɛw`T7(ɛQ(ɛQi H 2 P| C.ENG*hHx I`TJ_TQ1 ?.S?.S`T_T?.S`T_Tf M N E  Q| E N  R|  S| B_CDEF@p_?( @# T| B^CDEF@p'G^ @N ZE  U| ZE B2 V| 3 E B2 W| 3 +ZE p Y| HGjJ?7/j Z| BjJ? 'j [| BjJ? o  ]|  `xaxajJ?OF G  HReady to Dispense? j2 ^| BjJ??   _|  f\xaxajJ? !  J In (Chars)$   `|  f xaxajJ?   L Out (Tokens)$   H | 0޽h ?/ O|P| 13~I  ??@OQ>(  r Q S T `   j  BG1?  d  <1?X  d  <1?X L   Zxaxa1?Y  HReady to Dispense? d2  <1? `    `xaxa1?; F  6In    `Dxaxa1?; 7 F  7Out z  P    P,$D 0   HA ?1? t PX $ 0B 0    `tڥxaxa1?Z  K3: Tokens come out here r   BG1?@ z X`   X` ,$D 0  HA ?1?P ` X $ 0B 0r B BG1?X0   `\ߥxaxa1?AI G2: Light comes on 24z V{ P {V,$D 0   f\xaxa1?V{Y  L1: Characters go in here ~  NG1?` 02T   C#  N O$   O$ VN O$   O$ VN OQ$   OQ$    BC"DE8FBࠀ1NN1 rO2 k;  #-;OcurMv%vmhc_cGc'hrG-5-U}} }uu'M'%#;b "%"Mm  #;KvcbsO1@`OQ$ N |`   |`   B/CDE F(1lY@'/@`   B8CDEF108( @| N       BC"DE@FJ@1PP,"(HXo &6N]"u1@Tq}}eVF>>6 " o_Pgwwogg{oqwlgb]TJJEE@@@EoEX@P@@;86(11,@` N        BCDE,F6`@ 1  @`9 ! BCDEF`@ 1 @` " B8CDE4F>`@ 1 ( 8 (    @`z # B0CDE4F>`@ 1 ((( ( 0 (   @`  $ B0CDE8FB`@ 1    (0 ( (   @` ; % B(C DEF&`@ 1 (@`+S N B;} & B;} ' B0CDEF@p 00 @ B;[ ( B0C'DE4F> 0( ''"(00 0 @`V} N    )    N f   * f  N fK   + fK  " , BC'DEDFN0001`H0'h' $(@`f U  - BClDE@FJ0001P'8"(;XbglX@"'P'"$@`lK  N ~   . ~   / bBCDEF1?? w#26&@6T>cFqF>>FN]u,@mTNgvlT@'m @b_@88v8T@1@@ 80 {m^J6 @`~  N  (  0  ( j 1 :B.CEDEhFr``1.@&E@;66661,'#o_H8(68@` Z  2 BC DEF"``1   @`   N    3    4 BCDEF"``1@`   5 BCDE F*``1 @`   6 BC DE F*``1 @` ( N  Z  7  Z N  V3  8  V3  9 BCDEFࠀ1))8Oo,,,1;DIXg{oO8( vq l(g(b(]0X8X8S?IGIWDG@86(, TX@` V3 >N  7  :  7  ; |BCDEF1 @   < BC DEF1 @  = |BC DEF1 @  > B8CDEF 1 (8 @ 7 $N  Z  ?  Z tN  U  @  U N - U  A - U  B BCIDE F*1I?D_;I@`E U  C B/C#DEF"1 (/ #@`-$ \G  D BC DEF1  @`U= dG BN  L  E  L  F BCcDE@FJ1O@(,8GW o_1O;OJ?Y8c(^TO"$@` L  G BC DEF1  @`f v JN ? Z  H ? Z B I BC]DEF155'XO@,G_w"16E%OMJm@@EOXbl{'};}]eS=I%I?1''g"O?  7Ogww_{?l'Xlp@`? Z N G   J G   K B7C6DE,F61  '/#767#/ @`   L B'C"DE4F>1  " '  @`UB |d  M RBOC(DEtF~1O G @8 ( (8@@8(  08@GGG#8(G#OOO <@@`   N B C DEF"1   @`) 3  O BWCEDE,F41 E;6,''/7?G WO@G B H  0޽h ? 3333  ___PPT10 + WD ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*P%(D' =-o6Bdissolve*<3<*PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +  PF(  x  c $p- `     c $G  "  "@H  0޽h ? 3333  `F(  x  c $P5h `  h   c $G  " h "@H  0޽h ? 3333[   p(  r  S L `   2   `N |?"D  Knot ready to dispenseA2   `R |?"? d  Gready to dispenseAB  ZD8c?"F 6 B @  fD8c?" F 6 (   0e0e    BC(DE(F A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E (L8@0P @   S"Hv^p.   0e0e    B|CODE(F A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E S4|^sj"OJE; @   S"P  (   0e0e    BpCDE(F A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E PT@p( @pH8  @   S"(   0e0e    BXCXDE(F A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E 8Xh0h(0@X @   S"H6(   0e0e    BCDE(F A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E 0(Xpp  @   S"` N (   0e0e    B@CPDE(F A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E p8X@P@0 0 @   S" &f   NY 8c?"? k  >InsertC  N] 8c?" E Flush_A_TokenC  N|a 8c?" >InsertC  NXe 8c?" F  <SizeC  Nd 8c?"  <SizeC  Nk 8c?" V  LIs_Ready_To_DispenseC  No 8c?" F  LIs_Ready_To_DispenseC  Ns 8c?"  @Dispense  CH  0޽h ? 13  $(  r  S |z `   r  S P{  "  H  0޽h ? 13&  /'(  r  S  `     N 8c?"z K uprocedure_body Get_Next_Token ( alters Character_IStream& str, produces Text& token_text, produces Integer& token_kind ) { }CCC!CCCC(C,/]  ZD 8c?",$D 0 80 while (not self.Is_Ready_To_Dispense () and not str.At_EOS ()) { object Character ch; str.Read (ch); self.Insert (ch); } if (self.Is_Ready_To_Dispense ()) { self.Dispense (token_text, token_kind); } else { self.Flush_A_Token (token_text, token_kind); }1CCCCCCCCCCCC.CCCCCC CC*CCCC+Cb4 $ H  0޽h ? 132*___PPT10 +kcD' = @B Dq' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*C%(D' =-o6Bdissolve*<3<*CD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*CI%(D' =-o6Bdissolve*<3<*CID' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*If%(D' =-o6Bdissolve*<3<*IfD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*f}%(D' =-o6Bdissolve*<3<*f}D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*}%(D' =-o6Bdissolve*<3<*}D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =-o6Bdissolve*<3<*1+8+0+ +p  V(  x  c $ `      N 8c?"  procedure_body Get_Next_Non_Separator_Token ( alters Character_IStream& str, produces Text& token_text, produces Integer& token_kind ) { }C(CC!CCCC%C,=Z  Z 8c?"@Z ,$D 0  self.Get_Next_Token (str, token_text, token_kind); while ((token_kind == WHITE_SPACE) or (token_kind == COMMENT)) { self.Get_Next_Token (str, token_text, token_kind); }CC3CCCC5CC4CC,!H  0޽h ? 13RJ___PPT10*+kcD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*7%(D' =-o6Bdissolve*<3<*7D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*7a%(D' =-o6Bdissolve*<3<*7aD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*a%(D' =-o6Bdissolve*<3<*aD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+8+0+ +  #(  r  S t `   x  B 8c?"p @B  ZD8c?" B  ZD8c?"`  ` B   `D8c?"@` B   `D8c?"@ ` B   `D8c?"pB   `D8c?" PB  ZD8c?"P @B   `D8c?" pT  Z 8c?"  Tbuffer:  PROGRAM ready_to_dispense: falseL+ CGCGx  B 8c?"@  B  ZD8c?"P  P B  ZD8c?"0 0B   `D8c?"0B   `D8c?" 0B   `D8c?"P @ B   `D8c?"P B  ZD8c?" B   `D8c?"P @ T  Z 8c?"  d  Tbuffer:  PROGRAM  ready_to_dispense: trueL+ CGCG  Z0 8c?"x 9#m:A  Z  8c?"P 'p  8m:A   NA ?1? X $ 0B 0p !@ HG1?<  "  fxaxa1?r  h2Here s another character. 2 #  `  8c?",  @  CH  0޽h ? 133  s(  r  S T `     Z 8c?" @S  )1procedure Insert ( preserves Character ch ) is_abstract; /*! requires self.ready_to_dispense = false ensures self.buffer = #self.buffer * and self.ready_to_dispense = IS_COMPLETE_TOKEN_TEXT (#self.buffer, ch) !*/2 CC CC CC C C CCCCCC CC CCCC CC>CCC>/a H  0޽h ? 13 is not in OK_STRINGS ) or ( is in PREFIX (OK_STRINGS) and s * is not in PREFIX (OK_STRINGS) )RA%AA A AAAAA AA AAA AAAAAAAA AA  N 8c?"p ,$D 0  N 8c?" p ,$D 0  N 8c?"^ p*N ,$D 0  N 8c?" p ,$D 0l )  ) ,$D 0  N 8c?") ,$D 0   Z6 8c?"[  t:s is a complete  valid tokenGb  3 rG+HIw8c?"~ Xl  @ * @ *,$D 0  N 8c?"@  ,$D 0b   Z< 8c?" pR * c can start a  valid token, but s*<c> doesn t start a  valid tokenEEGb  # lG+HI<8c?" pH  0޽h ?/@    13___PPT10+,ÖD' = @B DC' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +  0(  x  c $LJ `   x  c $ K  "  H  0޽h ? 13  P(  r  S Y `     S Z  "<$ 0  H  0޽h ? 13n f ___PPT10F .+NwnD ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-o6Bdissolve*<3<*DD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*DZ%(D' =-o6Bdissolve*<3<*DZD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Z%(D' =-o6Bdissolve*<3<*Z+8+0+ +  b(  ~  s *Hl `     c $xg  "<$ 0  H  0޽h ? 13___PPT10v.+NwnD' = @B D' = @BA?%,( < +O%,( < +D' =%(D(' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*'%(D' =-o6Bdissolve*<3<*'D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*';%(D' =-o6Bdissolve*<3<*';D' =%(D(' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*;H%(D' =-o6Bdissolve*<3<*;HD@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*H%(D' =-o6Bdissolve*<3<*HD@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+8+0+ +   \(  x  c $t `     c $u  "<$ 0  H  0޽h ? 13~ v ___PPT10V .+_D ' = @B D ' = @BA?%,( < +O%,( < +D ' =%(%(Dp ' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*#%(D' =-o6Bdissolve*<3<*#D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*#d%(D' =-o6Bdissolve*<3<*#dD@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-o6Bdissolve*<3<*dD@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+8+0+ +    \(  x  c $ `     c $Ԇ  "<$ 0  H  0޽h ? 13v n ___PPT10N .+NwnD ' Hw= @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =-o6Bdissolve*<3<*DD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Ds%(D' =-o6Bdissolve*<3<*DsD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*s%(D' =-o6Bdissolve*<3<*s+8+0+ +  00(  x  c $| `   x  c $P  "  H  0޽h ? 13   @\(  x  c $,~ `     c $(  "<$ 0  H  0޽h ? 13~v___PPT10V.+NwnD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*J%(D' =-o6Bdissolve*<3<*JD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Jh%(D' =-o6Bdissolve*<3<*Jh+8+0+ +   \(  x  c $0 `     c $  "<$ 0  H  0޽h ? 13^V___PPT106.+֜D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*R%(D' =-o6Bdissolve*<3<*RD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*R%(D' =-o6Bdissolve*<3<*RD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+8+0+ +  P\(  x  c $ `     c $  0<$ 0  H  0޽h ? 13f^___PPT10>.+֜D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D' =-o6Bdissolve*<3<*6D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D' =-o6Bdissolve*<3<*6D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =-o6Bdissolve*<3<*(+8+0+ +#  i#a#`--"(  x  c $L `   2   ` 8c?" 9BC2   ` ѥ 8c?" 9DC2   `PX 8c?" / 9EC2   ` 8c?"  _ 9IC2   `T 8c?" 9PC2   ` 8c?" 9TC2   `  8c?" `_ 9WC2   ` 8c?"0 +o  9nC2   `h 8c?" O  9rC2   ` 8c?"   9tC2   ` 8c?" B identifier  C2   ` 8c?"  C white_space  C2   ` 8c?" V& ?commentC2   ` 8c?"   =errorCB   fD8c?"V@B   fD8c?"pB   `D8c?"Fv B   fD8c?"v B   fD8c?"vB   `D8c?"B   `D8c?" B   `D8c?" F B   `D8c?"0 Fvp B   `D8c?"`  B   `D8c?"` &B   `D8c?"` V pB   `D8c?"`  B   `D8c?" &` 2  # l| 8c?"@  =emptyC  Z 8c?"MP > B C ! Z 8c?"pEUW > D C " Z 8c?"x< > _ > E C # Z 8c?"O F  > I C $ Z0" 8c?"(D7 > P C % Zx% 8c?"9   > T C & ZP) 8c?"P7 > W C ' ZP. 8c?"6)  > n C ( Z0 8c?"Y @  > r C ) Z4 8c?" zf  > t C * Z8 8c?"  Hany other letterC + Z< 8c?" N  R  , \n , \t C , Z? 8c?"` G  > # C - Z # C  Z 8c?"` \$ a .. z ,  A .. Z C  ZH 8c?" ,D  Kany other characterC   0e0e    BCDE(F @  8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E 0p @`@`  @   S"0 (   0e0e    B`CPDE(F @  8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E xP`Hh@LP  @   S"   0e0e    B(CDE(F @  8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E `p0(`x @   S" P   0e0e    BCDE(F @  8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E XPP8H` @   S" 0h  Z6 8c?"$    j2any character except  \n C  ZL 8c?" V  ,  \n ,  \t C  ZT 8c?"  zB a .. z ,  A .. Z ,  0 .. 9 ,  - ""CJ  Z 8c?""  zany character except  a .. z ,  A .. Z ,   ,  \n ,  \t ,  # >>CH  0޽h ? 13  0(  x  c $`h `  h x  c $4h  " h H  0޽h ? 13 0 ((  ^ S     c $> @    H  0޽h ? ̙33 0 ((  ^ S     c $t9 @    H  0޽h ? ̙33 0 ((  ^ S     c $k @    H  0޽h ? ̙33 0 0l(  ^ S     c $hD @   bNTo check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep, ch) you will need to look at the buffer and decide what kind of token you are reading. Knowing that you can then check if ch is a character that belongs to that kind of token or not. If not, then the token IS complete. To determine WHICH_KIND (token_text), you again have to look at the buffer. You may try to be clever, but ultimately you need to compare the buffer to each keyword and condition to distinguish them from identifiers. By  quickly we mean that you can make these decisions without having to look at the buffer, or, in other words, each character in the machine is processed once (and exactly once, in Insert).H  0޽h ? ̙33 0 bZ@(  ^ S    T c $T @   Suppose the first character is  a . What token are we reading? Identifier. Suppose the first character is  b . What token are we reading? Identifier. So there is no need to distinguish the two states. However, if the first character is  P . What token are we reading? Identifier OR the keyword PROGRAM, but we don t know yet. So we should keep this as a separate state (to be able to make the appropriate decision quickly as soon as we get a character that allows us to do that). What if the first character is  I ? What token are we reading? Identifier or the keyword INSTRUCTION or the keyword IS or the keyword IF. So, again, we need to keep this as a separate state. So there are 14 possible states after the first character + 1 initial stateH  0޽h ? ̙33 0 RJP(  ^ S    D c $a @   Suppose the state is  B and the second character is  E . What token are we reading? Identifier or BEGIN. Suppose the state is  B and the second character is not  E . What token are we reading? Identifier. So there are 13 more states after reading two characters (plus the previous 15 = 28 states). In total, we d need 107 distinct states. For tokenizers/lexers that are generated by tools, there is no problem having hundreds of states the code is long but efficient. For our Tokenizing_Machine however, writing such code would be tedious and error-prone, so we ll use a compromise.,Y H  0޽h ? ̙33 0 (  X  C      S r @   activityH  0޽h ? ̙33 0  (  X  C      S { @   activityH  0޽h ? ̙33 0 ((  ^ S    h c $@2ݑĐEB@Ae OR gCo`ǐL2C of1<0s"yR$,/$|3Js2 JsrR*)_*8*&ٯ32:'3d敤%(xX!/O- JZ8+e[%C$3;g30(RP uCsG' 7c9c|HZM@(Z{t>PV9(#]*(f`k&7g?eZ`ϐB~`ANO 8N$H`(B  xp^RЀ3ÿ lHbP  LPÄ!1 4axĐ% y@( XyTxeH!]/ܮκa) 9 $ى C>@2ݑĐEB@Ae OR gCo`ǐL2C of1<0s"yR$,/$|3Js2 JsrR*)_*8*&ٯ32:'3d敤%(xX!/O- JZ8+e[%C$3;g30(RP uCsG' 7c9c|HZM@(Z{t>PV9(#]*(f`k&7g?eZ`ϐB~`ANO 8N$H`(B  xp^RЀ3ÿ lHbP  LPÄ!1 4axĐ% y@( XyTxeH!]/ܮκa) 9 $ى C>@2ݑĐEB@Ae OR gCo`ǐL2C of1<0s"yR$,/$|3Js2 JsrR*)_*8*&ٯ32:'3d敤%(xX!/O- JZ8+e[%C$3;g30(RP uCsG' 7c9c|HZM@(Z{t>PV9(#]*(f`k&7g?eZ`ϐB~`ANO 8N$H`(Br0,|:DJ 5sGu@[MRTiVF?ZXYwdlqi9}'C)d.\0PIXm_gmo۔ OUq mky@:,(   )2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery2Microsoft ClipArt Gallery $MS_CliOh+'04 hp  PowerPoint Presentation Paolo Bucciaol Paolo Bucci49lMicrosoft PowerPointon@`~Ag@@E@\g/G3g    -- @ !--'-- @ !40M---'--- @ !4MW---- @ !4MX---- @ !4MZ---- @ !4M[---- @ !4M\---- @ !4M]---- @ !4M^---- @ !4M_---- @ !4M`---- @ !4Ma---- @ !4Mb---- @ !4Mc---- @ !4Md--~-- @ !4Me--{-- @ !4Mf--w-- @ !4Mg--r-- @ !4Mh--m-- @ !4Mi--i-- @ !4Mj--d-- @ !4Mk--^-- @ !4Ml--Y-- @ !4Mm--S-- @ !4Mn--M-- @ !4Mo--G-- @ !4Mp--B-- @ !4Mq--<-- @ !4Mr--6-- @ !4Ms--0-- @ !4Mt--*-- @ !4Mu--%-- @ !4Mv---- @ !4Mw---- @ !4Mx---- @ !4My---'-- @ !4.{;--'--- @ !4{c---- @ !4{d---- @ !4{e--&-- @ !4{f----- @ !4{g--4-- @ !4{h--;-- @ !4{i--B-- @ !4{j--H-- @ !4{k--O-- @ !4{l--V-- @ !4{m--]-- @ !4{n--c-- @ !4{o--j-- @ !4{p--ݱq-- @ !4{q--حx-- @ !4{r--Ҩ~-- @ !4{s--ͣ-- @ !4{t--ƞ-- @ !4{u---- @ !4{v---- @ !4{w---- @ !4{x---- @ !4{y---- @ !4{z--{-- @ !4{{--u-- @ !4{|--n-- @ !4{}--g-- @ !4{~--ya-- @ !4{--qZ-- @ !4{--hS-- @ !4{--`L-- @ !4{--WF-- @ !4{--O?-- @ !4{--G8-- @ !4{-->1-- @ !4{--6*-- @ !4{---#-- @ !4{-- -- @ !4{-- -- @ !4{---'A .=s ( %')*,--./012222#$&(*,,-./01222 "$&(*+,-./01 "#%')+,--.01!#-u!gs~Ydp{KVamx' =HS_j! / : EQ\ , 8 CNcdefgKLMNO-./01]^_`aFGHIb !"#$VWXYZAB[D\PQRST;<=>?UKLMNO-./0123456FGHIJ !"#$%&'()ABCDE;<=>?@ -./0123456789:, !"#$%&'()*+, '-- @ !sAS--'--- @ !E/---- @ !5t---- @ !'---- @ !#---- @ ! ---- @ !---- @ !+---- @ !D---- @ !Y---- @ !q---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !%---- @ !6---- @ !O---- @ !d---- @ !}---- @ !---- @ !#---- @ !'---- @ !8---- @ !U:---- @ !#---'1-- @ !t---- $nUnU--'-- $nZnZ--'@BComic Sans MS-.  2 ,Code."Systemlv-@BComic Sans MS-. 2 T Generatoro.-@BComic Sans MS-. *2 Translator Architecture&) .-@BComic Sans MS-. 2 @Parser.--- $nXnX--'@BComic Sans MS-. 2 @ Tokenizero .---8S335S5S30480--'--8U335U5U30480--'--8X335X5X30480--'--8Z335Z5Z30480--'@BComic Sans MS-. 2 G string ofo   .-@BComic Sans MS-. 2 : characters   .-@BComic Sans MS-. 2 + (source code)   .-@BComic Sans MS-. 2 > string ofo   .-@BComic Sans MS-. 2 Ktokens  .-@BComic Sans MS-. 2 Eabstract  .-@BComic Sans MS-. 2 Gprogramt .-@BComic Sans MS-. 2 C string ofo   .-@BComic Sans MS-. 2 Fintegers   .-@BComic Sans MS-. 2 ( (object code)     .-Gallery2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery*2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery/ 00DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 00DWingdings MSn0:A 0 C.  @n?" dd@  @@``  C'(7.-O." aR )*$+' .)),,2$ ;]Iפ5Ì71 0e0e     A@  A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|ES"@8*ʚ;r1ʚ; g4VdVd :A 0ppp@ <4!d!dL$ 0T<4ddddL$ 0Tg4CdCd :A 0p@ pp<4BdBdL$ 0T80___PPT10 ? %?A Tokenizing Machine:Tokenizing Machine Continued& :Tokenizing Machine Continued& Type BL_Tokenizing_Machine_Kernel is modeled by ( buffer : string of character ready_to_dispense : boolean ) constraint & Initial Value (empty_string, false)2Z"     Root EntrydO)lD@PicturesCurrent UserASummaryInformation(F 5      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEmGHIJKLMNOPQRSTUVWXYZ[\]^_`bcdefghunopstvwxyz{|}~a pArt_Gallery02Microsoft ClipArt Gallery*2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery/ 00DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 00DWingdings MSn0:A 0 C.  @n?" dd@  @@``  C'(7.-O." aR )*$+' .)),,2$ ;]Iפ5Ì71 0e0e     A@  A8c 8c8c     ?1 d0u  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~0@Ty2 NP'p<'pA)BCD|ES"@8*ʚ;r1ʚ; g4VdVd :A 0ppp@ <4!d!dL$ 0T<4ddddL$ 0Tg4CdCd :A 0p@ pp<4BdBdL$ 0T80___PPT10 ? %?A Tokenizing Machine:PowerPoint Document(DocumentSummaryInformation8Tokenizing Machine Continued& :Tokenizing Machine Continued& Type BL_Tokenizing_Machine_Kernel is modeled by ( buffer : string of character ready_to_dispense : boolean ) constraint & Initial Value (empty_string, false)2Z"     ":Tokenizing Machine Continued& Operations m.Insert (ch) m.Dispense (token_text, token_kind) m.Is_Ready_To_Dispense () m.Flush_A_Token (token_text, token_kind) m.Size (),  s$A State-Transition View'Tokenizing BL ProgramsBToken Types KEYWORD IDENTIFIER CONDITION WHITE_SPACE COMMENT ERROR& 7 7%A Very Useful Extension&Another Useful Extension) How Does Insert Work?+ The Specification of Insert, An Important Math Operation(Other Math DefinitionswOK_STRINGS = {s: string of character (IS_KEYWORD (s))} union {s: string of character (IS_IDENTIFIER (s))} union {s: string of character (IS_CONDITION_NAME (s))} union {s: string of character (IS_WHITE_SPACE (s))} union {s: string of character (IS_COMMENT (s))} PREFIX (s_set) = {x: string of character (there exists y: string of character (x * y is in s_set))}Tx   >PREFIX Examples.s_set = { abc } PREFIX (s_set) = {  ,  a ,  ab ,  abc } s_set = { abc ,  de } PREFIX (s_set) = {  ,  a ,  ab ,  abc ,  d ,  de }- :Tokenizing Machine: ImplementationObvious Representation Text buffer_rep Boolean token_ready Insert (ch)? check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep], ch), and set self[token_ready] accordingly append ch at end of self[buffer_rep] L$ $ . hTokenizing Machine: Implementation Continued& Dispense (token_text, token_kind)? set token_text to all but the last character of self[buffer_rep] set token_kind to the value of WHICH_KIND (token_text) set self[token_ready] to false&##,  /hTokenizing Machine: Implementation Continued& *How do we  check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep], ch) ? How do we determine  WHICH_KIND (token_text) ? How do we do these things quickly?$0Making Decisions QuicklyKeep track of the  state of the buffer by adding one field to the representation: Text buffer_rep Boolean token_ready Integer buffer_state >S:S$1Possible Buffer StatesHow many interestingly different buffer states#_e Paolo BucciPaolo Buccig Services՜.+,0|    $ On-screen ShowThe Ohio State Universityn" {  Times New RomanComic Sans M do you think there may be? Let s start enumerating them& $i S20Buffer States Continued& Initial state (empty buffer) How many states after inserting the first character?  B ,  D ,  E ,  I ,  P ,  T ,  W ,  n ,  r ,  t , identifier (any other letter) white_space (  ,  \n ,  \t ) comment ( # ) error (any other character) <RZZZR30Buffer States Continued& RHow many states after inserting the second character?  BE ,  DO ,  EL ,  EN ,  IF ,  IN ,  IS ,  PR ,  TH ,  WH ,  ne ,  ra ,  tr , identifier (any other id character) white_space (  ,  \n ,  \t ) comment (any other character but  \n ) error (any character that cannot start a new  good token) 6664vA State Transition Diagram: Transitions Out of  empty Only5Structure of Body of Insert6A Simplified ViewWBuffer States EMPTY_BS ID_OR_KEYWORD_OR_CONDITION_BS WHITE_SPACE_BS COMMENT_BS ERROR_BS(JJ7The State Transition Diagram8Useful Private FunctionsIs_White_Space_Character (ch) Is_Digit_Character (ch) Is_Alphabetic_Character (ch) Is_Identifier_Character (ch) Can_Start_Token (ch) Id_Or_Keyword_Or_Condition (t) Buffer_Type (ch) Token_Kind (bs, str)/ !#9:;<=@  PF(  x  c $X  `     c $   "   "@H  0޽h ? 3333rWzm3z@:,(   )2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt STahoma WingdingsDefault DesignMicrosoft ClipArt GallerySlide 1A Tokenizing MachineTokenizing Machine ContinuedTokenizing Machine ContinuedTokenizing Machine ContinuedA State-Transition ViewTokenizing BL ProgramsA Very Useful ExtensionAnother Useful ExtensionHow Does Insert Work?The Specification of InsertAn Important Math OperationOther Math DefinitionsPREFIX Examples;Tokenizing Machine: Implementation5Tokenizing Machine: Implementation Continued5Tokenizing Machine: Implementation ContinuedMaking Decisions QuicklyPossible Buffer StatesBuffer States ContinuedBuffer States Continued<A State Transition Diagram: Transitions Out of empty OnlyStructure of Body of InsertA Simplified ViewThe State Transition DiagramUseful Private Functions  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles":Tokenizing Machine Continued& Operations m.Insert (ch) m.Dispense (token_text, token_kind) m.Is_Ready_To_Dispense () m.Flush_A_Token (token_text, token_kind) m.Size (),  s$A State-Transition View'Tokenizing BL ProgramsBToken Types KEYWORD IDENTIFIER CONDITION WHITE_SPACE COMMENT ERROR& 7 7%A Very Useful Extension&Another Useful Extension) How Does Insert Work?+ The Specification of Insert, An Important Math Operation(Other Math DefinitionswOK_STRINGS = {s: string of character (IS_KEYWORD (s))} union {s: string of character (IS_IDENTIFIER (s))} union {s: string of character (IS_CONDITION_NAME (s))} union {s: string of character (IS_WHITE_SPACE (s))} union {s: string of character (IS_COMMENT (s))} PREFIX (s_set) = {x: string of character (there exists y: string of character (x * y is in s_set))}Tx   >PREFIX Examples.s_set = { abc } PREFIX (s_set) = {  ,  a ,  ab ,  abc } s_set = { abc ,  de } PREFIX (s_set) = {  ,  a ,  ab ,  abc ,  d ,  de }- :Tokenizing Machine: ImplementationObvious Representation Text buffer_rep Boolean token_ready Insert (ch)? check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep], ch), and set self[token_ready] accordingly append ch at end of self[buffer_rep] L$ $ . hTokenizing Machine: Implementation Continued& Dispense (token_text, token_kind)? set token_text to all but the last character of self[buffer_rep] set token_kind to the value of WHICH_KIND (token_text) set self[token_ready] to false&##,  /hTokenizing Machine: Implementation Continued& *How do we  check if IS_COMPLETE_TOKEN_TEXT (self[buffer_rep], ch) ? How do we determine  WHICH_KIND (token_text) ? How do we do these things quickly?$0Making Decisions QuicklyKeep track of the  state of the buffer by adding one field to the representation: Text buffer_rep Boolean token_ready Integer buffer_state >S:S$1Possible Buffer StatesHow many interestingly different buffer states do you think there may be? Let s start enumerating them& $i S20Buffer States Continued& Initial state (empty buffer) How many states after inserting the first character?  B ,  D ,  E ,  I ,  P ,  T ,  W ,  n ,  r ,  t , identifier (any other letter) white_space (  ,  \n ,  \t ) comment ( # ) error (any other character) <RZZZR30Buffer States Continued& RHow many states after inserting the second character?  BE ,  DO ,  EL ,  EN ,  IF ,  IN ,  IS ,  PR ,  TH ,  WH ,  ne ,  ra ,  tr , identifier (any other id character) white_space (  ,  \n ,  \t ) comment (any other character but  \n ) error (any character that cannot start a new  good token) 6664vA State Transition Diagram: Transitions Out of  empty Only5Structure of Body of Insert6A Simplified ViewWBuffer States EMPTY_BS ID_OR_KEYWORD_OR_CONDITION_BS WHITE_SPACE_BS COMMENT_BS ERROR_BS(JJ7The State Transition Diagram8Useful Private FunctionsIs_White_Space_Character (ch) Is_Digit_Character (ch) Is_Alphabetic_Character (ch) Is_Identifier_Character (ch) Can_Start_Token (ch) Id_Or_Keyword_Or_Condition (t) Buffer_Type (ch) Token_Kind (bs, str)/ !#9:;<=@!    < (  r  S " `     Zp% 8c?"S  zmath definition IS_COMPLETE_TOKEN_TEXT ( s: string of character c: character ): boolean is ( s is in OK_STRINGS and s * is not in OK_STRINGS ) or ( is in PREFIX (OK_STRINGS) and s * is not in PREFIX (OK_STRINGS) ),A%AA A AA AAA AAA AAA AAAAA AAd  N 8c?"- ,$D 0  N 8c?" $ ,$D 0  N 8c?"% < ,$D 0  N 8c?"A 1 ,$D 0l u)  8 ,$D 0  N 8c?") ,$D 0   Z8{ 8c?"uk  t:s is a complete  valid tokenGb  3 rG+HIw8c?"~ Xl  @ *  6 ,$D 0  N 8c?"@  ,$D 0b   Z 8c?" p * c can start a  valid token, but s*<c> doesn t start a  valid tokenEEGb  # lG+HI<8c?" pH  0޽h ?/@    13___PPT10+,ÖD' = @B DC' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +r,-mǨM@