Home

Draco 1.2 Users Manual - Bayfront Technologies, Inc.

1. SYSERR atomic backtracking alternative SYSERR chr pointer not on line SYSERR failure to unlink in RFNDEF SYSERR illegal domain internal structure SYSERR illegal menu form SYSERR illegal prefix internal form in PATTACH1 FORM SYSERR illegal prefix internal form in RSCAN FORM SYSERR illegal prefix internal form in TSCAN FORM SYSERR inline refinement with wrong number of arguments SYSERR no binding for PATVAR in RHS of transform TFM SYSERR no mark on stack in LIST SYSERR rule PARSE RULE TREE has no MARK SYSERR transform should have refined SYSERR unknown directive
2. EXP STRING NODE STRING BEX BEX BEX1 BEX1 NODE OR 2 1 BEX1 BEX2 amp BEX2 NODE AND 2 1 BEX2 BEX3 NODE NOT 1 BEX3 BEX3 TRUE NODE TRUE FALSE NODE FALSE AEX lt AEX NODE LESSEQ 2 1 gt AEX NODE GTREQ 2 1 lt AEX NODE LESS 2 1 gt AEX NODE GTR 2 1 AEX NODE EQUAL 2 1 AEX NODE NOTEQ 2 1 AEX AEX1 AEX1 NODE ADD 2 1 _ AEX1 NODE SUB 2 1 AEX1 AEX2 AEX2 NODE MPY 2 1 AEX2 NODE IDIV 2 1 AEX2 NODE DIV 2 1 AEX2 AEX3 AEX2 NODE EXP 2 1 AEX3 AEX4 AEX4 NODE MINUS 1 AEX4 AEX4 NUMBER NODE NUMBER SIMALFN NAME TREE AP APSEQ EXP EXP NODE FNCALL 2 1 a TREE SL SLSEQ EXP sc EXP wjn NODE SSELECT 2 1 EMPTY BEX NODE PAREN 1 BLOCK SIMALFN SORT EXP NODE SQRT 1 INT EXP NODE INT 1 ABS EXP NODE ABS 1 PRINT TREE PRINI PRSEQ EXP EXP READNUM NODE READNUM READCHAR NODE READCHAR READSTRING NODE READSTRING WRITENUM EXP NODE WRITENU dj EX
3. UMBER OR e wow 2 A PAREN lt Ww 1 w PGM SLM PROGRAM LM TREEPRINT PGMSEQ 1 SLM 114 0 SLM END SLM PGMSEQ 1 TREEPRINT PGMSEQ 2 SLM SLM END SLM PRINT SLM PRINT LM TREEPRINT PRSEQ 1 PRSEQ 1 TREEPRINT PRSEQ 2 PROCCALL SLM 1 2 READCHAR READCHAR READNUM READNUM READSTRING READSTRING REPEA SLM REPEAT LM 1 SLM UNTIL 2 RETURN SLM RETURN RETURN SLM RETURN LM 1 SASSIGN SLM 1 2 SL LM TREEPRINT SLSEQ 1 SLSE 1 TREEPRINT SLSEQ 2 SORT SORT I x SSELECT 1 2 STRING 34 34 SUB gt 1 ou 2 A TRUE TRUE WHILE SLM WHILE 1 LM DO 2 WRITECHAR SLM WRITECHAR 1 WRITENUM SLM WRITENUM 1 WRITESTRING SLM WRITESTRING 1 END APPENDIX V AN EXAMPLE SET OF TRANSFORMATIONS This appendix presents a sample set of transformations for a slightly modified version of SIMAL and its prettyprinter The language has been modified to put objects it knows are constants into a internal form node with prefix keyword LCONST The prettyprinter has been modified to show these constants in brackets an
4. NUMBER LITERAL LIST OR CEX2 CEX2 CEX3 CEX3 NODE AND G EMPTY NODE EQUAL CH NUMBER LITERAL LITC r E CHR 2 LE CHR 1 R 1 HAR L NIL NIL NIL 1 N 1 NIL NIL 1 NIL NIL 1 1 1 51 Draco 1 2 Users Manual ANY 512300 DELTOK ANY PREFIX SPACING ID SPACING TOKEN ALPHA lt 80 gt ALPHA DIGIT STRING SPACING ANY TOKEN ANYBUT NUMBER SPACING TOKEN DIGIT lt 2 gt DIGI DELTOK CMNTCHRS TOKEN ANYBUT DELTOK ALPHA ANY A Z a z DIGIT ANY 0 9 7 SPACING ANY 32 10 13 9 END APPENDIX III THE DEFINITION OF A PRETTYPRINTER DESCRIPTION DI This appendix presents the external and internal description of a prettyprinter definition see PPGEN This description is from the file PPGEN DEF Any error in the construction of a prettyprinter using PPGEN refers to a rule in this file III 1 The File PPGEN DEF DEFINE PPSY PPGEN Prettyprinter Generatio James Neighbors Last Modif PPSYN PRETTY PRINTER ID LIST PR
5. ER INITI r 50 Draco 1 2 Users Manual NLIST NINFO MINFO RPTPR RPTTR NODE PARSER NODE NAME SNINFO EMPTY lt 1 gt NINFO ID NODE PARSER NODE NAME NUMBER NODE PARSER NODE NAME x NODE PARSER NODE STAR NUMBER NODE PARSER NODE SHARP NLIST NODE LIS STRING NODE PRINAC QUOTE wan NODE PRINAC PARSER TOKEN MAKE CR NODE TERPRI COL NUMBER NODE TAB LIST OR TEX2 TEX2 LIST AND TEX3 ID USE RULE NODE M EX1 mye S RPTTR ANY BUT CEX1 NODE NOT 1 EMPTY CEX1 NODE AND 1 PARSER SCANCHR EMPTY NODE AND T TOKEN NODE PARSER TOKEN START DELTOK NODE PARSER TOKEN END lt mom myn mom gt EX3 NODE PARSER REPEAT 1 NUM gt EX3 NODE PARSER REPEAT 1 NUM gt EX3 NODE PARSER REPEAT 1 NUM gt EX3 NODE PARSER REPEAT 1 EX3 NODE PARSER REPEAT 1 NIL NIL well 97 Ma 727 wn EX3 NODE PARSER REPEA NUM gt TEX3 NODE PARSER REPEA NUM gt TEX3 NODE PARSER REPEA NUM gt TEX3 NODE PARSER REPEA TEX3 NODE PARSER REPEAT 1 NIL NIL PARSER NODE 1 RAL RPTPR NODE NLIST NODE LITERAL NODE PARSER LITE LITCHAR NODE PARSER LITCHAR EMPTY NODE AND T
6. WRITECHAR EXP NODE WRITECHAR 1 WRITESTRING EXP NODE WRITESTRING 1 PREFIX SPACING ID SPACING TOKEN STRING SPACING ALPHA lt 10 gt ALPHA DIGIT DELTOK OK NUMBER SPACING TOK gt D Y N ANY ANYBUT ANY DELTOK N lt 1 gt DIGIT GIT EXPNT EMPTY HEE ANY 5 lt 1 2 F p EME EXPNT EMPTY DELTOK Draco 1 2 Users Manual EXPN ALPHA DIGIT SPACING END ANY E ANY A Z ANY 0 9 ANY Va IZ ANY 32 10 13 9 1 2 Example SIMAL Program EMPTY The familiar quadratic equation root solution PROGRA QUADRAT OCAL QUADRATIC TG I PRIN PRIN A LOOP A B C ROOT1 ROOT2 T QUADRATIC EADNUM IF A B R C ROOT ROOT PRIN GOTO END RI 0 THEN EADNUM FADNUM 1 B SQ 2 B SQ RETUR RT EQUA T INPUT A B C PARAMET RI N T THE ROO LOOP APPENDIX II THE DEFINITION OF DRACO BNF IN DRACO BNF ARE Pie 10 ERS ROOT1 SOLVER B 2 4 A C 2 A RT B 2 4 A C 2 A 5 AND 0012 lt 1 gt DIGIT U This appendix presents the file PARGEN DEF which describes Drac
7. DE LISP SEXPN DE NAME FPARAMS PROG LOCALS RETURN BODY D REFINEMENT D COMPONENT A QHW Wd lt 2 ti CHAPTER 6 CONVERTING A PROGRAM TO INTERNAL FORM WITH PARSE When a new system needs to be built which can be described in one of Draco s domain languages needs to be built the PARSE subsystem is used to convert the domain language program into the internal form Draco can manipulate The PARSE subsystem reads in the parser built by the PARGEN subsystem for the domain language If there are transformations defined for the domain they are used to automatically suggest possible transformations for the problem at hand These suggestions are attached to the programs internal form and are used when the program is transformed and refined by the TFMREF subsystem If no transformation library exists for the domain the message ERR transformation library lt DOMAIN gt TLB unavailbale for suggestions will be issued Even with this message an internal form will be created for the program but this program will not have suggestions for transformations 6 1 Using the PARSE Subsystem 26 Draco 1 2 Users Manual The following is an example interaction with the PARSE subsystem LANG is the name of the domain and PROG PGM is a file which contains a program written in LANG DRACO gt PARSE DOMAIN NAME LANG SOURCE FILE LANG PGM Draco loads the parser for the domain
8. Each component has a name and a list of possible arguments in the COMPONENT field The name is the prefix keyword of the internal form nodes to which the component applies The list of possible arguments name the subtrees of the internal form node If a node has a variable number of subtrees a name prefaced by a gt is used to denote the rest of the subtrees in the node A prose description of what the component does is given by the PURPOSE field If the component takes objects as arguments and or produces objects then the type of these objects in terms of the objects in the domain is given in the IOSPEC field of the component The DECISION field presents a prose description of the possible refinements of the component and the considerations involved in choosing between the alternatives Finally there is a set of refinements of the component which represent a possible implementation of the component in terms of the objects and operations of other domains The first REFINEMENT in the set of refinements is the default refinement In the absence of any other information Draco will attempt to use this refinement first Each REFINEMENT has a name and a BACKGROUND which is a prose description of the method the refinement implements and reference to where more information about the method may be found The CONDITIONS field of a refinement lists conditions which must be true before the component may be used There are basically two kinds of co
9. 2 2 2 Specifying a Legal Parser Some restrictions exist as to what a parse rule may add to the stack of nodes which construct the internal form tree 1 Ifaparse rule succeeds it can only put one node in the node stack Multiple nodes may be constructed during the parse rule constructing subtrees but when the rule succeeds the net change in the number of nodes in the node stack can be only one This rule makes sure that the internal from returned by a nonterminal in the syntax a parse rule is always a tree with the single node returned being the root This concept will be used later when we discuss describing software components 2 Ifa parse rule fails it may not add any nodes to the node stack Remember that the goal of parsing for Draco is to produce an internal form which captures all the information in the syntax of the problem domain The one parse rule one node restriction we have found guides to parser designer in capturing the entire syntax of the domin in the internal form 2 2 3 A Complete External Internal Form Example We will redo our assignment statement example from a previous section adding the internal form construction information DEFINE ASGN ALP DIG ANY 0 9 SPACES ANY 32 AT GANY Ac Z 1 tae he 4 3 3 ASGN IDENTIFIER LIT
10. CHARPRINT lt number gt LISTPRINT lt node item gt lt snumber gt lt number gt lt number gt Where in the above BNF a lt string gt is a string of characters contained in double quotes In this case lt identifier gt may be enclosed in angle brackets lt gt so that the identifier lt FURD gt is legal The identifiers in angle brackets are used to define a print definition for the classes defined during transformation library construction see Chapter 4 If an error occurs during the definition of a prettyprinter then the rule cited is part of the file PPGEN DEF which defines the syntax of a prettyprinter in Draco BNF The current version of PPGEN DEF is included in Appendix III of this document 3 2 An Example of a Prettyprinter Description Given the following parser definition from the previous chapter DEFINE ASGNSTMT ASGN IDENTIFIER LITERAL EX1 STRING LITERAL NODE ASSIGN 2 1 EX1 EX2 EX2 NODE ADD 2 1 EX2 EX3 EX3 NODE MPY 2 1 EX3 EX4 EX3 NODE EXP 2 1 EX4 IDENTIFIER LITERAL APARAMS NODE FNCALL 2 1 EMPTY NUMBER LITERAL 15 Draco 1 2 Users Manual EX1 APARAMS TREE APARAMS APSEQ EXP EXP PREFIX SPACES IDENTIFIER SPACES TOKEN ALPHA lt 5
11. lt 1 gt FNDEF END FNDEF NAME TREE FP FPSEQ NAME NAME BLOCK NODE FNDEF 3 2 1 STMT BLOCK IF BEX THEN STMT ELSE STMT NODE IFELSE 3 2 1 48 Draco 1 2 Users Manual EMPTY NODE IF 2 1 WHILE BEX DO STMT NODE WHILE 2 1 REPEAT STMT UNTIL BEX NODE REPEAT 2 1 FOR NAME AEX STEP AEX AEX DO S NODE FOR 5 4 3 2 1 O AEX DO S NODE FOR1 4 3 2 1 of RETURN EXP NODE RETVAL 1 EMPTY NODE RETURN GO TO ID NODE GOTO EMPTY y STMT NODE PAREN 1 SIMALFN NAME TREE SL SLSEQ EXP EXP NODE ASELECT 2 1 EXP NODE SASSIGN 2 1 EXP NODE ASSIGN 2 1 u STMT NODE LABEL 2 1 TREE AP APSEQ EXP EXP NODE PROCCALL 2 1 BLOCK LOCAL TREE EMPTY NODE NOLOC TREE BLK BLKSEQ STMT STMT NODE BLOCK 2 1 OC LOCSEQ NAME NAME Ep gt AME ID LITERAL
12. Syntax Meaning LIST name expression Forms a variable width node from all the nodes returned by the expression The name gives the node name SEXPN expression _ FORMS a LISP S expression from the nodes returned by the expression EXECUTE This treats the top of the node stack as a LISP expression and executes it Once again DON T USE THESE CONSTRUCTS IN A DOMAIN They are for internal use only The TACTICS interpreter is implemented using them Draco 1 2 Users Manual 2 4 Class of PARGEN Parsers The PARGEN system produces parsers which scan left to right with explicit backup The class of languages handled is less powerful than context free Some thought must be given to the ordering and content of the lt parse rule gt s and lt token rule gt s Rules which could recur without scanning off a character are illegal The worst case of this left recursion is of course illegal and must be removed by the author Backtracking rules must be included in the grammar whenever the complexity of the language to be recognized exceeds the power of an LL 1 parser In particular a set of rules a grammar is LL 1 parseable if and only if whenever there is a rule of the form ARULE ALPHA BETA then the following conditions hold 1 For no terminal symbol a do ALPHA and BETA derive strings beginning with a At most one of ALPHA and BETA can derive the empty string The current implement
13. 1 7 S 1 TPOS He N O G H tri 1 BER NODE EF1 NODE EF1 NODE LAMBDA TPTR PP PRINT1 EMPTY CAR TPTR TPOS AND CDR TPTR 1 52 Draco 1 2 Users Manual D ELTOK ANY CHARPRINT NUMBER NODE TYO OR INUMP CAR NTH E PREFIX SPACING ID SPACING TOKEN ALPHA ANY lt lt 40 gt ALPHA DIGIT ANY gt EMPTY DELTOK STRING SPACING ANY TOKEN ANYBUT NUMBER SPACING TOKEN DIGIT lt 2 gt DIGIT DELTOK CMNTCHRS TOKEN ANYBUT DELTOK ALPHA ANY A Z I az z I I _ 1 DIGIT ANY 0 9 SPACING ANY 32 10 13 9 END APPENDIX IV AN EXAMPLE PRETTYPRINTER DESCRIPTION This appendix presents an example description of a prettyprinter for the language defined in Appendix I This description is contained in the file SIMAL PPD and would be given to PPGEN to construct a prettyprinter The example SIMAL program in Appendix I was printed with the prettyprinter resulting from this description IV 1 A SIMAL Prettyprinter Description PRETTYPRINTER SIMAL SIMAL Example Language Prettyprinter James Neighbors Last Modified March 11 lt ZIDOPS gt 1 lt ZIDOPS
14. DE FRM E RASE LINE IL TERM MSG 27 wpa LINE COL H 2K initialize the terminal mode DE ERM INIT NIL TERM SM 1 message in inverse video DE ERM INVERSE S TERM MSG 27 7m EVAL CONS TERM MSG S TERM MSG 27 Om send a series of strings and ASCII codes to the terminal DE TERM MSG L PROG S LOOP SETQ S CAR L COND NULL L RETURN STRINGP S MAPC FUNCTION OUTCHR AEXPLODEC S NUMBERP S TYO S LITATOM S COND EQ S T TERPRI CONSP GET S VALUE MAPC FUNCTION OUTCHR AEXPLODEC EVAL S IAPC FUNCTION OUTCHR AEXPLODEC S COND EQ CAR S E EVAL CADR S IAPC FUNCTION OUTCHR AEXPLODEC EVAL S SETQ L CDR L GO LOOP CONSP S no access protected areas DE ERM PRCP NIL TERM MSG 27 u access protected areas DE ERM PSCP NIL TERM MSG 27 s send terminal commands DE ERM RM M TERM MSG 27 gt M 1 DE ERM SM M TERM MSG 27 gt M h display status line DF TERM STATUS S ERM PSCP ERM CUP 25 0 ERM ERASE LINE EVAL CONS TERM MS
15. END LOCALE PROGRAM QUADRATIC SQUADRATIC FMREF gt unload transform remove transformations FMREF gt locale PROGRAM QUADRATIC QUADRATIC TFMREF gt locale 1 SQUADRATIC LOCAL 0 seed TFMREF gt locale 1 LOCAL A B C ROOT1 ROOT2 LOOP sp TFMREF gt locale 1 LOCAL A B C ROOT1 ROOT2 TFMREF gt INFO 5725779 23 29 21 PROGRAM QUAD INT DOMAIN SIMAL PP transformations removed INSTANCE PROGRAM QUADRATIC instance and locale different SQUADRATIC END OCALE LOCAL A B C ROOT1 ROOT2 TFMREF gt HARDCOPY make file of prettyprinted instance Output File gt QUAD no default extension QUAD created TFMREF gt EXIT get out of TFMREF to Draco Do you want to save the changes Y N gt Y SAVE check QUAD INT saved DRACO gt CHAPTER 8 USING THE PROGRAM TRANSFORMATION MECHANISM The form and power of the transformations is discussed in the chapter on the transformation library generator XFMGEN The Draco 1 2 Users Manual TFMREF subsystem assumes that the transformation library already exists The transformation library is loaded only when it must be to save working room in memory Everytime the TFMREF system performs a transformation it prints out the before and after versions of the program fragment and will request a user OK if desired The subsections below present the transformation related commands 8 1 The SUGGEST comm
16. Parsing LANG from file LANG PGM kkkxkk one signifys a line read Parse Completed 0 errors detected the extension defaults to INT PROG INT created DRACO gt The error conditions and error messages are similar to those for PARGEN and PPGEN in that if an error occured during parsing a rule name and offending line would be printed In this case the offending line would come from PROG PGM and the rule would be contained in the parser definition for the domain LANG DEF 6 2 How Transformations are Suggested in PARSE In the example dialogue above the question Automatic Suggestion of Transformations was asked If the response to this question was yes Y then in the internal form that PARSE builds some suggestions of transformations are made The transformations are suggested by the prefix keyword at each node in the tree and no further matching is done Thus any transformation which could possibly apply is suggested Many of those suggested will not apply The suggestion mechanism assumes that the TRANSFORM command of the TFMREF subsystem will be used to weed out any inapplicable transformations very quickly If you plan to apply each transformation by hand individually in the TFMREF subsystem then the automatic suggestion of transformations option should not be taken If the option is taken then the suggested transformations are ordered by their application codes see XFMREF 6 3 Multiple Domains When writing progra
17. TRANS ifeliml 99 ifthen true x x TRANS ifelim2 99 ifthen false x empty TRANS ifelim3 99 ifelse true x y x TRANS ifelim4 99 ifelse false x y y ERASEPVARS We activate the XFMGEN subsystem through the BUILD command In the first session below XFMGEN notes it is creating a new transformation library It follows a list of the transformations inserted into the library anf the user is offered a prettyprinted version of the transformation library Finally the transformation library PARSER TLB is created DRACO gt build DOMAIN NAME parser DOMAIN PART transformation library Transformation Library Builder working on PARSER domain NOTE creating a new transformation library true false not not ifeliml ifelim2 ifelim3 ifelim4 Prettyprinted Transformation Catalog Listing Y N gt N NOTE PARSER TLB created DRACO gt When new transformations have to be added to the library the procedure to follow is similar Let us assuem that as some point in the future the insertion file PARSER TFM includes the following transformations PVARS x y z TRANS parenthelim 99 paren paren x paren x TRANS parenthelim2 98 stmnt paren x stmnt stmnt x stmnt TRANS parenthelim3 98 stmnt paren x OMEGA stmnt x OMEGA TRANS stmnteliml 12 stmnt empty stmnt stmnt TRANS stmntelim2 12 stmnt empty OMEGA OMEGA TRANS bodyelim 12 bod
18. 1 lt COMOP gt 2 to be added to the prettyprinter for the assignment statement example in the section on PPGEN For our example above the catalog would have looked like 4 6 82 18 00 00 LANG TLB lt COMOP gt ADD MPY lt COM gt XY 5 X lt COMOP gt Y gt Y lt COMOP gt X 21 Draco 1 2 Users Manual ADDX0 12 X 0 gt X EXPX0 11 2X70 gt 1 LDISTMPYADD 5 X 7 Y Z gt X Y X Z MPYX0 5 2X 0 gt 0 PARENPAREN 12 X gt X The first line gives the date time and the name of the file which contains the library The pattern variables in each transformation are preceeded by a question mark These catalog listings are useful references when working with the TFMREF subsystem Appendix V presents an example catalog of transformations for the language defined in Appendix I It is interesting to note how the special marker UNDEFINED is used in Appendix V and how the metarules can take advantage of such markers 4 4 Using the Transformation Builder System XFMGEN In this example we assume that the file PARSER TFM see figure below contains some transformations to be inserted into the library of the PARSER domain We further assume that the PARSER domain currently has no transformation library PVARS x y 2 TRANS true 95 compr x x true TRANS false 97 uneq x x false TRANS not 95 negation uneq x y compr x y TRANS not 95 negation compr x y uneq x y
19. CONDITIONS NODE TACTIC RRFIELD CONDITIONS BACKGROUND NODE TACTIC RRFIELD BACKGROUND DIRECTIVE NODE TACTIC RRFIELD DIRECTIVE INSTANTIATION NODE TACTIC RRFIELD INSTANTIATION ASSERTIONS NODE TACTIC RRFIELD ASSERTIONS RESOURCES NODE TACTIC RRFIELD RESOURCES ADJUSTME S7 NODE TACTIC RRFIELD ADJUSTMENTS DOMAIN NODE TACTIC RRFIELD DOMAIN AME NAMTOK NODE INTERN QUOTE STRING STRTOK LITERAL UMBER NUMTOK LITERAL PREFIX S ANY 32 10 13 9 AMTOK PREFIX TOKEN ANY a z A Z ANY a z A Z 0 9 The File TACTIC DE 99 STRTOK PREFIX ANY TOKEN ANYBUT DELTOK ANY UMTOK PREFIX TOKEN ANY 0 9 lt 5 gt ANY 0 9 DELTOK END APPENDIX VIII DRACO TERMINAL DEFINITION Draco can use a terminal s special features if the terminal type is defined and stored in a file named lt termtype gt TRM A new terminal type is defined as a a set of simple LISP functions that are known to Draco The functions for a specific terminal are invoked by setting the terminal type using the SET command of DRACO_MENU An example for the Zenith Heath H19 terminal in its ANSI configuration will serve as a guide 60 Draco 1 2 Users Manual clear th screen sends lt 56 gt 27 address DE TERM C erase th DE TERM CLEAR NIL TERM MSG 27 2d the cursor UP LINE COL TERM MSG 27 current line
20. SEX NAMES gt gt gt gt Kazoo R S SEQ F r d N SEQ Sally tose S SEQ M t F N SEQ Dick Ph UAE S SEQ F OMEGA N SEQ Jane OMEGA Given the parse rules GET NAME and GET SEX which could produce the appropriate nodes this internal form could be constructed by the fragement CHART SE X S SEQ NAME S N SE Q GE T SE X G FE T NAME NODE S ET 1 1 The CHART construct accepts a variable number of header nodes and internal node pairs followed by an expression to produce nodes The number of nodes produced by the expression before it fails must be an even multiple of the number of node name pairs 2 2 6 Elements of Internal Form Description This section summarizes the internal form mechanisms in Draco BNF In lt token rule gt s only Syntax Meaning TOKEN show the start of the token DELTOK put the token into the token buffer In lt group rule gt s only Syntax Meaning LITERAL push the token buffer on the stack NODE form a new node and push it on the stack LITCHAR push the ASCII value of the next character on the stack TREE A B E evaluate E until fail and build right leaning tree with A top node B internal nodes possibly none and OMEGA terminator of the sequence vertical pars
21. 1 OT NO flo REFINE FUNCTION ALREADY AVAILABLE FUNCTION ACTIC RRCHECK AVAILABLE RESOURCE ACTIC INSTANTIATION AVAILABLE 1 INSTANTIATION ACTIC RPRFIELD 1 INTER 1 QUOTE 1 END APPENDIX X DRACO ERROR NOTE AND SYSERR MESSAGES There are three basic kinds of messages from Draco ERR NOTE and SYSERR An ERR is an error condition caused by a domain builder or user and is handled by Draco A NOTE is a message given only for the users information no problem or extraordinary event has occured but the user s environment has in someway been modified The creation of a file is an example of where a NOTE is used A SYSERR is a disasterous error in the Draco mechanisim itself which was caught by an internal consistency check within Draco The user should never save anything after a SYSERR unless directed it is alright to do so ERR NAME not a legal insertion command ERR NAME name already ready in use NAME ERR TRANSFORMATION not a transformation ERR TRANSFORMATION not a transformation ERR INSTANTIATION TYPE instantiation illegal ERR COMPONENT needs an instantiation ERR FUNCTION may not be EXECUTED ERR CLASS not a class ERR CLASS too few arguments CLASS ERR EXECUTE call in wrong form RR Syntax error rule RULE RR TRANS wrong number of arguments TRANSFO
22. BNF used in syntax directed compiling which is the foundation of the META systems Schorre64 Draco 1 2 Users Manual 2 1 1 Draco BNF Described in BNF The Draco BNF is described below by standard BNF with the following metasymbols lt name gt denotes a rule obj denotes zero or more occurrences of obj denotes alternation and a single word or character with quotes on either side denotes itself Where lt character gt matches any character and lt schar gt matches any character except a double quote lt DracoBNF gt DEFINE lt identifier gt lt Draco rule gt END lt Draco rule gt lt parse rule gt lt token rule gt lt parse rule gt lt identifier gt lt pars xp gt lt pars xp gt lt parse seq gt lt parse seq gt lt parse seq gt lt parse seq gt lt parse seq gt lt pars le gt lt parse ele gt lt pars le gt lt identifier gt lt string gt lt parse exp gt lt parse iteration gt EMPTY lt parse exp gt lt parse exp gt lt parse iteration gt lt lt iteration range gt gt lt parse ele gt lt parse ele gt lt iteration range gt lt iteration number gt lt iteration number gt lt iteration number gt lt number gt lt token rule gt lt identifier gt lt token exp gt lt token exp gt lt token seq gt lt token seq gt lt token
23. EMPTY gt X SEMICXIFELSE 1 281 IF P THEN X ELSE Y gt IF P THEN 81 2 ELSE 281 SEMICXWHILEX 6 28 WHILE UNTIL X SUBOX 12 0 X gt X SUBDD 5 A B C D gt A D B C B 2D SUBDX 3 A B C gt A C B B SUBMAB 10 A B gt A B SUBMAMB 11 A B gt B A SUBX0 12 X 0 gt X SUBXD 3 A B C gt A C B C SUBXX 11 X X gt 0 WHILEEMP 9 WHILE P DO EMPTY gt EMPTY WHILEF 12 WHILE FALSE DO S gt EMPTY WHILEIFELSE 1 WHILE P DO IF 20 THEN R ELSE S gt WHILE P DO WHILE 20 DO R 2S WHILEPUN 10 WHILE P DO UNDEFINED gt UNDEFINED WHILEUNS 12 WHILE UNDEFINED DO S gt UNDEFINED APPENDIX VI THE DEFINITION OF A COMPONENT INSERTION FILE The definition of a packet of components to be added to a refinement library is described in this appendix Errors in scanning these packets in REFGEN refer to the file REFGEN DEF given below VI 1 The File REFGEN DEF DEFINE COMPONENTS Component Library Scanner James Neighbors Last Modified December 29 1982 COMPONEN
24. IN all domains GEN actions as LISP_inline_sequence GEN ACTION SEQ execution sequence in a LISP PROG GEN arcs as LISP_inline_sequence GEN GARC use a LISP COND GEN states as LISP_inline_sequence GEN GCALL simulate the call in LISP REFINE gt do summary Component Summary C P OMPONENT GSTATE URPOSE define a state in the generator network d he component appears in the program as STREE The refinements for the component are REFINEMENT as inline LISP ASSERTIONS GEN states as LISP_inline_sequence INSTANTIATION INLINE A D SSERTIONS GEN states as LISP_inline_sequence CMD SUMMARY error OMAIN LISP REFINE gt defer restart tactics COMPONENT DNAME PURPOSE Represent the given name as a data item rather than as a variable representing a value TYPE how this component appears in program REFINEMENT quote the name for LISP DOMAIN LISP COMPONENT GVFETCH PURPOSE Get the value of the subtree associated with the selector at the top level of the tr being generated REFINEMENT extract value with LISP COND DOMAIN LISP OTE function GEN GVFETCH 0 defined COMPONENT QUOTE PURPOSE Put a literal name in an ATN tree QUESTION REFINEMENT use a LISP quoted atom ASSERTIONS ATN trees as LISP_lists DOMAIN LIS
25. The first ALL construct simply displays the fields of the component No refinement is found so processing advances to the next ALL construct The ALL lt DIRECTIVE gt is met for refinements that contain a directive from the Domain Designer These are seldom used suggestions that usually result in a refinement DEFER command These occur in special cases where the inside out refinement implies that this component will be removed by refinement and as such no refinement is necessary The ALL lt FUNCTION tactic states that if we have already refined a function for this component then just use a call to that function The ALL lt INLINE tactic states that if we can inline the refinement then use it inline Thus the DEMO ENTRY tactics will create a function where possible resulting in smaller but slower code The results of the CMD SUMMARY tactics can be seen in the previous Chapter where the REFINE gt DO SUMMARY command was given They print inforformation print ASSERTIONS twice an error but make no USE or TRY decisions They are support for the System Specialist making decisions If none of the tactics with ENTRY find a refinement then the Refinement User Interface is invoked and the user may use the CMD rules for information and making refinement choices Contrary to the DEMO ENTRY rule above the INLINE ENTRY rule below will inline as much as possible and as a last resort use the default refinement Heavy inlining makes
26. Y IF P THEN S1 ELSE S2 EN X IF P 2X gt UNDEFINED E EMPTY gt IF P THEN TRUE gt IFELSEXTF 12 UNDEFINED gt UND W IFELSENOT 12 IF P THE IFELSET 12 IF TRUE HEN S1 ELSE S2 gt 251 IFELSEUNX 10 IF P THEN UNDEFINED ELSE IFELSEXEMP 12 IF P THEN S1 ELS IFELSEXFT 12 IF X THEN FALSE ELSE ELSE FALSE gt X IFELSEXUN 10 IF P THEN X ELSE IFELSEXX 11 IF P THEN S1 ELSE 51 gt S IFEMP 11 IF P T 1 HE I IFF 12 IF FALSE PTY gt EMPTY HEN 251 gt EMPTY IFIF 11 IF X TH IFLESE2IFELSE 11 EN IF IF P TH ELSE Y THEN THEN S2 ELSE 251 251 IF X THEN TRUE EF INED IF Y THEN S1 gt IF X amp Y THEN S1 IE X THEN IF Y THEN S1 ELSE S2 ELSE S2 gt IF X amp Y THI EN S1 ELSE S2 IFLESSEQFOR 11 IF X lt Y THEN FOR W X STEP 2 FOR W X STEP 22 TO 27 DO 231 gt TO Y DO 251 IFLESSFOR 11 IF X lt X Y THEN FOR W X STEP Z TO Y DO 2531 gt FOR W X STEP Z TO Y DO 251 IF
27. commands acceptable at the DRACO gt menu prompt can be put into a command file entitled DRACO INI This is useful for setting up terminal types and getting updates of the Draco software 1 5 Overview of the User Manual The manual is organized in 10 chapters and 10 appendicies The chapters are organized as follows Chapter 1 Introduction to the Draco approach and general guide to the system Chapter 2 Detaled explanation of how to write parser definitions using Draco and how to build a parser for a domain language Chapter 3 Detailed explanation of how to write a prettyprinter definition and how to build a prettyprinter for a domain language Chapter 4 Explanation of how to write transformations and how to build a transformation library for a domain language Chapter 5 Explanation of how to write components with refinements and how to build a component library Chapter 6 Explain and give example of how to parse a program in a domain language to the Draco internal form Chapter 7 Explain the use and the main commands of the Transformation and Refinement subsystem of Draco Chapter 8 Explain how a transformation library should be used to optimize a given program Explain how a System Specialist should use the system to to refine a program written in a domain language into an Chapter 9 executable language It describes all the necessary commands to do a refinement Chapter 10 Explain the Tactics subsystem and show how to use it Appendix I Gives
28. gt true Usually as the small packets of transformations in insertion files are added to the transformation library the user should concatenate these packets together into a file in case the transformation library ever need be generated from scratch The following file combines the transformations from this section PVARS x y 2 TRANS true 95 compr x x true TRANS false 97 uneq x x false TRANS not 95 negation uneq x y compr x y TRANS not 95 negation compr x y uneq x y TRANS ifeliml 99 ifthen true x x TRANS ifelim2 99 ifthen false x empty TRANS ifelim3 99 ifelse true x y x TRANS ifelim4 99 ifelse false x y y ERASEPVARS PVARS x y 2 TRANS parenthelim 99 paren paren x paren x TRANS parenthelim2 98 stmnt paren x stmnt stmnt x stmnt TRANS parenthelim3 98 stmnt paren x OMEGA stmnt x OMEGA TRANS stmnteliml 12 stmnt empty stmnt stmnt TRANS stmntelim2 12 stmnt empty OMEGA OMEGA TRANS bodyelim 12 body stmnt x OMEGA x TRANS bodyelim2 12 body stmnt empty OMEGA empty ERASEPVARS CHAPTER 5 BUILDING A COMPONENT LIBRARY WITH REFGEN 5 1 The Constituent Parts of a Component An example component for exponentiation is shown below The component provides the semantics for EXP internal form nodes for the language SIMAL which is lt Strong gt not lt Strong gt a domain speci
29. the meaning of the adjustment and a default setting An example adjustment term might adjust the accuracy of a refinement or limit the amount of time spent in calculating in the refinement The GLOBAL field lists all names used in the refinement which are not to be renamed The primary use of a GLOBAL definition is to define variable names which are reserved by a domain and cannot be renamed The SNOBOL variable amp ANCHOR is an example global GLOBAL definitions should seldom be used and are always suspect They seem to stem from a poor analysis of a domain Labels which are defined in the refinement are defined in the LABELS field of the refinement The way a refinement may be inserted into the internal form tree during refinement is governed by the INSTANTIATION field of the refinement The three modes of instantiation are INLINE FUNCTION and PARTIAL More than one instantiation may be given for a refinement with the first one listed being the default instantiation INLINE instantiation means the refinement is substituted directly into the internal form tree with all variables used in the refinement renamed including labels except for the arguments and those declared global FUNCTION instantiation substitutes a call for the component in the internal form tree and defines a function using the refinement for the body A new function is defined only if the same function from the same domain has not already been defined PARTIAL instantiation substitu
30. LISP read would be better DOMAIN LISP COMPONENT NOTEST PURPOSE No arctest is performed thus the test always succeeds concept does not print in domain REFINEMENT use a LISP true for the test DOMAIN LISP COMPONENT NOTEST PURPOSE No arctest is performed thus the test always succeeds REFINEMENT use a LISP true for the test DOMAIN LISP ENT TEST SEQ PURPOSE Try testl if it succeeds then try test2 otherwise fail the test REFINEMENT use McCarthy LISP AND for test sequence DOMAIN LISP user interrupts tactics from keyboard tactics interrupted by user tactics have failed to find a refinement invokes interactive refine interface O A 3 User Refinement Interface REFINE gt do summary interpret CMD SUMMARY tactic Component Summary COMPONENT TEST SEQ p PURPOSE ry testl if it succeeds then try test2 otherwise fail the test The component appears in the program as he refinements for the component are EEINEMENT use McCarthy LISP AND for test sequence NSTANTIATION INLINE OMAIN LISP 3 OHW REFINE gt help The Refinement User Interface Commands are TRY lt refinement gt lt instantiation gt attempt to use a refinement show and ask before use USE lt refinement gt lt instantiation gt use a refinement and don
31. NILL 0 GENERR exit OR genrstack RETRUN genrslt GO POP genrstack lt lt 1 lt lt lt UVUFOAUVUVOHAZAAN TFMREF gt TRANSFORM LO CODE 50 HI CODE 90 APPROVAL MODE ASK The System Specialist wishes to apply all transformations with application codes in the range 50 to 90 Approval for each transformation is also desired The transformation library is loaded If there were no TLB file available an error message would be displayed and the process aborted NOTE transformations loaded In the following lines Draco asks the System Specialist if it should apply each transformation For each transformation Draco gives the following lt name gt lt application code gt lt lhs gt gt lt rhs gt If the specialist confirms the transformation Y the left hand side lhs is substituted by the right hand side rhs at that point in the locale NIELI 50 NILL gt NIL Y N gt Y ANDSEQT 80 AND T gt Y N gt Y ANDSEQT 80 AND T gt Y N gt Y ANDEMPTY 80 AND gt T Y N gt Y ORT 80 OR T GO alab gt T Y N gt Y The following transformation relates large lhs and rhs expressions Look for the gt delimiter Remember Draco is printing the instance in 35 Draco 1 2 Users Manual the problem at hand no the transformation de
32. NOTE new domain instance selected automatically another GEN instance was found ROPNE 7 NOTE no domain instance selected no more GEN domain was found FMREF gt domain lisp NOTE GEN domain being removed FMREF gt instance SETQ genrslt NCONC genrslt LIST item Y N gt N not LISP domain instance we want sa een 01 Y N gt N still not the instance EMB selector CAR gentree 55 EN COND OR OC selector CAR gentree ERR Y N gt N yet again not the instance OODS gendict gentree PROG genrslt genrstack Draco 1 2 Users Manual OR ga DS Y N gt Y yes select this LISP instance TFMREF gt pp DE GWOODS gendict gentree PROG genrslt genrstack SETQ gentree LIST gentree GO STREE NILL lt STREE OR AND T T GO alab PUSH genrstack rlab PUSH gentree GO SUBJECT rlab PUSH genrstack rlabl PUSH gentree GO VERB PHRASE rlabl GO 51 alab NILL lt GENERR 51 OR AND EQUAL QUESTION GO alabl POP gentree GO exit alabl NILLE SS ss Sss OR AND EQUAL DECLARE GO alab3 POP gentree GO exit alab3 NILL lt GENERR exit OR genrstack RETRUN genrslt GO POP genrstack TFMREF
33. One of the following CLASS TRANS ANNOTATE APPLY DOMAIN EXIT HARDCOPY HELP INFO INSTANCE LOCALE NOINSTANCE EP REFINE REFLRU SAVE SUGGEST TACTICS TRANSFORM UNLOAD REFINE UNLOAD TRANSFOR The pretty printed version of the locale given below shows the new version of the code after the previous transformations were applied TFMREF gt PP DE GWOODS gendict gentree PROG genrslt genrstack SETQ gentree LIST gentree GO STREE STREE PUSH genrstack rlab PUSH gentree GO SUBJECT rlab PUSH genrstack rlabl PUSH gentree GO VERB PHRASE rlabl GO 51 alab GENERR 51 OR EQUAL QUESTION GO alabl POP gentree GO exit alabl OR EQUAL DECLARE GO alab3 POP gentree GO exit alab3 GENERR exit OR genrstack RETRUN genrslt GO POP genrstack CHAPTER 9 USING THE TFMREF REFINEMENT SUBSYSTEM 9 1 The TFMREF Commands Which Work With Refinements 9 2 How a Component is Used This section discusses how the fields of a component are used in the refinement process to choose an implementation for the operation or object the component represents First the IOSPEC conditions on the component should be verified by examining the internal form or refinement history of the surrounding internal form of the node to be refined Restrictions on the legal internal forms accepted by
34. TREE ID USE COMPONENT LITERAL NODE PARSER TRE CHART LIST PARSER CHART ID USE COMPONENT LITERAL EX1 lt 1 gt ID USE COMPONENT LITERAL ID USE COMPONENT LITERAL EX1 EX1 EX1 NODE PARSER ERRORBLOCK 2 1 DEF ID ODE PARSER DECLARE DEF USE ID NODE PARSER DECLARE USE RESOLVE ID NODE PARSER DECLARE RESOLVE RETRACT ID NODE PARSER DECLARE RETRACT ASSUME ID NODE PARSER DECLARE ASSUME CONTEXT PUSH ID NODE PARSER DECLARE PUSH CONTEXT POP ID NODE PARSER DECLARE POP 1 ERROR NODE PARSER ERROR FAIL NODE PARSER FAIL MSG LIST PROGN MINFO NODE AND T LIST ID LITERAL EX1 NODE PARSER LIST 2 1 SEXPN EX1 NODE PARSER SEXPN 1 EXECUTE NODE PARSER EXECUTE LIST NCONC ID USE COMPONENT
35. When working on the refinement of a large and complex system in an iterim stage ofdevelopment it is important to bound the context 27 Draco 1 2 Users Manual of refinement considered by the System Specialist In TFMREF this is acheved with three mechanisms DOMAIN INSTANCE and LOCALE While a program is being refined it may exist as program fragments in many domains at once The different domains are being used as modelling domains for the problem So the first index of bounded context is which DOMAIN the System Specialist intends to work in Once the domain is selected then which INSTANCE of this domain is desired provides a second restriction of context Finally provision is made for the System Specialist to specify a restricted LOCALE within the instance of the selected domain All of these narrowings of the context serve to focus both the System Specialist and TFMREF in examining what can be done Initially when TFMREF is entered it requests the file containing the internal form of the program to be refined the domain and the instance The following sections describe the commands which restrict the context The selected context can be displayed in a shorthand notation using the INFO command 7 1 1 The DOMAIN command DOMAIN lt domain name gt The domain command is used to change the domain the System Specialist whishes to work in TFMREF automatically performs a DOMAIN command upon entry All parts prettyprinter transformations
36. component In the DEFINE command we can determine which fields of the component we would like to display The simple demonstration tactics DEMO TCT we used for out refinement session in the previous chapter are shown below DEFINE HEAD ENTRY DEFINE DEMO ENTRY COMPONENT PURPOSE ALL REFINEMENT CONDITIONS ASSERTIONS BACKGROUND DOMAIN ALL lt DIRECTIVE gt USE ALL lt FUNCTION INSTANTIATION gt USE FUNCTION ALL lt INLINE INSTANTIATION gt USE INLINE DEFINE CMD SUMMARY Component Summary COMPONENT PURPOSE IOSPEC DECISION The component appears in the program as Loc 10 The refinements for the component are ALL REFINEMENT CONDITIONS ASSERTIONS BACKGROUND DIRECTIVE INSTANTIATION ASSERTIONS RESOURCES ADJUSTMENTS DOMAIN EXIT When the refinement mechanism needs to choose a refinement for a component it runs the ENTRY tactics in the order in which they were defined The HEAD tactics in this case simply prints a CRLF but does not choose a refinement The refinement mechanism then moves to the DEMO tactics that first print the component context to a internal tree depth of 4 LOC 4 The ALL construct steps though each refinement for the component until a refinement has been selected
37. either a sub command is needed or the specification of the original command does not contain enough characters to differentiate between a group of commands LINEFEED at the same point will show the possible commands needed to complete e Unknown Command is issued when a RETURN was given to activate the command and the given command is not one of the possible choices e Command Unconfirmed is issued when all the fields of a command have been filled in but the last field was not terminated by a RETURN The assumption is that a user does not understand the command if he prompts for more fields on the last field e lt fieldname gt was not specified is issued when some but not all of the required fields of a command have been specified The fieldname given is the next field to be entered Usually menus contain a help command which will print out detailed documentation for the commands in the menu The command will exit the menu returning to the next higher subsystem In addition a command to most requests for an input file name will return to the next higher menu Draco 1 2 Users Manual 1 4 Terminal Definition for Draco Some of the features available in new terminals are used by Draco to highlight information and interact with the user Primarily these interactions are based around the ANSI terminal standards Some flexability in defining new terminals is described in appendix APPX TERMINAL Commands from the main menu of Draco i e
38. gt 2 lt OIDOPS gt 1 lt OIDOPS gt 2 lt OP gt 1 lt OP gt 2 ABS ABS 1 myn ADD 1 4 2 AND 1 6 2 AP r JL TREEPRINT SPSEQ 1 APSEQ 1 TREEPRINT APSEQ 2 ASELECT 1 p 2 kk A ASSIGN SLM 1 2 BLK TREEPRINT BLKSEQ 2 BLKSEQ 1 TREEPRINT BLKSEQ 2 BLOCK SLM LM 1 2 DIV 1 2 EQUA 4 2 gt EXP 1 4 2 FALSE FALSE FNCALL 1 4 gt FNDEF 1 2 SLM LM 2 3 SLM FOR SLM FOR LM 1 2 STEP TO 4 DO SLM 22 5 FOR1 SLM FOR LM 1 2 TO 3 DO SLM 22 4 FP Her JL TREEPRINT FPSEQ 2 FPSEQ 1 TREEPRINT FPSEQ 2 GOTO SLM GOTO 1 GTR 1 gt 2 GTREQ 1 gt 2 IDIV TINE IF SLM IF 1 LM THEN 2 IFELS SLM IF 1 LM THEN INT IN 1 myn LABE LM 10 SLM 1 LM 0 2 LESS y lt 42 3 LESSEQ 1 lt 2 LOC LOCAL TREEPRINT LOCSEQ 1 LOFSEQ 1 TREEPRINT LOCSEQ 2 MINUS 1 7 MPY 4 x 2 NOLOC NOT S 1 7 NOTEQ 1 2 7 1982 f r r 3 2 SLM 22 ELSE 3 53 Draco 1 2 Users Manual
39. has EC s Reverse canonical form no EC s Reverse canonical form has EC s Operator arrangement no EC s Operator arrangement has EC s Flow statement arrangement no EC s Flow statement arrangement has EC s Program segment arrangement no EC s Program segment arrangement has EC s Start a Markov algorithm These are completely arbitrary and you may make up your own codes The codes for source to source transformations run from 1 to 99 while Markov algorithms use above 100 and 0 The Draco system knows nothing about particular application codes except that odd codes represent transformations with enabling conditions Since the current system does not support the checking of enabling conditions it stops and asks the user before it applies any transformation with an odd code The codes are used in the TFMREF subsystem by the TRANSFORM command In the future the application codes may be used for a best first style lookahead so the better transformations should have higher application codes 4 3 The Catalog of Transformations for a Domain When XFMGEN produces a new library it gives the option for a catalog listing The catalog is a listing of all the transformations in alphabetical order prettyprinted by the domain prettyprinter To prettyprint classes they must be defined to the prettyprinter Our example above would require the line lt COMOP gt
40. identity the set MPY and EXP lets do expx2 here at B 2 Y N gt Y before and after zoom out from where tfm took place get me to the instance root now did the program change ION SOLVER CRLF ETERS C 2 A we changed this line C 2 A ARE ROOT1 AND ROOT2 CRLF HI CODE 12 APPROVAL MODE ask The easier way to do transformations TRANSFORM applies transformations throughout th 3 and 12 mean application cod doing any transformations Al e currently selected locale es 3 to 12 and ask me before l transformations with enabling conditions will always ask anyway EXPX2 7 B 2 gt B B Y N gt Y TFMREF gt PP lets see where the change was made PROGRAM QUADRATIC SQUADRATIC LOCAL A B C ROOT1 ROOT2 LOOP PRINT QUADRATIC EQUATION SOLVER CRLF PRINT INPUT A B C PARAMETERS A READNUM IF A 0 THEN RETURN B READNUM C READNUM ROOT1 B SQRT B B 4 A C 2 A 32 Draco 1 2 Users Manual ROOT2 B SQRT B B 4 A C 2 A this line changed PRINT THE ROOTS ARE ROOT1 AND ROOT2 CRLF GOTO LOOP J END TFMREF gt INFO what am I doing with what when 5 25 79 23 28 41 PROGRAM QUAD INT D I OMAIN SIMAL PP TFM prettyprinter and transforms in memory STANCE PROGRAM QUADRATIC instance and locale are same SQUADRATIC
41. issue in writing parser descriptions is to make the grammar clear 2 1 5 Error Recovery During Parsing If the only control constructs we used in parser descriptions were sequence alternation and backtracking then the error recovery power of the parsers would be severly limited By error recovery here we mean being able to handle ill formed statements in the language report them to the user pass over them in the input stream and continue parsing Once a sequence operator reports a syntax error all alternation operators will pass on the error and backtracking operators will trap the error and try their next alternative A simple ill formed expression would usually cause the entire parse to fail either by backtracking out of the top level rule or by passing a syntax error back from the top level rule which would abort the parse Some error control could be built in by using the backtracking operator but we have decided to introduce a special error recovery mechanism called an error block The syntax of an error block is as follows lt parse ele gt lt parse ele gt The first expression of the block is attempted and if a syntax error results then the state of the parser is restored to the point where the error block was encountered an error message is printed indicating the rule which originated the error and the position in the input stream at the time of the error finally the second expression is attempted It is the goal of the second e
42. of entries These prefix form trees are built from the bottom up as Draco scans a program in a domain language In particular when a token is recognized in a lt token rule gt it is stored in a token buffer It is then the responsibility of a lt parse rule gt to take the token combine it into a new node and insert it into the growing tree The growing tree is maintained as a stack of objects which have not yet been combined into higher nodes The prefix form for a domain should have a single root which is left as the last node on the stack 2 2 1 External Internal Form Specification The operators for constructing internal forms are mixed in with the Draco BNF notation and each is preceeded by a period The internal form construction operators should not be confused with ANY and EMPTY which are part of the external form specification Only two rules from the earlier BNF specification of the syntax need be changed to add the tree construction operators The two revised rules and a new rule are given below lt pars le gt lt identifier gt lt string gt lt parse exp gt lt parse iteration gt EMPTY LITERAL LITCHAR NODE lt identifier gt lt node ele gt TREE lt identifier gt lt identifier gt lt parse exp gt CHART lt token ele gt lt identifier gt lt char rule gt lt token exp gt lt token iteration gt EMPTY TOKEN DELTOK
43. purpose high level languages for the domains or problem areas in which many similar systems are needed the use of software components to implement problems stated in these languages in a flexible and reliable way and the use of source to source program transformations to tailor the components to their use in a specific context The basic steps in the production of a specific system using a Draco supported domain specific high level language is as follows 1 An analyst with experience in developing many systems in a certain problem domain decides that the domain is understood well enough to define a language suitable for comfortably and easily describing other systems in the problem domain This person is called the Domain Analyst and the language described is called the Domain Language The Domain Analyst describes the domain and its internal form with the parser generator part of the BUILD subsystem of Draco which is described in Chapter 2 2 Once the Domain Analyst has described the external and internal form of the domain then how program fragments in the domain should be printed so that users find them easy to look at and accurate in their meaning must be described This is called prettyprinter generation and it is done by the Draco BUILD subsystem using the notations described in Chapter 3 3 The Domain Analyst must provide simplifying relations among the objects and operations of the domain These are used for simplification and optimization of pr
44. specification is given in Appendix APPX PAREXAMP with some example programs in the language 2 5 Using the Draco Parser Generator For the purposes of this example we assume that the definition of a language is already prepared in Draco BNF and in the file LANG DEF The following is an example transcript DRACO gt BUILD PARSER LANG LANG DEF screen clears kkkkkkk one signifys a line processed Parse Completed the extension defaults to PAR LANG PAR created DRACO gt Once the parser has been created programs in the new language may be parsed by the Draco subsystem PARSE If the parse had not successfully completed then the system would have stated why as in Draco 1 2 Users Manual KKK KKK ERR Syntax error rule EX3 STMTS STMT lt scan gt lt 256 gt STMT fa line from LANG DEF the lt SCAN gt marker is highlighted on some terminals and indicates the position in the input stream kkkkkkkkkkkkk more lines processed Parse Completed 1 errors detected The rule EX3 cited from PARGEN means the rule EX3 in the file PARGEN DEF which describes the Draco BNF of parsers in Draco BNF Other possible errors are discussed in the section on errors see ERR PARGEN DEF is reproduced in Appendix APPX PARGEN and it gives the exact syntax of a domain language definition CHAPTER 3 BUILDING A PRETTYPRINTER WITH PPGEN After the external and internal forms of a domain language have been described to Draco with BUI
45. t show or ask DEFER defer control back to the entry tactics restart tactics ABORT return to the TFMREF subsystem level stop tactics DO lt tactic CMD name gt do a predefined tactic command HELP this listing All of these commands are discussed in more detail in the Draco user manual REFINE gt information ABOUT memory usage Free Stoarge 40836 Full Word Space 6488 REFINE gt defer restart tactics Draco 1 2 Users Manual COMPONENT TEST PURPOSE Try tests for arc REFINEMENT use McCarthy LISP AND for test sequence DOMAIN LISP COMPONENT DNAME PURPOSE Represent the given name as a data item rather than as a variable representing a value SUBJ how this component appears in program REFINEMENT quote the name for LISP DOMAIN LISP OMPONE URPOSE et the subtree associated with the selector at the top c ENT GTFETCH P G level of the tr being generated R D EFINEMENT check tr xistence with LISP OR OMAIN LISP OT function GEN GTFETCH 0 defined refinement instantiated a function user interrupts tactics from keyboard NO NO tactics interrupted by user tactics have failed to find a refinement invokes interactive refine interface User Refinement Interface REFINE gt information ABOUT assertions
46. to Internal Form with PARSE 6 1 Using the PARSE Subsystem 6 2 How Transformations are Suggested in PARSE 6 3 Multiple Domains 7 Using TFMREF the Program Manipulation Subsystem 7 1 The TFMREF Commands Which Set the Context 7 1 1 The DOMAIN command 7 1 2 The INSTANCE command 7 1 3 The LOCALE Command 7 2 The Miscellaneous TFMREF Commands 7 2 1 The PP Command 7 2 2 The INFO Command 7 2 3 The HARDCOPY Command 7 2 4 The SAVE Command 7 2 5 The EXIT Command 7 3 A Summary of the TFMREF Commands 7 4 An Example Session with TFMREF 8 Using the Program Transformation Mechanism 8 1 The SUGGEST command 8 2 The APPLY Command 8 3 The TRANSFORM Command 8 4 The TRANS Command 8 5 The CLASS Command 8 6 The UNLOAD TRANSFORM Command 8 7 Transformation Example 9 Using the TFMREF Refinement Subsystem 9 1 The TFMREF Commands Which Work With Refinements 9 2 How a Component is Used 9 3 The Refinement Mechanism 9 4 The TFMREF Commmand REFINE 9 5 Commands Available through the Refinement 9 5 1 The TRY Command 9 5 2 The USE Command 9 5 3 The DEFER Command 9 5 4 The ABORT Command 9 5 5 The DO Command 9 5 6 The HELP Command 9 5 7 The INFORMATION Command 9 5 8 A Summary of the Refinement User Interfac 9 6 An Example Session with REFINE 10 Using the TFMREF Tactics Subsystem Notes References I A Complete External Internal Language Definition 1 1 External Internal SIMAL Definition I 2 Example SIMAL Programs 1 1 Quadra
47. will output tabs and spaces to get to the left margin If the carriage is past the current left margin then SLM will perform a carriage return before tabbing and spacing over to the left margin Remember if the output of the prettyprinter for a domain is to be acceptable input for the parser of the domain then that parser must accept tabs and spaces in positions where the prettyprinter indicates there will be whitespace in the prettyprinted output A numerical argument given to SLM as in SLM 65 will cause the SLM to be effective only if the column position of the carriage is greater than the argument Thus in the example above if a function call has more arguments than will fit on a line 60 columns then the arguments which overflow will be printed under the first argument to the function If a number appears by itself in a prettyprinter description then it means to send that ASCII code to the output It is alright to send literal carriage control characters to the output in that the prettyprinter understands where the carriage is but it is not a very good idea 3 3 Output Device Dependent Codes This is currently unimplemented but it is planned to provide an abstraction of different output devices for highlighting and cursor control The basic information needed by the prettyprinter for these operations is the character sequence to send and the change in screen position the code causes Some example control codes are given below 1 normal mod
48. 1 1 1 1 1 e 2 2 EE 2 2 e EF anions 3 a i N th 3 Building a Prettyprinter with PPGEN 3 1 The Syntax of a Prettyprinter Description 3 2 An Example of a Prettyprinter Description 3 3 Output Device Dependent Codes 3 4 Prettyprinting TREEs and CHARTs 3 5 Special Prettyprinter Functions 3 6 Jula 3 8 Elements of a Prettyprinter Description Producing a Successful Prettyprinter Using the BUILD Subsystem to create a Prettyprinter 4 Building a Transformation Library with XFMGEN 4 1 The Transformation Library and Metarules 4 1 1 Transformation Metarules Specifying the Program Transformations 4 2 1 The Syntax of a Transformation Insertion File 4 4 4 4 2 2 2 An Example of a Transformation Insertion File 2 3 Elements of a Transformation Insertion File 2 4 The Application Code of a Transformation 4 3 The Catalog of Transformations for a Domain 4 4 Using the Draco XFMGEN Subsystem Draco 1 2 Users Manual User Interface Commands 5 Building a Component Library with REFGEN 5 1 The Constituent Parts of a Component 5 2 The Motivation for Libraries of Components 5 3 Building a Component Library 6 Converting a Program
49. 7 B C gt A B gt A B 22 0 gt A B C FALSE amp X 11 ANDOO 11 X amp FALSE gt 11 X amp ANDXOR 9 X6 TRUI gt X X6 X X X amp Y IF X PA gt B gt 2X gt gt gt gt pprrrprrrrrrrrrrera ZZ ee zz ee ee lee ASSIG ASSIG ID XX 11 11 X X X Y X 7 gt 12 LOCAL X S gt BLOCKBLOCKN BLOCKEMP 12 LOCAL X EMPTY 12 X Y 12 X Y 12 KERSA EMPTY FOR BLOCK BLOCK BLOCK BLOCK BLOCK lt CALL gt ASSIGN BLOCKN EMP 12 FOR 12 F 2Z 12 iS BLOCK BLOCK IF IE IF 12 I PT LE HEN ZENE F H 2 261 FA X ANDTX FA kT 2V W ST gt UND 2 1 gt A lt div gt B EFINED A lt rel gt B IF B gt 0 THEN B ELSE A A lt rel gt IF C Ir gt gt C C C gt IF C gt A lt rel gt B C gt A lt rel gt lt uop gt X gt UND N S1 gt THEN S1 ELS 252 EF INED IF P E gt D gt UND REIN ED 2B A D B C 2 A C B B A 2 A B B 2C SE 12 TRUE SE X amp X Y gt T F H pa N Y FALS F E PTY X i g
50. CAL A B C ROOT1 ROOT2 LOOP PRINT QUADRATIC EQUATION SOLVER CRLF PRINT INPUT A B C PARAMETERS A READNUM IF A 0 THEN RETURN B READNUM C READNUM ROOT1 B SORT B 2 4 A C 2 A ROOT2 B SORT B 2 4 A C 2 PRINT THE ROOTS ARE ROOT1 AND ROOT2 CRLF GOTO LOOP END gt TFMREF gt LOCALE lets restrict the context PROGRAM QUADRATIC SQUADRATIC Lles END TFMREF gt locale 1 SQUADRATIC LOCAL swa TFMREF gt locale 1 LOCAL A B C ROOT1 ROOT2 LOOP wal TFMREF gt locale 2 LOOP Draco 1 2 Users Manual PRINT 7 PRINT TFMREF gt locale 2 PRINT INPUT A B C PARAMETERS A READNUM y TFMREF gt locale 2 A READNUM IF THEN TFMREF gt locale 2 IF A 0 THEN RETURN B READNUM TEMREF gt locale 2 progressively deeper into program B READNUM C READNUM TFMREF gt locale 2 C READNUM ROOT1 or TFMREF gt locale 2 ROOT1 ROOT2 FMREF gt locale 1 ROOT1 FMREF gt locale 2 number too large fan error try again FMREF gt locale 1 ected ZFA FMREF gt locale 1 B SQRT FMREF gt locale 1 B SQRT FMREF gt locale 2 SORT 4 whe 4424 FMREF gt loca
51. CTIC BL EMPTY NODE TACTIC LIST TACTIC BL RULE LIST PROGN RCMD RCMD NODE QUOTE 1 59 Draco 1 2 Users Manual RCMD STRING NODE TACTIC MESSAGE 1 COMPONENT NODE TACTIC RPCFIELD COMPONENT PURPOSE NODE TACTIC RPCFIELD PURPOSE TOSPEC NODE TACTIC RPCFIELD IOSPEC DECISION NODE TACTIC RPCFIELD DECISION LOC NUMBER NODE TFMREF LOC 1 EMPTY NODE TFMREF LOC TACTIC BLANK KLUGE USE DEFAULT NAME NODE REFINE USE NUM 1 1 EMPTY NODE REF INE USE NU 1 TACTIC BLAN
52. DIRECTIVE FUNCTION DEFINITION NODE DIRECTIVE DIRECTIVE CALL NODE DIRECTIVE DIRECTIVE FN CAL DEFER NODE DIRECTIVE DIRECTIVE DEFER CR END REFINEMENT lt 1 gt BLIN DOMAIN 2 U tr CONDITIONSET LIST CONDITIONS CONDITION WHITE CONDITION ASSERTIONSET LIST ASSERTIONS ASSERTION WHITE ASSERTION CONDITION NAME NAME as NAME NODE CONDITION 43 2 1 CR ASSERTION NAME NAME as NAME NODE ASSERTION 3 2 1 CR E ILIST NAME SEXPN NAME lt gt ILIST CR REFNAME REFNTOK LITERAL AME NAMETOK LITERAL LTEXT MLTOK LITERAL PREFIX ANY 32 9 WHITE lt 1 7 gt ANY 32 9 CR PREFIX ANY 13 10 ANY 13 10 EOF ANY 26 REFNTOK PREFIX TOKEN lt 1 gt NAMECHR ANY 32 DELTOK AMETOK PREFIX TOKEN lt 1 gt NAMECHR DELTOK AMECHR ANY A Z a z 0 9 l _ LTOK PREFIX TOKEN LINE ANY 32 9 LINE DELTOK LINE ANY 32 125 9 CR BLINE ANY 32 CR APPENDIX VII THE DEFINITION OF TACTICS This is the definition of t
53. DO EMPTY TEP X TO Y DO gt IF W lt Y THI FOR V W X ST WHILI UNTIL Y DO Y EN Z2 V W 7 EP X TO Y DO Draco 1 2 Users Manual 22 FORREDUCE 5 FOR V W STEP X TO Y DO DO Z V 0 gt FOR V W 0 511 22 FORTOWHILE 2 FOR V W STEP X TO Y DO V V X FORUN 12 FOR V W S UNDEE FORXX 11 FOR W X S 22 22 gt V W EP X Q TO Y Q WHILE V Y SIGN X lt 0 DO 2 EP X TO Y DO INED gt UNDEFINED gt GTREOXX 11 X gt X GTREQXY 10 X gt Y GTRMAMB 12 A gt B GTRXX 11 X gt X gt GTRXY 10 X gt Y gt gt gt gt FALSE EP Y TO X DO W X 22 TRUE A lt B IFELSE lt CALL gt 6 IF P IFELSE lt SEL gt 6 IF IFELSEEMPX 12 IF E X gt IF P TH IFELSEF 12 IF FALSE P THEN Y S1 ELS 2 THE EMPTY ELS HE S1 ELS E S2 gt 282 IFELSEIFXIFX 6 IF EN IF X THEN W ELSE IF Y THEN W gt S1 ELSE S2 gt THEN Y S1 ELSE Y S2 gt Y IF P THEN 251 ELSE S2 E Y S2 gt
54. DRACO INI initialization file may contain any of these command The rest of the sections of the manual assume that Draco is loaded and already in execution 1 3 Interacting with Draco Menus Draco uses a standard menu interaction which includes command completion and a help facility NOTE 4 The following keys control the menus in Draco e RETURN terminates commands and requests execution e LINEFEED requests information about the options which exist at the current point in the menu e ESCAPE requests that the menu driver fill in the current choice if it is unambiguous and prompt for the next menu item required If the current command is still ambiguous then the terminal will beep and the cursor will not move At this point a RETURN will abort the command because it is ambiguous and a LINEFEED will list the acceptable inputs Once one of the activation characters given above has been given no characters before the activating character can be deleted This is an effect of only activating on these characters and not activating on RUBOUT DELETE or BACKSPACE A command which has been entered correctly is usually aborted with a RETURN The following error messages are given by the menu driver when a command is aborted e Incomplete Command is issued when all the fields required by the command have not been filled in and a RETURN was given to activate the command e Ambiguous Command is issued when a RETURN was given to activate the command and
55. Draco 1 2 Users Manual Draco 1 2 Users Manual 21 June 1983 by James M Neighbors Department of Information and Computer Science University of California Irvine Irvine CA 92717 This work was supported by the National Science Foundation Software Engineering Section under NSF grant MCS 81 03718 and by the Air Force Office of Scientific Research Copyright 1983 1997 James M Neighbors All rights reserved Table of Contents 1 An Introduction to the Draco System Tal The Draco View of Software Production 1 2 Running the Draco System 1 3 Interacting with Draco Menus 1 4 Terminal Definition for Draco 2 Describing a Domain Language 2 1 The External Form Syntax Specification ae Draco BNF Described in BNF An Example of Draco BNF The PREFIX and SUFFIX Rules Controlling Parser Backtracking Error Recovery During Parsing Elements of External Form Description Recognizing the End of the File omplete External Internal Form Specification External Internal Form Specification Specifying a Legal Parser A Complete External Internal Form Example An Example Internal Form Elements of Internal Form Description ial Functions in Parsers Checking Consistency in Parsers Notifying the User Non Standard Parser Constructs of PARGEN Parsers ng the Draco Parser Generator N N 7 COINS ERO RO RE ROOTA RZN Re ro Ro SIN wio PBS WIN JH QJ Jo JOT JOO N 1
56. EE STREE PUSH genrstack rlab PUSH gentree GTFETCH SUBJ GO SUBJECT rlab PUSH genrstack rlab PUSH gentree GTFETCH VP GO VERB PHRASE rlabl GO 51 alab 45 Draco 1 2 Users Manual GENERR 51 OR EQUAL GVFETCH TYPE QUESTION GO alabl GOUT mon POP gentree GO exit alabl OR EQUAL GVFETCH TYPE DECLARE GO alab3 GOUT R mey POP gentree GO exit alab3 GENERR exit OR genrstack RETURN genrslt GO POP genrstack TFMREF gt hardcopy wg NOTE WG DOC created TFMREF gt exit Do you want to save the changes Y N gt Y NOTE WG INT saved DRACO gt This example is somewhat unrealistic in that it takes a fragement of the GEN domain and refines it all the way to an executable in LISP GEN is a modelling domain for NLP RDB which glues together a collection of domains e g DIC GEN ATN RDB to perform natural language database query see Neighbors80 Because of this the START function simply returns the definition of the GEN fragment and the exception GENERR and output GOUT handlers are not connected However this small example demonstrates the flavor of using the Draco refinement mechanism CHAPTER 10 USING THE TFMREF TACTICS SUBSYSTEM The TACTICS subsystem s objective is to provide guidelines that can be used during the refinement p
57. ERAL EX1 STRING LITERAL NODE ASSIGN 2 1 EX1 EX2 EX2 NODE ADD 2 1 EX2 EX3 EX3 NODE MPY 2 1 EX3 EX4 EX3 NODE EXP 2 1 EX4 IDENTIFIER LITERAL APARAMS NODE FNCALL 2 1 EMPTY NUMBER LITERAL wan EX1 MA A APARAMS TREE APARAMS APSEQ EXP EXP PREFIX SPACES IDENTIFIER SPACES TOKEN ALPHA lt 5 gt ALPHA DIGIT DELTOK NUMBER SPACES TOKEN DIGIT DIGIT DELTOK STRING SPACES TOKEN ANY ANYBUT ANY DELTOK H I END First of all notice the TOKEN and DELTOK operations which have been added to the token rules The TOKEN states which 10 Draco 1 2 Users Manual character should be the first in the token and the DELTOK places the token in the token buffer In this case the TOKEN in the IDENTIFIER rule states that the initial spaces are not part of the identifier The lt parse rule gt s form internal tree nodes from a stack of objects The operator LITERAL takes the last token put into the token buffer by a DELTOK and pushes it on the stack The operator NODE takes objects from the stack the token buffer and literal data ADD MPY etc forms these into a new node and pushes it on the stack Thus NODE takes just the token buffer forms it into a node and pushes it on the stack The operation NODE ADD 2 1 forms a new node consisting of the literal ADD the second object on the s
58. ES 12 IF TRUE THEN S1 gt 251 IFUN 10 IF P THEN UNDEFINED gt UNDEFINED LABELIFX 10 X IF P THE S GOTO X gt X WHILI LESSEQMAMB 12 A lt B gt A gt B LESSEQXX 11 X lt X gt TRUE LESSMAMB 12 A lt B gt A gt B LESSXX 11 X lt X gt FALSE MINUSO 14 0 gt 0 MINUSMINUSX 12 X gt X MINUSSUBAMB 9 A B gt B A MPYOX 11 O X gt 0 E P DO S 56 Draco 1 2 Users Manual PY1X 12 1 X gt 2X PYAMB 10 A B gt A B PYDD 5 A lt div gt B C lt div gt D gt 7A C lt div gt B D PYDX 3 A B C gt A C B PYMAB 10 A B gt A B PYMAMB 12 A B gt A B PYXO 11 X 0 gt 0 PYX1 12 X 1 gt X PYXD 3 C 7 A B gt A C B OTEQMAMB 12 A B gt A B OTEQUAL 8 OTEQXX 11 X X gt FALSE OTEQXY 10 X Y gt OTF 12 OTGTR 12 OTGTREQ 12 OTLESS 8 OTLESSEQ 8 OTNOT 12 OTNOTEQ 12 OTT 12 OTX 3 ELSE TRUE OR lt GE gt EQ 9 A lt ge gt B A B gt A gt B OR lt LE gt EQ 9 A lt le gt B A B gt A lt B ORAA 11 X amp OREQ lt GE gt 9 A B A l
59. G 8 ERM PRCP reset terminal state on exit DE TERM TERM NIL TERM RM 1 clear and home before message DE ERM TITLE S TERM CLEAR EVAL CONS TERM MSG 5 APPENDIX IX TACTICS PRETTYPRINTER DEFINITION The file TACTICS PPD shown below contains the definition of the tactics prettyprinter PRETTYPRINTER TACTICS PrettyPrinter for Internal Domain of TACTICS James Neighbors Last Modified August 26 1982 Draco 1 2 Users Manual ACTICS LISTPRINT SLM SLM ACTIC 2 CMDGRP LISTPRINT SLM SLM 10 13 C D DEFINE 3 Toon 1 LM 2 r PROGN LISTPRINT SLM 40 ACTIC RPCFIELD 1 FMREF LOC LOC LISTPRINT REFINE USE NUM USE LISTPRINT REFINE TRY NUM TRY LISTPRINT REFINE USE USE LISTPRINT REFINE TRY TRY LISTPRINT ACTIC CALL 1 ACTIC MESSAGE 34 1 34 ACTIC BLANK KLUGE ACTIC ALL KLUGE ALL ACTIC REFSCAN LM 1 2 3 AND lt LISTPRINT 6 SLM 40 gt OR EQ 1 IS 2 ACTIC RRFIELD
60. K K NUMBER NAME ODE REFINE USE NU 2 1 EMPTY ODE REF INE USE NU 1 TACTIC BLANK TRY DEFAULT NAME ODE REFINE TRY NUM 1 1 EMPTY ODE REFINE TRY NU 1 TACTIC BLANK K NUMBER NAME ODE REFINE TRY NUM 2 1 EMPTY NODE REF INE TRY NU 1 TACTIC BLANK ALL RPRED RCMND NODE TACTIC REFSCAN TACTIC ALL KL NUMBER RPRED RCMND NODE TACTIC REFSCAN 3 2 41 NAME ODE TACTIC CALL 1 RPRED lt LIST AND SPRED amp SPRED gt EMPTY NODE OR T RCMND LIST PROGN SCMD SCMD SPRED REFFLD IS NAME NODE EQ 2 41 EMPTY NO REFFLD NODE NOT 1 AVAILABLE FUNCTION NODE REFINE FUNCTION ALREADY RESOURCE NODE TACTIC RRCHECK NAME INSTANTIATION ODE TACTIC INSTANTIATION AVAILABLE 1 SCMD STRING NODE TACTIC MESSAGE 1 REFINEMENT NODE TACTIC RPRFIELD REFINEME e CONDITIONS NODE TACTIC RPRFIELD CONDITIONS BACKGROUND NODE TACTIC RPRFIELD BACKGROUND DIRECTIVE NODE TACTIC RPRFIELD DIRECTIVE INSTANTIATION NODE TACTIC RPRFIELD INSTANTIATION ASSERTIONS NODE TACTIC RPRFIELD ASSERTIONS RESOURCES NODE TACTIC RPRFIELD RESOURCES ADJUSTMENTS NODE TACTIC RPREIELD ADJUSTME S DOMAIN NODE TACTIC RPRFIELD DOMAIN USE NAME NODE REFINE USE 1 EMPTY NODE REFINE USE TAC TRY NAME NODE REFINE TRY 1 EMPTY NODE REFINE TRY TAC REFFLD REFINEME z NODE TACTIC RRFIELD REFINEMENT
61. LD Draco must be told how the internal form is to printed out The prettyprinter is also constructed using the BUILD subsystem which is described in this chapter The prettyprinter for a domain language is used whenever Draco needs to communicate a program fragment to a user In particular the transformation library constructing subsystem BUILD the transformation and refinement subsystem TFMREF and the program examination subsystem EXAMINE use the prettyprinter for a Domain Language The basic scheme for building prettyprinters is to describe a printing form for each node in the prefix internal form of the program Carriage positioning may be added to these printing forms 3 1 The Syntax of a Prettyprinter Description In this section we use the standard BNF notation see page to describe the simple syntax of a prettyprinter definition lt DracoPPdef gt PRETTYPRINTER lt identifier gt lt node rule gt END lt node rule gt lt identifier gt lt node item gt lt node item gt lt node item gt lt string gt lt number gt lt number gt LM COL lt number gt SLM SLM lt number gt lt list scan gt LM lt snumber gt TREEPRINT lt identifier gt lt number gt lt node item gt CHARTPRINT lt identifier gt lt number gt lt node item gt lt node item gt lt identifier gt lt number gt lt node item gt lt node item gt
62. MO TCT accessed from Draco disk area kkkkkkkkwkkkkwkkkkkk k Parse Completed 0 errors detected K Parse Completed 0 errors detected FMREF gt domain gen work in GEN domain OTE DRACO domain being removed FMREF gt instance outline of a GEN instance GENERATOR GWOODS ETWORK STREE i STREF 81 END Y N gt Y accept this instance TFMREF gt pp prettyprint of GEN instance GENERATOR GWOODS NETWORK STREE STREE 51 none gen SUBJ at SUBJECT gen VP at VERB PHRASE 51 exit YPE QUESTION out 27 r exit TYPE DECLARE out Ter i END FMREF gt noinstance NOTE no domain instance selected FMREF gt refine NOTE component library index loaded E new domain instance automatically selected NOTE 40 Draco 1 2 Users Manual COMPONENT DNAME PURPOSE Represent the given name as a data item rather than as a variable representing a value STREE how this component appears in program REFINEMENT quote the name for LISP DOMAIN LISP AE COMPONENT COMMENT PURPOSE To represent comments from the ATN domain i REFINEMENT LISP comment mechanism BACKGROUND This is an in memory comment perhaps a comment scanned off by a
63. Meaning characters equal to the ASCII value of A 65 characters equal to the ASCII value of 65 A characters matching A or B 01 characters whose ASCII value C is such that A lt C lt B The precedence of the parser control contructs is as follows Operator encapsulation sequence backtrack alternation 2 1 7 Recognizing the End of the File Some languages do not have explicit end of input markers such as END statements so Draco has a facility enabling domain language parsers to recognize the end of an input file When Draco recognizes the end of the input file it places one control Z ASCII 26 in the input stream to be recognized by the parser If the parser does not recognize the control Z and it tries to read further then an error will occur 2 2 The Complete External Internal Form Specification The Draco system expects the internal representation of a program to be a tree Each node in the tree must have an identifying name as the first entry in the node This form is called prefix form As an example the fragment 5 A B C 7 could be represented internally as EXP C 7 which is a legal prefix form in that the leftmost entry in each node is a name the prefix keyword Each node has a fixed number of Draco 1 2 Users Manual entries All nodes with the same prefix keyword have the same number
64. OGN END RESOLVE COMPONE COMMENT CMNTCHRS NOD n ied June 24 1983 PMDEF COMMENT PMDEF ID DEF COMPONENT LITERAL en r D CR Rule F SG PMDE NOD PROG TP COL 30 JAT 1 DEFINE PP MACRO 2 LAMBDA E PO Q E CDR E LINTOK NODE NILL LINTOK TOKEN ANYBUT A PMDEF1 LIST PROGN SPPOP PPOP STRING NODE PRINAC QUO NUMBER NODE TYO B Q TPOS POS 1 NY DELTOK E 1505 COL NUMBER NODE SLM NODE TAB TPOS NUMBER NOD MPTY LM AB LO U ji E AND GT CHRPOS ia NUMBE ODE DIFFERENCE POS NUMB ODE PLUS POS NUMBE EMPTY NOD NUMBER NODE PLUS POS NODE SETQ TPO 11 CAR NTH E i ry RAL P P TREEPRINT I N P NODE CAR N F P DEF1 NODE PP PRINT T CON CHARTPRINT QUOTE 4 3 QUOTE S POS TPOS LIST PP PRINT CHART lt 1 gt LISTPRINT PMDEF1 NODE MAP FUNCTION E4 NODE CHRPOS NODE QUOTE S
65. P 42 Draco 1 2 Users Manual COMPONENT GSTATE PURPOSE define a state in the generator network 51 REFINEMENT as inline LISP ASSERTIONS GEN states as LISP_inline_sequence DOMAIN LISP tactics interrupted by user tactics have failed to find a refinement User Refinement Interface REF INE gt abort exit tactics OTE aborting the refinement process TFMREF gt instance still working in GEN domain NERATOR GWOODS TWORK R N F HH D Y N gt Y FMREF gt pp inside out tactics have created LISP NERATOR GWOODS TWORK lt lt LISP gt gt R N F lt lt LISP gt gt MHEE D REF gt noinstance no domain instance selected O FMREF gt refine OTE new domain instance selected automatically COMPONENT GSTATE PURPOSE define a state in the generator network STREE REFINEMENT as inline LISP ASSERTIONS GEN states as LISP_inline_sequence DOMAIN LISP COMPONENT STATES SEQ PURPOSE Specify the ordering of the states in the original description REFINEMENT keep the same ordering in LISP inline ASSERTIONS GEN states as LISP_inline_sequence DOMAIN LISP 7 NOTE refinement replaced a domain last bit of GEN instance refined
66. PROCLIST W o Refinement LISP function list as a read execution sequence kkkkkk Component PROCLIST SEQ ER Refinement LISP function list as a read execution sequence kkkkkk Component PROCDEF ER Refinement LISP function definition KKKKKK KK etc The following figure is a fragment of the input file DRACO REF showing some of the components that were processed through the dialog transcribed above O PO T PROCLIST PROCS RPOS he list of functions known to Draco FINEMENT LISP function list as a read execution sequence STANTIATION INLINE TERNAL LISP G F ISPP PROCS D REFINEMENT D COMPONENT AAAHHDWVA 2 lt z 2 MPONENT PROCLIST SEQ PROCS1 PROCS2 RPOS he list of functions known to Draco FINEMENT lisp FUNCTION LIST AS A READ EXECUTION SEQUENCE STANTIATION INLINE TER SEESE ISPSEQ PROCS1 PROCS2 D REFINEMENT D COMPONENT td B H 1 2 lt 2 2 Q PONENT PROCDEF DOMAIN NAME VERSION BODY FPARAMS LOCALS PARTIALS LABELS RUPOSE A Draco function definition EFINEMENT Lisp function definition ACKGROUND WARNING could cause naming problems NSTANTIATION INLINE 0
67. RMATION RR TRANSFORM 1st arg must be less or equal to 2nd arg RR attempt to remove a mark from the node stack RR can t read FILE RR can t read FILE or try again RR end of file not recognized RR enter number or OK ta 0 ERR errorblock in rule RULE has failed to recover ERR no GROUP group of tactics loaded ERR no TACTIC CMD tactic loaded RR no DOMAIN domain parser available RR no component for COMPONENT in DOMAIN domain RR no domain instance has been selected RR no instance has been selected RR no locale has been selected RR no locale selected RR no locale selected RR no mark on stack to form list RR no prettyprinter available RR no refinement number NUMBER RR no tactic TACTIC CMD to delete RR no tactic group called GROUP to delete td tg tg td td td tg tg td td td tg tg td td 62 Draco 1 2 Users Manual RR no tactics loaded RR no tactics to delete RR non numeric argument RR non prefix structure LIST RR not a single top level RR number too large RR refinement library DOMAIN RLB unavailable RR rule RULE failed but constructed nodes RR rule RULE succeeded but did not return one node RR syntax rule RULE RR transformation librar
68. TS LIST COMSET lt 1 gt COMPONENT EOF RESOLVE COMPONENT COMPONENT COMPONENT LIST COMLIST NAME MSG CR Component COL 30 DEF COMPONENT NODE COMPONENT 1 LIST CPARAMS CPNAM CPNAM EMPTY NODE CPARAMS CR PURPOSE MLTEXT NODE PURPOSE 1 IOSPEC MLTEXT NODE IOSPEC 1 DECISION MLTEXT NODE DECISION 41 BLINE LIST REFSET lt 1 gt REFMNT END COMPONENT lt 1 gt BLINE CPNAM NAME NODE CPQUOTE 1 NA REFMNT REFINEMENT LIST REFLIST REFNAME MSG CR Refinement COL 30 NODE REFINEMENT 1 CR 5 BACKGROUND MLTEXT NODE BACKGROUND 1 INSTANTIATION LIST INSTANTIATION NAME NAME CR ASSERTIONS ASSERTIONSET CONDITIONS CONDITIONSET RESOURCES MLTEXT NODE RESOURCES 1 ADJUSTMENTS MLTEXT NODE ADJUSTMENTS 1 GLOBALS LIST GLOBALS NAME NAME CR LABELS LIST LABELS NAME NAME CR 58 Draco 1 2 Users Manual CODE NAME NAME CR ODE PARSE DOMAIN 2 1 EXECUTE LINE NODE CODE 3 NODE DOMAIN 2 INTERNAL NAME CR ILIST LINE NODE PARSE INTERNAL 2 1 EXECUTE NODE CODE 43 NODE
69. The manipulation of the token buffer will be described in a later section on internal forms Sometimes it is useful to be able to explicitly control the issuing syantx error and rule failure conditions in the parser This can be done using the FAIL and ERROR constructs As can be guessed the FAIL construct fails the current parse rule immediately without regard for any alternatives sequences backtracks or errorblocks in which it is embedded The ERROR construct raises a syntax error when it is encountered and it is dealt with in a manner similar to other synatx errors Draco 1 2 Users Manual 2 1 6 Elements of External Form Description This section summarizes the external form description mechanisms in Draco BNF In both lt parse rule gt and lt token rule gt Meaning sequence an A followed by a B followed by backtrack A or backtrack B alternation an A oraB or the last element of a alternation states that none of the alternatives need be taken error block try A and B handles errors encapsulation treat as one unit iteration zero or more instances of A iteration n to m instances of A implys any number In lt token rule gt only Syntax Meaning ANY A scan any char described by A ANYBUT A scan any char not described by A Inside ANY or ANYBUT character class descriptions
70. X1 NODE PAREN 1 Now to print this internal form node we must make the following prettyprinter definition PAREN 1 Now only the parentheses which appeared in the original program will be printed It is useful to put a representation of practically every text level item into the internal form This increases the accuracy of the prettyprinting the range of possible transformations 18 Draco 1 2 Users Manual and the range of possible refinements It does however make the transformation definitions a bit more complex in that they will be responsible for removing and maintaining the text level forms 3 8 Using the BUILD Subsystem to Create a Prettyprinter This section presents an example transcript Comments are in and user responses are underlined and terminated by a RETURN DRACO gt BUILD LANG PRETTYPRINTER file LANG PPD contains prettyprinter definition screen clears Prettyprinter Generator kkkkk one signifys a line processed Parse Completed 0 Errors Detected NOTE LANG DPP created the extension defaults to DPP DRACO gt As with parser generation if prettyprinter generation had not completed an error giving a rule would have been printed out In the case of prettyprinters this rule is contained in the file PPGEN DEF which is reproduced as Appendix III of this manual For other errors see Appendix X on errors Appendix IV contains a complete example prettyprinter fo
71. a complete example of a domain language SPL Appendix II Gives the definition of the main parser generator the Draco parser writen in Draco Gives the difinition of the Draco prettyprinter domain Gives an example of a prettyprinter description SPL Appendix V Gives an example of transformations Gives the definition of the Draco Component Library domain language the language used in describing components JE Gives the definition of the interpreter of the Tactics subsystem used in guiding refinement e Gives an example of a terminal type to Draco Gives the definition of the Tactics prettyprinter Appendix X Draco errors and messages CHAPTER 2 DESCRIBING A DOMAIN LANGUAGE Once the analysis of a problem domain has been completed the Domain Analyst must define a language suitable for describing solutions to programming problems in the domain This high level language should be very specific to the domain and capable of describing the objects and operations of the domain in a comfortable way In this section we are concerned with how to specify the external form syntax and internal form of a domain language to the Draco subsystem BUILD The chapters on transformations and refinements are concerned with specifying the semantics of the language 2 1 The External Form Syntax Specification Classically BNF has been used to describe the syntax of languages and Draco carries on this tradition The Draco BNF is similar to the
72. ain then the assertions are checked for consistency This places the overly strong restriction that all objects in a domain of the same type have the same implementation More experience with domains could probably remove this restriction If the asserted conditions conflict then the refinement of the program must be backed up 9 3 The Refinement Mechanism The refinement mechanism of Draco applies the component library of a domain to a locale within an instance of the domain in the internal form tree for the program being refined The locale is bounded by a domain instance which is a part of the internal form tree in the internal form of a particular domain Refinements are made in one domain at a time on an instance of the domain The locale mechanism is important for refinements in that the inner loop of the program should be refined first to pick efficient implementations These implementation decisions will affect the choices outside of the inner loop through the assertion and condition mechanism of the components The Draco refinement mechanism applies the components to the locale internal form tree using application policies similar to transformation application policies In general top down application is the best policy to avoid conflicting conditions which would require a backup of the refinement From the previous discussion about the selection of a refinement for a component and the user interaction necessary to make a choice it is evid
73. and SUGGEST The SUGGEST command causes the system to examine its internal form of the current locale and suggest what transformations it would apply or look at The suggest command goes hand in hand with the automatic suggestion of transformations option of the PARSE subsystem If the automatic suggestion option was not taken then initially the suggest command will not be able to suggest any transformations until one is performed manually Even if you intend to perform transformations one at a time manually it is a good strategy to use the automatic suggestion of transformations option and then use the TRANSFORM command discussed below to strip out all the transformations which don t really apply see the discussion of how transformations are suggested by PARSE 8 2 The APPLY Command APPLY lt transformation name gt The APPLY command applies a specified transformation to the current locale Remember by locale here we mean only the root of the internal form tree described from locale commands Using APPLY is very tedious and it is not recommended It is included simply because most transformation systems in the past have used such a command extensively The TRANSFORM command discussed below is the recommended replacement for the APPLY command 8 3 The TRANSFORM Command TRANSFORM lt code gt lt code gt TRANSFORM LO CODE lt code gt HI CODE lt code gt APPROVAL MODE lt answer gt The TRANSFORM command automatically applies transforma
74. and refinements of the old domain are removed from memory and the prettyprinter if one exists for the new domain is loaded The instance is unselected when a old domain is removed 7 1 2 The INSTANCE command INSTANCE The INSTANCE command is used to change the instance of the currently selected domain to some other instance of the domain in the selected program To select the instance TFMREF scans the program selected looking for program fragments written in the selected domain If it finds one it prettyprints it out to a certain depth using to indicate supressed detail It then asks the user if this was the instance he had in mind If so it selects the instance If no instance is selected then the other commands in TFMREF which require an instance will either automatically select an instance or not function until an instance is selected 7 1 3 The LOCALE Command LOCALE No of levels The LOCALE command restricts the context to a part of the selected instance by traversing the prefix tree internal form If you expect to apply transformations one at a time then the locale command must be used to set the location of application This is a tedious operation since TFMREF must be able to traverse the internal form of any domain without the System Specialist having to know the internal form of the domain When the locale command is given the system prints the currently selected locale and requests a number A negative number n moves up the tr
75. asic operation in this phase is the selection of an appropriate set of software components to implement the operations and objects in the domain which are used in the problem statement Then these components are specialized by program transformation described in Chapter 8 to the problem at hand and then separately refined described in Chapter 9 into another or the same domain and the cycle begins again The TFMREF subsystem allows the definition of refinement tactics described in Chapter 10 capable of removing the burden of answering low level questions from the System Specialist 8 The process the System Specialist uses to refine the problem is of course not strictly top down but the TFMREF subsystem keeps a record of the process which makes it look top down When the program is in an executable form it is printed out by the System Specialist and either acceptable or the specification cycle begins again with the existing Domain Language program 9 The refinement history of a program may be examined by a user of the EXAMINE subsystem NOTE 7 which states what refinements were used in the production of this program A higher level description of all parts of the program to whatever level up to the orginal Domain Language always exists in the refinement history It is hoped that these higher levels of abstraction of an existing program will be useful in understanding the program during the maintenance phase of its lifecycle The process described
76. at the name of a class the first identifier in the list must be surrounded by angle brackets lt gt this helps to separate class names from a prefix keyword 4 2 2 An Example of a Transformation Insertion File If we refer back to our assignment statement example see index with the internal form descriptions the following is an example transformation insertion file PVARS X Y Z CLASS lt COMOP gt ADD MPY TRANS ADDXO 12 ADD X 0 X TRANS MPYXO 11 MPY X 0 0 TRANS EXPXO 11 EXP X 0 1 TRANS lt COM gt XY 5 lt COMOP gt X Y lt COMOP gt Y X TRANS PARENPAREN 12 PAREN PAREN X PAREN X TRANS LDISTMPYADD 5 MPY X PAREN ADD Y Z PAREN ADD MPY X Y MPY X Z ERASEPVARS In the above example the nodes of the internal form are represented as lists of objects in parentheses If a node contains a pointer to another node then that node is shown inside of the first node Any identifier which is declared as a pattern variable PVARS will match a subtree or a constant Thus the X Y and Z s in the example insertion file are all pattern variables A class lt COMOP gt in the example above represents a restricted pattern variable Where the class name appears it will only match members of the class The class lt COMOP gt represents the commutative operators and their commutativity is stated as transformation lt COM gt XY A class can o
77. ation imposes the further constraint that only the last element of an alternation should directly derive the empty string with a EMPTY 3 If BETA can derive the empty string through a series of rule applications then ALPHA does not derive any strings beginning with a terminal symbol which is a member of the set of terminal symbols that can appear immediately to the right of ARULE in some sentential form Further information on LL 1 languages is found in Aho79 which is the source of the explanation above As an example of fitting the rules into the constraints imposed by the parser generator the rule RELOP EXP lt EXP EXP lt EXP would have to be changed to RELOP EXP lt lt EXP 4 or the less efficient RELOP EXP lt EXP EXP lt EXP There are two reasons for this change First in the original RELOP the first nonterminal of the two alternatives was the same EXP so the first alternative would always be taken if an EXP object appeared in the input stream In a sequence if the first object is present in the input stream then the rest of the sequence must be present or a syntax error is generated Second the lt must be tested for before the lt otherwise the lt might match the first part of a lt in the input stream and the wrong alternative would be taken A larger example of a complete external internal domain language
78. briefly above is dealt with in more detail in Neighbors80 which presents an SADT NOTE 2 model of the process Draco 1 2 Users Manual 1 2 Running the Draco System This section describes the loading and execution of the Draco system on the ICS PDP20A at U C Irvine as of June 1 1983 At this time access to the Draco system is restricted to members of the Reusable Software Project at U C Irvine NOTE 3 As in all the example transcripts in this manual the user input is strong type and terminated with RETURN and comments are in fephasis type we enter at the monitor level on the PDP20 DEFINE DRACO lt DRACO gt the Draco disk area DRACO screen clears Draco 1 2 some notices and bug messages are printed here DRACO gt HELP the current legal Draco commands are printed The Draco commands are BUILD generate a domain language parser DEF gt PAR gt generate a domain language internal form prettyprint gt generate a domain transformation library TFM gt TLB gt generate a domain refinement library REF gt RLB PARSE parse a program into internal form gt INT TFMREF transform and refine a program INT HIS gt INT HIS EXAMINE xamine the refinement of a program HIS SET set terminal type and other environmental parameters EXIT gt return to the monitor level LISP gt reenter LISP HELP this listing A to a filename or Y N request exits current subsystem
79. case letter of the alphabet followed by zero to five letters or digits A STRING is a sequence of zero or more spaces followed by a double quote followed by the string characters any chararacter except a double quote followed by a double quote The following are legal ASGN statements according to the Draco BNF above PHI col7 col5 FUDGE Person Edward the Great VAL7 5 3 6 4 ELS A 6 3 7 6 5 power Zee factor SIN 2 Pi APE FURD 5 FURD 3 B 2 1 3 The PREFIX and SUFFIX Rules Two rule names PREFIX and SUFFIX are used to shorten the Draco BNF description of a langauge If a Draco BNF description contains a PREFIX rule then this rule is applied before every test for a literal string characters enclosed in quotes Thus ASGN IDENTIFIER EX1 STRING 7 PREFIX SPACES is the same as ASGN IDENTIFIER SPACES EX1 STRING SPACES The SUFFIX rule operates in a similar manner except that if it exists it is applied after the test for the literal string has been successful If the PREFIX rule didn t exist in the example above then the statement PHI col7 col5 FUDGE would be legal while PHI col7 col5 FUDGE would not be legal because of the embedded spaces In general the PREFIX and SUFFIX rules are useful in shortening the description of languages without fixed fields 2 1 4 Controlli
80. ctions and temps The modules are GEN GOUT O item GEN GVFETCH 0 selector TEMP GEN GTFETCH 0 selector gentree DRACO START 0 falab alab0 alab2 exit rlab rlab0 alab alabl alab3 exit rlab rlabl Y N gt Y TFMREF gt refine COMPONENT FPARAMS SEQ PURPOSE The formal parameter sequence of a Draco function definition selector REFINEMENT LISP formal parameters DOMAIN LISP COMPONENT FPARAMS PURPOSE A formal parameter of a Draco function definition REFINEMENT LISP formal parameters DOMAIN LISP POCZ 7 NO refinement replaced Draco top level FMREF gt domain lisp NOTE DRACO domain being removed FMREF gt pp DE GOUT item PROG RETURN SETQ genrslt NCONC genrslt LIST item DE GVFETCH selector PROG TEMP URN COND ATOM SETQ TEMP OR MEMB selector CAR gentree ASSOC selector CAR gentree GENERR 2 CADR TEMP DE GTFETCH selector PROG gentree RETURN OR MEMB selector CAR gentree ASSOC selector CAR gentree GENERR DE START PROG alab alabO alab2 exit rlab rlab0 RETURN DE GWOODS gendict gentree PROG genrslt genrstack SETQ gentree LIST gentree GO STR
81. d to print all the classes in a sensible form Thus Y represents a match anything known to be constant This catalog represents most of the source to source program transformations found in the Irvine Program Transformation Catalogue Standish76 The listing is in the standard XFMGEN catalog format V 1 SIMAL Transformations NOTE 1997 Some past word processor Scribe treated SIMAL nots as comments so these transformations e g NOT are truncated here 5 3 79 19 18 18 SIMAL TLB lt BOP gt ASSIGN EXP DIV IDIV MPY SUB ADD NOTEQ EQUAL GTR LESS GTREQ LESSEQ AND OR lt CALL gt FNCALL PROCCALL lt DIV gt DIV IDIV lt GE gt GTR GTREQ lt LE gt LESS LESSEQ lt REL gt NOTEQ EQUAL GTR LESS GTREQ LESSEQ lt SEL gt ASELECT SSELECT lt UOP gt NOT MINUS lt BOP gt CC 12 X lt bop gt Y gt X lt bop gt Y lt BOP gt EMPX 12 EMPTY lt bop gt X gt UNDEFINED lt BOP gt IFELSEX 4 IF P THEN 81 ELSE S2 lt bop gt X gt IF P THEN 251 lt bop gt X ELSE 252 lt bop gt X lt BOP gt IFX 4 IF P THEN S1 lt bop gt X gt IF P THEN S1 lt bop gt X lt BOP gt UNX 12 X lt bop g
82. definition of the language Also it is sometimes useful to insert special markers with a transformation such as EMPTY or UNDEFINED which will start off other transformations As an example the transformation X O gt UNDEFINED prevents undefined forms in a language from propagating Remember if you insert such markers the domain prettyprinter must have a definition for printing them Also all the markers which do not have an associated component must be removed before refinment is attempted or an error will occur 4 2 1 The Syntax of a Transformation Insertion File In this section we use the standard BNF notation see BNF to describe the syntax of a transformation insertion file which contains a packet of transformations to add to a library lt DracoTIfile gt lt TIcmnds gt lt TIcmnds gt lt pvardef gt lt classdef gt lt transdef gt ERASEPVARS lt pvardef gt PVARS lt identifier gt lt identifier gt lt classdef gt CLASS lt lt identifier gt gt lt identifier gt lt identifie lt transdef gt TRANS lt identifier gt lt number gt lt lhs gt lt rhs gt lt rhs gt lt identifier gt lt intform gt lt lhs gt lt intform gt lt intform gt lt identifier gt lt rhs gt lt identifier gt lt idchar gt lt idchar gt lt idchar gt A 2 Joa se z 4 A lt number gt is a simple sequence of numerals Notice th
83. e 2 reverse video 3 underlined 4 blinking 53 16 combinations of the above 3 4 Prettyprinting TREEs and CHARTs As mentioned in the previous chapter on parser construction the parsers can build two kinds of special forms called TREEs and CHARTs The prettyprinters have two special constructs to print these forms as TREEPRINT and CHARTPRINT The prettyprinting of a right leaning tree is achieved using TREEPRINT If we have the following TREE internal form 16 Draco 1 2 Users Manual any node a b I ED Fos 1 IT SEQ zj IT SEQ OMEGA it could be prettyprinted in the IT prettyprint rule using TREEPRINT IT SEQ 1 expressionl expression2 The TREEPRINT construct would then look to see if the first subtree in the IT node is rooted with an IT SEQ node If so the first subtree of that node would be prettyprinted followed by the evaluation of expression and the prettyprinting of its second subtree If the subtree is empty i e it contains an OMEGA then expression2 is evaluated This recursive scheme is used to print trees of varying length NOTE 8 The use of TREEPRINT does not relieve the burden of producing prettyprinter rules for IT SEQ type nodes These prettyprinter rules are used only in priniting fragments for transformation and refinement pruposes The CHARTs which can be created by the parsers are printed using CHARTPRINT The use
84. e domain may want to remember what is included in the class 8 6 The UNLOAD TRANSFORM Command UNLOAD TRANSFORM 34 Draco 1 2 Users Manual When the transformations are loaded notice is given to the user As mentioned before the transformations are loaded automatically when required However if the System Specialist decides to perform some refinements and he wants more room in memory he may remove the transformations from memory with the TFMUNLOAD command They will be automatically loaded again if needed 8 7 Transformation Example The example given below shows a fragment of a session in which transformations are applied Following the example session a prettyprinted version of the locale being refined is given It is included so that the reader may compare the initial code and the final code This example is an intermediate result in the refinement of the ATN generator in Neighbors80 TEMREF gt PP DE GWOODS gendict gentree PROG genrslt genrstack ETQ gentree LIST gentree 0 STREE ILL lt lt RE R AND T T GO alab USH genrstack rlab USH gentree SUBJECT O w o USH genrstack rlabl USH gentree GO VERB PHRASE rlabl GO 51 alab NILL 2777 GENERR 51 OR AND EQUAL QUESTION GO alabl POP gentree GO exit alabl NILL 9 OR AND EQUAL DECLARE GO alab3 POP gentree GO exit alab3
85. ee n levels limiting to the instance root while a positive number n moves down the nth subtree Error messages are printed when the number of levels exceed the number of available subtrees The PP command prettyprints the current locale if one has been selected 7 2 The Miscellaneous TFMREF Commands This section presents the commands of the TFMREF subsystem which either present or save environmental information These commands are not specific to locale transformations or refinements 7 2 1 The PP Command PP The PP command prints the selected locale completely without the shorthand The output may be safely aborted with a control O 28 Draco 1 2 Users Manual 7 2 2 The INFO Command INFO The INFO command prints the time date program file you are working on the domain selected what is in memory PP prettyprinter TFM transformations REF refinement index the short version of the instance and the short version of the locale 7 2 3 The HARDCOPY Command HARDCOPY lt filename ext gt The HARDCOPY command enables the System Specialist to get a disk file of the prettyprinted version of the entire domain instance When a program has been refined from one domain language into an executable language this command must be used to get a copy of the resulting program 7 2 4 The SAVE Command SAVE The SAVE command saves the entire prefix internal form suggested transformations and refinement record over the old program f
86. ent that the user needs some mechanism to keep Draco from asking too many questions The user needs the ability to specify guidelines for answering the questions and these guidelines are called tactics The TACTICS subsystem see Chapter 10 of Draco allows the user to interactively define tactics which answer refinement questions for the refinement mechanism The subsystem also allows the user to read and write tactics from storage A standard set of tactics is already available When the refinement mechanism requires a user response it first applies the tactics to see if one of them provides an answer The refinement user interface could be used for applying refnements one at a time This would be very tedious work as tedious as applying transformations one at a time In general early versions of a high level domain specific program are refined by the default tacts These use easy and uncomplicated default refinements to obtain a first implementation and to check whether the system implements everything the user desires 9 4 The TFMREF Command REFINE Under the Transformation and Refinement subsystem TFMREF the REFINE command can be used to invoke the Refinement User Interface This is a new set of commands that enable the user to perform refinements and provide tactics Alternatively the Refinement User Interface is activated if the user interrupts automatic tactics during refinement 9 5 Commands available through the Refinement User Inte
87. fic language but will be used in examples so that the reader will not have to learn a domain specific language at this point COMPONENT EXP A B PURPOSE exponentiation raise A to the Bth power Draco 1 2 Users Manual IOSPEC A a number B a number a number DECISION The binary shift method is O ln2 B while the Taylor expansion is an adjustable number of terms Note the different conditions for each method REFINEMENT binary shift method CONDITIONS B an integer greater than 0 BACKGROUND see Knuth s Art of Vol 2 pg 399 Algorithm A INSTANTIATION FUNCTION INLINE RESOURCES none CODE SIMAL BLOCK POWER B NUMBER A ANSWER 1 E POWER gt O DO IF POWER AND 1 0 THEN ANSWER ANSWER NUMBER POWER POWER 2 NUMBER NUMBER NUMBER J RETURN ANSWER ND REFINEMENT REFINEMENT Taylor expansion CONDITIONS A greater than 0 BACKGROUND see VNR Math Encyclopedia pg 490 INSTANTIATION FUNCTION INLINE A A SSERTIONS none DJUSTMENTS TERMS 20 number of terms error is approximately B ln A TERMS TERMS CODE SIMAL BLOCK SUM 1 TOP B LN A TERM 1 FOR I 1 TO TERMS DO TERM TOP I TERM SUM SUM TERM RETURN SUM END REFINEMENT END COMPONENT
88. finition PROGSEQT 85 T P PUSH gentree GO SUBJECT rlab PUSH genrstack PUSH gentree GO VERB PHRASE rlabl GO S1 alab gt PUSH genrstack PUSH gentree GO SUBJECT rlab PUSH genrstack PUSH gentree GO VERB PHRASE rlabl GO 51 alab Y N gt USH genrstack By successively applying NILL1 and PROGSEGNIL the NILL comments will be eliminated from the locale NILL1 50 NILL gt IL Y N gt Y PROGSEQNIL 85 IL gt Y N gt Y AND1 80 AND EQUAL QUESTION gt EQUAL QUESTION Y N gt Y NILL1 50 NILL gt IL Y N gt Y AND1 80 AND EQUAL DECLARE gt EQUAL DECLARE Y N gt Y NILL1 50 NILL gt IL Y N gt Y PROGSEQNIL 85 IL gt Y N gt Y PROGSEQNIL 85 IL OR EQUAL DECLARE GO alab3 POP gentree GO exit alab3 gt OR EQUAL DECLARE GO alab3 POP gentree GO exit alab3 Y N gt PROGSEQNIL 85 NILSTREE alab GENERR 51 OR alabl OR alab3 GENERR gt STREE alab GENERR 51 OR 2 alabl OR Draco 1 2 Users Manual alab3 GENERR Y N gt At this point the system specialists interrogates the system about the functions available TFMREF gt
89. following which describes simple parenthesized arithmetic ALGOL like assignment statements DEFINE ASGN ASGN IDENTIFIER EX1 STRING EX1 EX2 EX2 EX2 EX3 EX3 EX3 EX4 EX3 EX4 IDENTIFIER EX1 EX1 EMPTY NUMBER EX1 PREFIX SPACES IDENTIFIER SPACES ALPHA lt 5 gt ALPHA DIGIT NUMBER SPACES DIGIT DIGIT STRING SPACES ANY ANYBUT ANY ALPHA ANY A Z a z DIGIT ANY 0 9 SPACES ANY 32 END The DEFINE tells Draco that this is a domain language description and the name which follows is the name of the first rule to be Draco 1 2 Users Manual invoked Sequences enclosed in double quotes are literal strings which are tested to see if they appear without double quotes in the input stream The slash denotes alternation similar to the logical bar I of BNF So an ASGN is started by an IDENTIFIER which must be followed by the sequence which is then followed by either a sequence described by rule EX1 or a STRING Whichever alternative is elected it must be followed by a semicolon IDENTIFIER is a lt token rule gt and it scans off individual characters An IDENTIFIER is a sequence of zero or more spaces 32 is the decimal ASCII representation of a space followed by an upper or lower
90. gt ALPHA DIGIT DELTOK NUMBER SPACES TOKEN DIGIT DIGIT DELTOK I H T G SPACES TOKEN ANY ANYBUT ANY DELTOK A ANY A Z a z T ANY 0 9 SPACES ANY 32 The following is an example of a prettyprinter for the assignment statement parser given above PRETTYPRINTER ASGNSTMT ASSIGN 1 LM 2 ADD MW JE PY 1 2 EXP SD gt FNCALL 1 LM 2 7 APARAMS 1 SLM 60 2 END In the example above ASGNSTMT is the name of the domain Notice that there is one line for each possible prefix keyword in the internal form The 1 in the lines refer to the next entry in the internal form node after the prefix keyword The strings in quotes are strings which will be printed verbatim with no spaces on either side The LM fixes the left margin to the position of the printing carriage at the time the LM is encountered This left margin prevails for the given rule and all rules called from it A LM with an unsigned number fixes the left margin at the column indicated by the number A LM with a signed number adds the given signed number to the left margin which preveiled when the prettyprint rule was entered and sets the left margin to the resultant value The SLM seeks the left margin set by the last LM If the carriage is before the current left margin then SLM
91. gt scan for refinements in the current locale TACTICS gt envoke the tactics subsystem SAVE gt save all the work so far HARDCOPY prettyprint the instance to a file EXIT gt exit the TFMREF subsystem HELP this list The TFMREF commands for transformation and refinement are described in Chapter 8 and Chapter 9 respectively Tactics are described in Chapter 10 29 Draco 1 2 Users Manual 7 4 An Example Session with TFMREF This section presents a session with TFMREF In the session don t be concerned with the meaning of the domain language being manipulated SIMAL see Appendix I What is of concern in the example is the way TFMREF commands interact with the user to manipulate this small trivial example In the transcript the denote comments and underlining denotes user responses All user responses are terminated with a RETURN DRACO gt TFMREF PROBLEM FILE quad fextension defaults to INT screen clears Transformation and Refinement Subsystem NOTE file last modified on 5 25 79 22 32 49 The modules are DRACO START 0 lt DL DOC_DOCUMENT gt Y N gt n FMREF gt Domain DOMAIN NAME SIMAL ALGOL like lang for examples NOTE DRACO domain being removed FMREF gt instance PROGRAM QUADRATIC shorthand printout SQUADRATIC LOCAL i zaad END Y N gt Y fis this the instance TFMREF gt PP lets see all of program PROGRAM QUADRATIC SQUADRATIC LO
92. gt save NOTE WG INT saved At this point the transformations shown in the example of Chapter 8 should be applied to remove unused generality However this is not required All that is required now is to instantiate Draco s model of functions and system phases for LISP This is held in the Draco domain so that the refinement mechanism knows how to create functions and phases FMREF gt domain draco NOTE LISP domain being removed FMREF gt refine NOTE file DRACO RLB accessed from Draco disk area NOTE component library index loaded NOTE new domain instance selected automatically See th xample in Chapter 5 where another subset of these Draco components is used to build the Component Library DRACO RLB COMPONENT APARAMS SEQ PURPOSE REFINEMENT LISP actual parameters BACKGROUND The actual parameters are treated as an execution sequence DOMAIN LISP COMPONENT APARAMS PURPOSE An actual parameter of a Draco function call REFINEMENT LISP actual parameters he sequence of actual parameters of a Draco function call 44 Draco 1 2 Users Manual BACKGROUND The actual parameters are evaluated DOMAIN LISP DOMAIN DRACO NOTE refinement merged a domain note no instance of DRACO domain in locale of refinement Draco looks for other Draco domain instances and finds one the top level with all the created fun
93. h of the tactics list for the given tactic If the list is not empty it executes the associated command group 9 5 6 The HELP command HELP The HELP command prints a summary of the commands available through the Refinement User Interface The printed text is read from the file REFUSER HLP Thus it can be customized if necessary by modifying the file The current file contents is given in section 9 5 8 9 5 7 The INFORMATION command The INFORMATION command enables the System Specialist to accquire information on Assertions and the use of memory by the system Thus there are two different formats INFORMATION ABOUT ASSERTIONS IN lt domain specification gt and INFORMATION ABOUT MEMORY USAGE The first form accepts the following for lt domain spoecification gt ALL DOMAINS CURRENT DOMAIN DOMAIN NAMED lt domain name gt ON lt objects and operations gt in each case the user gets a list of the relevant assertions The assertions provide the implementing concept information e g SIMAL integers as LISP numbers The second for reports the amout of free memory remaining as in Free Storage NNNN Full word Space MMMM 39 Draco 1 2 Users Manual 9 5 8 A summary of the Refinement User Interface commands The HELP see sections 9 5 6 command provides the following information REF INE gt HELP he Refinement User Interface Commands are H TRY lt refinement gt lt instan
94. he interpreter for the TACTICS subsystem Any errors in the TACTICS subsystem refer to the file TACTICS DEF which is reproduced below Any error in the construction of a prettyprinter using PPGEN refers to a rule in this file VIL1 The File TACTIC DEF DEFINE TACTCMD Tactics Parser Uses EXECUTE to be an Interpreter James Neighbors Last Modified December 12 1982 NOTE terrible use of TACTIC KLUGE should be removed TACTCMD TACDEF TACLIS TACDEL LOAD NAME NODE TACTIC LOAD 1 HELP NODE TACTIC HELP k EXECUTE EXIT ACDEF DEFINE NAME NAME RULE NODE TACTIC DEFINE 3 2 EMPTY RULE NODE TACTIC DEFINE 2 TAC EMPTY RULE NODE TACTIC DEFINE TACTIC ACDEL DELETE NAME NAME NODE TACTIC DELETE 2 1 EMPTY NODE TACTIC DELETE 1 TACTIC BLANK EMPTY NODE TACTIC DELETE TACTIC BLANK KL TACLIS LIST NAME NAME gt NAME NODE TACTIC LIST 3 2 1 EMPTY NODE TACTIC LIST 2 1 TAC EMPTY gt NAME NODE TACTIC LIST 2 TACTIC EMPTY NODE TACTIC LIST 1 TACTIC EMPTY gt NAME NODE TACTIC LIST TA
95. ile The name of the program file is given by the INFO command Upon EXITing the TFMREF subsystem the user is automatically asked if he wants to save the internal form This command is included for incremental saves to avoid the problem of a crash destroying the entire sessions work 7 2 5 The EXIT Command EXIT The EXIT command exits the TFMREF subsystem asks if a SAVE should be done and then returns to Draco 7 3 A Summary of the TFMREF Commands The TFMREF Subsystem has a HELP command which prints out the following summary of the TFMREF commands The TFMREF commands are DOMAIN gt specify a new domain to work with INSTANCE specify which instance of the chosen domain to work with NOINSTANCE remove any instance selection for autoselection LOCALE gt specify a subpart of the instance to work with PP gt display the locale selected INFO print out environment stats UNLOAD TRANSFORM unload the transformations for the domain UNLOAD REFINE unload the components for the domain REF LRU gt set the LRU stack length for no of components in mem TRANS print out a transformation CLASS gt print out a class SUGGEST gt suggest transformations to apply to the locale APPLY apply a transformation to the locale TRANSFORM scan for transformations in the current locale ANNOTATE attach transformations in lt domain gt TLB to internal form REF INE
96. ing CHART A B C evaluate E until fail and then build n number of right leaning trees with A C as top nodes and B D as internal DE nodes and OMEGA as terminator of all trees horizontal parsing Inside of a NODE only Syntax Meaning lt identifier gt literal data lt number gt literal data H lt number gt pop nth object on stack and use as is 2 3 Special Functions in Parsers In this section we will discuss three major features available to parser builders which do not affect the syntax of the language In Draco 1 2 Users Manual particular we will discuss data flow consistency checking functions diagnostics to the user and nonstandard internal form constructors 2 3 1 Checking Consistency in Parsers Within a parser for a certain language it is nice to be able to check the consistency of the objects given in the user s progarm For example if the language allows function calls and if a function is called in the users s program the parser should ensure that the function is defined later Quivalently if a function is defined then the parser should ensure that some other part of the program is using it Within Draco these operations are carried out by the following parser constructs Syntax Meaning The DEF construct declares that the contents of the token buffer contain the identifier of an object which is defi
97. ion of what to represent in the internal form and how to represent it is a difficult 20 Draco 1 2 Users Manual process 4 2 3 Elements of a Transformation Insertion File This section summarizes the commands to XFMGEN which may appear in a transformation insertion file Syntax Meaning CLASS lt classname gt This declares a restricted pattern variable named lt classname gt which can match any of the lt identifier gt lt identifier gt identifiers given The lt classname gt may appear anywhere in a transformation This declares all the identifiers as unrestricted pattern variables If a pattern variable PVARS lt identifier gt lt identifier gt 2 3 appears twice in a pattern then the objects it matches must be the same TRANS lt transname gt lt application code gt lt lhs gt lt rhs gt ERASEPVARS This erases all current pattern variables but not classes This describes a transformation with name lt transname gt and other fields as shown 4 2 4 The Application Code of a Transformation In the transformations above and in Appendix V the application codes follow the following rough guidelines NOTE 6 EC stands for enabling conditions Markov algorithm can enlarge locale Always do this transformation no EC s Always try this transformation has EC s Convert to canonical form no EC s Convert to canonical form
98. le 2 number too large FMREF gt locale 1 BO E FMREF gt locale 1 B 2 4 A C FMREF gt locale 1 B 2 fok lets look at the operator TFMREF gt PP 8 fyes were really there Draco 1 2 Users Manual TFMREF gt SUGGEST 10 OIDDEF 7 EXPX2 3 lt OP gt XIF 2 lt OP gt IFX TEMREF gt TRANS EXPX2 transformations loaded EXPX2 7 PZ gt RZY PA FMREF gt TRANS OIDDEF OIDDEF 10 X lt OIDOPS gt 1 FMREF gt CLASS lt OIDOPS gt lt OIDOPS gt MPY EXP FMREF gt APPLY EXPX2 XPX2 7 B 2 gt B B FMREF gt LOCALE 1 B B FMREF gt locale 1 B B 4 A C FMREF gt locale 2 SORT Ganie FMREF gt locale 100 PROGRAM QUADRATIC SQUADRATIC weed END TFMREF gt PP PROGRAM QUADRATIC QUADRATIC LOCAL A B C ROOT1 ROOT2 LOOP PRINT QUADRATIC EQUAT PRINT INPUT A B C PARAM A READNUM IF A 0 THEN RETURN B READNUM C READNUM ROOT1 B SQRT B B 4 A ROOT2 B SQRT B 2 4 A PRINT THE ROOTS GOTO LOOP ND Li TFMREF gt TRANSFORM LO CODE 3 fask for transformation suggestions transformation name and application code in application code order what does expx2 transformation do first get the transformation library fit makes into what is an OIDDEF gt X 1 identity operators which operators are 1
99. llman J D Principles of Compiler Design Addison Wesley Publishing Co 1977 Neighbors J M Software Construction Using Components PhD thesis University of California at Irvine 1980 UCI ICS technical report TR 160 Schorre D V META II A Syntax Oriented Compiler Writing Language In Proceedings of the ACM National Conference pages D1 3 1 to D1 3 11 ACM 1964 Standish T A Harriman D C Kibler D F and Neighbors J M The Irvine Program Transformation Catalogue Technical Report ICS Dept University of California at Irvine January 1976 Neighbors80 Schorre64 Standish76 APPENDIX I A COMPLETE EXTERNAL INTERNAL LANGUAGE DEFINITION In this appendix the complete external and internal definition for an example language called SIMAL is given along with an example program written in SIMAL SIMAL represents a conventional ALGOL like language It is hoped that domain languages will differ greatly from this form I 1 External Internal SIMAL Definition The following is the file SIMAL DEF If any errors occur during the parsing of a SIMAL program the rule names in the error messages will refer to parse rules in this file DEFINE SIMAL SIMAL simple ALGOL like language for examples James Neighbors Last Modified March 11 1982 SIMAL PROGRAM TREE PGM PGMSEQ NAME TREE AP APSEQ EXP EXP NODE PROCCALL 2 1
100. ms in one domain we can use statements in other domains To do this we need to signal to the parser that a change of domains will take place This is done with the following construct lt DOMAIN NAME gt lt RULE NAME gt lt statements gt No blanks are allowed between the braces and text The rule name can be the main rule of the parser of the inside domain or it can be a specific rule just related to the statement s we want to use CHAPTER 7 USING TFMREF THE PROGRAM MANIPULATION SUBSYSTEM The transformation and refinement subsystem of Draco TFMREF is used by a System Specialist to refine a program written in a domain language into an executable language Before the TFMREF system can manipulate a program it must be converted into the prefix internal form for the domain by PARSE The basic cycle of a System Specialist using TFMREF is to transform the program to remove inefficiencies and then to refine the program by selecting an appropriate refinement software component to implement the primitives of the domain used in the program This cycle is repeated over and over with the software components introducing meaning and the transformations stripping the generality out of the software components Each time a refinement is made a record is kept so that the EXAMINE subsystem can account for the purpose of any line at any level of refinement in the resulting system 7 1 The TFMREF Commands Which Set the Context
101. n USEd and not DEFed Each time the ASSUME construct is referenced it will either result in a fail which means that there are no ASSUME more objects of the type to be assumed or it will result in syntax recognition with the identifier of the next object of type the type to be assumed put on the node stack and automatically DEFed For example this is useful in the declaration of local variables in a function All variables used in the function and not declared to be global could be assumed to be local without having to have both a local and a global declaration 2 3 2 Notifying the User While the parser is parsing the user s program it is nidce to be able to tell the user what is going on For example it is nice to tell the user what major part of the program is currently being parsed This is doen with the MSG construct Within the MSG construct the following items are acceptable Syntax Meaning abced A string to be printed Print the token buffer contents CR Print a carriage return and linefeed COL value Advance the carriage to the given column Each time a crlf is encountered markers are printed as the parser does its work Most parser messages will need a CR first 2 3 3 Non Standard Parser Constructs The fillowing parser constructs are briefly described in the interest of completeness but they should not be used by domain parser builders
102. n a lt domain name gt REF file When the building process begins the Refinement Library lt domain name gt RLB file may not exist and it is created from scratch If the library is not empty the components in the lt domain name gt REF file are incorporated into it those that were already there are updated according to the new definition from the lt domain name gt REF file Thus this variant of the BUILD command is used both for creating and updating the refinement libraries To illustrate the dialogue with REFGEN we will use a set of refinement components of DRACO itself as input DRACO REF As we already have a Refinement Library for Draco REFGEN NOTEs it and provides a list of the components defined At this point if no lt domain name gt REF or lt domain name gt DEC files are found in the user directory REFGEN will flag an error and the process will be aborted REFGEN prints asterisks as it parses each line of the component definitions DRACO gt build DOMAIN NAME draco DOMAIN PART component library 25 Draco 1 2 Users Manual Component Library Builder working on DRACO domain NOTE existing component library contains APARAMS APARAMS SEQ FPARAMS FPARAMS SEQ LABELS LABELS SEQ LOCALS LOCALS SEQ PARTIALS PARTIALS SEQ PROCCALL PROCDEF PROCLIST pROCLIST SEQ SEQUENCE NOTE insertion file components replace library components Component
103. nditions conditions on the domain objects on which the component operates and conditions on previously made implementation decisions The conditions on the domain objects are local to the locale where the component will be used The conditions on the implementation decisions are global to the domain instance being refined The ASSERTIONS field of a refinement makes assertions about the implementation decisions the component makes if it is used The assertions are the opposites of the conditions on implementation decisions The management of assertions and conditions is discussed in more detail in Neighbors80 The RESOURCES field of a refinement states what other components will be required to perform initialization if the refinement is chosen The resource components are program parts which are executed before the resulting program begins execution initialization phase and they create information resources for the refinements used in the program An example use of a resource is a refinement for cosine which interpolates a table of cosines during execution The table must be built during the initialization phase and the name of the table must be passed to the interpolation refinement of the component cosine This 24 Draco 1 2 Users Manual is achieved by building a refinement which interpolates tables and requires a resource component which builds interpolation tables The ADJUSTMENTS field of a refinement states fine tuning settings for a refinement
104. ned DEF type to be of the given type The type is just a name made up by the parser builder FUNCTION would suffice for the example given above The USE construct declares that the contents of the token buffer contain the identifier of an object which has been referenced as the given type The RESOLVE construct checks to see that all the objects of the given type which have been defined have been RESOLVE __ referenced It also checks that all the objects of the given type which have been referenced have been defined Error type messages will be printed if any discrepancies occur However no syntax error or failure will be issued from the construct USE type RETRACT type The RETRACT construct erases any USE s or DEF s for the given type in the current context The CONTEXT PUSH construct saves all DEF s and USE s for the given type on a stack and erases them in the current context This is useful for objects with nested scoping such as labels local to BEGIN END blocks Upon entering the block the lables are pushed and upon exiting the block the labels are first resolved and then popped CONTEXT The CONTEXT POP construct retrieves the definitions for the type previously saved on the stack The stack is not POP type the same as the stack used in constructing trees CONTEXT PUSH type The ASSUME construct can be used to assume declarations for objects of the type which have bee
105. ng Parser Backtracking The alternation used in Draco assumes that one of the alternatives will succeed in matching the input stream A sequence succeeds in matching the input stream if all of the objects indicated in the sequence are found in the input stream remember the sequence operator is a blank If the first object in the sequence is not found then the sequence operator indicates a failure to recognize If the first object in the sequence is found but some other part of the sequence is not found then a problem occurs in that the pointer into the input stream has been advanced over the first object In this case the sequence operator indicates a syntax error but does not report it to the user yet The alternation operator passes the syntax error on up to the construct above it The backtracking operator l traps the syntax error returned by a nested sequence operator restores the state of the parser to the point where the backtracking operator was entered and trys the next alternative In short a backtracking operator is the same as an alternatation operator except that the state of the parser is saved and restored between the alternatives The backtacking operator indicates failure to recognize if none of the alternatives are present in the input stream The backtracking operator never results in a syntax error indication The backtracking operator is more expensive in time and space because of its state saving and restoring One could use o
106. nly backtracking operators in a parser definition without any alternation operators but the resulting parser would be very slow in execution The basic idea of having the two similar operators is to be able to specify in a parser description where the language described is simple LL 1 parseable and where LR k parsing must be used As an example of where backtracking is needed consider the following Draco BNF description A B n owen gt s Draco 1 2 Users Manual B a g h n ngm ju 3 The strings afg and afh are recognized by the grammar but the string afi would result in a failure of the rule A without advancing the input pointer If given an afi in the input stream the rule B would recognize the a and f in the first alternative and issue a syntax error to the backtracking operator in the A rule because the first two elements of the sequence were present but the h was missing The other alternative is not even tried The afg is recognized because the B rule returns a syntax error to the backtrack in A which restores the parser input pointer to be pointing to the a and then tries its next alternative We could rewrite the grammar in two ways by replacing the alternative in the B rule by a backtrack A B n fu ng B a g h n ff or by factoring the alternative in the B rule A B n fu gi B a wen h i The second option is of course faster in execution but the main
107. nly contain identifiers but it can appear anywhere in an internal form The transformations TRANS have a name application code left hand side lhs and right hand side rhs The lhs of a transformation must be an internal form not a simple identifier and the rhs of a transformation may be an internal form or an identifier The application code states what kind of transformation this is and it is discussed in a following section The lhs of a transformation is the form to be matched and the rhs of a transformation is the form which will replace it The ERASEPVARS command sets the list of current pattern variables to empty The pattern variables are defined only for the transformations in the insertion file and they do not have to be the same ones used for transformations already in the library The ERASEPVARS command is useful for concatenating together transformation insertion files to recreate a library from scratch Notice that the PAREN form which we added to the assignment statement example in the PARGEN section is cleverly used in the LDISTMPYADD transformation above The lhs of the transformation assumes that there is a PAREN between the MPY and the ADD because in no other way could the tree have been constructed The rhs is embedded in a PAREN because the precedence of ADD is less than MPY and the precedence must be maintained The transformation PARENPAREN and some others is needed to maintain only the PAREN s needed To reiterate the select
108. nts so that if the output from the prettyprinter is to be read back into PARSE then these characters must be acceptable input 3 7 Producing a Successful Prettyprinter Since the prettyprinter cannot print anything not in the internal form a successful prettyprinter relies on an internal form which represents everything from in the external syntactic representation Our assignment statement example s internal form is deficient in that we cannot create a prettyprinter that can take an internal form and print it in a form which can be parsed into the original internal form The problem with our example is that parentheses are not represented explicitly in the internal form Implicitly the parentheses are represented by the hierarchy of the operators and the structure of the tree but precedence information is available only to the parser not the prettyprinter As an example if we input ANS a B C it would be prettyprinted by our defined prettyprinter as ANS a B C While the internal representation is still correct the external representation is incorrect Quite a bit of thought must go into what will be represented in the internal form and how this representation will be printed out so that it is pleasing to look at and accurate in its meaning To solve our problem we should give the parentheses an internal representation by changing the line EX1 W in the assignment statement example see page to the line E
109. o BNF in Draco BNF and the internal LISP form parsers take when they are constructed When PARGEN cites a rule in an error during the construction of a domain parser the rule is from this file Also included in this appendix is a catalog listing of the transformations PARSER TLB which are used to optimize parsers see parser optimization II 1 The File PARGEN DEF DEFINE PARSER PARGEN Main Parser Generator James Neighbors Last Modified May 7 1983 PARSER DEFINE PARSER1 END RESOLVE RULE PARSER1 ID USE RULE LIST PROG NODE DEFINE PARSER FN PARSE LAMBDA NIL PARSI ST COMMENT COMMENT CMNTCHRS NODE NILL ST ID DEF RULE LITERAL MSG CR Rule 601 30 LITERAL EX1 NODE PARSER RULE 2 1 TEX1 NODE PARSER TOKEN 1 NODE DEFINE PARSER FN 2 LAMBDA NIL 1 ERRST NODE NILL ERRST TOKEN ANYBUT ANY DELTOK EX1 IST OR EX15 EX15 EX15 EX2 EX17 NODE PARSER BACKTRACK 2 1 EMPTY EX17 EX2 EX17 NODE PARSER BACKTRACK 2 1 EMPTY EX2 EX3 LIST AND EX3 NODE AND 2 OR 1 PARSER ERROR EX3 ID USE RULE NODE STRING NODE PARSER TEST STRING EX1 J
110. of CHARTPRINT is similar to the use of TREEPRINT If we had the following node I any node z A S s B pasten A SEQ a B SEQ 1 Lo j A SEQ b OMEGA B SEQ 2 OMEGA we could use the following definition in the any node prettyprinter rule to print a two column chart CHARTPRINT A SEQ 2 gt as B SEQ 3 If used in the above chart internal form it would result in the following output gt a as 1 gt b as 2 The CHARTPRINT directive pulls one element at a time from each of the right leaning internal form trees and prettyprints them across the page The two expressions associated with each tree are printed before and after the tree element If all the trees of a chart are empty then the chartprint does no printing 3 5 Special PrettyPrinter Functions The CHARPRINT directive takes one subtree specification e g 1 and attempts to treat the selected item as a number If it is a number it is sent as an ASCII code For example CHARPRINT 2 applied to the internal form l any node 23 65 would print an A since 65 is the ASCII code for an A This is used where a domain language contains special quoted characters The LISTPRINT prettyprinter directive is the printing analog of the SEXPN and LIST parsing directives These are for internal use only and should no
111. ograms in the domain These simplifications are accepted in terms of source to source program transformations by the BUILD subsystem which forms them into a library of transformations The creation of transformations is discussed in Chapter 4 4 Finally the Domain Analyst must prepare a prose description of the meaning of the operations and objects in the domain 5 This prose description is turned over to a Domain Designer who specifies components for the objects and operations in the domain which refine the objects and operations of one domain into other domains known to the Draco system These components are formed into libraries by the Draco subsystem BUILD from specifications described in Chapter 5 A component is a set of refinements each capable of implementing a domain object or operation under certain stated conditions while making certain implementation assertions 6 A new system defined by a Systems Analyst which can be described in a Domain Language known to Draco can inherit some analysis design and coding from the Draco library The statement of the system to be constructed is cast in a Domain Language The Domain Language program is then turned into an internal form by the PARSE subsystem The use of the PARSE subsystem is described in Chapter 6 This internal form is then given to a System Specialist 7 The System Specialist interacts with the transformation and refinement subsystem of Draco called TFMREF described in Chapter 7 The b
112. quired for each component definition Basically the only required fields are COMPONENT REFINEMENT INSTANTIATION and CODE 5 2 The Motivation for Libraries of Components Components are placed into libraries in much the same way and for much the same reason that transformations are placed into libraries The processing of a single component for inclusion in the component library of a domain is very expensive For each refinement in the component the parser for the domain s in which the refinement is written must be loaded to parse the external form into internal form Once the code for the refinement is in internal form the agendas of the internal form are annotated with transformations of interest from the transformation library of the target domain These transformation suggestions are made in much the same way that transformation suggestions are made when a domain language program is parsed as discussed on lt A HREF TRANSSUGGEST gt page lt A gt The transformation suggestions will point out things of interest when the refinement is used Thus Draco supports a component library construction facility where a group of components may be replaced or added without disturbing the other components in the library 5 3 Building a Component Library The REFGEN subsystem in DRACO supports the construction of libraries of components The process is activated by using a variant of the BUILD command The components to be inserted in the library are kept i
113. r example the set of program statements could be represented internally as I I I STMT SEQ stmtl I I 1 STMT SEQ stmt2 7 P t STMT SEQ stmtn OMEGA If we had a parse rule GET STMT which could build nodes for statements in a particular language then the construction of this internal form could be achieved by the syntax TREE STMTS STMT SEQ GET STMT The TREE construct always takes the three arguments the header node name for the tree the internal node name for the tree and an expression which produces multiple nodes to be linked together in the tree This internal form structure is known and exapected by the 11 Draco 1 2 Users Manual refinement part of Draco It is acceptable to have a tree with no internal nodes indicating a variable length structure with no elements While the TREE constructor is used for scanning variable length structures from Top to bottom and building a tree some mechanism must be defined for scanning sets of variable length structures from left to right An example of such a structure is a table in which we wish to associate the columns together in a tree rather than the rows even though we must scan through the table a row at a time Consider the problem where we wish to scan the following table of data female Sally male Dick female Jane into the following internal form SER vas eee
114. r the language presented in Appendix I CHAPTER 4 BUILDING A TRANSFORMATION LIBRARY WITH XFMGEN After the Domain Analyst has settled upon an internal and external representation of the domain language and described this to Draco through PARGEN the simple relationships between the objects and operations in his language must be described These relationships are described as program transformations on the prefix internal structure of the domain The transformations will be used to simplify program fragments written in the language These fragments may come from refinements of other domain languages into this language the results of transformations on this language or the use of PARSE to take in a program in this language The transformations usually represent relations which the Domain Analyst regards as being obvious such as x 0 implies NOTE 5 x The transformations will be used to strip the generality out of software components written in the language when they are used in a specific problem 4 1 The Transformation Library and Metarules The subsystem XFMGEN takes the view that transformations are incrementally added to a library of transformations for a domain If a library does not exist then XFMGEN will create one There are two basic reasons for the incremental construction of the transformation library First it is hard to come up with all the useful transformations for a domain at once Second if automatic metarule generation disc
115. rface The following sections describe the low level Refinement commands that are accessible through the Refinement User Interface 9 5 1 The TRY command TRY REFINEMENT NUMBER lt ref gt UNDER INSTANTIATION lt inst gt The TRY command attempts to apply the selected refinement of a component by it s order number lt ref gt in the component The 38 Draco 1 2 Users Manual default refinement is always number 0 The instantiation lt inst gt is either INLINE or FUNCTION INLINE instatiates the refinement inline as a macro expansion FUNCTION abstracts a function of the refinement and inserts a call to the abstracted function With TRY the user is asked for final approval 9 5 2 The USE command USE REFINEMENT NUMBER lt ref gt UNDER INSTANTIATION lt inst gt The USE command is equivalent to the TRY command except that the user s approval is not requested 9 5 3 The DEFER command DEFER The effect of the DEFER command us similar to that of ABORT that is it interrupts the refinement process but in this case it defers making a decision about the component refinement and shifts control to the entry tactics 9 5 4 The ABORT command ABORT The ABORT command aborts the refinement process and transfers control back to the TFMREF subsystem level Tactics are halted 9 5 5 The DO command DO TACTICS COMMAND lt tactic CMD name gt The DO command produces a searc
116. rich opportunities for transformations and results in faster programs DEFINE HEAD ENTRY COMPONENT LOC 3 DEFINE INLINE ENTRY ALL lt DIRECTIVE gt USE ALL lt AVAILABLE FUNCTION gt USE FUNCTION ALL lt FUNCTION INSTANTIATION gt USE FUNCTION USE DEFAULT EXIT The tactics parser and prettyprinter are in Appendices VII and IX NOTES 47 Draco 1 2 Users Manual NOTE 1 NOTE 2 NOTE 3 NOTE 4 Draco is Latin for dragon SADT is a registered trademark of SofTech Inc Members of group 4800 can access the software We would have liked to have made the Draco menu driver compatible with the standard Tops 20 Exec but in UCI Lisp under the PA1050 simulator we have input activation only on linefeed carriage return and escape These are the control keys used by the menu driver NOTE 5 NOTE 6 NOTE 7 NOTE In fact the scheme is actually iterative to avoid very large levels of recursion resulting from printing large programs where 8 the statements are in a tree This is necessary to avoid blowing the LISP special and regular pushdown lists Draco uses gt to denote implication for transformations We plan to change from using numbers to domain specific names for the operations The EXAMINE subsystem and history recording are not operational in the current system REFERENCES Aho79 Aho A V and U
117. rocess to prevent Draco for asking too many questions The TACTICS subsystem in an interpreter that allows the user to define tactics interactively DEFINE or to use an existing tactic set LOAD The TACTICS subsystem is called from the TFMREF system with the command TACTICS This activates the TACTICS interpreter After the loading of the interpreter are printed during this process we can use any of the TACTICS commands FMREF gt TACTICS HELP prints the help file he TACTICS commands are DEFINE define a tactic LIST list the tactics to screen or file DELETE delete a tactic LOAD gt load tactics from a file HELP this list EXI return to TFMREF subsystem More detail on the syntax of these commands may be found in the Draco manual Remember all commands must be terminated by a semicolon LOAD DEMO DEMO TCT is the tactic file KKK KKK KKK KKK KEK KKK KK KKK KKEKK each is one line processed Parse Completed 0 errors detected EXIT TFMREF gt The DEFINE command defines the rules The format of the command is 46 Draco 1 2 Users Manual DEFINE lt rulegroup name gt lt rule name gt lt rule gt Rules with rule name ENTRY are automatically run as tactics Rules with the rulegroup name CMD must be invoked from the Refinement User Interface The goal of all tactic rules is to get a refinement for a single
118. seq gt lt token ele gt lt token ele gt lt token ele gt lt identifier gt lt char rule gt lt token exp gt lt token iteration gt EMPTY lt token iteration gt lt lt iteration range gt gt lt token ele gt 5 lt token ele gt lt char rule gt ANY lt char exp gt ANYBUT lt char exp gt lt char exp gt lt char range gt lt char range gt lt char range gt lt char value gt lt char value gt lt char value gt lt char value gt lt number gt lt character gt lt identifier gt lt alphabetic gt lt alphabetic gt lt digit gt lt identifier gt lt number gt lt digit gt lt digit gt lt string gt lt schar gt lt alphabetic gt A B Z la b z lt digit gt zgz 0 1 wee 9 Figure 2 1 BNF for Parser Definition 2 1 2 An Example of Draco BNF The lt token rule gt s specify how to collect characters into tokens lexemes while the lt parse rule gt s specify how to group tokens together to parse the external form The lt char rule gt s specify what characters to accept within a lt token rule gt The iteration rules lt parse iteration gt and lt token iteration gt are similar to the notation used above and specify sequences which may occur zero or more up to an optional limit times Kleene and are a subset of the available values of iteration As an example of the Draco BNF consider the
119. t Z LOCAL X 25 rl PTY 2X 27 X Y S EMPTY EP 2X TO DO FOR V W STI 22 gt gt gt gt em e gt 51 HEN S1 gt B IF P THI IF P THI lt rel gt A lt rel gt B B gt 0 HEN A lt rel gt B B lt rel gt A A lt rel gt B B lt rel gt A 5 F H gt 0 5 2B THI EN lt uop gt S1 EN lt uop gt S1 ELSE lt uop gt S2 F D 2 EP 2X 10 21 DO EN S1 gt LSE S2 IE BLOCKNREPEAT 12 EAT Cl r BLOCK DIVDD DIVDX DIVXD HI 12 WHILE A B C 2D A B C gt C A B gt 2X 3 3 2 2X H EL EN S1 SE S2 25 F UNTIL Y gt R 22 DO Y gt gt A D B C A B C B C A 12 A B gt A B EQUALMAMB EQUALXX 11 X 7X gt TRUI F a EXP00 12 0 0 gt UND EFI NED EXP1X 14 EXPAMB 10 EXPX0 9 EXPX1 14 EXPX2 9 FNCALL 12 FOREMP 11 107X gt 1 A B gt 2X00 gt 1 2X01 gt X X 2 gt X X LOG 0 gt UN FOR W X STEP EMPTY gt FOR V W S 2Z V 1 FORFUNROLL 1 A 2B DEF INED 2Y LO 22
120. t UNDEFINED gt UNDEFINED lt BOP gt XEMP 12 X lt bop gt EMPTY gt UNDEFINED lt BOP gt XIF 3 X lt bop gt IF P THEN S1 gt IF P THEN X lt bop gt S1 lt BOP gt XIFELSE 3 X lt bop gt IF P THEN S1 gt IF P THEN X lt bop gt S1 lt BOP gt XUN 12 UNDEFINED lt bop gt X gt UNDEFINED lt DIV gt 0X 9 O lt div gt X gt 0 lt DIV gt AMB 10 A lt div gt B gt A lt div gt B lt DIV gt MAB 10 A lt div gt B gt A lt div gt B 54 Draco 1 2 Users Manual lt DIV gt MAMB 12 A lt div gt B lt DIV gt X0 12 X lt div gt 0 gt DIV gt X1 12 X lt div gt l gt DIV gt XX 11 X lt div gt X gt REL gt 0S 10 O lt rel gt A B REL gt 1D 9 1 lt rel gt A B gt lt lt lt lt A RI lt R gt AA i gt DD 10 9 A C lt rel gt B A C lt rel gt B A REL gt MM 9 A C lt rel gt B B REL gt S0 REL gt SS UOP gt C UOP gt EM UOP gt IF UOP gt IE 0 0 A B lt rel gt 0 A C lt rel gt lt uop gt X gt lt uop gt EMPTY lt uop gt IF P TH 3 lt uop gt IF ryj im 12 NRA p UOP gt UN 12 DOX 12 DAMB 10 DDD 5 DDX 3 DMAB 9 DMAMB 12 DX0 12 DXD 3 DFX 11 DNOTXX DXF 11 DXNOTX DXT 12 DXX 11 DXY 3 lt uop gt UNDEFINE 0 X gt X A B gt A B C D A
121. t be used in domain languages Draco 1 2 Users Manual 3 6 Elements of a Prettyprinter Description This section summarizes the elements which may appear in a prettyprinter line and what they do abcd print a literal string lt number gt print the ASCII character LM fix left margin at current position LM lt number gt fix left margin at original margin plus the argument fix left margin at original margin minus the LM lt number gt argument LM lt number gt fix left margin at original margin plus the argument move to column number do crlf if necessary uses tabs COL lt number gt and spaces seek left margin from LM do crlf if necessary uses SLM tabs and spaces SLM lt number gt do SLM if print column is greater than number TREEPRINT lt identifier gt lt number gt lt node item gt prints TREE parsed internal forms CHARTPRINT lt identifier gt lt number gt lt node item gt lt identifier gt lt number gt lt node item gt prints CHART parsed internal forms CHARPRINT lt number gt prints explicit ASCII code LISTPRINT lt node item gt prints LIST parsed internal forms The printing of ASCII codes does not confuse the line column counter and these may be freely combined with the other directives It is important to note that the prettyprinter will output tabs and spaces when it inde
122. t ge gt B gt A gt B OREQ lt LE gt 9 A B A lt le gt B gt A lt B ORFX 12 FALSE X gt 2X ORNOTXX 11 ORTX 11 TRUE X gt TRUE ORXAND 9 X X amp Y gt X ORXF 12 X FALSE gt X ORXNOTX 11 X ORXT 11 X TRUE gt TRUE ORXX 11 2X X gt 2X ORXY 3 X Y gt IF X THEN TRUE ELSE Y PARCONST 12 X gt X PAREMP 12 EMPTY gt EMPTY PARF 12 FALSE gt FALSE PARPAR 12 2X gt X PART 12 TRUE gt RUE PARUN 12 UNDEFINED gt UNDEFINED REPEATEMP 9 REPEAT EMPTY UNTIL P gt EMPTY REPEATIFELSE 1 REPEAT IF Q THEN R ELSE S UNTIL P gt REPEAT WHILE Q DO R 25 UNTIL P REPEATSUN 10 REPEAT S UNTIL UNDEFINED gt UNDEFINED REPEATUNP 12 REPEAT UNDEFINED UNTIL P gt UNDEFINED SEMICAW 2 X Y X WHILE P X DO 0 X X Y X gt WHILE P X Y X DO Q X SEMICBLOCKN 12 S1 S2 gt 281 252 SEMICEMPX 12 EMPTY 2X gt X SEMICIFELSEX 2 IF P THEN X ELSE Y 251 gt IF P THEN X 2811 ELSE Y 2511 u EMICIFIF 9 IF P THEN X IF ELSE Y SEMICLEMPS 12 X EMPTY 25 gt X 25 SEMICLXIF 10 X 252 IF REPEAT 29 UNTIL Y Draco 1 2 Users Manual SEMICXEMP 12 X
123. tack and the object on top of the stack The operation NODE MPY 1 1 forms the literal MPY and the top two elements of the stack into a node WARNING Note that this is tricky NODE EXP 1 2 forms the top of the stack and the third element of the original stack into a new node The operation removes the elements from the stack when they are fetched 2 2 4 An Example Internal Form Using our example assignment definition above the prefix internal form of the statement ANS GEO B 2 E E 2 C 15 l ASSIGN ANS I ADD cones l l U i FNCALL GEO EXP E eases l I APARAMS EXP 2 C APARAM B APARAM OMEGA toot MPY 2 E Notice that the precedence of the operators is done by ordering the lt parse rule gt s and that multiply is left associative while exponentiation is right associative 2 2 5 Variable Length Structures in Internal Forms Due to the restriction that all nodes of a certain type have the same number of subtrees some mechanism must be developed to allow a variable number of elements in some cases For example not all programs have the same number of statements in them so some structure must be developed to hold a variable number of statements In Draco this is done by means of right leaning trees with header nodes internal nodes and a special termination marker Fo
124. tes a call for the component in the internal form tree with some of the arguments already evaluated in the body of the function defined Limitations are placed on the partially evaluated forms allowed When a function is defined the defining domain component name and a version number are used to differentiate between functions of the same name in different domains and FUNCTION and PARTIAL versions of the same function in the same domain The final field of a refinement is either a DIRECTIVE to Draco or the internal form of a domain The internal form of a domain may be described either in a parenthesized tree notation with the INTERNAL domain directive or it may be specified in the external form domain language of the domain with the CODE domain nonterminal directive The CODE directive causes the parser for the specified domain to be read in and started to recognize the given nonterminal symbol A DIRECTIVE to Draco is one of the following alternatives view the component as a function definition by the user program view the component as a function call defer from refining this component and remove the node which invoked this component from the internal form tree The Draco DIRECTIVEs are used when a domain language is defined which allows function definitions functions calls and such things as refinements for comments which remove them from the program since they are saved in the refinement history Not all the component and refinement fields are re
125. the domain language parser might make this step easier Second a REFINEMENT is chosen and the refinement CONDITIONS are checked If an implementation decision condition is violated then the refinement may not be used Local conditions on the domain objects are formed into surrounding code for the refinement body The hope is that transformations for the domain will be able to remove this surrounding code by proving the conditions correct and removing the code 37 Draco 1 2 Users Manual The user is then asked about any ADJUSTMENTS for the refinement If the user supplies no adjustments then the default adjustments are used Next the refinement body is instantiated into the internal form according to the users wishes for INSTANTIATION and the allowed instantiations for the refinement The body is instantiated with minimal renaming to avoid naming conflicts If the refinement is instantiated as a function and a function already exists then the already defined function is used Once the refinement is inserted any necessary RESOURCES are added to the initialization phase of the developing program These resources are usually high level program fragments which also have to be refined Finally the ASSERTIONS for the refinement are made in the scope of the domain instance The assertions are a kind of lock and key mechanism with the conditions of other refinements When two domain instances are merged into a single instance of a same or other dom
126. tiation gt attempt to use a refinement show and ask before use USE lt refinement gt lt instantiation gt use a refinement and don t show or ask DEFER defer control back to the entry tactics restart tactics ABORT return to the TFMREF subsystem level stop tactics DO lt tactic CMD name gt do a predefined tactic command H LP this listing All of these commands are discussed in more detail in the Draco user manual 9 6 An example session with REFINE This section presents a session with REFINE In the session don t be concerned with the meaning of the domain language being manipulated it is the same one used in the example of Chapter 8 What is of concern in the example is the way in which the commands of the Refinement User Interface interact with the user to manipulate this example In the transcript user responses are underlined and comments included between curly brackets In particular every time appears it means that the output from Draco is similar for different components and it is not transcribed in order to prevent the example from being excessively long The transcript follows TFMREF gt One of the following CLASS TRANS ANNOTATE APPLY DOMAIN EXIT HARDCOPY HELP INFO INSTANCE LOCALE NOINSTANCE PP REFINE REFLRU SAVE SUGGEST TACTICS TRANSFORM UNLOAD REFINE UNLOAD TRANSFORI TFMREF gt tactics NOTE file DE
127. tic Equation II The Definition of Draco BNF in Draco BNF II 1 The File PARGEN DEF III The Definition of a Prettyprinter Description III 1 The File PPGEN DEF IV An Example Prettyprinter Description IV 1 A SIMAL Prettyprinter Description V An Example Set of Transformations V 1 SIMAL Transformations VI The Definition of a Component Insertion File VI 1 The File REFGEN DEF VII The Definition of Tactics VII 1 The File TACTIC DEF Draco 1 2 Users Manual VIII Draco Error Note and Syserr Messages CHAPTER 1 AN INTRODUCTION TO THE DRACO SYSTEM It has been a common practice to name new computer langauges after stars Since the system described in this manual is a mechanism which manipulates special purpose languages it seems only fitting to name it after a structure of stars a galaxy Draco NOTE 1 is a dwarf elliptical galaxy in our local group of galaxies which is domainated by the large spiral galaxies Milky Way and Andromeda Draco is a small nearby companion of the Milky Way 1 2E 5 solar masses and 68 kiloparsecs from Earth This small size and close distance to home is well suited to the current system which is a small prototype 1 1 The Draco View of Software Production The Draco system addresses itself to the routine production of many systems which are similar to each other The theory behind its operation is described in detail in Neighbors80 Three themes dominate the way Draco operates the use of special
128. tions of a certain application code range all over the selected locale It allows the System Specialist to have the system request approval of each transformation lt answer gt is ASK or NOASK The transformations are applied to the locale from the leaves of the internal form up to the root of the locale At each node the transformation with the highest application code is applied first When a transformation is successfully applied if the information in the metarules specifies transformations on the new program fragment then the bottom up process begins again on the new fragment It suffices to say that all the information in the metarules is taken advantage of by TRANSFORM After a TRANSFORM the SUGGEST command will give rules suggested by the metarules during the TRANSFORM whose application codes were outside the range given to TRANSFORM The more obscure transformations are usually suggested by the system in this way 8 4 The TRANS Command TRANS lt transformation name gt The TRANS command prints out the text of a transformation This is useful for examining a transformation suggested by the SUGGEST command The format of the transformation is the same as for a catalog listing see catalog 8 5 The CLASS Command CLASS lt class name gt The CLASS command prints out the prefix keywords which match a class This is only included because the TRANS command may print out a class name as part of the transformation and an initiate of th
129. ussed below is used it is computationally expensive to start a library from scratch 4 1 1 Transformation Metarules As XFMGEN reads in the transformations it has the capability to automatically produce metarules Briefly these metarules give Draco information about what it can do next after it applies a transformation The metarules state where it is important to apply which transformations in what order The metarules are expensive to produce since for every transformation added to the library every transformation in the library including the new one must be examined for possible relations to the new transformation The examination process itself is expensive Thus if we have a library of n 1 transformations the complexity of adding a new transformation is O n while the complexity of reconstructing the whole library is O n n Since the library for a domain typically consists of 200 1000 transformations sample size of two the difference between incremental addition to a library and reconstructing the library is significant The specific scheme for automatically generating transformation metarules is described in Neighbors80 Chapter 3 and Appendix II 4 2 Specifying the Program Transformations 19 Draco 1 2 Users Manual Unfortunately the program transformations must be specified in the prefix internal form of the domain language The reason for this is that some transformations are not syntatically correct according to the external
130. xpression to skip over the ill formed statement If the second expression results in an error then the user is again notified that error recovery was unsuccessful and the syntax error is returned as the result of the error block with the state of the parser restored to the point where the error block was encountered If the first expression in the error block succeeds or fails then it is the result of the error block The error block only stops syntax errors As an example of using an error block consider the following grammar which recognizes statements STMT followed by a semicolon The error recovery strategy for an ill formed STMT is to scan all the characters up a semicolon The error reporting is already handled by the error block BODY STMT STERR STERR TOKEN ANYBUT DELTOK If a syntax error occurs inside of the error recovery part of an error block then a message is given that the error recovery has failed is given and the syntax error propagates out of the error block It is important for the parser designer to remember that an error message is printed to the user every time a syntax error occurs Thus syntax errors should not be used by a parser designer as a control strategy Token rules indicated by a rather than a never generate a syntax error and never advance the input pointer on a failure The token buffer always contains the token recognized in the input by the last token which succeeded
131. y DOMAIN TLB unavailable ERR transformation library FILE unavailable for suggestions ERR underflow of the node stack E F I iE saved y F FILE created DOMAIN domain being removed adding to an existing transformation library creating a component library for the domain creating a new transformation library domain already selected existing component library contains existing tactic TACTIC replaced file FILE accessed from Draco disk area file last modified on DATE function USER FUNCTION 0 defined function definition exhausted domain instance insertion file components replace library components new domain instance automatically selected no domain instance selected no instance of DOMAIN domain in locale of refinement no prettyprinter available no tactics have been loaded refinement deferred by directive refinement index loaded refinement merged a domain refinement replaced Draco top level refinement replaced a domain resource check RRCHECK is a stub tactics interrupted by user transformations loaded function DOMAIN COMPONENT 0 defined 2222222222222222 222222222 2 2 Zb bibi bi bi bl bl bi bi bd bd bt OOOOOOOOOOOOOOOOOOOOOOOOOCOOCO i
132. y stmnt x OMEGA x TRANS bodyelim2 12 body stmnt empty OMEGA empty ERASEPVARS The following dialogue updates PARSER TLB with the content of the new transformation insertion file In this second session XFMGEN the Transformation Library Builder notes that a transformation library PARSER TLB already exists DRACO gt build DOMAIN NAME parser DOMAIN PART transformation library Transformation Library Builder working on PARSER domain NOTE adding to an exisiting transformation library parenthelim parenthelim2 parenthelim3 stmnteliml stmntelim2 bodyelim bodyelim2 Prettyprinted Transformation Catalog Listing Y N gt Y NOTE PARSER CAT created NOTE PARSER TLB created A prettyprinted version of the updated library PARSER CAT is shown below 3 24 83 1 49 2pm PARSER TLB bodyelim 12 x gt x 22 Draco 1 2 Users Manual bodyelim2 12 empty gt empty false 97 x x gt false ifeliml 99 if true then 2X end if gt x ifelim2 99 if false then 2X end if gt empty ifelim3 99 if true then x else y end if gt x ifelim4 99 if false then 2X else y end if gt y not 95 x y not gt y not 95 x Py not gt x y parenthelim 99 x gt x parenthelim2 98 2X gt X parenthelim3 98 22 gt X stmnteliml 12 empty gt stmnt stmntelim2 12 empty gt true 95 x x

Draco 1.2 Users Manual - Bayfront Technologies, Inc.

Contents

Download Pdf Manuals

Related Search

Related Contents