%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- FIXED: 15 Primary -> 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 -> 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 FLOAT: 1.765E+01 <=== (Top of Stack) Primary -> 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+@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+@U-. $ ~2 Push @R+C@R- twice; we'll skip one step involving the production Primary -> . 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 (408) 727-6671 Toll-free Order Line: (800) 538-9787