ࡱ> ( R/ 0|DTimes New Roman0:A 0DComic Sans MSn0:A 0 B DTahomaans MSn0:A 0"0DWingdings MSn0:A 0@DSymbolgs MSn0:A 0< R A>UU  @n?" dd@  @@`` |4*    ; <T9   ) 0e0e    A A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|ES"@8*ʚ;ʚ; g4hdhd :A 0ppp@ <4!d!dL$ 00M <4ddddL$ 00M g4CdCd :A 0p@ pp<4BdBdL$ 00M 80___PPT10 ? % Translator ArchitectureHere s the PlanDesign a context-free grammar to specify (syntactically) valid BL programs Use the grammar to implement a recursive descent parser (i.e., an algorithm to parse BL programs and construct the corresponding Program object)Specifying Syntax with CFGsdContext-free grammars (cfg) Some syntactically valid real constants: 37.044 615.22E16 99241. 18.E-93&E E 9Rewrite Rules for Real ConstantsFour Components of a CFGNonterminal symbols , , , Terminal symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, E, +, -, . Start symbol Rewrite rules on previous slideZ5ZZ)Z ZZZZ5)   A Derivation of 5.6E10A Derivation of 5.6E10A Derivation of 5.6E10A Derivation of 5.6E10 A Derivation Tree for 5.6E10 Find a Derivation Tree for 5.E3FThe derivation tree: Can you find a derivation tree for .6E10?GG Language Generated by a CFGDefinition: Let G = (Nonterminals, Terminals, , Rewrite Rules) be a context-free grammar. The language generated (or specified) by G is denoted L(G) and is defined as: x k   /Another Example: A CFG for Boolean Expressions CFG for Boolean ExpressionsrWhat are the nonterminal symbols? What are the terminal symbols? What is the start symbol? How many rewrite rules? "PQs 9A Derivation Tree for NOT((T OR F)) ;Find a Derivation Tree for ((T OR NOT (F)) AND T) A Famous Context-free Grammar rWhat s So Special About This CFG?$Find a derivation tree for 4 + 6 * 28What s So Special Continued& (Find the derivation tree for (4 + 6) * 2How About These Rewrite Rules?(New Rules Continued& $Find a derivation tree for 4 + 6 * 2(New Rules Continued& "How about this tree for 4 + 6 * 2?B ` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@(?n<d@ `7 `2@`7``2 n?" ddH@ f @`PR    @ ` ` p>>  z   (     <wM " .  TlM d" .  <lM "U_ .  TOM d">& .  N;M "P .  <$M "{ .  C xhpM ?d?"mU .  6M  "` M  T Click to edit Master title style! !$  0܏M  " " M  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6xt/  "@ M  B*  6$y/  "@`  M  D*  6P|/  "` M  D*B  s *޽h ? 13 321%     @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$ $  60  "`p    F*  6H  "`p    H*  6  "`   H*B  s *޽h ? 13* 0 :(    0@  P    \*   00t       ^* d  c $ ?     08   @   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6D  `P    \*   6  `    ^* H  0޽h ? ̙3380___PPT10.3h==F  0` N(  `x ` c $b|  `  |  L @`   `# P@ ` T|  ?"}   BCode Generator ` T 8c?"@`  L ` P  `#  @  ` TO|  ?" l @  :Parser  ` T 8c?"` P L ` P   `# 0@  ` T<|  ?" @  = Tokenizer    ` T 8c?"` P B `  `D8c?"0B `  `D8c?" B `  `D8c?" B `  `D8c?"P ` Tk|  ?"p  X"string of characters (source code)## ` T(y|  ?"p   Fstring of tokens ` T)|  ?"q   Fabstract program ` T(|  ?"p  V string of integers (object code)!!l   ` ,$D 0 ` ZG~6HnK8c?"  `  f4%| 8c?"w[  H ;?Hl   ` ` @,$D 0 ` T8c?"  ` ` ZL*|  ?"  :ParserH ` 0޽h ? 3333 ___PPT10+*D' = @B D' = @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$(  dr d S #z  `   r d S *z   " z  H d 0޽h ? 13  p$(  r  S z  `  z  r  S Lz   " z  H  0޽h ? 3333+    `  (  x  c $Dz  `  z     `?  ??9 J<real constant> <digit seqnce> . <digit seqnce> | <digit seqnce> . <digit seqnce> <exponent> | <digit seqnce> . | <digit seqnce> . <exponent> <exponent> E <digit seqnce> | E + <digit seqnce> | E - <digit seqnce> <digit seqnce> <digit> <digit seqnce> | <digit> <digit> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9J P-'  UUl `  `,$D 02   `8c?"p   f;z 8c?"` Mcan be rewritten as  B T8c?"q@8l Up Up,$D 02    `8c?"p    fL? 8c?"@U <or   T8c?"=@H  0޽h ?/@     3333 ___PPT10+GD' = @B D' = @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<*+  P$$(  $r $ S ?  `  ?  r $ S ?   " ?  H $ 0޽h ? 3333y  \T@ h(  hx h c $4?  `  ?  * h Tp:?  ?"+b,$D  0 d &n L h  fLD? 8c?"Pp,$D 0 t>We begin with the start symbol&   Z h  fDH? 8c?"7 ,$D 0 L& and choose one of its rewrite rules:''t h  f^? 8c?" [,$D 0 ,<real constant> <digit seqnce> . <digit seqnce> | <digit seqnce> . <digit seqnce> <exponent> | <digit seqnce> . | <digit seqnce> . <exponent>>YR"  h  f8c?"  ,$D 0H h 0޽h ? 3333  ___PPT10 +=[mD ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =-o6Bdissolve*<3<*hD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =-o6Bdissolve*<3<*hD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =-o6Bdissolve*<3<*hD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* h%(D' =-o6Bdissolve*<3<* h++0+h?  ++0+h?  ++0+h?  +:  2 * 0 l(  lx l c $tu?  `  ?   l Tw?  ?"++b,$D  0 x<real constant> <digit seqnce> . <digit seqnce> <exponent>P=n  l  fU? 8c?"Pp,$D 0 ZNow we choose one of the nonterminal symbols& ..  Z l  f}? 8c?"7 ,$D 0 L& and choose one of its rewrite rules:''" l  `8c?"P p,$D 0  l  f? 8c?"P YV ,$D 0 f<digit seqnce> <digit> <digit seqnce> | <digit>>4$."  l  `8c?"@ , ` ,$D 0H l 0޽h ? 3333___PPT10+YD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =-o6Bdissolve*<3<*lD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =-o6Bdissolve*<3<*lD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =-o6Bdissolve*<3<*lD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =-o6Bdissolve*<3<* lD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =-o6Bdissolve*<3<* l++0+l?  ++0+l?  ++0+ l?  +    p\ (  px p c $T?  `  ?  Z p T$  ?"++_,$D  0 <real constant> <digit seqnce> . <digit seqnce> <exponent> <digit> . <digit seqnce> <exponent>dn     p  fĮ? 8c?"Pbp,$D 0 ^Again we choose one of the nonterminal symbols& 00  Z p  f  8c?"7 ,$D 0 L& and choose one of its rewrite rules:''" p  `8c?"@2 `,$D 0 p  f` 8c?"P p ,$D 0 ^<digit> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9>0'" p  `8c?"P  p ,$D 0H p 0޽h ? 3333___PPT10+±"D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-o6Bdissolve*<3<*pD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-o6Bdissolve*<3<*pD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-o6Bdissolve*<3<*pD' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-o6Bdissolve*<3<*pD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-o6Bdissolve*<3<*p++0+p  ++0+p  ++0+p  +1    tM (  tx t c $  `     t Td$  ?"++\,$D  0 ><real constant> <digit seqnce> . <digit seqnce> <exponent> <digit> . <digit seqnce> <exponent> 5 . <digit seqnce> <exponent>n     j  t T  ?"@,$D  0 R 5 . <digit> <exponent> 5 . 6 <exponent> 5 . 6 E <digit seqnce> 5 . 6 E <digit> <digit seqnce> 5 . 6 E 1 <digit seqnce> 5 . 6 E 1 <digit> 5 . 6 E 1 0$n            $$(( (((( ((((,,00 000000004488 88 l G]<c tG<,$D  0  t  fa 8c?"G]<c If it s possible to find such a derivation, we write: <real constant> 5.6E10JO6  t  f؉ 8c?"* $ D 9*H t 0޽h ? 3333%%___PPT10e%+;D%' = @B D$' = @BA?%,( < +O%,( < +D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* t%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* tD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* tD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* t.%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* t.D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* t.D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* t.H%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* t.HD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* t.HD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* tHj%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* tHjD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* tHjD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* tj%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* tjD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* tjD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* t%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* tD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* tD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* t%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* tD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* tDn' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =+4 8?\CB#ppt_xBCB#ppt_xB*Y3>B ppt_x<*tD' =+4 8?dCB1+#ppt_h/2BCB#ppt_yB*Y3>B ppt_y<*t+8+0+ t  +K  !!+3,S(  ,r , S &  `    , T(  ?"4  A , T,  ?" @ , T0  ?"  @ , T  ?"#C  @ , T  ?"P p  @ , T  ?"# C  9  , T8  ?"#) C  9  , T(.  ?"P p  9  , TĄ  ?"   9  , T`  ?"  <     , T  ?"K 9. ,  `,  ?"# pC  9E ,  `  ?"P p  95 ,  `  ?"P  p  96 ,  `ij  ?"   91 ,  `g  ?" 90 ,@ Z8c?"\d  ,@ Z8c?"d  , Z8c?"d {  , Z8c?"d  , Z8c?"\\#  , Z8c?"{ { # !,@ Z8c?" # ", Z8c?"u# #,@ T8c?"C _uP  $, Z8c?"C uUP  %, Z8c?"p UU  &, Z8c?"p __  ', Z8c?" UU (, Z8c?"C { { P  ), Z8c?"C \\P " *,  `8c?"``,$D 0" +,  `8c?""B ,$D 0" ,,  `8c?"" B ,$D 0" -,  `8c?"" pB ,$D 0" .,  `8c?"P p ,$D 0" /,  `8c?"P p ,$D 0" 0,  `8c?"P  p ,$D 0" 1,  `8c?"  ,$D 0" 2,  `8c?",$D  0" 3,  `8c?"  ,$D  0H , 0޽h ?,,,, ,,,,,, ,, ,,, , , , ,,!, ,,",, ,#,,,$,, ,%, ,,&, ,,', ,,(,,,), 3333))___PPT10)+J2ID)' = @B DW)' = @BA?%,( < +O%,( < +D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<**,D' =1:Bvisible*o3>+B#style.visibility<**,%(D' =-o6Bdissolve*<3<**,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*+,D' =1:Bvisible*o3>+B#style.visibility<*+,%(D' =-o6Bdissolve*<3<*+,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*/,D' =1:Bvisible*o3>+B#style.visibility<*/,%(D' =-o6Bdissolve*<3<*/,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*,,D' =1:Bvisible*o3>+B#style.visibility<*,,%(D' =-o6Bdissolve*<3<*,,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*0,D' =1:Bvisible*o3>+B#style.visibility<*0,%(D' =-o6Bdissolve*<3<*0,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*-,D' =1:Bvisible*o3>+B#style.visibility<*-,%(D' =-o6Bdissolve*<3<*-,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*.,D' =1:Bvisible*o3>+B#style.visibility<*.,%(D' =-o6Bdissolve*<3<*.,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*1,D' =1:Bvisible*o3>+B#style.visibility<*1,%(D' =-o6Bdissolve*<3<*1,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*3,D' =1:Bvisible*o3>+B#style.visibility<*3,%(D' =-o6Bdissolve*<3<*3,D' =%(D' =%(DW' =4@BB BB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*2,D' =1:Bvisible*o3>+B#style.visibility<*2,%(D' =-o6Bdissolve*<3<*2,+.  UM)0(  0r 0 S T  `   r 0 S (        0 T\  ?"p( ,$D 0 Al Ycp #0Ycp,$D 0 0 T,x  ?"YP p @  0 Tԕ  ?"* Pcp <    0 Tp  ?"y P@ p 9. 0B Z8c?"X P 0 Z8c?"X  P 0 Z8c?"X GPl pF  $0pF ,$D 0  0 T8  ?" F  9 0 Z8c?"p }l  p  &0p  ,$D 0 0 T6  ?"   @ 0  ` >  ?"  9E 0B Z8c?"z pG  0 Z8c?"Gp% l  v  '0 v ,$D 0  0 TA  ?" v  9 0 T8c?"% % l    (0  ,$D 0 0  `@  ?"`   93 0 Z8c?"% %` l  i  %0 i ,$D 0 0  `4I  ?" i  95 "0 Z8c?"   )0  fL 8c?"W ( ,$D 0 @Why not?  H 0 0޽h ? 0000000 000 00 000 000 0 00 000 00"0 3333,$___PPT10+;IDx' = @B D3' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-o6Bdissolve*<3<*0D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*#0%(D' =-o6Bdissolve*<3<*#0D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*$0%(D' =-o6Bdissolve*<3<*$0D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%0%(D' =-o6Bdissolve*<3<*%0D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*&0%(D' =-o6Bdissolve*<3<*&0D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*'0%(D' =-o6Bdissolve*<3<*'0D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*(0%(D' =-o6Bdissolve*<3<*(0D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)0%(D' =-o6Bdissolve*<3<*)0+p+0+0  ++0+)0  +  914(  4r 4 S Xh  `   r 4 S ,i  "   8 p 4   4  `k  ?":p% 7*p 4  `n  ?" hL(G) = {x: string of Terminals (<start symbol> x)}F5+H 4 0޽h ? 3333J  8(  8r 8 S   `    8  `T  ??  H<bool exp> T | F | NOT ( <bool exp> ) | ( <bool exp> AND <bool exp> ) | ( <bool exp> OR <bool exp> ):on   c uH 8 0޽h ? 3333s   @(  @r @ S 8  `   r @ S ܕ   `    @  `,q  ?"! h,$D 0 D   $ @  `  ?"!{h ,$D 0 RT, F, AND, OR, NOT, (, ) @  `  ?"n  ,$D 0 D     @  `  ?"n ,$D 0 ;5H @ 0޽h ? 3333 ___PPT10 +f.lD ' = @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' =-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<*@++0+@  ++0+@  ++0+@  ++0+@  +  D(  Dr D S @  `    D  `t  ?"  % @    D  `  ?"~ =NOT D  `仳  ?"~H ;( D  `  ?"~ ;) D  `,ij  ?"~ ) @    D  `4ȳ  ?"1 * x  @     D  `˳  ?"1 rx  @     D  `ʳ  ?"1 x  <OR  D  `γ  ?"1 x  ;(  D  ` ׳  ?"1 x  ;)  D  `ճ  ?" am  ;T D  `@ݳ  ?" 62 ;F D@ Z8c?"%UM ~ D@ Z8c?"%M ~ D Z8c?"%M ~ D Z8c?"%M ~ D@ Z8c?"f 1  D@ Z8c?" 1  D@ Z8c?" 1  D Z8c?" 1  D Z8c?" 61  D Z8c?"x   D@ Z8c?"x  H D 0޽h ?`DDDDDD DDD DDDD DDDDDD DDD DDD DDD DD DDD 33337  ?!7!+:H(  Hx H c $`  `    H  `  ?" ,$D 0 @   l ` 5H`,$D 0 H  `(  ?"k  @     H  `  ?"kC @     H  `  ?" kf  =AND  H  `  ?"k ;(  H  `<  ?"k` ;) HB T8c?"c k HB T8c?"_ k HB T8c?"0  k H T8c?" k H T8c?" kl yu  :Hyu ,$D 0 H  `  ?"y. u  ;T H Z8c?". l u  6Hu ,$D 0 H  `  ?". mu  @    H  `  ?". i u  @     H  `  ?". u  <OR !H  `  ?". u  ;( "H  `t  ?" . u  ;) %HB T8c?"#_.  &HB T8c?"*_.  'H T8c?"_.  (H T8c?"_& .  )H T8c?"_-. l u I  7Hu I ,$D 0 #H  `  ?" I  ;T *H Z8c?"*u + l u I  8Hu I ,$D 0 H  `h  ?" I  =NOT H  `  ?"D  I  ;( H  `  ?"' I  ;) H  `  ?"U  I  @    +H T8c?"& u   1H Z8c?"u &   2H Z8c?" u &   3H Z8c?"& u  l  I   9HI   ,$D 0 0H  `X  ?"   ;F 4H Z8c?" I H H 0޽h ? H HHHHHH HHH HH H HH HHH H!H%H HH&HH H'HHH(HH"H)HH#H*HHH+HHH1HHH2HHH3HH0H4H 3333___PPT10+Å!D' = @B D;' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*H%(D' =-o6Bdissolve*<3<*HD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*5H%(D' =-o6Bdissolve*<3<*5HD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*6H%(D' =-o6Bdissolve*<3<*6HD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*7H%(D' =-o6Bdissolve*<3<*7HD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*8H%(D' =-o6Bdissolve*<3<*8HD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*9H%(D' =-o6Bdissolve*<3<*9HD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*:H%(D' =-o6Bdissolve*<3<*:H+8+0+H  +  nfL(  Lr L S  /  @`  /  L L Tp`|  ?? B<expression> <expression> <addop> <term> | <term> <term> <term> <multop> <factor> | <factor> <factor> ( <expression> ) | <digit seqnce> <addop> + | - <multop> * | DIV | MOD <digit seqnce> <digit> <digit seqnce> | <digit> <digit> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 97$  0 0-  $$((,,00(00> >UH L 0޽h ? 3333~K  ))7;P&(  Pr P S   `   r P S d   "    P  fh 8c?"p@P j B   +l ^j 1Pj^,$D 0 P  f 8c?"  = P  f 8c?" <  P  ft 8c?"^n B    PB Z8c?"fjH  P Z8c?"H jH  P Z8c?"H jl 9z  2P9z ,$D 0  P  f 8c?"9z  <  P Z8c?"ffl z   3Pz  ,$D 0  P  f 8c?"   >   !P Z8c?"fz g  l 0   4P 0 ,$D 0 P  fh 8c?"0   D "P Z8c?"g g l D  5P D,$D 0 P  f, 8c?"D  = #P Z8c?"g g l  6P,$D 0 P  fT 8c?" ;4 $P Z8c?"ggl   z  7P z ,$D 0 P  f 8c?"  z  ;+ %P Z8c?"H I (l  z  8P z ,$D 0 P  f4 8c?" z  < P  f 8c?"pNz  >   P  f 8c?"z  >   &PB Z8c?"  'P Z8c?" (P Z8c?"*l  z  9Pz ,$D  0 P  f8 8c?"  N  >   P  f<" 8c?"   = P  f\ 8c?"{ Q  ;6 P  f( 8c?"   D )P Z8c?" z   *P Z8c?"   +PB Z8c?"   ,P Z8c?"  l {z D  :Pz {D ,$D  0 P  f`( 8c?"{ D  ;* -P Z8c?"z  ,l z ` ;Pz `,$D  0 P  f4/ 8c?" `  D P  f2 8c?" M  = P  f4 8c?"  ;2 .P Z8c?"*z *  /P Z8c?"* *  0P Z8c?"* * H P 0޽h ?OP PPPPPPPP P P P P P!P PP"PPP#PPP$PPP%PPP&PPP'PPP(PPP)PPP*PPP+P PP,P"PP-P$PP.P&PP/P(PP0P 3333c![!___PPT10;!+xL5D!' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*1P%(D' =-o6Bdissolve*<3<*1PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*7P%(D' =-o6Bdissolve*<3<*7PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*2P%(D' =-o6Bdissolve*<3<*2PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*3P%(D' =-o6Bdissolve*<3<*3PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*4P%(D' =-o6Bdissolve*<3<*4PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*5P%(D' =-o6Bdissolve*<3<*5PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*6P%(D' =-o6Bdissolve*<3<*6PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*8P%(D' =-o6Bdissolve*<3<*8PD' =%(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<*9P%(D' =-o6Bdissolve*<3<*9PD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*;P%(D' =-o6Bdissolve*<3<*;P+Q  22p@ST8 '/(  Tr T S   l cP  PTP c ,$D 0  T # lx 8c? "mv p  < T Z8c? " P v  T # l| 8c? "2   >   T  `8c? " p  T # l 8c? "c  D T  `8c? "  T # lȂ 8c? "v  = TB  `8c? "  T # lK 8c? ".   ;4 T  `8c? "  l  RT,$D 0 T # lM 8c?" <  T  `8c?"Ll  a ST a,$D 0 #T  `8c?" T # lTR 8c? "  <  T # ldU 8c? "\: >   !T # lY 8c? "a >   "TB  `8c? "  $T  `8c? "l z I LTz I,$D 0 &T  f^ 8c? "z I >   *T Z8c? "  l g0 KTg0,$D 0 /T # lc 8c? "g0 ;* 0T  `8c? "Pl 0P  JT0P ,$D 0 2T # lg 8c? "0 D 3T # lti 8c? "60  = 4T # l,W 8c? "V eP  ;2 5T  `8c? " 6T  `8c? "6 7T  `8c? "0 V @l  0  MT 0 ,$D 0 T # lƯ 8c? " 60  B     T Z8c? "  6 9T # l˯ 8c? " 6 0  ;( :T # lJ 8c? "160  ;) ;TB Z8c? "X  6    >T # l 8c? " V 6P  = ?T # lL 8c? "V P  < @TB  `8c? " 0 V  AT  `8c? " 0 V  BT  `8c? " 0 V l v P  OTP v ,$D  0 'T # l 8c? "   = (T # l 8c? "A  ;6 )T # l 8c? "v   D +T Z8c? "p   ,TB  `8c? "   -T  `8c? "   CT # l 8c? "Ev p  >   DT Z8c? "P v  l  P C p  QTP C p ,$D  0 ET # l4 8c? " v C p  ;+ FT Z8c? " P v H T 0޽h ? &TT TTT T=T TT TTTTTTTTTTTT TT"T T T#T T!T$T T&T*TCT)T+T)T'T,T'T(T-T T/T0T!T2T5T2T3T6T3T4T7T&T9T;T&T:TTATT?TBT?TCTDT >TETFT 3333xp___PPT10P+hD4' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*RT%(D' =-o6Bdissolve*<3<*RTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*ST%(D' =-o6Bdissolve*<3<*STD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*KT%(D' =-o6Bdissolve*<3<*KTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*JT%(D' =-o6Bdissolve*<3<*JTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*LT%(D' =-o6Bdissolve*<3<*LTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*MT%(D' =-o6Bdissolve*<3<*MTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*NT%(D' =-o6Bdissolve*<3<*NTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*PT%(D' =-o6Bdissolve*<3<*PTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*QT%(D' =-o6Bdissolve*<3<*QTD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*OT%(D' =-o6Bdissolve*<3<*OT+  ~v`X(  Xr X S x  p`   \ X T _  ??  <expression> <expression> <op> <expression> | ( <expression> ) | <digit seqnce> <op> + | - | * | DIV | MOD <digit seqnce> <digit> <digit seqnce> | <digit> <digit> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9V M &,'PN& > H X 0޽h ? 3333y%    P'8\$ ((  \x \ c $P0  `   x \ c $HĪ   "   l \ 8\/,$D 0 \  f& 8c?"o! f B    \ # l@Ъ 8c?" {  : \ # l`ɪ 8c?"/  B    \ # lԪ 8c?"; B     \B  `8c?"fH   \B  `8c?" fH   \  `8c?"H f  \ # lު 8c?" v  D \  `8c?" \ # l4٪ 8c?"  !  = \  `8c?"v   \ # l$ 8c?" z  ;4 \B  `8c?"   \ # l 8c?"a  v  ;+ \  `8c?"   \ # lܪ 8c?"  v  B     \ # l 8c?"J v  : !\ # l 8c?"3v  B    "\B  `8c?"  #\  `8c?" $\  `8c?"Z &\ # l 8c?"   D '\ # l4 8c?"^ ' *  ;6 )\ # lܪ 8c?"  = *\B  `8c?" v   +\  `8c?"  ,\  `8c?" '  /\ # l 8c?"  g  ;* 0\B  `8c?"v   2\ # l 8c? "V \  D 3\ # l֪ 8c? "N e  = 4\ # lL˪ 8c? "'  ;2 5\B  `8c? "Yv Z  6\  `8c? "Y Z  7\  `8c? "Z Z' H \ 0޽h ? \\ \\\ \\\ \\ \\ \\\\\\ \\\ \\"\ \ \#\ \!\$\ \&\*\&\)\+\)\'\,\ \/\0\!\2\5\2\3\6\3\4\7\ 33335-___PPT10 +jD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*8\%(D' =-o6Bdissolve*<3<*8\+     '(x(  xx x c $4D  `   x x c $D   "   8 tn/ (xC=/ x # lE 8c?"  B    x # lB 8c?" (0  : x # lM 8c?"( B    x # lP 8c?" (B B     xB Z8c?"   x  `8c?" s (  x Z8c?"    x # lU 8c?"h n  D  x  `8c?"ik x # l< 8c?"_ 8 v  = x  `8c?"k k8  x # lW 8c?"   ;2 xB  `8c?"i k  x # l`` 8c?"   ;* x  `8c?"s s  x # ld 8c?"Q  B    x # lPg 8c?"y  : x # l? 8c?"5  B    xB  `8c?"x x  `8c?" x  `8c?"  x # ll 8c?"t8 z  D x # lq 8c?"H / ;4 x # lZ 8c?"l   = xB  `8c?"w x8  x  `8c?"w x  x  `8c?"x xH   x # l|{ 8c?"^8   ;+ !xB  `8c?" 8  "x # l x 8c?" 8    D #x # lP 8c?"   = $x # l 8c?"H t / ;6 %xB  `8c?"  8  &x  `8c?"    'x  `8c?"  H H x 0޽h ? x xxx xx xx x x xxxxxxxxxxxx xxx xxx xxx xxx xxxx x!xx"x%x"x#x&x#x$x'x 3333rt07%@d/OQc 0$/]beNzS:im5Me\|zhmR6Oh+'0P< hp   ( 4@HParsing Paolo Bucci8C:\WINDOWS\Application Data\Microsoft\Templates\321.potComputing Servicesi26pMicrosoft PowerPointn D@tB@ #l$@eG:g  w  -- @ !--'-- @ !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:---- @ !#---'@BComic Sans MS-. *2 Translator Architecture&) ."System-@BComic Sans MS-.  2 ,Code.-@BComic Sans MS-. 2 T Generator.--- $nZnZ--'@BComic Sans MS-. 2 @Parser.--- $nXnX--'@BComic Sans MS-. 2 @ Tokenizer .--- $nUnU--'--8S335S5S30480--'--8U335U5U30480--'--8X335X5X30480--'--8Z335Z5Z30480--'@BComic Sans MS-. 2 G string of   .-@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)     .-1--$qBCDEGJ NRV$\+a2g9n@uG}MSY^chmquy|)6C}x(r9kHcW[]VdRjMqHvC|=82-'!u52 /%(/ 8A JRZahnty}tth]SH~>|4y*u rnjfa\XRMGB<60)#B--'v--$CBCDEGJ NRV$\+a2g9n@uG}MSY^chmquy|)6C}pdXL@|5y*uqm hc^YSMG@92+$ B----%qBCDEGJ NRV$\+a2g9n@uG}MSY^chmquy|)6C}x(r9kHcW[]VdRjMqHvC|=82-'!u52 /%(/ 8A JRZahnty}tth]SH~>|4y*u rnjfa\XRMGB<60)#B----%t--'@BComic Sans MS-. 1 2 ]V?4.-1-- @ !t---- $nXnX--'@BComic Sans MS-. 2 @Parser.-՜.+,0    $ On-screen ShowThe Ohio State Universitye{ Times New RomanComic Sans MSTahoma WingdingsSymbol321Translator ArchitectureHeres the PlanSpecifying Syntax with CFGs:Rewrite Rules for Real ConstantsFour Components of a CFGA Derivation of 5.6E10A Derivation of 5.6E10A Derivation of 5.6E10A Derivation of 5.6E10A Derivation Tree for 5.6E10 Find a Derivation Tree for 5.E3Language Generated by a CFG0Another Example: A CFG for Boolean ExpressionsCFG for Boolean Expressions:A Derivation Tree for NOT((T OR F))<Find a Derivation Tree for ((T OR NOT (F)) AND T)A Famous Context-free Grammar:Whats So Special About This CFG?Whats So Special ContinuedHow About These Rewrite Rules?New Rules ContinuedNew Rules Continued  Fonts UsedDesign Template Slide TitlesRoot EntrydO)2@Current User/SummaryInformation([<PowerPoint Document(_δ.buccibucciolo Buccig ServicesRoot EntrydO)׳PCurrent UserASummaryInformation([<PowerPoint Document(#_δ Paolo BucciPaolo Buccig Services  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ\]^_`abcdefghijklmnopqrstuvwxy{|}~Root EntrydO)Current UserSummaryInformation([<PowerPoint Document(DocumentSummaryInformation8z