Simtel MSDOS 1992 June/SIMTEL_0692.cdr/msdos/pascal/qparser.arc/QPDEMO.TXT

Text File | 1985-09-30 | 11.4 KB | 391 lines

%0
#1

                          @B+@K+Greetings!@B-@K-

          ... and thanks for running this brief demo program

We're going on a short tour of some of the features of the QPARSER
translator writing system.  Qparser is an LALR(1) parser table generator
that accepts a context-free grammar specification of a language.  Based
on that grammar, it produces a complete ready-to-compile Pascal or C
program that will correctly parse sentences in that language.
$
~1

@R+But it's more...@R-  Qparser is also a complete @U+strategy@U- of
translator construction.  It supplies a @U+semantics action@U- system,
including @U+symbol table functions@U-, @U+semantics stack declarations@U-,
and more.  There are @U+fully worked out@U- example translators, ranging
in complexity from a simple calculator to a Pascal subset compiler.
Finally, there's a companion textbook available from SRA that covers both
the theory and practice of translator design.  It was written by Dr.
William Barrett, who also designed the Qparser system.

But let's look at an example.
$
~2
*
@U+This@U- window will be used for comments on the program shown in the
@U+other@U- window.

$
#2
This window will be used to show the effect of running a program.  The
material typed by the program will be shown

   like this

while the material that @U+you@U- would type will be shown

   @R+like this@R-
$
*
#1
*
~1
~1
Let's first look at a compiled interpreter, a program called CALC.COM.

CALC was prepared by

    1. writing a grammar for it (20 lines),
    2. extending one or two data structures (about 5 lines),
    3. writing some Pascal semantics actions (about 60 lines).

What we're going to show is the @U+effect@U- of running CALC.  You can
try everything yourself later, following the simple directions in the
Qparser booklet.
$


~2
~2

When you execute CALC, you will first get a prompt: ">".  CALC will then
expect a simple arithmetic expression:
#2
*
C> @R+CALC@R-

> @R+5 + 6.5*(9-3)@R-
$
#1
*
CALC will reply with the result
#2
   = 44
$
#1
*
You can also write simple assignment statements, such as:
#2
> @R+X := 5 + 15@R-
   = 20
$
#1
*
Once variable X has been defined,
you can use X in other expressions, for example:
#2
> @R+Y := x+5@R-
   = 25
$
#1
*
The point of this exercise is not to run a calculator, but to demonstrate
that a simple @U+grammar@U- and a few lines of @U+semantics@U- are all
you need to produce this interpreter.

We're now going to expose some of the inner workings of the CALC parser.
Again, the various debugging and report tools are @U+built into@U- the
Qparser system.  You need only to add a few extensions to make them suit
your special purposes.

$
Type the character @R+!@R- before entering an expression, for example,
#2
> @R+! 15 + (17.65*22 - 45)@R-
$
#1

The @R+!@R- will bring up a debugging menu before the rest of the line
is scanned; it looks like this:
#2
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+D@R-
$
#1
*
Simply press the first letter of the command you want (you don't
have to press enter).

For example, type @R+D@R- to set a debug level.  Then you will see:
#2
Set debug level (0, 1, 2...) ? @R+2@R-
$
#1
Type @R+2@R- (enter), to choose debug level 2.
You'll get the main prompt
again, so type @R+C@R- to continue.  You'll then see this:
#2
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R-
  <integer>                  FIXED:   15
Primary -> <integer>
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R-
$
#1
*
This says that the @U+semantics stack@U- contains one item, the first
integer in the input stream (15).  FIXED refers to its type.  The
last line,

   Primary -> <integer>

is the grammar rule that is about to be applied.  The integer 15 will be
@U+reduced@U- to a @U+Primary@U-.
$

When you type @R+C@R-, you'll see the result of applying the "Primary"
grammar rule.  You'll also see the rule about to be applied:
#2
   Primary                   FLOAT:  1.500E+01
Expr -> Term
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R-
$
#1
*
This announces that the fixed point number 15 has been converted into a
floating point number.  That action was part of the semantics action
Pascal code written for CALC.  When you hit @R+C@R- again:
#2
   Expr                      FLOAT:  1.500E+01
   +                         OTHER
   (                         OTHER
   <real>                    FLOAT:  1.765E+01      <=== (Top of Stack)
Primary -> <real>
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R-
$
#1
*
Now it's getting interesting.  The semantics stack carries four items.
The @U+Expr@U- is at the bottom of the stack and the @U+<real>@U- is on
top.  Recall that our expression was

    @R+15 + ( 17.65@R- *22 - 45)

The parser has worked through the highlighted portion; the rest hasn't
been scanned yet.  You can see the trail left in the stack; the @R+15@R-
is the @U+Expr@U-, and the @R+17.65@R- is the @U+<real>@U-.
$

~2
Push @R+C@R- twice; we'll skip one step involving the production
Primary -> <integer>.  You'll see this displayed:
#2
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R_
   Expr                      FLOAT:  1.500E+01
   +                         OTHER
   (                         OTHER
   Primary                   FLOAT:  1.765E+01
   *                         OTHER
   Primary                   FLOAT:  2.200E+01      <=== (Top of Stack)
Term -> Term * Fact
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R-
$
#1
~1
*
At this and every other point in the parsing, the
   @K+top stack elements correspond to the grammar rule's right part@K-
The names may not always agree, owing to a single production optimization
made by Qparser, but the positions always will.  In this case,

   Term   corresponds to:   Primary     FLOAT:  1.765E+01
   *      corresponds to:   *
   Fact   corresponds to:   Primary     FLOAT:  2.200E+01
$

Notice how the stack top corresponds to the right-most member of the rule.
When you type @R+C@R-, these three elements will be replaced by a single
element, which is the rule's left member:
#2
   Expr                      FLOAT:  1.500E+01
   +                         OTHER
   (                         OTHER
   Primary                   FLOAT:  3.883E+02      <=== (Top of Stack)
Expr -> Term
I(dentifier, D(ebug level, A(ll symbols, C(ontinue? @R+C@R-
$
#1
*
Also notice how the product of 17.65 and 22 has been carried out, and the
result (388.3) has been placed on the stack.  That @U+semantic action@U-
is part of the Pascal code that must be written by you as the user.



$
#2
*
#1
*
~1
~1
~1
~1
~1
~1
~1
~1
~1
This brief demo should give you a feel for the Qparser system, which
can solve several algorithmic tasks for you:

   * The derivation of an input string has been uncovered and reproduced
     as production rule operations.

   * Information is carried on the semantics until needed later.

   * Names and numbers are scanned and put into the stack at the right
     place.

   * When each production rule pops up, the top of the semantics stack
     carries just what is needed for the operation that it implies.

The semantic actions must be coded by you in Pascal
or C -- but Qparser provides a convenient and powerful framework
for doing this.

$
*
We invite you to actually run CALC yourself.  You've
already figured out how to run this demo program; use the same
execution sequence to run CALC.  We recommend setting DOS to the
disk drive name that contains the demo diskette, for example,

C> @R+A:@R-
A>

will set the default disk drive to drive A.


$
*
Try some experiments, such as the following:

   Look at names by choosing the @R+I@R-(dentifier option.

   Make a syntax error and see what happens.

   Choose a lower or higher debug level:
      1 is production rule only
      2 is the stack and production rule
      3 shows READ and LOOKAHEAD actions (for those who know how LR
          parsers work)
      4 shows lots of detail during error recovery


$
After you've tried that, try running LR1 on the CALC grammar.  When
you type LR1 by itself --

C> @R+LR1@R-

-- you will get a screen full of options.  Choose
a report level greater than 0, for example,

C> @R+LR1 CALC -L3@R-


$
You'll get lots more information scrolling across the screen.  Hit
@R+control-S@R- to stop the scrolling, and @R+control-Q@R- to continue.

If you are familiar with LR item-sets, you'll see these produced.  The
last table produced is a state-by-state description of the LR parser
finite-state machine.


$
*
LR1 will try to write a table file to your demo diskette.
There isn't much room on that diskette, so we suggest
transferring the demo files to another diskette.

Since Qparser can easily produce voluminous Pascal source files,
we recommend a system with a hard disc.  A large grammar will
also need considerable memory -- 512 Kbytes minimum is recommended.


$
We suggest actually generating a full parser.  Start with CALC, since
it's all worked out.  Just enter these commands:

C> @R+LR1 CALC@R-
C> @R+LR1P CALC -s CALCSKEL@R-


$
These commands should produce a source file CALC.PAS, which you can
examine with an editor.  We suggest comparing it to the source file
CALCSKEL.PAS.  Qparser has converted the "skeleton" file CALCSKEL into
the syntactically correct Pascal source file CALC.PAS.  You should also
take a look at the grammar CALC.GRM, and compare the production rules
with the semantic program information found in the procedure APPLY.

(Alternately you could use LR1SKEL with the CALC grammar --

C> @R+LR1P CALC -s LR1SKEL@R-

to generate a working program which recognizes the same grammar but
behaves very differently. )


$
CALC.PAS contains several @B+include directives@B-, i.e. statements
directing the compiler to include code from another file -- look for
lines containing @U+{$I@U- followed by a file name in the CALC.PAS source.
The named files have to be available when you compile CALC.


$
We recommend using the Turbo Pascal compiler, vs. 2.0 or later.  However,
you can also modify CALCSKEL and its  include files to suit some other
Pascal compiler.  Just try compiling CALC and see where the syntax errors
occur -- it should be clear how to make the necessary changes.

Note that by changing a skeleton file's syntax, you also change all the
generated files, so you only have to do that once.  In fact, the full
Qparser system contains a set of C skeletons, enabling you to produce a
translator in C.


$
*
The full Qparser system also contains a simulator, an assembler and
a subset Pascal compiler.  These are valuable resources in developing a
translator system, or for instructional purposes.

The companion textbook, @U+Compiler Construction: Theory and Practice@U-,
can now be ordered from Science Research Associates, Chicago.  This
text has been adopted by many colleges and universities, and covers the
concepts of Qparser in considerable detail.


$
*
Thanks for running me.  Follow the instructions in the demo booklet for
some interesting experiments that you can run with QPARSER.  Happy parsing!


                          QCAD Systems, Inc.

                          San Jose, CA 95129
                            [phone]
                  Toll-free Order Line: [phone]