home *** CD-ROM | disk | FTP | other *** search
/ Power Programming / powerprogramming1994.iso / progtool / turbopas / tutorpas.arc / TUTOR1.DOC < prev    next >
Text File  |  1988-07-30  |  17KB  |  462 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.                                   24 July 1988
  35.  
  36.  
  37.                               Part I: INTRODUCTION
  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.  
  85.        This series of articles is a tutorial on the theory  and practice
  86.        of  developing language parsers and compilers.    Before  we  are
  87.        finished,  we  will  have  covered  every   aspect   of  compiler
  88.        construction, designed a new programming  language,  and  built a
  89.        working compiler.
  90.  
  91.        Though I am not a computer scientist by education (my Ph.D. is in
  92.        a different  field, Physics), I have been interested in compilers
  93.        for many years.  I have  bought  and tried to digest the contents
  94.        of virtually every  book  on  the  subject ever written.  I don't
  95.        mind  telling you that it was slow going.    Compiler  texts  are
  96.        written for Computer  Science  majors, and are tough sledding for
  97.        the rest of us.  But over the years a bit of it began to seep in.
  98.        What really caused it to jell was when I began  to  branch off on
  99.        my own and begin to try things on my own computer.  Now I plan to
  100.        share with you what I have  learned.    At the end of this series
  101.        you will by no means be  a  computer scientist, nor will you know
  102.        all the esoterics of  compiler  theory.    I intend to completely
  103.        ignore the more theoretical  aspects  of  the  subject.  What you
  104.        _WILL_ know is all  the  practical aspects that one needs to know
  105.        to build a working system.
  106.  
  107.        This is a "learn-by-doing" series.  In the course of the series I
  108.        will be performing  experiments  on  a  computer.    You  will be
  109.        expected to follow along,  repeating  the  experiments that I do,
  110.        and  performing  some  on your own.  I will be using Turbo Pascal
  111.        4.0 on a PC  clone.   I will periodically insert examples written
  112.        in TP.  These will be executable code, which you will be expected
  113.        to copy into your own computer and run.  If you don't have a copy
  114.        of  Turbo,  you  will be severely limited in how well you will be
  115.        able to follow what's going on.  If you don't have a copy, I urge
  116.        you to get one.  After  all,  it's an excellent product, good for
  117.        many other uses!
  118.  
  119.        Some articles on compilers show you examples, or show you  (as in
  120.        the case of Small-C) a finished product, which you can  then copy
  121.        and  use without a whole lot of understanding of how it works.  I
  122.        hope to do much more  than  that.    I  hope to teach you HOW the
  123.        things get done,  so that you can go off on your own and not only
  124.        reproduce what I have done, but improve on it.ABAB
  125.                                      - 2 -A*A*
  126. PA A
  127.  
  128.  
  129.  
  130.  
  131.  
  132.        This is admittedly an ambitious undertaking, and it won't be done
  133.        in  one page.  I expect to do it in the course  of  a  number  of
  134.        articles.    Each  article will cover a single aspect of compiler
  135.        theory,  and  will  pretty  much  stand  alone.   If  all  you're
  136.        interested in at a given time is one  aspect,  then  you  need to
  137.        look only at that one article.  Each article will be  uploaded as
  138.        it  is complete, so you will have to wait for the last one before
  139.        you can consider yourself finished.  Please be patient.
  140.  
  141.        The average text on  compiler  theory covers a lot of ground that
  142.        we won't be covering here.  The typical sequence is:
  143.  
  144.         o An introductory chapter describing what a compiler is.
  145.  
  146.         o A chapter or two on syntax equations, using Backus-Naur Form
  147.           (BNF).
  148.  
  149.         o A chapter or two on lexical scanning, with emphasis on
  150.           deterministic and non-deterministic finite automata.
  151.  
  152.         o Several chapters on parsing theory, beginning with top-down
  153.           recursive descent, and ending with LALR parsers.
  154.  
  155.         o A chapter on intermediate languages, with emphasis on P-code
  156.           and similar reverse polish representations.
  157.  
  158.         o Many chapters on alternative ways to handle subroutines and
  159.           parameter passing, type declarations, and such.
  160.  
  161.         o A chapter toward the end on code generation, usually for some
  162.           imaginary CPU with a simple instruction set.  Most readers
  163.           (and in fact, most college classes) never make it this far.
  164.  
  165.         o A final chapter or two on optimization. This chapter often
  166.           goes unread, too.
  167.  
  168.  
  169.        I'll  be taking a much different approach in  this  series.    To
  170.        begin  with,  I  won't dwell long on options.  I'll be giving you
  171.        _A_ way that works.  If you want  to  explore  options,  well and
  172.        good ...  I  encourage  you  to do so ... but I'll be sticking to
  173.        what I know.   I also will skip over most of the theory that puts
  174.        people  to  sleep.  Don't get me  wrong:  I  don't  belittle  the
  175.        theory, and it's vitally important  when it comes to dealing with
  176.        the more tricky  parts  of  a  given  language.  But I believe in
  177.        putting first things first.    Here we'll be dealing with the 95%
  178.        of compiler techniques that don't need a lot of theory to handle.
  179.  
  180.        I  also  will  discuss only one approach  to  parsing:  top-down,
  181.        recursive descent parsing, which is the  _ONLY_  technique that's
  182.        at  all   amenable  to  hand-crafting  a  compiler.    The  other
  183.        approaches are only useful if you have a tool like YACC, and also
  184.        don't care how much memory space the final product uses.A6A6
  185.                                      - 3 -A*A*
  186. PA A
  187.  
  188.  
  189.  
  190.  
  191.  
  192.        I  also take a page from the work of Ron Cain, the author of  the
  193.        original Small C.  Whereas almost all other compiler authors have
  194.        historically  used  an  intermediate  language  like  P-code  and
  195.        divided  the  compiler  into two parts (a front end that produces
  196.        P-code,  and   a  back  end  that  processes  P-code  to  produce
  197.        executable   object  code),  Ron  showed  us   that   it   is   a
  198.        straightforward  matter  to  make  a  compiler  directly  produce
  199.        executable  object  code,  in  the  form  of  assembler  language
  200.        statements.  The code will _NOT_ be the world's tightest code ...
  201.        producing optimized code is  a  much  more  difficult job. But it
  202.        will work, and work reasonably well.  Just so that I  don't leave
  203.        you with the impression that our end product will be worthless, I
  204.        _DO_ intend to show you how  to  "soup up" the compiler with some
  205.        optimization.
  206.  
  207.        Finally, I'll be  using  some  tricks  that I've found to be most
  208.        helpful in letting  me  understand what's going on without wading
  209.        through a lot of boiler plate.  Chief among these  is  the use of
  210.        single-character tokens, with no embedded spaces,  for  the early
  211.        design work.  I figure that  if  I  can get a parser to recognize
  212.        and deal with I-T-L, I can  get  it  to do the same with IF-THEN-
  213.        ELSE.  And I can.  In the second "lesson,"   I'll  show  you just
  214.        how easy it  is  to  extend  a  simple parser to handle tokens of
  215.        arbitrary length.  As another  trick,  I  completely  ignore file
  216.        I/O, figuring that  if  I  can  read source from the keyboard and
  217.        output object to the screen, I can also do it from/to disk files.
  218.        Experience  has  proven  that  once  a   translator   is  working
  219.        correctly, it's a  straightforward  matter to redirect the I/O to
  220.        files.    The last trick is that I make no attempt  to  do  error
  221.        correction/recovery.   The   programs   we'll  be  building  will
  222.        RECOGNIZE errors, and will not CRASH, but they  will  simply stop
  223.        on the first error ... just like good ol' Turbo does.  There will
  224.        be  other tricks that you'll see as you go. Most of them can't be
  225.        found in any compiler textbook, but they work.
  226.  
  227.        A word about style and efficiency.    As  you will see, I tend to
  228.        write programs in  _VERY_  small, easily understood pieces.  None
  229.        of the procedures we'll  be  working with will be more than about
  230.        15-20 lines long.  I'm a fervent devotee  of  the  KISS  (Keep It
  231.        Simple, Sidney) school of software development.  I  try  to never
  232.        do something tricky or  complex,  when  something simple will do.
  233.        Inefficient?  Perhaps, but you'll like the  results.    As  Brian
  234.        Kernighan has said,  FIRST  make  it  run, THEN make it run fast.
  235.        If, later on,  you want to go back and tighten up the code in one
  236.        of  our products, you'll be able to do so, since the code will be
  237.        quite understandable. If you  do  so, however, I urge you to wait
  238.        until the program is doing everything you want it to.
  239.  
  240.        I  also  have  a  tendency  to  delay  building  a module until I
  241.        discover that I need  it.    Trying  to anticipate every possible
  242.        future contingency can  drive  you  crazy,  and  you'll generally
  243.        guess wrong anyway.    In  this  modern day of screen editors and
  244.        fast compilers, I don't hesitate to change a module when I feel IA6A6
  245.                                      - 4 -A*A*
  246. PA A
  247.  
  248.  
  249.  
  250.  
  251.  
  252.        need a more powerful one.  Until then,  I'll  write  only  what I
  253.        need.
  254.  
  255.        One final caveat: One of the principles we'll be sticking to here
  256.        is that we don't  fool  around with P-code or imaginary CPUs, but
  257.        that we will start out on day one  producing  working, executable
  258.        object code, at least in the form of  assembler  language source.
  259.        However, you may not  like  my  choice  of assembler language ...
  260.        it's 68000 code, which is what works on my system (under SK*DOS).
  261.        I  think  you'll  find, though, that the translation to any other
  262.        CPU such as the 80x86 will  be  quite obvious, though, so I don't
  263.        see  a problem here.  In fact, I hope someone out there who knows
  264.        the '86 language better than I do will offer  us  the  equivalent
  265.        object code fragments as we need them.
  266.  
  267.  
  268.        THE CRADLE
  269.  
  270.        Every program needs some boiler  plate  ...  I/O  routines, error
  271.        message routines, etc.   The  programs we develop here will be no
  272.        exceptions.    I've  tried to hold  this  stuff  to  an  absolute
  273.        minimum, however, so that we  can  concentrate  on  the important
  274.        stuff without losing it  among  the  trees.  The code given below
  275.        represents about the minimum that we need to  get  anything done.
  276.        It consists of some I/O routines, an error-handling routine and a
  277.        skeleton, null main program.   I  call  it  our  cradle.    As we
  278.        develop other routines, we'll add them to the cradle, and add the
  279.        calls to them as we  need to.  Make a copy of the cradle and save
  280.        it, because we'll be using it more than once.
  281.  
  282.        There are many different ways to organize the scanning activities
  283.        of  a  parser.   In Unix systems, authors tend to  use  getc  and
  284.        ungetc.  I've had very good luck with the  approach  shown  here,
  285.        which is to use  a  single, global, lookahead character.  Part of
  286.        the initialization procedure  (the  only part, so far!) serves to
  287.        "prime  the  pump"  by reading the first character from the input
  288.        stream.  No other special  techniques are required with Turbo 4.0
  289.        ... each successive call to  GetChar will read the next character
  290.        in the stream.
  291.  
  292.  
  293.        {--------------------------------------------------------------}
  294.        program Cradle;
  295.  
  296.        {--------------------------------------------------------------}
  297.        { Constant Declarations }
  298.  
  299.        const TAB = ^I;
  300.  
  301.        {--------------------------------------------------------------}
  302.        { Variable Declarations }
  303.  
  304.        var Look: char;              { Lookahead Character }A6A6
  305.                                      - 5 -A*A*
  306. PA A
  307.  
  308.  
  309.  
  310.  
  311.  
  312.        {--------------------------------------------------------------}
  313.        { Read New Character From Input Stream }
  314.  
  315.        procedure GetChar;
  316.        begin
  317.           Read(Look);
  318.        end;
  319.  
  320.        {--------------------------------------------------------------}
  321.        { Report an Error }
  322.  
  323.        procedure Error(s: string);
  324.        begin
  325.           WriteLn;
  326.           WriteLn(^G, 'Error: ', s, '.');
  327.        end;
  328.  
  329.  
  330.        {--------------------------------------------------------------}
  331.        { Report Error and Halt }
  332.  
  333.        procedure Abort(s: string);
  334.        begin
  335.           Error(s);
  336.           Halt;
  337.        end;
  338.  
  339.  
  340.        {--------------------------------------------------------------}
  341.        { Report What Was Expected }
  342.  
  343.        procedure Expected(s: string);
  344.        begin
  345.           Abort(s + ' Expected');
  346.        end;
  347.  
  348.        {--------------------------------------------------------------}
  349.        { Match a Specific Input Character }
  350.  
  351.        procedure Match(x: char);
  352.        begin
  353.           if Look = x then GetChar
  354.           else Expected('''' + x + '''');
  355.        end;
  356.  
  357.  
  358.        {--------------------------------------------------------------}
  359.        { Recognize an Alpha Character }
  360.  
  361.        function IsAlpha(c: char): boolean;
  362.        begin
  363.           IsAlpha := upcase(c) in ['A'..'Z'];
  364.        end;A6A6
  365.                                      - 6 -A*A*
  366. PA A
  367.  
  368.  
  369.  
  370.  
  371.  
  372.        {--------------------------------------------------------------}
  373.        { Recognize a Decimal Digit }
  374.  
  375.        function IsDigit(c: char): boolean;
  376.        begin
  377.           IsDigit := c in ['0'..'9'];
  378.        end;
  379.  
  380.  
  381.        {--------------------------------------------------------------}
  382.        { Get an Identifier }
  383.  
  384.        function GetName: char;
  385.        begin
  386.           if not IsAlpha(Look) then Expected('Name');
  387.           GetName := UpCase(Look);
  388.           GetChar;
  389.        end;
  390.  
  391.  
  392.        {--------------------------------------------------------------}
  393.        { Get a Number }
  394.  
  395.        function GetNum: char;
  396.        begin
  397.           if not IsDigit(Look) then Expected('Integer');
  398.           GetNum := Look;
  399.           GetChar;
  400.        end;
  401.  
  402.  
  403.        {--------------------------------------------------------------}
  404.        { Output a String with Tab }
  405.  
  406.        procedure Emit(s: string);
  407.        begin
  408.           Write(TAB, s);
  409.        end;
  410.  
  411.  
  412.        {--------------------------------------------------------------}
  413.        { Output a String with Tab and CRLF }
  414.  
  415.        procedure EmitLn(s: string);
  416.        begin
  417.           Emit(s);
  418.           WriteLn;
  419.        end;A9A9
  420.  
  421.                                      - 7 -A*A*
  422. PA A
  423.  
  424.  
  425.  
  426.  
  427.  
  428.        {--------------------------------------------------------------}
  429.        { Initialize }
  430.  
  431.        procedure Init;
  432.        begin
  433.           GetChar;
  434.        end;
  435.  
  436.  
  437.        {--------------------------------------------------------------}
  438.        { Main Program }
  439.  
  440.        begin
  441.           Init;
  442.        end.
  443.        {--------------------------------------------------------------}
  444.  
  445.  
  446.        That's it for this introduction.  Copy the code above into TP and
  447.        compile it.  Make sure that it compiles and runs  correctly. Then
  448.        proceed to the first lesson, which is on expression parsing.
  449.  
  450.  
  451.        *****************************************************************
  452.        *                                                               *
  453.        *                        COPYRIGHT NOTICE                       *
  454.        *                                                               *
  455.        *   Copyright (C) 1988 Jack W. Crenshaw. All rights reserved.   *
  456.        *                                                               *
  457.        *****************************************************************AUAU
  458.  
  459. APAP
  460.  
  461.                                      - 8 -A*A*
  462. @