home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 224b.lha / infix.txt < prev    next >
Text File  |  1989-04-08  |  9KB  |  259 lines
  1.  
  2.                     More on the infix parser.
  3.                     =========================
  4.  
  5.  
  6.  N. Wirth helped me with this one.  I was leafing through his book:
  7.  Algorithm+DataStructures=Programs one day and found some charting, I
  8.  forget the name of it.  Anyhow, they seemed neat at the time and give
  9.  almost a direct correspondence to code.  Something other people using
  10.  other types of flowcharts have also noticed. (Notably: Wil Baden in
  11.  Charting Forth, 1986 FORML Conference Procedings, a superb paper).
  12.  
  13.  I know some people are probably horrified.  Using Wirth for Forth? Well,
  14.  I believe that Wirth one day will write (if he didn't already) a
  15.  threaded interpreted language.
  16.  
  17.  I also wanted to write a recursive utility that did a little more then
  18.  calculate a bunch of numbers in a special sequence. (fibo...? a heck.)
  19.  If you don't like it recursive, look through the back issues of Forth
  20.  Dimensions for a operator-stack type parser.
  21.  
  22.  What follows are an explanation of the precedence, the charts on which
  23.  it is based (I hope they are clear enough) and a small description of
  24.  the routines which is in addition to the shadow screens.
  25.  
  26.  
  27. Precedence.
  28. -----------
  29.  
  30.  Every infix parser takes precedence of operators into consideration. The
  31.  following are defined from the highest to lowest precedence:
  32.  
  33.   operator    explanation
  34.  
  35.    (   )     nesting
  36.    -   ~     negate       not
  37.    <<  >>    shift left   shift right
  38.    &   !     and          or
  39.    *   /     multiply     divide
  40.    +   -     add          subtract
  41.  
  42.  
  43.  These operators work on numbers, which have a 32 bit limit in my system.
  44.  Numbers can also start with an $ sign. This indicates an hexadecimal
  45.  radix, and for the number following only.  In addition to numbers the
  46.  system can use identifiers.  These identifiers are normal Forth
  47.  constants. Forth variables would use the address of that variable,
  48.  simply what that identifier leaves on the stack.
  49.  
  50.  Identifiers must start with a _ (underscore) . (period) or an alpha
  51.  character. The rest can be alpha characters, numbers or _ and .
  52.  The length of the identifier is limited by the underlying Forth, usually
  53.  31 characters.
  54.  
  55.  
  56. Charts. ( From the top down )
  57. -------
  58.  
  59.  expression
  60.  
  61.         ------------> simple-ex >----+--+------>
  62.                 ^                    |  |
  63.                 |                    v  v
  64.                 |
  65.                 |                    +  -
  66.                 |
  67.                 |                    |  |
  68.                 +--------------------+--+
  69.  
  70.  
  71.  simple-ex
  72.  
  73.         ------------>    term   >----+--+------>
  74.                 ^                    |  |
  75.                 |                    v  v
  76.                 |
  77.                 |                    *  /
  78.                 |
  79.                 |                    |  |
  80.                 +--------------------+--+
  81.  
  82.  
  83.  term
  84.  
  85.         ------------>   factor  >----+--+------>
  86.                 ^                    |  |
  87.                 |                    v  v
  88.                 |
  89.                 |                    &  !
  90.                 |
  91.                 |                    |  |
  92.                 +--------------------+--+
  93.  
  94.  
  95.  factor
  96.  
  97.         ------------>  factor1  >----+--+------>
  98.                 ^                    |  |
  99.                 |                    v  v
  100.                 |
  101.                 |                   <<  >>
  102.                 |
  103.                 |                    |  |
  104.                 +--------------------+--+
  105.  
  106.  
  107.  factor1
  108.  
  109.         ---+-------+----->  factor2  >--------->
  110.            |       ^
  111.            |       |
  112.            +-> - >-+
  113.            |       |
  114.            +-> ~ >-+
  115.  
  116.  
  117.  factor2
  118.  
  119.         ---+--------> getconstant >---------+---->
  120.            |                                ^
  121.            |                                |
  122.            +-> ( >--> expression  >---> ) >-+
  123.  
  124.  
  125.  getconstant
  126.  
  127.         ---+--------> getnumber >---------------->
  128.            |                             ^
  129.            |                             |
  130.            +------->  identifier >-------+
  131.            |                             |
  132.            |                             |
  133.            +--> ' >--> getchar >--> ' >--+
  134.  
  135.  
  136.  getnumber
  137.  
  138.         ---+---------------> digit >-+----------->
  139.            |         ^   ^           |
  140.            |         |   |           |
  141.            +--> $ >--+   +-----------+
  142.  
  143.  
  144.  identifier
  145.  
  146.         ---+-> letter >-------+----------------+-->
  147.            |            ^   ^ |              ^ |
  148.            |            |   | |              | |
  149.            +-->  _  >---+   | +--> letter >--+ |
  150.            |            |   | |              | |
  151.            |            |   | |              | |
  152.            +-->  .  >---+   | +--> digit  >--+ |
  153.                             |                  |
  154.                             +------------------+
  155.  
  156.  
  157.  
  158. Routines.
  159. ---------
  160.  
  161.  TEST
  162.   Small word to test the evaluation process. Uncomment it before loading.
  163.   To use it, type from the Forth prompt (e.g.):
  164.   5 constant testcon
  165.   test  2*8+_testcon
  166.   which should leave the answer on the stack. Reverse the order and the
  167.   result should be the same, precedence.
  168.  
  169.  EVALUATE  (s addr len -- n )
  170.   The topmost word of the parser.  It returns the value of the
  171.   expression, using the string non destructively.  It initializes the
  172.   pointer and counter to keep track of the current character to be
  173.   examined, ie. the symbol.
  174.  
  175.  (EXPRESSION)
  176.   The default for expression.  This word corresponds to the first graph.
  177.   Note that it is indirectly recursive, by calling the deferred word
  178.   expression, which is itself.
  179.   Also I have omitted stack pictures, in a recursive context it varies
  180.   with the input. Doesn't matter as long as the end result is not
  181.   variable.
  182.   Program flow is almost a direct correspondence to the graph.
  183.  
  184.  SIMPLE-EX
  185.   The next graph translates into this word. Also recursive, as the arrow
  186.   around the graph implies.  The order of operator precedence is bottom
  187.   up; this is the second level from the bottom, the characters * and /
  188.   are scanned for here.  If not present, the routine is exited, with the
  189.   result from TERM.
  190.  
  191.  TERM
  192.   Recursive routine, looks for the logical & and ! symbols.  It is
  193.   expected that the expressions presented to this parser are not to
  194.   deeply nested, or the stack might overflow?  Normally, that will not be
  195.   the case.  Most calculators allow appr. 10 levels of nesting, and I
  196.   think this one will outdo them.
  197.  
  198.  FACTOR
  199.   Recursive also.  Here I cheated a little, I don't parse the entire >>
  200.   and <<.  I simply ignore the second character.  The second 'readsymbol'
  201.   takes care of that.
  202.  
  203.  FACTOR1
  204.   The negate and not level.  It is not recursive, simply decides on the
  205.   character in symbol, what to do with factor2.  The graph doesn't have
  206.   an arrow back to itself.
  207.  
  208.  FACTOR2
  209.   Looks at the next symbol, and if it is a (, bracket that is, will call
  210.   expression, and cause indirect recursion, by calling the entire
  211.   sequence.  Note how the missing ), closing bracket, is handled.
  212.   If it is not a nesting, getconstant gets called.
  213.  
  214.  GETCONSTANT
  215.   A constant can be a character, a number or an identifier.  Each one has
  216.   a special starting character, allowing for this parser not to have to
  217.   backtrack.  Letter? is in this version [ . | _ | a..z | A..Z ]
  218.  
  219.  IDENTIFIER
  220.   Places the substring from the expression at (Forth's) 'here', appends a
  221.   null character after it (required in my system) and finds it in the
  222.   Forth context dictionary.  If not found aborts with an error message,
  223.   displaying the unknown identifier.  If found, it will execute the word.
  224.   Therefore if the word is a constant it will return a value on the
  225.   stack.  Any word returning a value could be used, even one with side
  226.   effects.
  227.  
  228.  GETNUMBER
  229.   Also places a substring at 'here', but calls 'number' to convert the
  230.   string into a value.  The number is in hex base if preceded by $.
  231.   Again: ' 0 here count + c! '  is particular to my system, most other
  232.   F83's will require a blank instead of a zero.
  233.  
  234.  GETCHAR
  235.   Read the next symbol and uses it as a character constant.  Since Forth
  236.   already translates it for me, it is easy.  It does expect a closing
  237.   single quote and aborts complaining if it is missing.
  238.  
  239.  The first screen of the parser is a set of normal Forth words the
  240.  explanation on the shadow screen is explicit enough.  The only strange
  241.  trick used here is not to point to the beginning of the string, but to
  242.  one character past the end.  This allows the length of the string to be
  243.  decremented to zero, at which time the string is exhausted.  This makes
  244.  it unnecessary to keep the length in a variable and comparing a counter,
  245.  which is incremented, to it.  The current symbol is pointed to by
  246.  symbol> - insymbol  or the end of the string less the counter.
  247.  On this screen I have also defined what a digit and what a letter should
  248.  be.
  249.  
  250.  This parser can be extended, modified, to allow more levels and
  251.  operators, or to change the meaning of identifiers.  An example of how
  252.  techniques from other languages can be used in Forth.  And this parser
  253.  can be used for people who cannot get the hang of RPN.  I wrote it to
  254.  input a bunch of text files written in another language.
  255.  
  256.  Peter Appelman.
  257.  
  258.  
  259.