home *** CD-ROM | disk | FTP | other *** search
/ Power Programming / powerprogramming1994.iso / progtool / turbopas / tutorpas.arc / TUTOR7.DOC < prev    next >
Text File  |  1988-11-07  |  81KB  |  2,595 lines

  1. OPA A
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.                             LET'S BUILD A COMPILER!
  29.  
  30.                                        By
  31.  
  32.                             Jack W. Crenshaw, Ph.D.
  33.  
  34.                                 7 November 1988
  35.  
  36.  
  37.                            Part VII: LEXICAL SCANNING
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67. PA A
  68.  
  69.  
  70.  
  71.  
  72.  
  73.        *****************************************************************
  74.        *                                                               *
  75.        *                        COPYRIGHT NOTICE                       *
  76.        *                                                               *
  77.        *   Copyright (C) 1988 Jack W. Crenshaw. All rights reserved.   *
  78.        *                                                               *
  79.        *****************************************************************
  80.  
  81.  
  82.        INTRODUCTION
  83.  
  84.        In the last installment, I left you with a  compiler  that  would
  85.        ALMOST  work,  except  that  we  were  still  limited to  single-
  86.        character tokens.  The purpose of  this  session is to get rid of
  87.        that restriction, once and for all.  This means that we must deal
  88.        with the concept of the lexical scanner.
  89.  
  90.        Maybe I should mention why we  need  a lexical scanner at all ...
  91.        after all, we've been able to manage all right  without  one,  up
  92.        till now, even when we provided for multi-character tokens.
  93.  
  94.        The ONLY reason, really, has to do with keywords.  It's a fact of
  95.        computer life that the syntax for a keyword has the same  form as
  96.        that  for  any  other identifier.  We can't tell until we get the
  97.        complete word whether or not it  IS  a keyword.  For example, the
  98.        variable IFILE and the keyword IF look just alike, until  you get
  99.        to the third character.  In the examples to date, we  were always
  100.        able to make  a  decision  based  upon the first character of the
  101.        token, but that's  no  longer possible when keywords are present.
  102.        We  need to know that a given string is a keyword BEFORE we begin
  103.        to process it.  And that's why we need a scanner.
  104.  
  105.        In the last session, I also promised that  we  would  be  able to
  106.        provide for normal tokens  without  making  wholesale  changes to
  107.        what we have  already done.  I didn't lie ... we can, as you will
  108.        see later.  But every time I set out to install these elements of
  109.        the software into  the  parser  we  have already built, I had bad
  110.        feelings about it.  The whole thing felt entirely too much like a
  111.        band-aid.  I finally figured out what was causing the  problem: I
  112.        was installing lexical scanning software without first explaining
  113.        to you what scanning is all about, and what the alternatives are.
  114.        Up  till  now, I have studiously avoided  giving  you  a  lot  of
  115.        theory,  and  certainly  not  alternatives.    I  generally don't
  116.        respond well to the textbooks that give you twenty-five different
  117.        ways  to do something, but no clue as to which way best fits your
  118.        needs.  I've tried to avoid that pitfall by just showing  you ONE
  119.        method, that WORKS.
  120.  
  121.        But  this is an important area.  While  the  lexical  scanner  is
  122.        hardly the most  exciting  part  of  a compiler, it often has the
  123.        most  profound  effect  on  the  general  "look  & feel"  of  the
  124.        language, since after all it's the  part  closest to the user.  I
  125.        have a particular structure in mind for the scanner  to  be  used
  126.        with  KISS.    It fits the look &  feel  that  I  want  for  thatA*A*
  127.                                      - 2 -
  128. PA A
  129.  
  130.  
  131.  
  132.  
  133.  
  134.        language.  But it may not work at  all  for  the  language YOU'RE
  135.        cooking  up,  so  in this one case I feel that it's important for
  136.        you to know your options.
  137.  
  138.        So I'm going to depart, again, from my  usual  format.    In this
  139.        session we'll be getting  much  deeper  than usual into the basic
  140.        theory of languages and  grammars.    I'll  also be talking about
  141.        areas OTHER than compilers in  which  lexical  scanning  plays an
  142.        important role.  Finally, I will show you  some  alternatives for
  143.        the structure of the lexical scanner.  Then, and only  then, will
  144.        we get back to our parser  from  the last installment.  Bear with
  145.        me ... I think you'll find it's worth the wait.    In fact, since
  146.        scanners have many applications  outside  of  compilers,  you may
  147.        well find this to be the most useful session for you.
  148.  
  149.  
  150.        LEXICAL SCANNING
  151.  
  152.        Lexical scanning is the process of scanning the  stream  of input
  153.        characters and separating it  into  strings  called tokens.  Most
  154.        compiler  texts  start  here,  and  devote  several  chapters  to
  155.        discussing various ways to build scanners.  This approach has its
  156.        place, but as you have already  seen,  there  is a lot you can do
  157.        without ever even addressing the issue, and in  fact  the scanner
  158.        we'll  end  up with here won't look  much  like  what  the  texts
  159.        describe.  The reason?    Compiler  theory and, consequently, the
  160.        programs resulting from it, must  deal with the most general kind
  161.        of parsing rules.  We don't.  In the real  world,  it is possible
  162.        to specify the language syntax in such a way that a pretty simple
  163.        scanner will suffice.  And as always, KISS is our motto.
  164.  
  165.        Typically, lexical scanning is  done  in  a  separate part of the
  166.        compiler, so that the parser per  se  sees only a stream of input
  167.        tokens.  Now, theoretically it  is not necessary to separate this
  168.        function from the rest of the parser.  There is  only  one set of
  169.        syntax equations that define the  whole language, so in theory we
  170.        could write the whole parser in one module.
  171.  
  172.        Why  the  separation?      The  answer  has  both  practical  and
  173.        theoretical bases.
  174.  
  175.        In  1956,  Noam  Chomsky  defined  the  "Chomsky   Hierarchy"  of
  176.        grammars.  They are:
  177.  
  178.             o Type 0:  Unrestricted (e.g., English)
  179.  
  180.             o Type 1:  Context-Sensitive
  181.  
  182.             o Type 2:  Context-Free
  183.  
  184.             o Type 3:  Regular
  185.  
  186.        A few features of the typical programming  language (particularly
  187.        the older ones, such as FORTRAN) are Type  1,  but  for  the mostA*A*
  188.                                      - 3 -
  189. PA A
  190.  
  191.  
  192.  
  193.  
  194.  
  195.        part  all  modern  languages can be described using only the last
  196.        two types, and those are all we'll be dealing with here.
  197.  
  198.        The  neat  part about these two types  is  that  there  are  very
  199.        specific ways to parse them.  It has been shown that  any regular
  200.        grammar can be parsed using a particular form of abstract machine
  201.        called the state machine (finite  automaton).    We  have already
  202.        implemented state machines in some of our recognizers.
  203.  
  204.        Similarly, Type 2 (context-free) grammars  can  always  be parsed
  205.        using  a  push-down  automaton (a state machine  augmented  by  a
  206.        stack).  We have  also  implemented  these  machines.  Instead of
  207.        implementing  a literal stack, we have  relied  on  the  built-in
  208.        stack associated with recursive coding to do the job, and that in
  209.        fact is the preferred approach for top-down parsing.
  210.  
  211.        Now, it happens that in  real, practical grammars, the parts that
  212.        qualify as  regular expressions tend to be the lower-level parts,
  213.        such as the definition of an identifier:
  214.  
  215.             <ident> ::= <letter> [ <letter> | <digit> ]*
  216.  
  217.        Since it takes a different kind of abstract machine to  parse the
  218.        two  types  of  grammars, it makes sense to separate these lower-
  219.        level functions into  a  separate  module,  the  lexical scanner,
  220.        which is built around the idea of a state machine. The idea is to
  221.        use the simplest parsing technique needed for the job.
  222.  
  223.        There is another, more practical  reason  for  separating scanner
  224.        from  parser.   We like to think of the input source  file  as  a
  225.        stream  of characters, which we process  right  to  left  without
  226.        backtracking.  In practice that  isn't  possible.    Almost every
  227.        language has certain keywords such as  IF,  WHILE, and END.  As I
  228.        mentioned  earlier,    we  can't  really  know  whether  a  given
  229.        character string is a keyword, until we've reached the end of it,
  230.        as defined by a space or other delimiter.  So  in  that sense, we
  231.        MUST  save  the  string long enough to find out whether we have a
  232.        keyword or not.  That's a limited form of backtracking.
  233.  
  234.        So the structure of a conventional compiler involves splitting up
  235.        the functions of  the  lower-level and higher-level parsing.  The
  236.        lexical  scanner  deals  with  things  at  the  character  level,
  237.        collecting characters into strings, etc., and passing  them along
  238.        to the parser proper as indivisible tokens.  It's also considered
  239.        normal to let the scanner have the job of identifying keywords.
  240.  
  241.  
  242.        STATE MACHINES AND ALTERNATIVES
  243.  
  244.        I  mentioned  that  the regular expressions can be parsed using a
  245.        state machine.   In  most  compiler  texts,  and  indeed  in most
  246.        compilers as well, you will find this taken literally.   There is
  247.        typically  a  real  implementation  of  the  state  machine, with
  248.        integers used to define the current state, and a table of actionsA*A*
  249.                                      - 4 -
  250. PA A
  251.  
  252.  
  253.  
  254.  
  255.  
  256.        to  take   for  each  combination  of  current  state  and  input
  257.        character.  If you  write  a compiler front end using the popular
  258.        Unix tools LEX and YACC, that's  what  you'll get.  The output of
  259.        LEX is a state machine implemented in C, plus a table  of actions
  260.        corresponding to the input grammar given to LEX.  The YACC output
  261.        is  similar  ...  a canned table-driven parser,  plus  the  table
  262.        corresponding to the language syntax.
  263.  
  264.        That  is  not  the  only  choice,  though.     In   our  previous
  265.        installments, you have seen over and over that it is  possible to
  266.        implement  parsers  without  dealing  specifically  with  tables,
  267.        stacks, or state variables.    In fact, in Installment V I warned
  268.        you that if you  find  yourself needing these things you might be
  269.        doing something wrong, and not taking advantage of  the  power of
  270.        Pascal.  There are basically two ways to define a state machine's
  271.        state: explicitly, with  a  state number or code, and implicitly,
  272.        simply by virtue of the fact that I'm at a  certain  place in the
  273.        code  (if  it's  Tuesday,  this  must be Belgium).  We've  relied
  274.        heavily on the implicit approaches  before,  and  I  think you'll
  275.        find that they work well here, too.
  276.  
  277.        In practice, it may not even be necessary to HAVE  a well-defined
  278.        lexical scanner.  This isn't our first experience at dealing with
  279.        multi-character tokens.   In  Installment  III,  we  extended our
  280.        parser to provide  for  them,  and  we didn't even NEED a lexical
  281.        scanner.    That  was  because  in that narrow context, we  could
  282.        always tell, just  by  looking at the single lookahead character,
  283.        whether  we  were  dealing  with  a  number,  a variable,  or  an
  284.        operator.  In effect, we  built  a  distributed  lexical scanner,
  285.        using procedures GetName and GetNum.
  286.  
  287.        With keywords present,  we  can't know anymore what we're dealing
  288.        with, until the entire token is  read.    This leads us to a more
  289.        localized  scanner; although,  as you will see,  the  idea  of  a
  290.        distributed scanner still has its merits.
  291.  
  292.  
  293.        SOME EXPERIMENTS IN SCANNING
  294.  
  295.        Before  getting  back  to our compiler,  it  will  be  useful  to
  296.        experiment a bit with the general concepts.
  297.  
  298.        Let's  begin with the two definitions most  often  seen  in  real
  299.        programming languages:
  300.  
  301.             <ident> ::= <letter> [ <letter> | <digit> ]*
  302.             <number ::= [<digit>]+
  303.  
  304.        (Remember, the '*' indicates zero or more occurences of the terms
  305.        in brackets, and the '+', one or more.)
  306.  
  307.        We  have already dealt with similar  items  in  Installment  III.
  308.        Let's begin (as usual) with a bare cradle.  Not  surprisingly, we
  309.        are going to need a new recognizer:A*A*
  310.                                      - 5 -
  311. PA A
  312.  
  313.  
  314.  
  315.  
  316.  
  317.        {--------------------------------------------------------------}
  318.        { Recognize an Alphanumeric Character }
  319.  
  320.        function IsAlNum(c: char): boolean;
  321.        begin
  322.           IsAlNum := IsAlpha(c) or IsDigit(c);
  323.        end;
  324.        {--------------------------------------------------------------}
  325.  
  326.  
  327.        Using this let's write the following two routines, which are very
  328.        similar to those we've used before:
  329.  
  330.  
  331.        {--------------------------------------------------------------}
  332.        { Get an Identifier }
  333.  
  334.        function GetName: string;
  335.        var x: string[8];
  336.        begin
  337.           x := '';
  338.           if not IsAlpha(Look) then Expected('Name');
  339.           while IsAlNum(Look) do begin
  340.             x := x + UpCase(Look);
  341.             GetChar;
  342.           end;
  343.           GetName := x;
  344.        end;
  345.  
  346.  
  347.        {--------------------------------------------------------------}
  348.        { Get a Number }
  349.  
  350.        function GetNum: string;
  351.        var x: string[16];
  352.        begin
  353.           x := '';
  354.           if not IsDigit(Look) then Expected('Integer');
  355.           while IsDigit(Look) do begin
  356.             x := x + Look;
  357.             GetChar;
  358.           end;
  359.           GetNum := x;
  360.        end;
  361.        {--------------------------------------------------------------}
  362.  
  363.  
  364.        (Notice  that this version of GetNum returns  a  string,  not  an
  365.        integer as before.)
  366.  
  367.        You  can  easily  verify that these routines work by calling them
  368.        from the main program, as inABAB
  369.                                      - 6 -A*A*
  370. PA A
  371.  
  372.  
  373.  
  374.  
  375.  
  376.             WriteLn(GetName);
  377.  
  378.        This  program  will  print any legal name typed in (maximum eight
  379.        characters, since that's what we told GetName).   It  will reject
  380.        anything else.
  381.  
  382.        Test the other routine similarly.
  383.  
  384.  
  385.        WHITE SPACE
  386.  
  387.        We  also  have  dealt with embedded white space before, using the
  388.        two  routines  IsWhite  and  SkipWhite.    Make  sure that  these
  389.        routines are in your  current  version of the cradle, and add the
  390.        the line
  391.  
  392.             SkipWhite;
  393.  
  394.        at the end of both GetName and GetNum.
  395.  
  396.        Now, let's define the new procedure:
  397.  
  398.  
  399.        {--------------------------------------------------------------}
  400.        { Lexical Scanner }
  401.  
  402.        Function Scan: string;
  403.        begin
  404.           if IsAlpha(Look) then
  405.              Scan := GetName
  406.           else if IsDigit(Look) then
  407.              Scan := GetNum
  408.           else begin
  409.              Scan := Look;
  410.              GetChar;
  411.           end;
  412.           SkipWhite;
  413.        end;
  414.        {--------------------------------------------------------------}
  415.  
  416.  
  417.        We can call this from the new main program:A>A>
  418.  
  419.  
  420.                                      - 7 -A*A*
  421. PA A
  422.  
  423.  
  424.  
  425.  
  426.  
  427.        {--------------------------------------------------------------}
  428.        { Main Program }
  429.  
  430.  
  431.        begin
  432.           Init;
  433.           repeat
  434.              Token := Scan;
  435.              writeln(Token);
  436.           until Token = CR;
  437.        end.
  438.        {--------------------------------------------------------------}
  439.  
  440.  
  441.        (You will have to add the declaration of the string Token  at the
  442.        beginning of the program.  Make it any convenient length,  say 16
  443.        characters.)
  444.  
  445.        Now,  run the program.  Note how the  input  string  is,  indeed,
  446.        separated into distinct tokens.
  447.  
  448.  
  449.        STATE MACHINES
  450.  
  451.        For  the  record,  a  parse  routine  like  GetName  does  indeed
  452.        implement a state machine.  The state is implicit in  the current
  453.        position in the code.  A very useful trick for visualizing what's
  454.        going on is  the  syntax  diagram,  or  "railroad-track" diagram.
  455.        It's a little difficult to draw  one  in this medium, so I'll use
  456.        them very sparingly, but  the  figure  below  should give you the
  457.        idea:
  458.  
  459.  
  460.                   |-----> Other---------------------------> Error
  461.                   |
  462.           Start -------> Letter ---------------> Other -----> Finish
  463.                   ^                        V
  464.                   |                        |
  465.                   |<----- Letter <---------|
  466.                   |                        |
  467.                   |<----- Digit  <----------
  468.  
  469.  
  470.        As  you  can  see,  this  diagram  shows  how  the logic flows as
  471.        characters  are  read.    Things  begin, of course, in the  start
  472.        state, and end when  a  character  other  than an alphanumeric is
  473.        found.  If  the  first  character  is not alpha, an error occurs.
  474.        Otherwise the machine will continue looping until the terminating
  475.        delimiter is found.
  476.  
  477.        Note  that at any point in the flow,  our  position  is  entirely
  478.        dependent on the past  history  of the input characters.  At that
  479.        point, the action to be taken depends only on the  current state,A6A6
  480.                                      - 8 -A*A*
  481. PA A
  482.  
  483.  
  484.  
  485.  
  486.  
  487.        plus the current input character.  That's what make this  a state
  488.        machine.
  489.  
  490.        Because of the difficulty of drawing  railroad-track  diagrams in
  491.        this medium, I'll continue to  stick to syntax equations from now
  492.        on.  But I highly recommend the diagrams to you for  anything you
  493.        do that involves parsing.  After a little practice you  can begin
  494.        to  see  how  to  write  a  parser  directly from  the  diagrams.
  495.        Parallel paths get coded into guarded actions (guarded by IF's or
  496.        CASE statements),  serial  paths  into  sequential  calls.   It's
  497.        almost like working from a schematic.
  498.  
  499.        We didn't even discuss SkipWhite, which  was  introduced earlier,
  500.        but it also is a simple state machine, as is GetNum.  So is their
  501.        parent procedure, Scan.  Little machines make big machines.
  502.  
  503.        The neat thing that I'd like  you  to note is how painlessly this
  504.        implicit approach creates these  state  machines.    I personally
  505.        prefer it a lot over the table-driven approach.  It  also results
  506.        is a small, tight, and fast scanner.
  507.  
  508.  
  509.        NEWLINES
  510.  
  511.        Moving right along, let's modify  our scanner to handle more than
  512.        one line.  As I mentioned last time, the most straightforward way
  513.        to  do  this  is to simply treat the newline characters, carriage
  514.        return  and line feed, as white space.  This is, in fact, the way
  515.        the  C  standard  library  routine,  iswhite, works.   We  didn't
  516.        actually try this  before.  I'd like to do it now, so you can get
  517.        a feel for the results.
  518.  
  519.        To do this, simply modify the single executable  line  of IsWhite
  520.        to read:
  521.  
  522.  
  523.           IsWhite := c in [' ', TAB, CR, LF];
  524.  
  525.  
  526.        We need to give the main  program  a new stop condition, since it
  527.        will never see a CR.  Let's just use:
  528.  
  529.  
  530.           until Token = '.';
  531.  
  532.  
  533.        OK, compile this  program  and  run  it.   Try a couple of lines,
  534.        terminated by the period.  I used:
  535.  
  536.  
  537.             now is the time
  538.             for all good men.ABAB
  539.                                      - 9 -A*A*
  540. PA A
  541.  
  542.  
  543.  
  544.  
  545.  
  546.        Hey,  what  happened?   When I tried it, I didn't  get  the  last
  547.        token, the period.  The program didn't halt.  What's more, when I
  548.        pressed the  'enter'  key  a  few  times,  I still didn't get the
  549.        period.
  550.  
  551.        If you're still stuck in your program, you'll find that  typing a
  552.        period on a new line will terminate it.
  553.  
  554.        What's going on here?  The answer is  that  we're  hanging  up in
  555.        SkipWhite.  A quick look at  that  routine will show that as long
  556.        as we're typing null lines, we're going to just continue to loop.
  557.        After SkipWhite encounters an LF,  it tries to execute a GetChar.
  558.        But since the input buffer is now empty, GetChar's read statement
  559.        insists  on  having  another  line.    Procedure  Scan  gets  the
  560.        terminating period, all right,  but  it  calls SkipWhite to clean
  561.        up, and SkipWhite won't return until it gets a non-null line.
  562.  
  563.        This kind of behavior is not quite as bad as it seems.  In a real
  564.        compiler,  we'd  be  reading  from  an input file instead of  the
  565.        console, and as long  as  we have some procedure for dealing with
  566.        end-of-files, everything will come out  OK.  But for reading data
  567.        from the console, the behavior is just too bizarre.  The  fact of
  568.        the matter is that the C/Unix convention is  just  not compatible
  569.        with the structure of  our  parser,  which  calls for a lookahead
  570.        character.    The  code that the Bell  wizards  have  implemented
  571.        doesn't use that convention, which is why they need 'ungetc'.
  572.  
  573.        OK, let's fix the problem.  To do that, we need to go back to the
  574.        old definition of IsWhite (delete the CR and  LF  characters) and
  575.        make  use  of  the procedure Fin that I introduced last time.  If
  576.        it's not in your current version of the cradle, put it there now.
  577.  
  578.        Also, modify the main program to read:
  579.  
  580.  
  581.        {--------------------------------------------------------------}
  582.        { Main Program }
  583.  
  584.  
  585.        begin
  586.           Init;
  587.           repeat
  588.              Token := Scan;
  589.              writeln(Token);
  590.              if Token = CR then Fin;
  591.           until Token = '.';
  592.        end.
  593.        {--------------------------------------------------------------}
  594.  
  595.  
  596.        Note the "guard"  test  preceding  the  call to Fin.  That's what
  597.        makes the whole thing work, and ensures that we don't try to read
  598.        a line ahead.A6A6
  599.                                     - 10 -A*A*
  600. PA A
  601.  
  602.  
  603.  
  604.  
  605.  
  606.        Try the code now. I think you'll like it better.
  607.  
  608.        If you refer to the code  we  did in the last installment, you'll
  609.        find that I quietly sprinkled calls to Fin  throughout  the code,
  610.        wherever  a line break was appropriate.  This  is  one  of  those
  611.        areas that really affects the look  &  feel that I mentioned.  At
  612.        this  point  I  would  urge  you  to  experiment  with  different
  613.        arrangements  and  see  how  you  like  them.    If you want your
  614.        language  to  be  truly  free-field,  then  newlines   should  be
  615.        transparent.   In  this  case,  the  best  approach is to put the
  616.        following lines at the BEGINNING of Scan:
  617.  
  618.  
  619.                  while Look = CR do
  620.                     Fin;
  621.  
  622.  
  623.        If, on the other  hand,  you  want  a line-oriented language like
  624.        Assembler, BASIC, or FORTRAN  (or  even  Ada...  note that it has
  625.        comments terminated by newlines),  then  you'll  need for Scan to
  626.        return CR's as tokens.  It  must  also  eat the trailing LF.  The
  627.        best way to do that is to use this line,  again  at the beginning
  628.        of Scan:
  629.  
  630.                  if Look = LF then Fin;
  631.  
  632.  
  633.        For other conventions, you'll  have  to  use  other arrangements.
  634.        In my example  of  the  last  session, I allowed newlines only at
  635.        specific places, so I was somewhere in the middle ground.  In the
  636.        rest of these sessions, I'll be picking ways  to  handle newlines
  637.        that I happen to like, but I want you to know how to choose other
  638.        ways for yourselves.
  639.  
  640.  
  641.        OPERATORS
  642.  
  643.        We  could  stop now and have a  pretty  useful  scanner  for  our
  644.        purposes.  In the fragments of KISS that we've built so  far, the
  645.        only tokens that have multiple characters are the identifiers and
  646.        numbers.    All  operators  were  single  characters.   The  only
  647.        exception I can think of is the relops <=, >=,  and  <>, but they
  648.        could be dealt with as special cases.
  649.  
  650.        Still, other languages have  multi-character  operators,  such as
  651.        the ':=' of  Pascal or the '++' and '>>' of C.  So  while  we may
  652.        not need multi-character operators, it's  nice to know how to get
  653.        them if necessary.
  654.  
  655.        Needless to say, we  can  handle operators very much the same way
  656.        as the other tokens.  Let's start with a recognizer:ANAN
  657.                                     - 11 -A*A*
  658. PA A
  659.  
  660.  
  661.  
  662.  
  663.  
  664.        {--------------------------------------------------------------}
  665.        { Recognize Any Operator }
  666.  
  667.        function IsOp(c: char): boolean;
  668.        begin
  669.           IsOp := c in ['+', '-', '*', '/', '<', '>', ':', '='];
  670.        end;
  671.        {--------------------------------------------------------------}
  672.  
  673.  
  674.        It's important to  note  that  we  DON'T  have  to  include every
  675.        possible  operator in this list.   For  example,  the  paretheses
  676.        aren't  included, nor is the terminating  period.    The  current
  677.        version of Scan handles single-character operators  just  fine as
  678.        it is.  The list above includes only those  characters  that  can
  679.        appear in multi-character operators.  (For specific languages, of
  680.        course, the list can always be edited.)
  681.  
  682.        Now, let's modify Scan to read:
  683.  
  684.  
  685.        {--------------------------------------------------------------}
  686.        { Lexical Scanner }
  687.  
  688.        Function Scan: string;
  689.        begin
  690.           while Look = CR do
  691.              Fin;
  692.           if IsAlpha(Look) then
  693.              Scan := GetName
  694.           else if IsDigit(Look) then
  695.              Scan := GetNum
  696.           else if IsOp(Look) then
  697.              Scan := GetOp
  698.           else begin
  699.              Scan := Look;
  700.              GetChar;
  701.           end;
  702.           SkipWhite;
  703.        end;
  704.        {--------------------------------------------------------------}
  705.  
  706.  
  707.        Try the program now.  You  will  find that any code fragments you
  708.        care  to throw at it will be neatly  broken  up  into  individual
  709.        tokens.
  710.  
  711.  
  712.        LISTS, COMMAS AND COMMAND LINES
  713.  
  714.        Before getting back to the main thrust of our study, I'd  like to
  715.        get on my soapbox for a moment.ABAB
  716.                                     - 12 -A*A*
  717. PA A
  718.  
  719.  
  720.  
  721.  
  722.  
  723.        How many times have you worked with a program or operating system
  724.        that had rigid rules about how you must separate items in a list?
  725.        (Try,  the  last  time  you  used MSDOS!)  Some programs  require
  726.        spaces as delimiters, and  some  require  commas.   Worst of all,
  727.        some  require  both,  in  different  places.    Most  are  pretty
  728.        unforgiving about violations of their rules.
  729.  
  730.        I think this is inexcusable.  It's too  easy  to  write  a parser
  731.        that will handle  both  spaces  and  commas  in  a  flexible way.
  732.        Consider the following procedure:
  733.  
  734.  
  735.        {--------------------------------------------------------------}
  736.        { Skip Over a Comma }
  737.  
  738.        procedure SkipComma;
  739.        begin
  740.           SkipWhite;
  741.           if Look = ',' then begin
  742.              GetChar;
  743.              SkipWhite;
  744.           end;
  745.        end;
  746.        {--------------------------------------------------------------}
  747.  
  748.  
  749.        This eight-line procedure will skip over  a  delimiter consisting
  750.        of any number (including zero)  of spaces, with zero or one comma
  751.        embedded in the string.
  752.  
  753.        TEMPORARILY, change the call to SkipWhite in Scan to  a  call  to
  754.        SkipComma,  and  try  inputting some lists.   Works  nicely,  eh?
  755.        Don't you wish more software authors knew about SkipComma?
  756.  
  757.        For the record, I found that adding the  equivalent  of SkipComma
  758.        to my Z80 assembler-language programs took all of  6  (six) extra
  759.        bytes of  code.    Even  in a 64K machine, that's not a very high
  760.        price to pay for user-friendliness!
  761.  
  762.        I  think  you can see where I'm going here.  Even  if  you  never
  763.        write a line of a compiler code in your life, there are places in
  764.        every program where  you  can  use  the concepts of parsing.  Any
  765.        program that processes a command line needs them.   In  fact,  if
  766.        you  think  about  it for a bit, you'll have to conclude that any
  767.        time  you  write  a program that processes  user  inputs,  you're
  768.        defining a  language.  People communicate with languages, and the
  769.        syntax implicit in your program  defines that language.  The real
  770.        question  is:  are  you  going  to  define  it  deliberately  and
  771.        explicitly, or just let it turn out to be  whatever  the  program
  772.        ends up parsing?
  773.  
  774.        I claim that you'll have  a better, more user-friendly program if
  775.        you'll take the time to define the syntax explicitly.  Write down
  776.        the syntax equations or  draw  the  railroad-track  diagrams, andA*A*
  777.                                     - 13 -
  778. PA A
  779.  
  780.  
  781.  
  782.  
  783.  
  784.        code the parser using the techniques I've shown you here.  You'll
  785.        end  up with a better program, and it will be easier to write, to
  786.        boot.
  787.  
  788.  
  789.        GETTING FANCY
  790.  
  791.        OK, at this point we have a pretty nice lexical scanner that will
  792.        break  an  input stream up into tokens.  We could use  it  as  it
  793.        stands and have a servicable compiler.  But there are  some other
  794.        aspects of lexical scanning that we need to cover.
  795.  
  796.        The main consideration is <shudder> efficiency.  Remember when we
  797.        were dealing  with  single-character  tokens,  every  test  was a
  798.        comparison of a single character, Look, with a byte constant.  We
  799.        also used the Case statement heavily.
  800.  
  801.        With the multi-character tokens being returned by Scan, all those
  802.        tests now become string comparisons.  Much slower.  And  not only
  803.        slower, but more awkward, since  there is no string equivalent of
  804.        the  Case  statement  in Pascal.  It seems especially wasteful to
  805.        test for what used to be single characters ... the '=',  '+', and
  806.        other operators ... using string comparisons.
  807.  
  808.        Using string comparison is not  impossible ... Ron Cain used just
  809.        that approach in writing Small C.  Since we're  sticking  to  the
  810.        KISS principle here, we would  be truly justified in settling for
  811.        this  approach.    But then I would have failed to tell you about
  812.        one of the key approaches used in "real" compilers.
  813.  
  814.        You have to remember: the lexical scanner is going to be called a
  815.        _LOT_!   Once for every token in the  whole  source  program,  in
  816.        fact.   Experiments  have  indicated  that  the  average compiler
  817.        spends  anywhere  from 20% to 40% of  its  time  in  the  scanner
  818.        routines.  If there were ever a place  where  efficiency deserves
  819.        real consideration, this is it.
  820.  
  821.        For this reason, most compiler writers ask the lexical scanner to
  822.        do  a  little  more work, by "tokenizing"  the input stream.  The
  823.        idea  is  to  match every token  against  a  list  of  acceptable
  824.        keywords  and operators, and return unique  codes  for  each  one
  825.        recognized.  In the case of ordinary variable  names  or numbers,
  826.        we  just return a code that says what kind of token they are, and
  827.        save the actual string somewhere else.
  828.  
  829.        One  of the first things we're going to need is a way to identify
  830.        keywords.  We can always do  it  with successive IF tests, but it
  831.        surely would be nice  if  we  had  a general-purpose routine that
  832.        could compare a given string with  a  table of keywords.  (By the
  833.        way, we're also going  to  need such a routine later, for dealing
  834.        with symbol tables.)  This  usually presents a problem in Pascal,
  835.        because standard Pascal  doesn't  allow  for  arrays  of variable
  836.        lengths.   It's  a  real  bother  to  have to declare a differentA6A6
  837.                                     - 14 -A*A*
  838. PA A
  839.  
  840.  
  841.  
  842.  
  843.  
  844.        search routine for every table.    Standard  Pascal  also doesn't
  845.        allow for initializing arrays, so you tend to see code like
  846.  
  847.             Table[1] := 'IF';
  848.             Table[2] := 'ELSE';
  849.             .
  850.             .
  851.             Table[n] := 'END';
  852.  
  853.        which can get pretty old if there are many keywords.
  854.  
  855.        Fortunately, Turbo Pascal 4.0 has extensions that  eliminate both
  856.        of  these  problems.   Constant arrays can be declared using TP's
  857.        "typed constant" facility, and  the  variable  dimensions  can be
  858.        handled with its C-like extensions for pointers.
  859.  
  860.        First, modify your declarations like this:
  861.  
  862.  
  863.        {--------------------------------------------------------------}
  864.        { Type Declarations  }
  865.  
  866.        type Symbol = string[8];
  867.  
  868.             SymTab = array[1..1000] of Symbol;
  869.  
  870.             TabPtr = ^SymTab;
  871.        {--------------------------------------------------------------}
  872.  
  873.  
  874.        (The dimension  used  in  SymTab  is  not  real ... no storage is
  875.        allocated by the declaration itself,  and the number need only be
  876.        "big enough.")
  877.  
  878.        Now, just beneath those declarations, add the following:
  879.  
  880.  
  881.        {--------------------------------------------------------------}
  882.        { Definition of Keywords and Token Types }
  883.  
  884.        const KWlist: array [1..4] of Symbol =
  885.                      ('IF', 'ELSE', 'ENDIF', 'END');
  886.  
  887.        {--------------------------------------------------------------}
  888.  
  889.  
  890.        Next, insert the following new function:
  891.  
  892.  
  893.        {--------------------------------------------------------------}
  894.        { Table Lookup }
  895.  
  896.        { If the input string matches a table entry, return the entry
  897.          index.  If not, return a zero.  }A*A*
  898.                                     - 15 -
  899. PA A
  900.  
  901.  
  902.  
  903.  
  904.  
  905.        function Lookup(T: TabPtr; s: string; n: integer): integer;
  906.        var i: integer;
  907.            found: boolean;
  908.        begin
  909.           found := false;
  910.           i := n;
  911.           while (i > 0) and not found do
  912.              if s = T^[i] then
  913.                 found := true
  914.              else
  915.                 dec(i);
  916.           Lookup := i;
  917.        end;
  918.        {--------------------------------------------------------------}
  919.  
  920.  
  921.        To test it,  you  can  temporarily  change  the  main  program as
  922.        follows:
  923.  
  924.  
  925.        {--------------------------------------------------------------}
  926.        { Main Program }
  927.  
  928.  
  929.        begin
  930.           ReadLn(Token);
  931.           WriteLn(Lookup(Addr(KWList), Token, 4));
  932.        end.
  933.        {--------------------------------------------------------------}
  934.  
  935.  
  936.        Notice how Lookup is called: The Addr function sets up  a pointer
  937.        to KWList, which gets passed to Lookup.
  938.  
  939.        OK, give this  a  try.    Since we're bypassing Scan here, you'll
  940.        have to type the keywords in upper case to get any matches.
  941.  
  942.        Now that we can recognize keywords, the next thing is  to arrange
  943.        to return codes for them.
  944.  
  945.        So what kind of code should we return?  There are really only two
  946.        reasonable choices.  This seems like an ideal application for the
  947.        Pascal enumerated type.   For  example,  you can define something
  948.        like
  949.  
  950.             SymType = (IfSym, ElseSym, EndifSym, EndSym, Ident, Number,
  951.                            Operator);
  952.  
  953.        and arrange to return a variable of this type.   Let's  give it a
  954.        try.  Insert the line above into your type definitions.
  955.  
  956.        Now, add the two variable declarations:ABAB
  957.                                     - 16 -A*A*
  958. PA A
  959.  
  960.  
  961.  
  962.  
  963.  
  964.            Token: Symtype;          { Current Token  }
  965.            Value: String[16];       { String Token of Look }
  966.  
  967.  
  968.        Modify the scanner to read:
  969.  
  970.  
  971.        {--------------------------------------------------------------}
  972.        { Lexical Scanner }
  973.  
  974.        procedure Scan;
  975.        var k: integer;
  976.        begin
  977.           while Look = CR do
  978.              Fin;
  979.           if IsAlpha(Look) then begin
  980.              Value := GetName;
  981.              k := Lookup(Addr(KWlist), Value, 4);
  982.              if k = 0 then
  983.                 Token := Ident
  984.              else
  985.                 Token := SymType(k - 1);
  986.              end
  987.           else if IsDigit(Look) then begin
  988.              Value := GetNum;
  989.              Token := Number;
  990.              end
  991.           else if IsOp(Look) then begin
  992.              Value := GetOp;
  993.              Token := Operator;
  994.              end
  995.           else begin
  996.              Value := Look;
  997.              Token := Operator;
  998.              GetChar;
  999.           end;
  1000.           SkipWhite;
  1001.        end;
  1002.        {--------------------------------------------------------------}
  1003.  
  1004.  
  1005.        (Notice that Scan is now a procedure, not a function.)
  1006.  
  1007.  
  1008.        Finally, modify the main program to read:AKAK
  1009.  
  1010.                                     - 17 -A*A*
  1011. PA A
  1012.  
  1013.  
  1014.  
  1015.  
  1016.  
  1017.        {--------------------------------------------------------------}
  1018.        { Main Program }
  1019.  
  1020.        begin
  1021.           Init;
  1022.           repeat
  1023.              Scan;
  1024.              case Token of
  1025.                Ident: write('Ident ');
  1026.                Number: Write('Number ');
  1027.                Operator: Write('Operator ');
  1028.                IfSym, ElseSym, EndifSym, EndSym: Write('Keyword ');
  1029.              end;
  1030.              Writeln(Value);
  1031.           until Token = EndSym;
  1032.        end.
  1033.        {--------------------------------------------------------------}
  1034.  
  1035.  
  1036.        What we've done here is to replace the string Token  used earlier
  1037.        with an enumerated type. Scan returns the type in variable Token,
  1038.        and returns the string itself in the new variable Value.
  1039.  
  1040.        OK, compile this and give it a whirl.  If everything  goes right,
  1041.        you should see that we are now recognizing keywords.
  1042.  
  1043.        What  we  have  now is working right, and it was easy to generate
  1044.        from what  we  had  earlier.    However,  it still seems a little
  1045.        "busy" to me.  We can  simplify  things a bit by letting GetName,
  1046.        GetNum, GetOp, and Scan be  procedures  working  with  the global
  1047.        variables Token and Value, thereby eliminating the  local copies.
  1048.        It  also seems a little cleaner to move  the  table  lookup  into
  1049.        GetName.  The new form for the four procedures is, then:
  1050.  
  1051.  
  1052.        {--------------------------------------------------------------}
  1053.        { Get an Identifier }
  1054.  
  1055.        procedure GetName;
  1056.        var k: integer;
  1057.        begin
  1058.           Value := '';
  1059.           if not IsAlpha(Look) then Expected('Name');
  1060.           while IsAlNum(Look) do begin
  1061.             Value := Value + UpCase(Look);
  1062.             GetChar;
  1063.           end;
  1064.           k := Lookup(Addr(KWlist), Value, 4);
  1065.           if k = 0 then
  1066.              Token := Ident
  1067.           else
  1068.              Token := SymType(k-1);
  1069.        end;A6A6
  1070.                                     - 18 -A*A*
  1071. PA A
  1072.  
  1073.  
  1074.  
  1075.  
  1076.  
  1077.        {--------------------------------------------------------------}
  1078.        { Get a Number }
  1079.  
  1080.        procedure GetNum;
  1081.        begin
  1082.           Value := '';
  1083.           if not IsDigit(Look) then Expected('Integer');
  1084.           while IsDigit(Look) do begin
  1085.             Value := Value + Look;
  1086.             GetChar;
  1087.           end;
  1088.           Token := Number;
  1089.        end;
  1090.  
  1091.  
  1092.        {--------------------------------------------------------------}
  1093.        { Get an Operator }
  1094.  
  1095.        procedure GetOp;
  1096.        begin
  1097.           Value := '';
  1098.           if not IsOp(Look) then Expected('Operator');
  1099.           while IsOp(Look) do begin
  1100.             Value := Value + Look;
  1101.             GetChar;
  1102.           end;
  1103.           Token := Operator;
  1104.        end;
  1105.  
  1106.  
  1107.        {--------------------------------------------------------------}
  1108.        { Lexical Scanner }
  1109.  
  1110.        procedure Scan;
  1111.        var k: integer;
  1112.        begin
  1113.           while Look = CR do
  1114.              Fin;
  1115.           if IsAlpha(Look) then
  1116.              GetName
  1117.           else if IsDigit(Look) then
  1118.              GetNum
  1119.           else if IsOp(Look) then
  1120.              GetOp
  1121.           else begin
  1122.              Value := Look;
  1123.              Token := Operator;
  1124.              GetChar;
  1125.           end;
  1126.           SkipWhite;
  1127.        end;
  1128.        {--------------------------------------------------------------}ABAB
  1129.                                     - 19 -A*A*
  1130. PA A
  1131.  
  1132.  
  1133.  
  1134.  
  1135.  
  1136.        RETURNING A CHARACTER
  1137.  
  1138.        Essentially  every scanner I've ever seen  that  was  written  in
  1139.        Pascal  used  the  mechanism of an enumerated type that I've just
  1140.        described.  It is certainly  a workable mechanism, but it doesn't
  1141.        seem the simplest approach to me.
  1142.  
  1143.        For one thing, the  list  of possible symbol types can get pretty
  1144.        long. Here, I've used just one symbol, "Operator,"  to  stand for
  1145.        all of the operators, but I've seen other  designs  that actually
  1146.        return different codes for each one.
  1147.  
  1148.        There is, of course, another simple type that can be  returned as
  1149.        a  code: the character.  Instead  of  returning  the  enumeration
  1150.        value 'Operator' for a '+' sign, what's wrong with just returning
  1151.        the character itself?  A character is just as good a variable for
  1152.        encoding the different  token  types,  it  can  be  used  in case
  1153.        statements  easily, and it's sure a lot easier  to  type.    What
  1154.        could be simpler?
  1155.  
  1156.        Besides, we've already  had  experience with the idea of encoding
  1157.        keywords as single characters.  Our previous programs are already
  1158.        written  that  way,  so  using  this approach will  minimize  the
  1159.        changes to what we've already done.
  1160.  
  1161.        Some of you may feel that this idea of returning  character codes
  1162.        is too mickey-mouse.  I must  admit  it gets a little awkward for
  1163.        multi-character operators like '<='.   If you choose to stay with
  1164.        the  enumerated  type,  fine.  For the rest, I'd like to show you
  1165.        how to change what we've done above to support that approach.
  1166.  
  1167.        First, you can delete the SymType declaration now ... we won't be
  1168.        needing that.  And you can change the type of Token to char.
  1169.  
  1170.        Next, to replace SymType, add the following constant string:
  1171.  
  1172.  
  1173.           const KWcode: string[5] = 'xilee';
  1174.  
  1175.  
  1176.        (I'll be encoding all idents with the single character 'x'.)
  1177.  
  1178.  
  1179.        Lastly, modify Scan and its relatives as follows:AQAQ
  1180.  
  1181.                                     - 20 -A*A*
  1182. PA A
  1183.  
  1184.  
  1185.  
  1186.  
  1187.  
  1188.        {--------------------------------------------------------------}
  1189.        { Get an Identifier }
  1190.  
  1191.        procedure GetName;
  1192.        begin
  1193.           Value := '';
  1194.           if not IsAlpha(Look) then Expected('Name');
  1195.           while IsAlNum(Look) do begin
  1196.             Value := Value + UpCase(Look);
  1197.             GetChar;
  1198.           end;
  1199.           Token := KWcode[Lookup(Addr(KWlist), Value, 4) + 1];
  1200.        end;
  1201.  
  1202.  
  1203.        {--------------------------------------------------------------}
  1204.        { Get a Number }
  1205.  
  1206.        procedure GetNum;
  1207.        begin
  1208.           Value := '';
  1209.           if not IsDigit(Look) then Expected('Integer');
  1210.           while IsDigit(Look) do begin
  1211.             Value := Value + Look;
  1212.             GetChar;
  1213.           end;
  1214.           Token := '#';
  1215.        end;
  1216.  
  1217.  
  1218.        {--------------------------------------------------------------}
  1219.        { Get an Operator }
  1220.  
  1221.        procedure GetOp;
  1222.        begin
  1223.           Value := '';
  1224.           if not IsOp(Look) then Expected('Operator');
  1225.           while IsOp(Look) do begin
  1226.             Value := Value + Look;
  1227.             GetChar;
  1228.           end;
  1229.           if Length(Value) = 1 then
  1230.              Token := Value[1]
  1231.           else
  1232.              Token := '?';
  1233.        end;AEAE
  1234.  
  1235.                                     - 21 -A*A*
  1236. PA A
  1237.  
  1238.  
  1239.  
  1240.  
  1241.  
  1242.        {--------------------------------------------------------------}
  1243.        { Lexical Scanner }
  1244.  
  1245.        procedure Scan;
  1246.        var k: integer;
  1247.        begin
  1248.           while Look = CR do
  1249.              Fin;
  1250.           if IsAlpha(Look) then
  1251.              GetName
  1252.           else if IsDigit(Look) then
  1253.              GetNum
  1254.           else if IsOp(Look) then begin
  1255.              GetOp
  1256.           else begin
  1257.              Value := Look;
  1258.              Token := '?';
  1259.              GetChar;
  1260.           end;
  1261.           SkipWhite;
  1262.        end;
  1263.  
  1264.  
  1265.        {--------------------------------------------------------------}
  1266.        { Main Program }
  1267.  
  1268.  
  1269.        begin
  1270.           Init;
  1271.           repeat
  1272.              Scan;
  1273.              case Token of
  1274.                'x': write('Ident ');
  1275.                '#': Write('Number ');
  1276.                'i', 'l', 'e': Write('Keyword ');
  1277.                else Write('Operator ');
  1278.              end;
  1279.              Writeln(Value);
  1280.           until Value = 'END';
  1281.        end.
  1282.        {--------------------------------------------------------------}
  1283.  
  1284.  
  1285.        This program should  work  the  same  as the previous version.  A
  1286.        minor  difference  in  structure,  maybe,  but   it   seems  more
  1287.        straightforward to me.
  1288.  
  1289.  
  1290.        DISTRIBUTED vs CENTRALIZED SCANNERS
  1291.  
  1292.        The structure for the lexical scanner that I've just shown you is
  1293.        very conventional, and  about  99% of all compilers use something
  1294.        very  close  to it.  This is  not,  however,  the  only  possible
  1295.        structure, or even always the best one.A*A*
  1296.                                     - 22 -
  1297. PA A
  1298.  
  1299.  
  1300.  
  1301.  
  1302.  
  1303.        The problem with the  conventional  approach  is that the scanner
  1304.        has no knowledge of context.  For example,  it  can't distinguish
  1305.        between the assignment operator '=' and  the  relational operator
  1306.        '=' (perhaps that's why both C and Pascal  use  different strings
  1307.        for the  two).    All  the scanner can do is to pass the operator
  1308.        along  to  the  parser, which can hopefully tell from the context
  1309.        which operator is meant.    Similarly, a keyword like 'IF' has no
  1310.        place in the middle of a  math  expression, but if one happens to
  1311.        appear there, the scanner  will  see no problem with it, and will
  1312.        return it to the parser, properly encoded as an 'IF'.
  1313.  
  1314.        With this  kind  of  approach,  we  are  not really using all the
  1315.        information at our disposal.  In the middle of an expression, for
  1316.        example, the parser  "knows"  that  there  is no need to look for
  1317.        keywords,  but it has no way of telling the scanner that.  So the
  1318.        scanner  continues to do so.  This, of  course,  slows  down  the
  1319.        compilation.
  1320.  
  1321.        In real-world compilers, the  designers  often  arrange  for more
  1322.        information  to be passed between parser  and  scanner,  just  to
  1323.        avoid  this  kind of problem.  But  that  can  get  awkward,  and
  1324.        certainly destroys a lot of the modularity of the structure.
  1325.  
  1326.        The  alternative  is  to seek some  way  to  use  the  contextual
  1327.        information that comes from knowing where we are  in  the parser.
  1328.        This leads us  back  to  the  notion of a distributed scanner, in
  1329.        which various portions  of  the scanner are called depending upon
  1330.        the context.
  1331.  
  1332.        In KISS, as  in  most  languages,  keywords  ONLY  appear  at the
  1333.        beginning of a statement.  In places like  expressions,  they are
  1334.        not allowed.  Also, with one minor exception (the multi-character
  1335.        relops)  that  is  easily  handled,  all  operators   are  single
  1336.        characters, which means that we don't need GetOp at all.
  1337.  
  1338.        So it turns out  that  even  with  multi-character tokens, we can
  1339.        still always tell from the  current  lookahead  character exactly
  1340.        what kind of token is coming,  except  at the very beginning of a
  1341.        statement.
  1342.  
  1343.        Even at that point, the ONLY  kind  of  token we can accept is an
  1344.        identifier.  We need only to determine if that  identifier  is  a
  1345.        keyword or the target of an assignment statement.
  1346.  
  1347.        We end up, then, still needing only GetName and GetNum, which are
  1348.        used very much as we've used them in earlier installments.
  1349.  
  1350.        It may seem  at first to you that this is a step backwards, and a
  1351.        rather  primitive  approach.   In fact, it is an improvement over
  1352.        the classical scanner, since we're  using  the  scanning routines
  1353.        only where they're really needed.  In places  where  keywords are
  1354.        not allowed, we don't slow things down by looking for them.ABAB
  1355.                                     - 23 -A*A*
  1356. PA A
  1357.  
  1358.  
  1359.  
  1360.  
  1361.  
  1362.        MERGING SCANNER AND PARSER
  1363.  
  1364.        Now that we've covered  all  of the theory and general aspects of
  1365.        lexical scanning that we'll be needing, I'm FINALLY ready to back
  1366.        up my claim that  we  can  accomodate multi-character tokens with
  1367.        minimal change to our previous work.  To keep  things  short  and
  1368.        simple I will restrict myself here to a subset of what we've done
  1369.        before; I'm allowing only one control construct (the  IF)  and no
  1370.        Boolean expressions.  That's enough to demonstrate the parsing of
  1371.        both keywords and expressions.  The extension to the full  set of
  1372.        constructs should be  pretty  apparent  from  what  we've already
  1373.        done.
  1374.  
  1375.        All  the  elements  of  the  program to parse this subset,  using
  1376.        single-character tokens, exist  already in our previous programs.
  1377.        I built it by judicious copying of these files,  but  I  wouldn't
  1378.        dare try to lead you through that process.  Instead, to avoid any
  1379.        confusion, the whole program is shown below:
  1380.  
  1381.  
  1382.        {--------------------------------------------------------------}
  1383.        program KISS;
  1384.  
  1385.        {--------------------------------------------------------------}
  1386.        { Constant Declarations }
  1387.  
  1388.        const TAB = ^I;
  1389.              CR  = ^M;
  1390.              LF  = ^J;
  1391.  
  1392.        {--------------------------------------------------------------}
  1393.        { Type Declarations  }
  1394.  
  1395.        type Symbol = string[8];
  1396.  
  1397.             SymTab = array[1..1000] of Symbol;
  1398.  
  1399.             TabPtr = ^SymTab;
  1400.  
  1401.  
  1402.        {--------------------------------------------------------------}
  1403.        { Variable Declarations }
  1404.  
  1405.        var Look  : char;              { Lookahead Character }
  1406.            Lcount: integer;           { Label Counter       }
  1407.  
  1408.  
  1409.        {--------------------------------------------------------------}
  1410.        { Read New Character From Input Stream }
  1411.  
  1412.        procedure GetChar;
  1413.        begin
  1414.           Read(Look);
  1415.        end;A*A*
  1416.                                     - 24 -
  1417. PA A
  1418.  
  1419.  
  1420.  
  1421.  
  1422.  
  1423.        {--------------------------------------------------------------}
  1424.        { Report an Error }
  1425.  
  1426.        procedure Error(s: string);
  1427.        begin
  1428.           WriteLn;
  1429.           WriteLn(^G, 'Error: ', s, '.');
  1430.        end;
  1431.  
  1432.  
  1433.        {--------------------------------------------------------------}
  1434.        { Report Error and Halt }
  1435.  
  1436.        procedure Abort(s: string);
  1437.        begin
  1438.           Error(s);
  1439.           Halt;
  1440.        end;
  1441.  
  1442.  
  1443.        {--------------------------------------------------------------}
  1444.        { Report What Was Expected }
  1445.  
  1446.        procedure Expected(s: string);
  1447.        begin
  1448.           Abort(s + ' Expected');
  1449.        end;
  1450.  
  1451.        {--------------------------------------------------------------}
  1452.        { Recognize an Alpha Character }
  1453.  
  1454.        function IsAlpha(c: char): boolean;
  1455.        begin
  1456.           IsAlpha := UpCase(c) in ['A'..'Z'];
  1457.        end;
  1458.  
  1459.  
  1460.        {--------------------------------------------------------------}
  1461.        { Recognize a Decimal Digit }
  1462.  
  1463.        function IsDigit(c: char): boolean;
  1464.        begin
  1465.           IsDigit := c in ['0'..'9'];
  1466.        end;
  1467.  
  1468.  
  1469.        {--------------------------------------------------------------}
  1470.        { Recognize an AlphaNumeric Character }
  1471.  
  1472.        function IsAlNum(c: char): boolean;
  1473.        begin
  1474.           IsAlNum := IsAlpha(c) or IsDigit(c);
  1475.        end;A6A6
  1476.                                     - 25 -A*A*
  1477. PA A
  1478.  
  1479.  
  1480.  
  1481.  
  1482.  
  1483.        {--------------------------------------------------------------}
  1484.        { Recognize an Addop }
  1485.  
  1486.        function IsAddop(c: char): boolean;
  1487.        begin
  1488.           IsAddop := c in ['+', '-'];
  1489.        end;
  1490.  
  1491.  
  1492.        {--------------------------------------------------------------}
  1493.        { Recognize a Mulop }
  1494.  
  1495.        function IsMulop(c: char): boolean;
  1496.        begin
  1497.           IsMulop := c in ['*', '/'];
  1498.        end;
  1499.  
  1500.  
  1501.        {--------------------------------------------------------------}
  1502.        { Recognize White Space }
  1503.  
  1504.        function IsWhite(c: char): boolean;
  1505.        begin
  1506.           IsWhite := c in [' ', TAB];
  1507.        end;
  1508.  
  1509.  
  1510.        {--------------------------------------------------------------}
  1511.        { Skip Over Leading White Space }
  1512.  
  1513.        procedure SkipWhite;
  1514.        begin
  1515.           while IsWhite(Look) do
  1516.              GetChar;
  1517.        end;
  1518.  
  1519.  
  1520.        {--------------------------------------------------------------}
  1521.        { Match a Specific Input Character }
  1522.  
  1523.        procedure Match(x: char);
  1524.        begin
  1525.           if Look <> x then Expected('''' + x + '''');
  1526.           GetChar;
  1527.           SkipWhite;
  1528.        end;
  1529.  
  1530.  
  1531.        {--------------------------------------------------------------}
  1532.        { Skip a CRLF }
  1533.  
  1534.        procedure Fin;
  1535.        begin
  1536.           if Look = CR then GetChar;A*A*
  1537.                                     - 26 -
  1538. PA A
  1539.  
  1540.  
  1541.  
  1542.  
  1543.  
  1544.           if Look = LF then GetChar;
  1545.           SkipWhite;
  1546.        end;
  1547.  
  1548.  
  1549.        {--------------------------------------------------------------}
  1550.        { Get an Identifier }
  1551.  
  1552.        function GetName: char;
  1553.        begin
  1554.           while Look = CR do
  1555.              Fin;
  1556.           if not IsAlpha(Look) then Expected('Name');
  1557.           Getname := UpCase(Look);
  1558.           GetChar;
  1559.           SkipWhite;
  1560.        end;
  1561.  
  1562.  
  1563.        {--------------------------------------------------------------}
  1564.        { Get a Number }
  1565.  
  1566.        function GetNum: char;
  1567.        begin
  1568.           if not IsDigit(Look) then Expected('Integer');
  1569.           GetNum := Look;
  1570.           GetChar;
  1571.           SkipWhite;
  1572.        end;
  1573.  
  1574.  
  1575.        {--------------------------------------------------------------}
  1576.        { Generate a Unique Label }
  1577.  
  1578.        function NewLabel: string;
  1579.        var S: string;
  1580.        begin
  1581.           Str(LCount, S);
  1582.           NewLabel := 'L' + S;
  1583.           Inc(LCount);
  1584.        end;
  1585.  
  1586.  
  1587.        {--------------------------------------------------------------}
  1588.        { Post a Label To Output }
  1589.  
  1590.        procedure PostLabel(L: string);
  1591.        begin
  1592.           WriteLn(L, ':');
  1593.        end;
  1594.  
  1595.  
  1596.        {--------------------------------------------------------------}
  1597.        { Output a String with Tab }A*A*
  1598.                                     - 27 -
  1599. PA A
  1600.  
  1601.  
  1602.  
  1603.  
  1604.  
  1605.        procedure Emit(s: string);
  1606.        begin
  1607.           Write(TAB, s);
  1608.        end;
  1609.  
  1610.  
  1611.        {--------------------------------------------------------------}
  1612.  
  1613.        { Output a String with Tab and CRLF }
  1614.  
  1615.        procedure EmitLn(s: string);
  1616.        begin
  1617.           Emit(s);
  1618.           WriteLn;
  1619.        end;
  1620.  
  1621.  
  1622.        {---------------------------------------------------------------}
  1623.        { Parse and Translate an Identifier }
  1624.  
  1625.        procedure Ident;
  1626.        var Name: char;
  1627.        begin
  1628.           Name := GetName;
  1629.           if Look = '(' then begin
  1630.              Match('(');
  1631.              Match(')');
  1632.              EmitLn('BSR ' + Name);
  1633.              end
  1634.           else
  1635.              EmitLn('MOVE ' + Name + '(PC),D0');
  1636.        end;
  1637.  
  1638.  
  1639.        {---------------------------------------------------------------}
  1640.        { Parse and Translate a Math Factor }
  1641.  
  1642.        procedure Expression; Forward;
  1643.  
  1644.        procedure Factor;
  1645.        begin
  1646.           if Look = '(' then begin
  1647.              Match('(');
  1648.              Expression;
  1649.              Match(')');
  1650.              end
  1651.           else if IsAlpha(Look) then
  1652.              Ident
  1653.           else
  1654.              EmitLn('MOVE #' + GetNum + ',D0');
  1655.        end;
  1656.  
  1657.  
  1658.        {---------------------------------------------------------------}A*A*
  1659.                                     - 28 -
  1660. PA A
  1661.  
  1662.  
  1663.  
  1664.  
  1665.  
  1666.        { Parse and Translate the First Math Factor }
  1667.  
  1668.  
  1669.        procedure SignedFactor;
  1670.        var s: boolean;
  1671.        begin
  1672.           s := Look = '-';
  1673.           if IsAddop(Look) then begin
  1674.              GetChar;
  1675.              SkipWhite;
  1676.           end;
  1677.           Factor;
  1678.           if s then
  1679.              EmitLn('NEG D0');
  1680.        end;
  1681.  
  1682.  
  1683.        {--------------------------------------------------------------}
  1684.        { Recognize and Translate a Multiply }
  1685.  
  1686.        procedure Multiply;
  1687.        begin
  1688.           Match('*');
  1689.           Factor;
  1690.           EmitLn('MULS (SP)+,D0');
  1691.        end;
  1692.  
  1693.  
  1694.        {-------------------------------------------------------------}
  1695.        { Recognize and Translate a Divide }
  1696.  
  1697.        procedure Divide;
  1698.        begin
  1699.           Match('/');
  1700.           Factor;
  1701.           EmitLn('MOVE (SP)+,D1');
  1702.           EmitLn('EXS.L D0');
  1703.           EmitLn('DIVS D1,D0');
  1704.        end;
  1705.  
  1706.  
  1707.        {---------------------------------------------------------------}
  1708.        { Completion of Term Processing  (called by Term and FirstTerm }
  1709.  
  1710.        procedure Term1;
  1711.        begin
  1712.           while IsMulop(Look) do begin
  1713.              EmitLn('MOVE D0,-(SP)');
  1714.              case Look of
  1715.               '*': Multiply;
  1716.               '/': Divide;
  1717.              end;
  1718.           end;
  1719.        end;A*A*
  1720.                                     - 29 -
  1721. PA A
  1722.  
  1723.  
  1724.  
  1725.  
  1726.  
  1727.        {---------------------------------------------------------------}
  1728.        { Parse and Translate a Math Term }
  1729.  
  1730.        procedure Term;
  1731.        begin
  1732.           Factor;
  1733.           Term1;
  1734.        end;
  1735.  
  1736.  
  1737.        {---------------------------------------------------------------}
  1738.        { Parse and Translate a Math Term with Possible Leading Sign }
  1739.  
  1740.        procedure FirstTerm;
  1741.        begin
  1742.           SignedFactor;
  1743.           Term1;
  1744.        end;
  1745.  
  1746.  
  1747.        {---------------------------------------------------------------}
  1748.        { Recognize and Translate an Add }
  1749.  
  1750.        procedure Add;
  1751.        begin
  1752.           Match('+');
  1753.           Term;
  1754.           EmitLn('ADD (SP)+,D0');
  1755.        end;
  1756.  
  1757.  
  1758.        {---------------------------------------------------------------}
  1759.        { Recognize and Translate a Subtract }
  1760.  
  1761.        procedure Subtract;
  1762.        begin
  1763.           Match('-');
  1764.           Term;
  1765.           EmitLn('SUB (SP)+,D0');
  1766.           EmitLn('NEG D0');
  1767.        end;
  1768.  
  1769.  
  1770.        {---------------------------------------------------------------}
  1771.        { Parse and Translate an Expression }
  1772.  
  1773.        procedure Expression;
  1774.        begin
  1775.           FirstTerm;
  1776.           while IsAddop(Look) do begin
  1777.              EmitLn('MOVE D0,-(SP)');
  1778.              case Look of
  1779.               '+': Add;
  1780.               '-': Subtract;A*A*
  1781.                                     - 30 -
  1782. PA A
  1783.  
  1784.  
  1785.  
  1786.  
  1787.  
  1788.              end;
  1789.           end;
  1790.        end;
  1791.  
  1792.  
  1793.        {---------------------------------------------------------------}
  1794.        { Parse and Translate a Boolean Condition }
  1795.        { This version is a dummy }
  1796.  
  1797.        Procedure Condition;
  1798.        begin
  1799.           EmitLn('Condition');
  1800.        end;
  1801.  
  1802.  
  1803.        {---------------------------------------------------------------}
  1804.        { Recognize and Translate an IF Construct }
  1805.  
  1806.        procedure Block;
  1807.         Forward;
  1808.  
  1809.        procedure DoIf;
  1810.        var L1, L2: string;
  1811.        begin
  1812.           Match('i');
  1813.           Condition;
  1814.           L1 := NewLabel;
  1815.           L2 := L1;
  1816.           EmitLn('BEQ ' + L1);
  1817.           Block;
  1818.           if Look = 'l' then begin
  1819.              Match('l');
  1820.              L2 := NewLabel;
  1821.              EmitLn('BRA ' + L2);
  1822.              PostLabel(L1);
  1823.              Block;
  1824.           end;
  1825.           PostLabel(L2);
  1826.           Match('e');
  1827.        end;
  1828.  
  1829.  
  1830.        {--------------------------------------------------------------}
  1831.        { Parse and Translate an Assignment Statement }
  1832.  
  1833.        procedure Assignment;
  1834.        var Name: char;
  1835.        begin
  1836.           Name := GetName;
  1837.           Match('=');
  1838.           Expression;
  1839.           EmitLn('LEA ' + Name + '(PC),A0');
  1840.           EmitLn('MOVE D0,(A0)');
  1841.        end;A*A*
  1842.                                     - 31 -
  1843. PA A
  1844.  
  1845.  
  1846.  
  1847.  
  1848.  
  1849.        {--------------------------------------------------------------}
  1850.        { Recognize and Translate a Statement Block }
  1851.  
  1852.        procedure Block;
  1853.        begin
  1854.           while not(Look in ['e', 'l']) do begin
  1855.              case Look of
  1856.               'i': DoIf;
  1857.               CR: while Look = CR do
  1858.                      Fin;
  1859.               else Assignment;
  1860.              end;
  1861.           end;
  1862.        end;
  1863.  
  1864.  
  1865.        {--------------------------------------------------------------}
  1866.        { Parse and Translate a Program }
  1867.  
  1868.        procedure DoProgram;
  1869.        begin
  1870.           Block;
  1871.           if Look <> 'e' then Expected('END');
  1872.           EmitLn('END')
  1873.        end;
  1874.  
  1875.  
  1876.        {--------------------------------------------------------------}
  1877.  
  1878.        { Initialize }
  1879.  
  1880.        procedure Init;
  1881.        begin
  1882.           LCount := 0;
  1883.           GetChar;
  1884.        end;
  1885.  
  1886.  
  1887.        {--------------------------------------------------------------}
  1888.        { Main Program }
  1889.  
  1890.        begin
  1891.           Init;
  1892.           DoProgram;
  1893.        end.
  1894.        {--------------------------------------------------------------}
  1895.  
  1896.  
  1897.        A couple of comments:
  1898.  
  1899.         (1) The form for the expression parser,  using  FirstTerm, etc.,
  1900.             is  a  little  different from what you've seen before.  It's
  1901.             yet another variation on the same theme.  Don't let it throw
  1902.             you ... the change is not required for what follows.A*A*
  1903.                                     - 32 -
  1904. PA A
  1905.  
  1906.  
  1907.  
  1908.  
  1909.  
  1910.         (2) Note that, as usual, I had to add calls to Fin  at strategic
  1911.             spots to allow for multiple lines.
  1912.  
  1913.        Before we proceed to adding the scanner, first copy this file and
  1914.        verify that it does indeed  parse things correctly.  Don't forget
  1915.        the "codes": 'i' for IF, 'l' for ELSE, and 'e' for END or ENDIF.
  1916.  
  1917.        If the program works, then let's press on.  In adding the scanner
  1918.        modules to the program, it helps  to  have a systematic plan.  In
  1919.        all  the  parsers  we've  written  to  date,  we've  stuck  to  a
  1920.        convention that the current lookahead character should  always be
  1921.        a non-blank character.  We  preload  the  lookahead  character in
  1922.        Init, and keep the "pump primed"  after  that.  To keep the thing
  1923.        working right at newlines, we had to modify this a bit  and treat
  1924.        the newline as a legal token.
  1925.  
  1926.        In the  multi-character version, the rule is similar: The current
  1927.        lookahead character should always be left at the BEGINNING of the
  1928.        next token, or at a newline.
  1929.  
  1930.        The multi-character version is shown next.  To get it,  I've made
  1931.        the following changes:
  1932.  
  1933.  
  1934.         o Added the variables Token  and Value, and the type definitions
  1935.           needed by Lookup.
  1936.  
  1937.         o Added the definitions of KWList and KWcode.
  1938.  
  1939.         o Added Lookup.
  1940.  
  1941.         o Replaced GetName and GetNum by their multi-character versions.
  1942.           (Note that the call  to  Lookup has been moved out of GetName,
  1943.           so  that  it  will  not   be  executed  for  calls  within  an
  1944.           expression.)
  1945.  
  1946.         o Created a new,  vestigial  Scan that calls GetName, then scans
  1947.           for keywords.
  1948.  
  1949.         o Created  a  new  procedure,  MatchString,  that  looks  for  a
  1950.           specific keyword.  Note that, unlike  Match,  MatchString does
  1951.           NOT read the next keyword.
  1952.  
  1953.         o Modified Block to call Scan.
  1954.  
  1955.         o Changed the calls  to  Fin  a  bit.   Fin is now called within
  1956.           GetName.
  1957.  
  1958.        Here is the program in its entirety:
  1959.  
  1960.  
  1961.        {--------------------------------------------------------------}
  1962.        program KISS;A6A6
  1963.                                     - 33 -A*A*
  1964. PA A
  1965.  
  1966.  
  1967.  
  1968.  
  1969.  
  1970.        {--------------------------------------------------------------}
  1971.        { Constant Declarations }
  1972.  
  1973.        const TAB = ^I;
  1974.              CR  = ^M;
  1975.              LF  = ^J;
  1976.  
  1977.        {--------------------------------------------------------------}
  1978.        { Type Declarations  }
  1979.  
  1980.        type Symbol = string[8];
  1981.  
  1982.             SymTab = array[1..1000] of Symbol;
  1983.  
  1984.             TabPtr = ^SymTab;
  1985.  
  1986.  
  1987.        {--------------------------------------------------------------}
  1988.        { Variable Declarations }
  1989.  
  1990.        var Look  : char;              { Lookahead Character }
  1991.            Token : char;              { Encoded Token       }
  1992.            Value : string[16];        { Unencoded Token     }
  1993.            Lcount: integer;           { Label Counter       }
  1994.  
  1995.  
  1996.        {--------------------------------------------------------------}
  1997.        { Definition of Keywords and Token Types }
  1998.  
  1999.        const KWlist: array [1..4] of Symbol =
  2000.                      ('IF', 'ELSE', 'ENDIF', 'END');
  2001.  
  2002.        const KWcode: string[5] = 'xilee';
  2003.  
  2004.  
  2005.        {--------------------------------------------------------------}
  2006.        { Read New Character From Input Stream }
  2007.  
  2008.        procedure GetChar;
  2009.        begin
  2010.           Read(Look);
  2011.        end;
  2012.  
  2013.        {--------------------------------------------------------------}
  2014.        { Report an Error }
  2015.  
  2016.        procedure Error(s: string);
  2017.        begin
  2018.           WriteLn;
  2019.           WriteLn(^G, 'Error: ', s, '.');
  2020.        end;
  2021.  
  2022.  
  2023.        {--------------------------------------------------------------}A*A*
  2024.                                     - 34 -
  2025. PA A
  2026.  
  2027.  
  2028.  
  2029.  
  2030.  
  2031.        { Report Error and Halt }
  2032.  
  2033.        procedure Abort(s: string);
  2034.        begin
  2035.           Error(s);
  2036.           Halt;
  2037.        end;
  2038.  
  2039.  
  2040.        {--------------------------------------------------------------}
  2041.        { Report What Was Expected }
  2042.  
  2043.        procedure Expected(s: string);
  2044.        begin
  2045.           Abort(s + ' Expected');
  2046.        end;
  2047.  
  2048.        {--------------------------------------------------------------}
  2049.        { Recognize an Alpha Character }
  2050.  
  2051.        function IsAlpha(c: char): boolean;
  2052.        begin
  2053.           IsAlpha := UpCase(c) in ['A'..'Z'];
  2054.        end;
  2055.  
  2056.  
  2057.        {--------------------------------------------------------------}
  2058.        { Recognize a Decimal Digit }
  2059.  
  2060.        function IsDigit(c: char): boolean;
  2061.        begin
  2062.           IsDigit := c in ['0'..'9'];
  2063.        end;
  2064.  
  2065.  
  2066.        {--------------------------------------------------------------}
  2067.        { Recognize an AlphaNumeric Character }
  2068.  
  2069.        function IsAlNum(c: char): boolean;
  2070.        begin
  2071.           IsAlNum := IsAlpha(c) or IsDigit(c);
  2072.        end;
  2073.  
  2074.  
  2075.        {--------------------------------------------------------------}
  2076.        { Recognize an Addop }
  2077.  
  2078.        function IsAddop(c: char): boolean;
  2079.        begin
  2080.           IsAddop := c in ['+', '-'];
  2081.        end;
  2082.  
  2083.  
  2084.        {--------------------------------------------------------------}A*A*
  2085.                                     - 35 -
  2086. PA A
  2087.  
  2088.  
  2089.  
  2090.  
  2091.  
  2092.        { Recognize a Mulop }
  2093.  
  2094.        function IsMulop(c: char): boolean;
  2095.        begin
  2096.           IsMulop := c in ['*', '/'];
  2097.        end;
  2098.  
  2099.  
  2100.        {--------------------------------------------------------------}
  2101.        { Recognize White Space }
  2102.  
  2103.        function IsWhite(c: char): boolean;
  2104.        begin
  2105.           IsWhite := c in [' ', TAB];
  2106.        end;
  2107.  
  2108.  
  2109.        {--------------------------------------------------------------}
  2110.        { Skip Over Leading White Space }
  2111.  
  2112.        procedure SkipWhite;
  2113.        begin
  2114.           while IsWhite(Look) do
  2115.              GetChar;
  2116.        end;
  2117.  
  2118.  
  2119.        {--------------------------------------------------------------}
  2120.        { Match a Specific Input Character }
  2121.  
  2122.        procedure Match(x: char);
  2123.        begin
  2124.           if Look <> x then Expected('''' + x + '''');
  2125.           GetChar;
  2126.           SkipWhite;
  2127.        end;
  2128.  
  2129.  
  2130.        {--------------------------------------------------------------}
  2131.        { Skip a CRLF }
  2132.  
  2133.        procedure Fin;
  2134.        begin
  2135.           if Look = CR then GetChar;
  2136.           if Look = LF then GetChar;
  2137.           SkipWhite;
  2138.        end;
  2139.  
  2140.  
  2141.        {--------------------------------------------------------------}
  2142.        { Table Lookup }
  2143.  
  2144.        function Lookup(T: TabPtr; s: string; n: integer): integer;
  2145.        var i: integer;A*A*
  2146.                                     - 36 -
  2147. PA A
  2148.  
  2149.  
  2150.  
  2151.  
  2152.  
  2153.            found: boolean;
  2154.        begin
  2155.           found := false;
  2156.           i := n;
  2157.           while (i > 0) and not found do
  2158.              if s = T^[i] then
  2159.                 found := true
  2160.              else
  2161.                 dec(i);
  2162.           Lookup := i;
  2163.        end;
  2164.  
  2165.  
  2166.        {--------------------------------------------------------------}
  2167.        { Get an Identifier }
  2168.  
  2169.        procedure GetName;
  2170.        begin
  2171.           while Look = CR do
  2172.              Fin;
  2173.           if not IsAlpha(Look) then Expected('Name');
  2174.           Value := '';
  2175.           while IsAlNum(Look) do begin
  2176.             Value := Value + UpCase(Look);
  2177.             GetChar;
  2178.           end;
  2179.           SkipWhite;
  2180.        end;
  2181.  
  2182.  
  2183.        {--------------------------------------------------------------}
  2184.        { Get a Number }
  2185.  
  2186.        procedure GetNum;
  2187.        begin
  2188.           if not IsDigit(Look) then Expected('Integer');
  2189.           Value := '';
  2190.           while IsDigit(Look) do begin
  2191.             Value := Value + Look;
  2192.             GetChar;
  2193.           end;
  2194.           Token := '#';
  2195.           SkipWhite;
  2196.        end;
  2197.  
  2198.  
  2199.        {--------------------------------------------------------------}
  2200.        { Get an Identifier and Scan it for Keywords }
  2201.  
  2202.        procedure Scan;
  2203.        begin
  2204.           GetName;
  2205.           Token := KWcode[Lookup(Addr(KWlist), Value, 4) + 1];
  2206.        end;A*A*
  2207.                                     - 37 -
  2208. PA A
  2209.  
  2210.  
  2211.  
  2212.  
  2213.  
  2214.        {--------------------------------------------------------------}
  2215.        { Match a Specific Input String }
  2216.  
  2217.        procedure MatchString(x: string);
  2218.        begin
  2219.           if Value <> x then Expected('''' + x + '''');
  2220.        end;
  2221.  
  2222.  
  2223.        {--------------------------------------------------------------}
  2224.        { Generate a Unique Label }
  2225.  
  2226.        function NewLabel: string;
  2227.        var S: string;
  2228.        begin
  2229.           Str(LCount, S);
  2230.           NewLabel := 'L' + S;
  2231.           Inc(LCount);
  2232.        end;
  2233.  
  2234.  
  2235.        {--------------------------------------------------------------}
  2236.        { Post a Label To Output }
  2237.  
  2238.        procedure PostLabel(L: string);
  2239.        begin
  2240.           WriteLn(L, ':');
  2241.        end;
  2242.  
  2243.  
  2244.        {--------------------------------------------------------------}
  2245.        { Output a String with Tab }
  2246.  
  2247.        procedure Emit(s: string);
  2248.        begin
  2249.           Write(TAB, s);
  2250.        end;
  2251.  
  2252.  
  2253.        {--------------------------------------------------------------}
  2254.        { Output a String with Tab and CRLF }
  2255.  
  2256.        procedure EmitLn(s: string);
  2257.        begin
  2258.           Emit(s);
  2259.           WriteLn;
  2260.        end;
  2261.  
  2262.  
  2263.        {---------------------------------------------------------------}
  2264.        { Parse and Translate an Identifier }
  2265.  
  2266.        procedure Ident;
  2267.        beginA*A*
  2268.                                     - 38 -
  2269. PA A
  2270.  
  2271.  
  2272.  
  2273.  
  2274.  
  2275.           GetName;
  2276.           if Look = '(' then begin
  2277.              Match('(');
  2278.              Match(')');
  2279.              EmitLn('BSR ' + Value);
  2280.              end
  2281.           else
  2282.              EmitLn('MOVE ' + Value + '(PC),D0');
  2283.        end;
  2284.  
  2285.  
  2286.        {---------------------------------------------------------------}
  2287.        { Parse and Translate a Math Factor }
  2288.  
  2289.        procedure Expression; Forward;
  2290.  
  2291.        procedure Factor;
  2292.        begin
  2293.           if Look = '(' then begin
  2294.              Match('(');
  2295.              Expression;
  2296.              Match(')');
  2297.              end
  2298.           else if IsAlpha(Look) then
  2299.              Ident
  2300.           else begin
  2301.              GetNum;
  2302.              EmitLn('MOVE #' + Value + ',D0');
  2303.           end;
  2304.        end;
  2305.  
  2306.  
  2307.        {---------------------------------------------------------------}
  2308.        { Parse and Translate the First Math Factor }
  2309.  
  2310.        procedure SignedFactor;
  2311.        var s: boolean;
  2312.        begin
  2313.           s := Look = '-';
  2314.           if IsAddop(Look) then begin
  2315.              GetChar;
  2316.              SkipWhite;
  2317.           end;
  2318.           Factor;
  2319.           if s then
  2320.              EmitLn('NEG D0');
  2321.        end;
  2322.  
  2323.  
  2324.        {--------------------------------------------------------------}
  2325.        { Recognize and Translate a Multiply }
  2326.  
  2327.        procedure Multiply;
  2328.        beginA*A*
  2329.                                     - 39 -
  2330. PA A
  2331.  
  2332.  
  2333.  
  2334.  
  2335.  
  2336.           Match('*');
  2337.           Factor;
  2338.           EmitLn('MULS (SP)+,D0');
  2339.        end;
  2340.  
  2341.  
  2342.        {-------------------------------------------------------------}
  2343.        { Recognize and Translate a Divide }
  2344.  
  2345.        procedure Divide;
  2346.        begin
  2347.           Match('/');
  2348.           Factor;
  2349.           EmitLn('MOVE (SP)+,D1');
  2350.           EmitLn('EXS.L D0');
  2351.           EmitLn('DIVS D1,D0');
  2352.        end;
  2353.  
  2354.  
  2355.        {---------------------------------------------------------------}
  2356.        { Completion of Term Processing  (called by Term and FirstTerm }
  2357.  
  2358.        procedure Term1;
  2359.        begin
  2360.           while IsMulop(Look) do begin
  2361.              EmitLn('MOVE D0,-(SP)');
  2362.              case Look of
  2363.               '*': Multiply;
  2364.               '/': Divide;
  2365.              end;
  2366.           end;
  2367.        end;
  2368.        {---------------------------------------------------------------}
  2369.        { Parse and Translate a Math Term }
  2370.  
  2371.        procedure Term;
  2372.        begin
  2373.           Factor;
  2374.           Term1;
  2375.        end;
  2376.  
  2377.  
  2378.        {---------------------------------------------------------------}
  2379.        { Parse and Translate a Math Term with Possible Leading Sign }
  2380.  
  2381.        procedure FirstTerm;
  2382.        begin
  2383.           SignedFactor;
  2384.           Term1;
  2385.        end;
  2386.  
  2387.  
  2388.        {---------------------------------------------------------------}
  2389.        { Recognize and Translate an Add }A*A*
  2390.                                     - 40 -
  2391. PA A
  2392.  
  2393.  
  2394.  
  2395.  
  2396.  
  2397.        procedure Add;
  2398.        begin
  2399.           Match('+');
  2400.           Term;
  2401.           EmitLn('ADD (SP)+,D0');
  2402.        end;
  2403.  
  2404.  
  2405.        {---------------------------------------------------------------}
  2406.        { Recognize and Translate a Subtract }
  2407.  
  2408.        procedure Subtract;
  2409.        begin
  2410.           Match('-');
  2411.           Term;
  2412.           EmitLn('SUB (SP)+,D0');
  2413.           EmitLn('NEG D0');
  2414.        end;
  2415.  
  2416.  
  2417.        {---------------------------------------------------------------}
  2418.        { Parse and Translate an Expression }
  2419.  
  2420.        procedure Expression;
  2421.        begin
  2422.           FirstTerm;
  2423.           while IsAddop(Look) do begin
  2424.              EmitLn('MOVE D0,-(SP)');
  2425.              case Look of
  2426.               '+': Add;
  2427.               '-': Subtract;
  2428.              end;
  2429.           end;
  2430.        end;
  2431.  
  2432.  
  2433.        {---------------------------------------------------------------}
  2434.        { Parse and Translate a Boolean Condition }
  2435.        { This version is a dummy }
  2436.  
  2437.        Procedure Condition;
  2438.        begin
  2439.           EmitLn('Condition');
  2440.        end;
  2441.  
  2442.  
  2443.        {---------------------------------------------------------------}
  2444.        { Recognize and Translate an IF Construct }
  2445.  
  2446.        procedure Block; Forward;
  2447.  
  2448.  
  2449.        procedure DoIf;
  2450.        var L1, L2: string;A*A*
  2451.                                     - 41 -
  2452. PA A
  2453.  
  2454.  
  2455.  
  2456.  
  2457.  
  2458.        begin
  2459.           Condition;
  2460.           L1 := NewLabel;
  2461.           L2 := L1;
  2462.           EmitLn('BEQ ' + L1);
  2463.           Block;
  2464.           if Token = 'l' then begin
  2465.              L2 := NewLabel;
  2466.              EmitLn('BRA ' + L2);
  2467.              PostLabel(L1);
  2468.              Block;
  2469.           end;
  2470.           PostLabel(L2);
  2471.           MatchString('ENDIF');
  2472.        end;
  2473.  
  2474.  
  2475.        {--------------------------------------------------------------}
  2476.        { Parse and Translate an Assignment Statement }
  2477.  
  2478.        procedure Assignment;
  2479.        var Name: string;
  2480.        begin
  2481.           Name := Value;
  2482.           Match('=');
  2483.           Expression;
  2484.           EmitLn('LEA ' + Name + '(PC),A0');
  2485.           EmitLn('MOVE D0,(A0)');
  2486.        end;
  2487.  
  2488.  
  2489.        {--------------------------------------------------------------}
  2490.        { Recognize and Translate a Statement Block }
  2491.  
  2492.        procedure Block;
  2493.        begin
  2494.           Scan;
  2495.           while not (Token in ['e', 'l']) do begin
  2496.              case Token of
  2497.               'i': DoIf;
  2498.               else Assignment;
  2499.              end;
  2500.              Scan;
  2501.           end;
  2502.        end;
  2503.  
  2504.  
  2505.        {--------------------------------------------------------------}
  2506.  
  2507.        { Parse and Translate a Program }
  2508.  
  2509.        procedure DoProgram;
  2510.        begin
  2511.           Block;A*A*
  2512.                                     - 42 -
  2513. PA A
  2514.  
  2515.  
  2516.  
  2517.  
  2518.  
  2519.           MatchString('END');
  2520.           EmitLn('END')
  2521.        end;
  2522.  
  2523.  
  2524.        {--------------------------------------------------------------}
  2525.  
  2526.        { Initialize }
  2527.  
  2528.        procedure Init;
  2529.        begin
  2530.           LCount := 0;
  2531.           GetChar;
  2532.        end;
  2533.  
  2534.  
  2535.        {--------------------------------------------------------------}
  2536.        { Main Program }
  2537.  
  2538.        begin
  2539.           Init;
  2540.           DoProgram;
  2541.        end.
  2542.        {--------------------------------------------------------------}
  2543.  
  2544.  
  2545.        Compare this program with its  single-character  counterpart.   I
  2546.        think you will agree that the differences are minor.
  2547.  
  2548.  
  2549.        CONCLUSION
  2550.  
  2551.        At this point, you have learned how to parse  and  generate  code
  2552.        for expressions,  Boolean  expressions,  and  control structures.
  2553.        You have now learned how to develop lexical scanners, and  how to
  2554.        incorporate their elements into a translator.  You have still not
  2555.        seen ALL the elements combined into one program, but on the basis
  2556.        of  what  we've  done before you should find it a straightforward
  2557.        matter to extend our earlier programs to include scanners.
  2558.  
  2559.        We are very  close  to  having  all  the elements that we need to
  2560.        build a real, functional compiler.  There are still a  few things
  2561.        missing, notably procedure  calls  and type definitions.  We will
  2562.        deal with  those  in  the  next  few  sessions.  Before doing so,
  2563.        however, I thought it  would  be fun to turn the translator above
  2564.        into a true compiler.  That's what we'll  be  doing  in  the next
  2565.        installment.
  2566.  
  2567.        Up till now, we've taken  a rather bottom-up approach to parsing,
  2568.        beginning with low-level constructs and working our way  up.   In
  2569.        the next installment,  I'll  also  be  taking a look from the top
  2570.        down,  and  we'll  discuss how the structure of the translator is
  2571.        altered by changes in the language definition.A6A6
  2572.                                     - 43 -A*A*
  2573. PA A
  2574.  
  2575.  
  2576.  
  2577.  
  2578.  
  2579.        See you then.
  2580.  
  2581.        *****************************************************************
  2582.        *                                                               *
  2583.        *                        COPYRIGHT NOTICE                       *
  2584.        *                                                               *
  2585.        *   Copyright (C) 1988 Jack W. Crenshaw. All rights reserved.   *
  2586.        *                                                               *
  2587.        *****************************************************************AUAU
  2588.  
  2589.  
  2590.  
  2591.  
  2592.  
  2593. AHAH
  2594.                                     - 44 -A*A*
  2595. @