<div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><div class="t m0 x0 h1 y0 ff1 fs0 fc0 sc0 ls0 ws0">Compiler Construction</div><div class="t m0 x1 h1 y1 ff1 fs0 fc0 sc0 ls0 ws0">using Flex and Bison</div><div class="t m0 x2 h2 y2 ff1 fs1 fc0 sc0 ls0 ws1">An<span class="_0 blank"></span>thon<span class="_0 blank"></span>y A. Aab<span class="_0 blank"></span>y</div><div class="t m0 x3 h3 y3 ff2 fs2 fc0 sc0 ls0 ws2">W<span class="_1 blank"></span>alla W<span class="_1 blank"></span>alla College</div><div class="t m0 x4 h3 y4 ff2 fs2 fc0 sc0 ls0 ws3">cs.ww<span class="_0 blank"></span>c.edu</div><div class="t m0 x5 h3 y5 ff2 fs2 fc0 sc0 ls0 ws3">aab<span class="_0 blank"></span>yan@ww<span class="_0 blank"></span>c.edu</div><div class="t m0 x6 h3 y6 ff2 fs2 fc0 sc0 ls0 ws2">V<span class="_1 blank"></span>ersion of April 22, 2005</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><div class="t m0 x7 h4 y7 ff3 fs3 fc0 sc0 ls0 ws4">Cop<span class="_2 blank"></span>yrigh<span class="_2 blank"></span>t <span class="v1">c</span></div><div class="t m0 x8 h5 y7 ff4 fs3 fc0 sc0 ls1">\ue00d<span class="ff3 ls0 ws5">2003 An<span class="_2 blank"></span>thon<span class="_2 blank"></span>y A. Aab<span class="_2 blank"></span>y</span></div><div class="t m0 x7 h5 y8 ff3 fs3 fc0 sc0 ls0 ws5">W<span class="_1 blank"></span>alla W<span class="_0 blank"></span>alla College</div><div class="t m0 x7 h5 y9 ff3 fs3 fc0 sc0 ls0 ws5">204 S. College Av<span class="_2 blank"></span>e.</div><div class="t m0 x7 h5 ya ff3 fs3 fc0 sc0 ls0 ws5">College Place, W<span class="_1 blank"></span>A 99324</div><div class="t m0 x7 h5 yb ff3 fs3 fc0 sc0 ls0 ws6">E-mail: aab<span class="_2 blank"></span>y<span class="_2 blank"></span>an@ww<span class="_2 blank"></span>c.edu</div><div class="t m0 x7 h5 yc ff3 fs3 fc0 sc0 ls0 ws7">LaT<span class="_1 blank"></span>eX sources av<span class="_0 blank"></span>ailable b<span class="_0 blank"></span>y request.</div><div class="t m0 x9 h5 yd ff3 fs3 fc0 sc0 ls0 ws8">This material ma<span class="_2 blank"></span>y b<span class="_3 blank"> </span>e distributed only sub<span class="_3 blank"> </span>ject to the terms and conditions</div><div class="t m0 x7 h5 ye ff3 fs3 fc0 sc0 ls0 ws9">set forth in the Op<span class="_3 blank"> </span>en Publication License, v1.0 or later (the latest version is</div><div class="t m0 x7 h5 yf ff3 fs3 fc0 sc0 ls0 ws5">presen<span class="_2 blank"></span>tly a<span class="_2 blank"></span>v<span class="_0 blank"></span>ailable at <span class="ff5 wsa">http://www.opencontent.org/openpub</span></div><div class="t m0 x9 h5 y10 ff3 fs3 fc0 sc0 ls0 wsb">This b<span class="_3 blank"> </span>o<span class="_3 blank"> </span>ok is distributed in the hop<span class="_3 blank"> </span>e it will b<span class="_3 blank"> </span>e useful, but without an<span class="_2 blank"></span>y w<span class="_2 blank"></span>ar-</div><div class="t m0 x7 h5 y11 ff3 fs3 fc0 sc0 ls0 wsc">ran<span class="_2 blank"></span>t<span class="_2 blank"></span>y;<span class="_4 blank"> </span>without ev<span class="_2 blank"></span>en the implied w<span class="_2 blank"></span>arran<span class="_0 blank"></span>ty of merc<span class="_0 blank"></span>hantabilit<span class="_0 blank"></span>y or \ufb01tness for a</div><div class="t m0 x7 h5 y12 ff3 fs3 fc0 sc0 ls0 wsd">particular<span class="_5 blank"> </span>purp ose.</div><div class="t m0 x9 h5 y13 ff3 fs3 fc0 sc0 ls0 wse">The author encourages wide distribution of this bo<span class="_3 blank"> </span>ok for p<span class="_3 blank"> </span>ersonal and com-</div><div class="t m0 x7 h5 y14 ff3 fs3 fc0 sc0 ls0 wsf">mercial use, provided the abov<span class="_0 blank"></span>e copyrigh<span class="_0 blank"></span>t notice remains intact and the method</div><div class="t m0 x7 h5 y15 ff3 fs3 fc0 sc0 ls0 ws5">adheres to the pro<span class="_2 blank"></span>visions of the Op<span class="_3 blank"> </span>en Publication Liscense lo<span class="_3 blank"> </span>cated at</div><div class="t m0 x7 h6 y16 ff5 fs3 fc0 sc0 ls0 wsa">http://www.opencontent.org/openpub</div><div class="t m0 x9 h5 y17 ff3 fs3 fc0 sc0 ls0 ws10">In summary<span class="_1 blank"></span>, you ma<span class="_0 blank"></span>y copy and distribute this bo<span class="_3 blank"> </span>ok free of charge or for a</div><div class="t m0 x7 h5 y18 ff3 fs3 fc0 sc0 ls0 ws11">pro\ufb01t.<span class="_6 blank"> </span>No explicit p<span class="_3 blank"> </span>ermission is required from the author for reproduction of</div><div class="t m0 x7 h5 y19 ff3 fs3 fc0 sc0 ls0 ws5">this b<span class="_3 blank"> </span>o<span class="_3 blank"> </span>ok in an<span class="_2 blank"></span>y medium, ph<span class="_2 blank"></span>ysical or electronic.</div><div class="t m0 x9 h5 y1a ff3 fs3 fc0 sc0 ls0 ws12">Note, deriv<span class="_0 blank"></span>ative w<span class="_0 blank"></span>orks and translations of this do<span class="_3 blank"> </span>cument m<span class="_0 blank"></span>ust include the</div><div class="t m0 x7 h5 y1b ff3 fs3 fc0 sc0 ls0 ws5">original cop<span class="_2 blank"></span>yrigh<span class="_2 blank"></span>t notice m<span class="_2 blank"></span>ust remain in<span class="_2 blank"></span>tact.</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><div class="t m0 xa h5 y1c ff3 fs3 fc0 sc0 ls0 ws5">T<span class="_1 blank"></span>o Pamela Aab<span class="_0 blank"></span>y</div><div class="t m0 xb h5 y1d ff3 fs3 fc0 sc0 ls0">i</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><div class="t m0 xc h5 y1d ff3 fs3 fc0 sc0 ls0">ii</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img fetchpriority="low" loading="lazy" class="bi xd y1e w1 h7" alt="" src="https://files.passeidireto.com/50c69933-84d8-45d3-b095-8f8c9bd76025/bg5.png"><div class="t m0 xe h1 y1f ff1 fs0 fc0 sc0 ls0 ws14">Con<span class="_1 blank"></span>ten<span class="_0 blank"></span>ts</div><div class="t m0 xe h5 y20 ff6 fs3 fc0 sc0 ls0 ws15">1<span class="_7 blank"> </span>In<span class="_0 blank"></span>tro duction<span class="_8 blank"> </span>1</div><div class="t m0 xe h5 y21 ff6 fs3 fc0 sc0 ls0 ws16">2<span class="_7 blank"> </span>The P<span class="_0 blank"></span>arser<span class="_9 blank"> </span>5</div><div class="t m0 xe h5 y22 ff6 fs3 fc0 sc0 ls0 ws16">3<span class="_7 blank"> </span>The Scanner<span class="_8 blank"> </span>9</div><div class="t m0 xe h5 y23 ff6 fs3 fc0 sc0 ls0 ws16">4<span class="_7 blank"> </span>The Con<span class="_0 blank"></span>text<span class="_a blank"> </span>13</div><div class="t m0 xe h5 y24 ff6 fs3 fc0 sc0 ls0 ws17">5 Optimization<span class="_b blank"> </span>19</div><div class="t m0 xe h5 y17 ff6 fs3 fc0 sc0 ls0 ws18">6<span class="_7 blank"> </span>Virtual Mac<span class="_0 blank"></span>hines<span class="_c blank"> </span>21</div><div class="t m0 xe h5 y25 ff6 fs3 fc0 sc0 ls0 ws15">7<span class="_7 blank"> </span>Co de<span class="_d blank"> </span>Generation<span class="_e blank"> </span>27</div><div class="t m0 xe h5 y26 ff6 fs3 fc0 sc0 ls0 ws18">8<span class="_7 blank"> </span>P<span class="_0 blank"></span>eephole Optimizati<span class="_3 blank"> </span>on<span class="_f blank"> </span>37</div><div class="t m0 xe h5 y27 ff6 fs3 fc0 sc0 ls0 ws17">9 Exercises<span class="_10 blank"> </span>39</div><div class="t m0 xe h5 y28 ff6 fs3 fc0 sc0 ls0 ws16">A<span class="_6 blank"> </span>Simple - The complete implementation<span class="_11 blank"> </span>47</div><div class="t m0 xf h5 y29 ff3 fs3 fc0 sc0 ls0 ws19">A.1<span class="_12 blank"> </span>The<span class="_5 blank"> </span>parser:<span class="_13 blank"> </span>Simple.y<span class="_13 blank"> </span>. . . . . . . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>47</div><div class="t m0 xf h5 y2a ff3 fs3 fc0 sc0 ls0 ws19">A.2<span class="_12 blank"> </span>Directions<span class="_15 blank"> </span>. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>51</div><div class="t m0 xf h5 y2b ff3 fs3 fc0 sc0 ls0 ws19">A.3<span class="_12 blank"> </span>The<span class="_5 blank"> </span>scanner:<span class="_13 blank"> </span>Simple.lex<span class="_16 blank"> </span>. . . . . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>52</div><div class="t m0 xf h5 y2c ff3 fs3 fc0 sc0 ls0 ws19">A.4<span class="_12 blank"> </span>The<span class="_5 blank"> </span>sym<span class="_2 blank"></span>b<span class="_3 blank"> </span>ol<span class="_5 blank"> </span>table:<span class="_13 blank"> </span>ST.h<span class="_12 blank"> </span>. . . . . . . . . . . . . . . . . .<span class="_17 blank"> </span>. . . . .<span class="_14 blank"> </span>53</div><div class="t m0 xf h5 y2d ff3 fs3 fc0 sc0 ls0 ws19">A.5<span class="_12 blank"> </span>The<span class="_5 blank"> </span>co<span class="_3 blank"> </span>de<span class="_5 blank"> </span>generator:<span class="_13 blank"> </span>CG.h<span class="_13 blank"> </span>. . . . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>54</div><div class="t m0 xf h5 y2e ff3 fs3 fc0 sc0 ls0 ws19">A.6<span class="_12 blank"> </span>The<span class="_5 blank"> </span>stac<span class="_2 blank"></span>k<span class="_5 blank"> </span>machine:<span class="_13 blank"> </span>S<span class="_2 blank"></span>M.h<span class="_12 blank"> </span>. . . . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>55</div><div class="t m0 xf h5 y2f ff3 fs3 fc0 sc0 ls0 ws19">A.7<span class="_12 blank"> </span>Sample<span class="_5 blank"> </span>program:<span class="_13 blank"> </span>test<span class="_d blank"> </span>simple<span class="_18 blank"> </span>. . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>57</div><div class="t m0 xe h5 y30 ff6 fs3 fc0 sc0 ls0 ws1a">B Lex/Flex<span class="_19 blank"> </span>59</div><div class="t m0 xf h5 y31 ff3 fs3 fc0 sc0 ls0 ws19">B.1<span class="_1a blank"> </span>Lex/Flex<span class="_5 blank"> </span>Examples<span class="_5 blank"> </span>. . . . . . . . . . . . . . . . . . . . . . . . . .<span class="_14 blank"> </span>59</div><div class="t m0 xf h5 y32 ff3 fs3 fc0 sc0 ls0 ws19">B.2<span class="_1a blank"> </span>The<span class="_5 blank"> </span>Lex/Flex<span class="_5 blank"> </span>Input<span class="_5 blank"> </span>File<span class="_13 blank"> </span>. . . . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>61</div><div class="t m0 xf h5 y33 ff3 fs3 fc0 sc0 ls0 ws19">B.3<span class="_1a blank"> </span>The<span class="_5 blank"> </span>Generated<span class="_5 blank"> </span>Scanner<span class="_18 blank"> </span>. . . . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>66</div><div class="t m0 xf h5 y34 ff3 fs3 fc0 sc0 ls0 ws19">B.4<span class="_1a blank"> </span>In<span class="_2 blank"></span>terfacing<span class="_5 blank"> </span>with<span class="_5 blank"> </span>Y<span class="_1 blank"></span>acc/Bison . . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>67</div><div class="t m0 x10 h5 y1d ff3 fs3 fc0 sc0 ls0">iii</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf6" class="pf w0 h0" data-page-no="6"><div class="pc pc6 w0 h0"><div class="t m0 x7 h5 y7 ff6 fs3 fc0 sc0 ls0 ws1b">C Y<span class="_1 blank"></span>acc/Bison<span class="_8 blank"> </span>69</div><div class="t m0 x9 h5 y8 ff3 fs3 fc0 sc0 ls0 ws19">C.1<span class="_1a blank"> </span>An<span class="_5 blank"> </span>Ov<span class="_0 blank"></span>erview<span class="_1c blank"> </span>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>69</div><div class="t m0 x9 h5 y9 ff3 fs3 fc0 sc0 ls0 ws19">C.2<span class="_1a blank"> </span>A<span class="_5 blank"> </span>Y<span class="_1 blank"></span>acc/Bison<span class="_5 blank"> </span>Example<span class="_1d blank"> </span>. . . . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>71</div><div class="t m0 x9 h5 ya ff3 fs3 fc0 sc0 ls0 ws19">C.3<span class="_1a blank"> </span>The<span class="_5 blank"> </span>Y<span class="_1 blank"></span>acc/Bison<span class="_5 blank"> </span>Input<span class="_5 blank"> </span>File<span class="_1d blank"> </span>. . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>72</div><div class="t m0 x9 h5 yb ff3 fs3 fc0 sc0 ls0 ws19">C.4<span class="_1a blank"> </span>Y<span class="_1 blank"></span>acc/Bison<span class="_5 blank"> </span>Output:<span class="_13 blank"> </span>the<span class="_5 blank"> </span>P<span class="_2 blank"></span>arser<span class="_5 blank"> </span>File<span class="_7 blank"> </span>. . . . . . . . . . . . . . . .<span class="_1b blank"> </span>86</div><div class="t m0 x9 h5 yc ff3 fs3 fc0 sc0 ls0 ws19">C.5<span class="_1a blank"> </span>P<span class="_0 blank"></span>arser<span class="_5 blank"> </span>C-Language<span class="_5 blank"> </span>Interface<span class="_1e blank"> </span>. . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>87</div><div class="t m0 x9 h5 y35 ff3 fs3 fc0 sc0 ls0 ws19">C.6<span class="_1a blank"> </span>Debugging<span class="_5 blank"> </span>Y<span class="_1 blank"></span>our<span class="_5 blank"> </span>P<span class="_2 blank"></span>arser<span class="_1d blank"> </span>. . . . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>90</div><div class="t m0 x9 h5 yd ff3 fs3 fc0 sc0 ls0 ws19">C.7<span class="_1a blank"> </span>Stages<span class="_5 blank"> </span>in<span class="_5 blank"> </span>Using<span class="_5 blank"> </span>Y<span class="_1 blank"></span>acc/Bison<span class="_16 blank"> </span>. . . . . . . . . . . . . . . . . . . . .<span class="_1b blank"> </span>95</div><div class="t m0 x11 h5 y1d ff3 fs3 fc0 sc0 ls0">iv</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf7" class="pf w0 h0" data-page-no="7"><div class="pc pc7 w0 h0"><div class="t m0 xe h8 y36 ff1 fs4 fc0 sc0 ls0 ws1c">Chapter 1</div><div class="t m0 xe h1 y37 ff1 fs0 fc0 sc0 ls0 ws1d">In<span class="_1 blank"></span>tro duction</div><div class="t m0 xe h5 y38 ff3 fs3 fc0 sc0 ls0 ws1e">A language translator is a program whic<span class="_0 blank"></span>h translates programs written in a source</div><div class="t m0 xe h5 y39 ff3 fs3 fc0 sc0 ls0 ws1f">language in<span class="_2 blank"></span>to an equiv<span class="_0 blank"></span>alen<span class="_2 blank"></span>t program in an ob<span class="_1f blank"> </span>ject language.<span class="_20 blank"> </span>The source language</div><div class="t m0 xe h5 y3a ff3 fs3 fc0 sc0 ls0 ws20">is usually a high-lev<span class="_2 blank"></span>el programming language and the ob<span class="_3 blank"> </span>ject language is usually</div><div class="t m0 xe h5 y3b ff3 fs3 fc0 sc0 ls0 ws21">the mac<span class="_2 blank"></span>hine language of an actual computer.<span class="_20 blank"> </span>F<span class="_1 blank"></span>rom the pragmatic p<span class="_3 blank"> </span>oint of view,</div><div class="t m0 xe h5 y3c ff3 fs3 fc0 sc0 ls0 ws22">the translator de\ufb01nes the seman<span class="_2 blank"></span>tics of the programming language, it transforms</div><div class="t m0 xe h5 y3d ff3 fs3 fc0 sc0 ls0 ws23">op<span class="_3 blank"> </span>erations sp<span class="_3 blank"> </span>eci\ufb01ed b<span class="_2 blank"></span>y the syn<span class="_2 blank"></span>tax in<span class="_2 blank"></span>to op<span class="_3 blank"> </span>erations of the computational mo<span class="_3 blank"> </span>del to</div><div class="t m0 xe h5 y3e ff3 fs3 fc0 sc0 ls0 ws24">some real or virtual mac<span class="_2 blank"></span>hine.<span class="_d blank"> </span>T<span class="_3 blank"> </span>his c<span class="_2 blank"></span>hapter sho<span class="_2 blank"></span>ws ho<span class="_2 blank"></span>w con<span class="_2 blank"></span>text-free grammars are</div><div class="t m0 xe h5 y3f ff3 fs3 fc0 sc0 ls0 ws25">used in the construction of language translators.<span class="_20 blank"> </span>Since the translation is guided</div><div class="t m0 xe h5 y40 ff3 fs3 fc0 sc0 ls0 ws26">b<span class="_2 blank"></span>y the syn<span class="_2 blank"></span>tax of the source language, the translation is said to b<span class="_3 blank"> </span>e <span class="ff7 wsa">syntax-dir<span class="_0 blank"></span>e<span class="_0 blank"></span>cte<span class="_2 blank"></span>d<span class="ff3">.</span></span></div><div class="t m0 xf h5 y41 ff3 fs3 fc0 sc0 ls2">A<span class="ff7 ls0 ws27">c<span class="_0 blank"></span>ompiler <span class="ff3 ws28">is a translator whose source language is a high-lev<span class="_2 blank"></span>el language and</span></span></div><div class="t m0 xe h5 y42 ff3 fs3 fc0 sc0 ls0 ws7">whose ob<span class="_1f blank"> </span>ject language is close to the machine langu<span class="_2 blank"></span>age of an actual computer.</div><div class="t m0 xe h5 y43 ff3 fs3 fc0 sc0 ls0 ws29">The t<span class="_2 blank"></span>ypical compiler consists of several p<span class="_2 blank"></span>hases each of whic<span class="_0 blank"></span>h passes its output</div><div class="t m0 xe h5 y44 ff3 fs3 fc0 sc0 ls0 ws5">to the next phase</div><div class="t m0 xf h5 y45 ff4 fs3 fc0 sc0 ls3">\u2022<span class="ff3 ls0 ws2a">The <span class="ff7 ws2b">lexic<span class="_0 blank"></span>al<span class="_5 blank"> </span>phase <span class="ff3 ws2c">(scanner) groups characters in<span class="_0 blank"></span>to lexical units or tokens.</span></span></span></div><div class="t m0 x12 h5 y46 ff3 fs3 fc0 sc0 ls0 ws2d">The input to the lexical phase is a c<span class="_0 blank"></span>haracter stream.<span class="_1a blank"> </span>The output is a</div><div class="t m0 x12 h5 y47 ff3 fs3 fc0 sc0 ls0 ws2e">stream of tok<span class="_2 blank"></span>ens.<span class="_20 blank"> </span>Regular expressions are used to de\ufb01ne the tokens recog-</div><div class="t m0 x12 h5 y48 ff3 fs3 fc0 sc0 ls0 ws2f">nized b<span class="_2 blank"></span>y a scanner (or lexical analyzer).<span class="_20 blank"> </span>The scanner is implemented as a</div><div class="t m0 x12 h5 y49 ff3 fs3 fc0 sc0 ls0 ws5">\ufb01nite state mac<span class="_2 blank"></span>hine.</div><div class="t m0 x12 h5 y4a ff3 fs3 fc0 sc0 ls0 ws30">Lex and Flex are tools for generating scanners:<span class="_13 blank"> </span>programs which recognize</div><div class="t m0 x12 h5 y4b ff3 fs3 fc0 sc0 ls0 ws31">lexical patterns in text.<span class="_6 blank"> </span>Flex is a faster version of Lex.<span class="_6 blank"> </span>In this chapter</div><div class="t m0 x12 h5 y4c ff3 fs3 fc0 sc0 ls0 ws32">Lex/Flex refers to either of the tools.<span class="_1a blank"> </span>The app<span class="_3 blank"> </span>endix on Lex/Flex is a</div><div class="t m0 x12 h5 y4d ff3 fs3 fc0 sc0 ls0 ws5">condensation of the man<span class="_2 blank"></span>ual page \u201c\ufb02exdo<span class="_3 blank"> </span>c\u201d b<span class="_2 blank"></span>y V<span class="_1 blank"></span>ern Paxon.</div><div class="t m0 xf h5 y4e ff4 fs3 fc0 sc0 ls3">\u2022<span class="ff3 ls0 ws33">The <span class="ff7 ws34">p<span class="_0 blank"></span>arser <span class="ff3 ws35">groups tokens in<span class="_0 blank"></span>to syn<span class="_2 blank"></span>tactical units.<span class="_13 blank"> </span>The output of the parser</span></span></span></div><div class="t m0 x12 h5 y4f ff3 fs3 fc0 sc0 ls0 ws36">is a parse tree represen<span class="_2 blank"></span>tation of the program.<span class="_13 blank"> </span>Con<span class="_0 blank"></span>text-free grammars are</div><div class="t m0 x12 h5 y50 ff3 fs3 fc0 sc0 ls0 ws37">used to de\ufb01ne the program structure recognized b<span class="_0 blank"></span>y a parser.<span class="_4 blank"> </span>The parser</div><div class="t m0 x12 h5 y51 ff3 fs3 fc0 sc0 ls0 ws5">is implemen<span class="_2 blank"></span>ted as a push-do<span class="_2 blank"></span>wn automata.</div><div class="t m0 x13 h5 y1d ff3 fs3 fc0 sc0 ls0">1</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf8" class="pf w0 h0" data-page-no="8"><div class="pc pc8 w0 h0"><div class="t m0 x14 h5 y7 ff3 fs3 fc0 sc0 ls0 ws38">Y<span class="_1 blank"></span>acc and Bison are to<span class="_3 blank"> </span>ols for generating parsers:<span class="_20 blank"> </span>programs which recognize</div><div class="t m0 x14 h5 y8 ff3 fs3 fc0 sc0 ls0 ws39">the structure grammatical structure of programs.<span class="_20 blank"> </span>Bison is a faster version</div><div class="t m0 x14 h5 y9 ff3 fs3 fc0 sc0 ls0 ws3a">of Y<span class="_1 blank"></span>acc.<span class="_15 blank"> </span>In this chapter, Y<span class="_1 blank"></span>acc/Bison refers to either of these to<span class="_3 blank"> </span>ols.<span class="_21 blank"> </span>The</div><div class="t m0 x14 h5 ya ff3 fs3 fc0 sc0 ls0 ws3b">sections on Y<span class="_1 blank"></span>acc/Bison are a condensation and extension of the do<span class="_3 blank"> </span>cument</div><div class="t m0 x14 h5 yb ff3 fs3 fc0 sc0 ls0 ws3c">\u201cBISON the Y<span class="_1 blank"></span>acc-compatible Parser Generator\u201d b<span class="_0 blank"></span>y Charles Donnelly and</div><div class="t m0 x14 h5 yc ff3 fs3 fc0 sc0 ls0 ws5">Ric<span class="_2 blank"></span>hard Stallman.</div><div class="t m0 x9 h5 y52 ff4 fs3 fc0 sc0 ls3">\u2022<span class="ff3 ls0 ws3d">The <span class="ff7 ws3e">semantic analysis phase </span><span class="ws3f">anal<span class="_2 blank"></span>yzes the parse tree for con<span class="_2 blank"></span>text-sensitiv<span class="_2 blank"></span>e</span></span></div><div class="t m0 x14 h5 y53 ff3 fs3 fc0 sc0 ls0 wse">information often called the <span class="ff7 wsb">static semantics</span><span class="ws40">.<span class="_20 blank"> </span>The output of the semantic</span></div><div class="t m0 x14 h5 y54 ff3 fs3 fc0 sc0 ls0 ws41">analysis phase is an annotated parse tree.<span class="_15 blank"> </span>Attribute grammars are used</div><div class="t m0 x14 h5 y55 ff3 fs3 fc0 sc0 ls0 ws5">to describ<span class="_3 blank"> </span>e the static semantics of a program.</div><div class="t m0 x14 h5 y56 ff3 fs3 fc0 sc0 ls0 ws42">This phase is often com<span class="_2 blank"></span>bined with the parser.<span class="_16 blank"> </span>During the parse,<span class="_13 blank"> </span>infor-</div><div class="t m0 x14 h5 y57 ff3 fs3 fc0 sc0 ls0 ws43">mation concerning v<span class="_0 blank"></span>ariables and other ob<span class="_1f blank"> </span>jects is stored in a <span class="ff7 ws29">symb<span class="_0 blank"></span>ol table<span class="ff3">.</span></span></div><div class="t m0 x14 h5 y58 ff3 fs3 fc0 sc0 ls0 ws5">The information is utilized to p<span class="_3 blank"> </span>erform the con<span class="_2 blank"></span>text-sensitiv<span class="_2 blank"></span>e c<span class="_2 blank"></span>hec<span class="_2 blank"></span>king.</div><div class="t m0 x9 h5 y59 ff4 fs3 fc0 sc0 ls3">\u2022<span class="ff3 ls0 ws44">The <span class="ff7 ws45">optimizer </span><span class="ws46">applies seman<span class="_2 blank"></span>tics preserving transformations to the anno-</span></span></div><div class="t m0 x14 h5 y5a ff3 fs3 fc0 sc0 ls0 ws47">tated parse tree to simplify the structure of the tree and to facilitate the</div><div class="t m0 x14 h5 y5b ff3 fs3 fc0 sc0 ls0 ws5">generation of more e\ufb03cien<span class="_2 blank"></span>t co<span class="_3 blank"> </span>de.</div><div class="t m0 x9 h5 y5c ff4 fs3 fc0 sc0 ls3">\u2022<span class="ff3 ls0 ws48">The <span class="ff7 ws49">c<span class="_0 blank"></span>o<span class="_0 blank"></span>de gener<span class="_2 blank"></span>ator <span class="ff3 ws4a">transforms the simpli\ufb01ed annotated parse tree in<span class="_2 blank"></span>to</span></span></span></div><div class="t m0 x14 h5 y5d ff3 fs3 fc0 sc0 ls0 ws21">ob<span class="_1f blank"> </span>ject co<span class="_3 blank"> </span>de using rules whic<span class="_2 blank"></span>h denote the seman<span class="_0 blank"></span>tics of the source language.</div><div class="t m0 x14 h5 y5e ff3 fs3 fc0 sc0 ls0 ws5">The co<span class="_3 blank"> </span>de generator ma<span class="_2 blank"></span>y b<span class="_3 blank"> </span>e integrated with th<span class="_2 blank"></span>e parser.</div><div class="t m0 x9 h5 y5f ff4 fs3 fc0 sc0 ls3">\u2022<span class="ff3 ls0 ws4b">The <span class="ff7 ws4c">p<span class="_0 blank"></span>e<span class="_0 blank"></span>ep-hole <span class="ff3 ws35">optimizer examines the ob<span class="_1f blank"> </span>ject co<span class="_3 blank"> </span>de, a few instructions at a</span></span></span></div><div class="t m0 x14 h5 y60 ff3 fs3 fc0 sc0 ls0 ws7">time, and attempts to do mac<span class="_0 blank"></span>hine dep<span class="_3 blank"> </span>endent code improv<span class="_0 blank"></span>ements.</div><div class="t m0 x9 h5 y61 ff3 fs3 fc0 sc0 ls0 ws10">In con<span class="_2 blank"></span>trast with compilers an <span class="ff7 ws4d">interpr<span class="_0 blank"></span>eter <span class="ff3 ws8">is a program which sim<span class="_0 blank"></span>ulates the</span></span></div><div class="t m0 x7 h5 y62 ff3 fs3 fc0 sc0 ls0 ws4e">execution of programs written in a source language.<span class="_4 blank"> </span>Interpreters ma<span class="_0 blank"></span>y b<span class="_3 blank"> </span>e used</div><div class="t m0 x7 h5 y63 ff3 fs3 fc0 sc0 ls0 ws4f">either at the source program lev<span class="_2 blank"></span>el or an interpr<span class="_2 blank"></span>eter may be used it interpret an</div><div class="t m0 x7 h5 y64 ff3 fs3 fc0 sc0 ls0 ws50">ob<span class="_1f blank"> </span>ject co<span class="_3 blank"> </span>de for an idealized machine.<span class="_d blank"> </span>This is the case when a compiler generates</div><div class="t m0 x7 h5 y65 ff3 fs3 fc0 sc0 ls0 ws51">co<span class="_3 blank"> </span>de for an idealized mac<span class="_2 blank"></span>hine whose arc<span class="_2 blank"></span>hitecture more closely resem<span class="_2 blank"></span>bles the</div><div class="t m0 x7 h5 y66 ff3 fs3 fc0 sc0 ls0 wsd">source<span class="_5 blank"> </span>co de.</div><div class="t m0 x9 h5 y67 ff3 fs3 fc0 sc0 ls0 ws52">There are sev<span class="_2 blank"></span>eral other t<span class="_2 blank"></span>yp<span class="_3 blank"> </span>es of translators that are often used in conjunction</div><div class="t m0 x7 h5 y68 ff3 fs3 fc0 sc0 ls0 ws53">with a compiler to facilitate the execution of programs.<span class="_18 blank"> </span>An <span class="ff7 ws54">assembler </span>is a</div><div class="t m0 x7 h5 y69 ff3 fs3 fc0 sc0 ls0 ws55">translator whose source language (an assem<span class="_2 blank"></span>bly language) represen<span class="_0 blank"></span>ts a one-to-one</div><div class="t m0 x7 h5 y6a ff3 fs3 fc0 sc0 ls0 ws56">transliteration of the ob<span class="_3 blank"> </span>ject machine code.<span class="_15 blank"> </span>Some compilers generate assembly</div><div class="t m0 x7 h5 y6b ff3 fs3 fc0 sc0 ls0 ws4a">co<span class="_3 blank"> </span>de whic<span class="_2 blank"></span>h is then assembled in<span class="_0 blank"></span>to machine code by an assem<span class="_0 blank"></span>bler.<span class="_1a blank"> </span>A <span class="ff7 wsa">lo<span class="_0 blank"></span>ader</span></div><div class="t m0 x7 h5 y6c ff3 fs3 fc0 sc0 ls0 ws41">is a translator whose source and ob<span class="_3 blank"> </span>ject languages are machine language.<span class="_15 blank"> </span>The</div><div class="t m0 x7 h5 y6d ff3 fs3 fc0 sc0 ls0 ws55">source language programs con<span class="_2 blank"></span>tain tables of data spe<span class="_3 blank"> </span>cifying points in the program</div><div class="t m0 x7 h5 y6e ff3 fs3 fc0 sc0 ls0 ws57">whic<span class="_2 blank"></span>h m<span class="_2 blank"></span>ust b<span class="_3 blank"> </span>e mo<span class="_3 blank"> </span>di\ufb01ed if the program is to b<span class="_3 blank"> </span>e executed.<span class="_21 blank"> </span>A <span class="ff7 ws58">link<span class="_20 blank"> </span>e<span class="_0 blank"></span>ditor <span class="ff3 wsa">takes</span></span></div><div class="t m0 x7 h5 y6f ff3 fs3 fc0 sc0 ls0 ws59">collections of executable programs and links them together for actual execution.</div><div class="t m0 x7 h5 y70 ff3 fs3 fc0 sc0 ls4">A<span class="ff7 ls0 ws5a">pr<span class="_0 blank"></span>epr<span class="_0 blank"></span>o<span class="_0 blank"></span>c<span class="_0 blank"></span>essor <span class="ff3 ws6">is a translator whose source language is an extended form of</span></span></div><div class="t m0 x7 h5 y71 ff3 fs3 fc0 sc0 ls0 ws3b">some high-lev<span class="_2 blank"></span>el language and whose ob<span class="_1f blank"> </span>ject language is the standard form of the</div><div class="t m0 x7 h5 y72 ff3 fs3 fc0 sc0 ls0 ws5">high-lev<span class="_2 blank"></span>el language.</div><div class="t m0 x9 h5 y50 ff3 fs3 fc0 sc0 ls0 ws26">F<span class="_1 blank"></span>or illustration purp<span class="_3 blank"> </span>oses,<span class="_1e blank"> </span>w<span class="_0 blank"></span>e will construct a compiler for a simple imp<span class="_3 blank"> </span>erative</div><div class="t m0 x7 h5 y51 ff3 fs3 fc0 sc0 ls0 ws5b">programming language called <span class="ff8 wsa">Simple</span><span class="ws5c">.<span class="_15 blank"> </span>The context-free grammar for Simple is</span></div><div class="t m0 xc h5 y1d ff3 fs3 fc0 sc0 ls0">2</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pf9" class="pf w0 h0" data-page-no="9"><div class="pc pc9 w0 h0"><img fetchpriority="low" loading="lazy" class="bi x0 y73 w2 h9" alt="" src="https://files.passeidireto.com/50c69933-84d8-45d3-b095-8f8c9bd76025/bg9.png"><div class="t m0 x12 ha y74 ff9 fs5 fc0 sc0 ls0 ws5d">program ::= LET [ decla<span class="_0 blank"></span>rations ] IN command<span class="_5 blank"> </span>sequence END</div><div class="t m0 x12 ha y75 ff9 fs5 fc0 sc0 ls0 ws5d">declarations ::= INTEGER [ id seq ] IDENTIFIER .</div><div class="t m0 x12 ha y76 ff9 fs5 fc0 sc0 ls0 ws5d">id seq ::= id<span class="_5 blank"> </span>seq...<span class="_d blank"> </span>IDENTIFIER ,</div><div class="t m0 x12 ha y77 ff9 fs5 fc0 sc0 ls0 ws5d">command sequence ::= command...<span class="_d blank"> </span>command</div><div class="t m0 x12 ha y78 ff9 fs5 fc0 sc0 ls0 ws5d">command ::= SKIP ;</div><div class="t m0 x15 ha y79 ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws5e">IDENTIFIER := expression ;</span></div><div class="t m0 x15 ha y7a ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws5d">IF exp THEN command sequence ELSE command<span class="_5 blank"> </span>sequence FI ;</span></div><div class="t m0 x15 ha y7b ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws5d">WHILE exp DO command sequence END ;</span></div><div class="t m0 x15 ha y7c ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws5d">READ IDENTIFIER ;</span></div><div class="t m0 x15 ha y7d ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws5e">WRITE expression ;</span></div><div class="t m0 x12 ha y7e ff9 fs5 fc0 sc0 ls0 ws5f">expression ::= NUMBER <span class="ffa ls5">|</span><span class="ws60">IDENTIFIER <span class="ffa ls5">|</span><span class="ws5d">\u2019(\u2019 exp<span class="_0 blank"></span>ression \u2019)\u2019</span></span></div><div class="t m0 x9 ha y7f ffa fs5 fc0 sc0 ls6">|<span class="ff9 ls0 ws61">expression <span class="ffb ls7">+</span>exp<span class="_0 blank"></span>ression <span class="ffa ls5">|</span>expression <span class="ffa ls7">\u2212</span><span class="ws62">exp<span class="_0 blank"></span>ression</span></span></div><div class="t m0 x9 ha y80 ffa fs5 fc0 sc0 ls6">|<span class="ff9 ls0 ws61">expression </span><span class="ls8">\u2217<span class="ff9 ls0 ws61">exp<span class="_0 blank"></span>ression <span class="ffa ls5">|</span>expression <span class="ffc ls8">/</span><span class="ws62">exp<span class="_0 blank"></span>ression</span></span></span></div><div class="t m0 x9 ha y81 ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws5d">expression \u02c6<span class="_17 blank"> </span>expression</span></div><div class="t m0 x9 ha y82 ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws61">expression <span class="ffb ls7">=</span><span class="ws62">exp<span class="_0 blank"></span>ression</span></span></div><div class="t m0 x9 ha y83 ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws61">expression <span class="ffc ls7"><</span><span class="ws62">exp<span class="_0 blank"></span>ression</span></span></div><div class="t m0 x9 ha y84 ffa fs5 fc0 sc0 ls5">|<span class="ff9 ls0 ws61">expression <span class="ffc ls7">></span><span class="ws62">exp<span class="_0 blank"></span>ression</span></span></div><div class="t m0 x16 h5 y85 ff3 fs3 fc0 sc0 ls0 ws5">Figure 1.1:<span class="_13 blank"> </span>Simple</div><div class="t m0 xe h5 y86 ff3 fs3 fc0 sc0 ls0 ws63">giv<span class="_2 blank"></span>en in Figure 1.1 where the non-terminal sym<span class="_2 blank"></span>b<span class="_3 blank"> </span>ols are giv<span class="_2 blank"></span>en in all lo<span class="_2 blank"></span>w<span class="_2 blank"></span>er case,</div><div class="t m0 xe h5 y87 ff3 fs3 fc0 sc0 ls0 ws64">the terminal sym<span class="_2 blank"></span>b<span class="_3 blank"> </span>ols are giv<span class="_2 blank"></span>en in all caps or as literal sym<span class="_0 blank"></span>b<span class="_3 blank"> </span>ols and, where the</div><div class="t m0 xe h5 y88 ff3 fs3 fc0 sc0 ls0 ws47">literal sym<span class="_2 blank"></span>b<span class="_3 blank"> </span>ols con\ufb02ict with the meta sym<span class="_2 blank"></span>b<span class="_3 blank"> </span>ols of the EBNF, they are enclosed</div><div class="t m0 xe h5 y89 ff3 fs3 fc0 sc0 ls0 ws65">with single quotes.<span class="_1c blank"> </span>The start symbol is <span class="ff8 wsa">program</span><span class="ws66">.<span class="_1c blank"> </span>While the grammar uses</span></div><div class="t m0 xe h5 y8a ff3 fs3 fc0 sc0 ls0 ws67">upp<span class="_3 blank"> </span>er-case to high-ligh<span class="_2 blank"></span>t terminal sym<span class="_2 blank"></span>b<span class="_3 blank"> </span>ols, they are to b<span class="_3 blank"> </span>e implemented in lo<span class="_0 blank"></span>wer</div><div class="t m0 xe h5 y8b ff3 fs3 fc0 sc0 ls0 wsa">case.</div><div class="t m0 xf h5 y8c ff3 fs3 fc0 sc0 ls0 ws68">There are t<span class="_2 blank"></span>w<span class="_2 blank"></span>o con<span class="_2 blank"></span>text sensitive requir<span class="_2 blank"></span>ements;<span class="_17 blank"> </span>v<span class="_0 blank"></span>ariables must be declared</div><div class="t m0 xe h5 y8d ff3 fs3 fc0 sc0 ls0 ws5">b<span class="_3 blank"> </span>efore they are referenced and a v<span class="_0 blank"></span>ariable ma<span class="_2 blank"></span>y b<span class="_3 blank"> </span>e declared only once.</div><div class="t m0 x13 h5 y1d ff3 fs3 fc0 sc0 ls0">3</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div> <div id="pfa" class="pf w0 h0" data-page-no="a"><div class="pc pca w0 h0"><div class="t m0 xc h5 y1d ff3 fs3 fc0 sc0 ls0">4</div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div>