home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c100 / 3.ddi / PARSER.ZIP / PARSER.ASC
Encoding:
Text File  |  1990-09-27  |  15.4 KB  |  669 lines
  1. _A HOME BREW C++ PARSER_
  2. by John M. Dlugosz
  3.  
  4. [LISTING ONE]
  5.  
  6. /* TOKENS. */
  7.  
  8.    <error>
  9.    <identifier>  => KW_SEARCH
  10.    <operator>    => OP_SEARCH
  11.    <punctuator>  => OP_SEARCH
  12.    <number>
  13.    <string>
  14.    <eof>
  15.    <type>
  16.  
  17. /* KEYWORDS. */
  18.  
  19.    auto break case cdecl char class const continue default delete do
  20.    double else enum extern far float for friend goto huge if inline int
  21.    interrupt long near new operator overload pascal private protected
  22.    public register return short signed sizeof static struct switch this
  23.    typedef union unsigned virtual void volatile while
  24.  
  25. /* OPERATORS. */
  26.  
  27.    || &&
  28.    < <= == > >=
  29.    + - * / %
  30.    ? ++ -- '->'
  31.    ! ~ ^ '|' & >> <<
  32.    = <<= != %= &= *= += -= /= |= >>= ^=
  33.  
  34. /* PUNCTUATORS. */
  35.  
  36.    '...' . , : ; [ ] { } ( ) ::
  37.  
  38. /* NONTERMINALS. */
  39.  
  40. Input -> File_and_tell <eof>
  41.  
  42. File_and_tell -> File      => AllDoneNow  1   /* normal completion */
  43.  
  44. File -> Item | File Item
  45.  
  46. Item -> Declaration
  47.    /* or Definition.  not in yet. */
  48.  
  49.  
  50. /**************************************************************
  51. To recognize a declaration, the storage class and type appear
  52. once.  They are remembered.  Each declaration is seperated by
  53. commas, and share the same type.  The FinishedDeclarator calls
  54. an action for each one found.
  55. ****************/
  56.  
  57. Declaration
  58.    -> StorageClass Type_w/const Declarators ;
  59.  
  60. Declarators
  61.    -> FinishedDeclarator
  62.    -> FinishedDeclarator , Declarators
  63.  
  64. FinishedDeclarator -> Declarator Initializer?  => Declaration 1
  65.  
  66. /*********************************/
  67.  
  68.  
  69. Initializer?
  70.    ->
  71.    -> = Expression
  72.    -> = { Expression-List }
  73. /* -> ( Expression-List ) */
  74.  
  75. Expression-List
  76.    -> Expression
  77.    -> Expression Expression-List
  78.  
  79.  
  80. StorageClass
  81.    ->            => StoreStorage 0
  82.    -> static     => StoreStorage 1
  83.    -> extern     => StoreStorage 2
  84.    -> typedef    => StoreStorage 3
  85.    -> auto       => StoreStorage 4
  86.    -> register   => StoreStorage 5
  87.  
  88. Type_w/const  /* const may appear before or after the type name */
  89.    -> Const/Volatile? Type Const/Volatile?       => StoreBaseConstVol
  90.  
  91. Type
  92.    -> char            => StoreType 1
  93.    -> signed char     => StoreType 2
  94.    -> unsigned char   => StoreType 3
  95.    -> int             => StoreType 4
  96.    -> short           => StoreType 4
  97.    -> short int       => StoreType 4
  98.    -> signed int      => StoreType 4
  99.    -> signed short    => StoreType 4
  100.    -> signed short int      => StoreType 4
  101.    -> unsigned        => StoreType 5
  102.    -> unsigned int    => StoreType 5
  103.    -> unsigned short    => StoreType 5
  104.    -> unsigned short int    => StoreType 5
  105.    -> long            => StoreType 6
  106.    -> signed long     => StoreType 6
  107.    -> unsigned long   => StoreType 7
  108.    -> float           => StoreType 8
  109.    -> double          => StoreType 9
  110.    -> long double     => StoreType 10
  111.    -> void            => StoreType 11
  112.    -> enum Tag        => StoreType 12
  113.    -> Class Tag       => StoreType 13
  114.    -> union Tag       => StoreType 14
  115.  
  116. Tag
  117.    -> <identifier>    => StoreTag 1
  118.    -> <type>          => StoreTag 2
  119.  
  120. Class
  121.    -> struct
  122.    -> class
  123.  
  124. OverloadableOp -> * | / | = | + /* and all the others */
  125.  
  126. Elipses? -> | '...'
  127.  
  128. /* Declarations */
  129.  
  130. Declarator
  131.    -> Decl2
  132.    -> ReachAttribute * Const/Volatile? Declarator    => TypeModifier 3
  133.    -> ReachAttribute & Const/Volatile? Declarator    => TypeModifier 4
  134.  
  135. Decl2
  136.    -> Decl2 ( Arg-Declaration-List )       => TypeModifier 1
  137.    -> Decl2 [ ConstExp? ]                  => TypeModifier 2
  138.    -> Decl3
  139.  
  140. Decl3
  141.    -> Dname          => Dname 1
  142.    -> ( Declarator )
  143.  
  144. Const/Volatile?  /* const or volotile, neither, or both */
  145.   ->                   => ConstVol 0
  146.   -> const             => ConstVol 1
  147.   -> volatile          => ConstVol 2
  148.   -> const volatile    => ConstVol 3
  149.   -> volatile const    => ConstVol 3
  150.  
  151.  
  152. ReachAttribute
  153.   ->         => ReachType 0
  154.   -> near    => ReachType 4
  155.   -> far     => ReachType 8
  156.  
  157. Dname
  158.   -> SimpleDname
  159.   -> <type> :: SimpleDname
  160.  
  161. SimpleDname
  162.   -> <identifier>
  163.   -> <type>
  164.   -> ~ <type>
  165.   -> Operator-FunctionName
  166.  
  167. Operator-FunctionName
  168.    -> operator OverloadableOp  /* overload operator */
  169.    -> operator <type> /* conversion operator */
  170.        /* this should really allow any abstract type definition, not just
  171.           a simple type name.  I'll change it later */
  172.    -> operator <identifier>  /* ERROR production */
  173.  
  174.  
  175. /* Argument list for function declarations */
  176.  
  177. Arg-Declaration-List
  178.    -> Start-Nested-Type A-Decl-List? Elipses? End-Nested-Type
  179.  
  180. Start-Nested-Type    -> =>  NestedType 1
  181. End-Nested-Type      -> =>  NestedType 0
  182.  
  183. A-Decl-List?
  184.    ->
  185.    -> A-Decl-List
  186.  
  187. A-Decl-List
  188.    -> A-Decl-List , Argument-Declaration
  189.    -> Argument-Declaration
  190.  
  191. Argument-Declaration
  192.    -> StorageClass Type_w/const Declarator  => Declaration 2
  193.  
  194. /* Expressions */
  195.  
  196. ConstExp?
  197.    ->
  198.    -> ConstExp
  199.  
  200. ConstExp -> Expression    /* semantics will check */
  201.  
  202. Expression
  203.    /* stub out for now */
  204.    -> <identifier>
  205.    -> <number>
  206.    -> <string>
  207.  
  208.  
  209.  
  210.  
  211. [LISTING TWO]
  212.  
  213.  
  214. // the node class is central to date representation.
  215. // Everything it knows is in a node.
  216.  
  217. enum node_flavor {  //state the derived type from a node
  218.    nf_base, nf_type, nf_def
  219.    };
  220.  
  221. class node {
  222. protected:
  223.    node();
  224.    virtual ~node();
  225. public:
  226.    node_flavor flavor;
  227.    virtual void print();
  228.    };
  229.  
  230. enum primary_t { type_void, type_char, type_int, type_long, type_float, 
  231.       type_double, type_ldouble, type_enum, type_class, type_union, 
  232.       type_pointer, type_reference, type_array, type_function };
  233.  
  234. class def_node_list;  //forward ref
  235.  
  236. class type_node : public node {
  237. public:
  238.    type_node* to_what;
  239.    type_node ();
  240.    ~type_node();
  241.    void print();
  242.    unsigned flags;
  243.    primary_t primary;
  244.    node* secondary() { return to_what; }
  245.    atom tag;
  246.    def_node_list* aggr;
  247.    void stuff_primary (int x, atom tagname);
  248.    bool isConst() { return flags&1; }
  249.    bool isVol() { return flags&2; }
  250.    bool isNear() { return flags&4; }
  251.    bool isFar() { return flags&8; }
  252.    bool isUnsigned() { return flags&16; }
  253.    };
  254.  
  255. class def_node : public node {
  256. public:
  257.    atom name;
  258.    int storage_class;
  259.    type_node* type;
  260.    void print();
  261.    def_node (atom n, int store, type_node* t);
  262.    };
  263.  
  264. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  265. /*     lists of nodes                       */
  266. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  267.  
  268. class node_list {
  269.    node** list;
  270.    int capacity;
  271.    int count;
  272. public:
  273.    node_list();
  274.    ~node_list() { delete list; }
  275.    node** access (int x);
  276.    int size() { return count; }
  277.    void add(node* n) { *access(count++) = n; }
  278.    };
  279.  
  280. #define create_list(TYPE) class TYPE##_node_list : public node_list { \
  281. public:\
  282. TYPE##_node*& operator[] (int x) { return *(TYPE##_node **)access(x); } }
  283.  
  284. create_list (type);
  285. create_list (def);
  286.  
  287.  
  288.  
  289. [LISTING THREE]
  290.  
  291. /*****************************************************
  292. File: ACTIONS.CPP    Copyright 1989 by John M. Dlugosz
  293.    the Actions called from the parser
  294. *****************************************************/
  295.  
  296. #include "usual.hpp"
  297. #include <stream.hpp>
  298. #include "atom.hpp"
  299. #include "node.hpp"
  300. #include "define.hpp"
  301.  
  302. // #define SHORT return 0    
  303. /* short out actions for testing parser only.
  304.    if something suddenly goes wrong, I can stub
  305.    out all the actions to make sure I'm not walking
  306.    on data somewhere.  */
  307. #define SHORT
  308.    // the normal case.
  309.  
  310. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  311.  
  312. static char last_token[81];
  313.  
  314. void get_last_token()
  315. {
  316. /* copy last token from scanner into a nul-terminated string */
  317. int len= 80;  //maximum sig. length
  318. extern char *T_beg, *T_end;  //from the scanner
  319. char* source= T_beg;
  320. char* dest= last_token;
  321.  
  322. //cout << (unsigned)T_beg << "  " << T_end;
  323. //for (int x= 0;  x < 5;  x++)   cout.put(T_beg[x]);
  324.  
  325. while (len-- && source < T_end) *dest++ = *source++;
  326. *dest= '\0';
  327. }
  328.  
  329. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  330.  
  331. /* in a declaration, a storage class is the first thing I get.  This starts
  332.    it off.  Then a ConstVol, a StoreType, and a second ConstVol.  The const
  333.    or volatile keyword may appear before or after the type, with equal
  334.    effect.  The two bits are ORed together for the final result.
  335.    After this, I get one or more calls to Declaration.
  336. */
  337.  
  338. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  339.  
  340. // the type I'm building
  341. struct working_type {
  342.    type_node* this_type;    //the tail
  343.    type_node* root_type;    //the head
  344.    int base_type;
  345.    atom tag_name; // if base_type has a name
  346.    atom name;  //The name of the thing being declared
  347.    int storage_class;
  348.    int const_vol;
  349.    working_type* next;
  350.    } MainType;
  351.  
  352. working_type* Tx= &MainType;
  353. /* this is accessed through a pointer because a declarator can be encounted
  354.    while parsing another declarator.  This lets me stack them.  */
  355.  
  356. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  357.  
  358. static int const_vol_stack[50];
  359. static int const_vol_stacktop= 0;
  360.  
  361. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  362.  
  363. int Declaration (int x,...)
  364. {
  365. /* values for x:  1- global or local def.
  366.                   2- parameters
  367.                   3- struct/union list
  368. */
  369. SHORT;
  370. /* This finishes it off.  A complete declaration has been found. */
  371. Tx->this_type->stuff_primary (Tx->base_type, Tx->tag_name);
  372. Tx->this_type->flags |= Tx->const_vol;
  373. // build the 'thing' from the type_node and the name.
  374. store_thing (Tx->root_type, Tx->name, Tx->storage_class, x);
  375. // Tx->root_type->print();
  376. // cout.put('\n');
  377. return 0;
  378. }
  379.  
  380. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  381.  
  382. int StoreBaseConstVol (int x,...)
  383. {
  384. SHORT;
  385. // the first two calls to ConstVol apply here.
  386. Tx->const_vol =  const_vol_stack[--const_vol_stacktop];
  387. Tx->const_vol |= const_vol_stack[--const_vol_stacktop];
  388. return 0;
  389. }
  390.  
  391. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  392.  
  393. int StoreType (int x,...)
  394. {
  395. SHORT;
  396. Tx->base_type= x;
  397. return 0;
  398. }
  399.  
  400. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  401.  
  402. int StoreTag (int x,...)
  403. {
  404. SHORT;
  405. /* called when a struct, union, or enum is parsed. The tag is the last
  406.    token read.  After this call, the StoreType call is made with 'union'
  407.    or whatever.  */
  408. get_last_token();
  409. Tx->tag_name= atoms[last_token];
  410. return 0;
  411. }
  412.  
  413. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  414.  
  415. int StoreStorage (int x,...)
  416. {
  417. SHORT;
  418. /* this is the first thing called */
  419. Tx->storage_class= x;
  420. return 0;
  421. }
  422.  
  423. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  424.  
  425. int Dname (int x,...)
  426. {
  427. SHORT;
  428. /* if x==1, the last token is the name of a thing being declared.  If
  429.    x==0, there is no name and this is an abstact declarator.  Either
  430.    way, build a type node and store the name.  This overwrites the type 
  431.    node, as it will be the first thing called.  */
  432.  
  433. if (x) {
  434.    get_last_token();
  435.    Tx->name= atoms[last_token];
  436.    }
  437. Tx->this_type= new type_node;
  438. Tx->root_type= Tx->this_type;
  439. return 0;
  440. }
  441.  
  442. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  443.  
  444. int TypeModifier (int x,...)
  445. {
  446. SHORT;
  447. /*  1 t()     2 t[]     3 *t     4 &t        */
  448.  
  449. switch (x) {
  450.    case 1:
  451.       Tx->this_type->primary= type_function;
  452.       // attach parameter list
  453.       Tx->this_type->aggr= completed_def_list;
  454.       break;
  455.    case 2:
  456.       Tx->this_type->primary= type_array;
  457.       // >> attach size
  458.       break;
  459.    case 3:
  460.       Tx->this_type->primary= type_pointer;
  461.       Tx->this_type->flags |= const_vol_stack[--const_vol_stacktop];
  462.       break;
  463.    case 4:
  464.       Tx->this_type->primary= type_reference;
  465.       Tx->this_type->flags |= const_vol_stack[--const_vol_stacktop];
  466.       break;
  467.    }
  468. Tx->this_type->to_what= new type_node;
  469. Tx->this_type= Tx->this_type->to_what;
  470.  
  471. return 0;
  472. }
  473.  
  474. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  475.  
  476. int ConstVol (int x,...)
  477. {
  478. SHORT;
  479. /*  1-const  2-volatile  3-both  */
  480. const_vol_stack[const_vol_stacktop++]= x;
  481. return 0;
  482. }
  483.  
  484. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  485.  
  486. int ReachType (int x,...)
  487. {
  488. SHORT;
  489. /* 0-default  1-near  2-far */
  490. return 0;
  491. }
  492.  
  493. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  494.  
  495. int NestedType (int x, ...)
  496. {
  497. SHORT;
  498. working_type* p;
  499. if (x) {  //start nesting
  500.    p= new working_type;
  501.    p->next= Tx;
  502.    Tx= p;
  503.    }
  504. else {  //restore old type
  505.    p= Tx;
  506.    Tx= Tx->next;
  507.    delete p;
  508.    }
  509. parameter_list (x);  //pass on to DEFINE module
  510. return 0;
  511. }
  512.  
  513. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  514. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  515. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  516.  
  517. int AllDoneNow (int x, ...)
  518. {
  519. SHORT;
  520. cout << "parser complete. \n";
  521. for (int loop= 0;  loop < global_stuff.size();  loop++) {
  522.    global_stuff[loop]->print();
  523.    cout.put ('\n');
  524.    }
  525. return 0;
  526. }
  527.  
  528.  
  529. [LISTING FOUR]
  530.  
  531. /*****************************************************
  532. File: ATOM.CPP       Copyright 1989 by John M. Dlugosz
  533.    store strings
  534. *****************************************************/
  535.  
  536. #include "usual.hpp"
  537. #include "atom.hpp"
  538.  
  539. extern "C" void* malloc (unsigned size);
  540. extern "C" void free (void*);
  541. extern "C" void* realloc (void*, unsigned);
  542.  
  543. atom_storage atoms(16);
  544.  
  545. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  546.  
  547. atom_storage::atom_storage (int size)
  548. {
  549. count= 0;
  550. capacity= size;
  551. list= (char**) malloc (size * sizeof(char*));
  552. }
  553.  
  554. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  555.  
  556. atom_storage::~atom_storage()
  557. {
  558. free (list);
  559. }
  560.  
  561. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  562.  
  563. extern "C" int strcmp(char*,char*);
  564. extern "C" char* strdup(char*);
  565.  
  566. atom atom_storage::operator[] (char* s)
  567. {
  568. for (int loop= 0;  loop < count;  loop++) {
  569.    if (!strcmp(s, list[loop])) return loop;  //found it
  570.    }
  571. if (count == capacity) {  // make it bigger
  572.    capacity += capacity/2;
  573.    list= (char**)realloc(list,capacity*sizeof(char*));
  574.    }
  575. list[count]= strdup(s);
  576. return count++;
  577. }
  578.  
  579.  
  580.  
  581.  
  582. [LISTING FIVE]
  583.  
  584.  
  585. typedef int atom;
  586.  
  587. class atom_storage {
  588.    char** list;
  589.    int count;
  590.    int capacity;
  591. public:
  592.    atom_storage(int size);
  593.    ~atom_storage();
  594.    char* operator[] (atom x) { return list[x]; }
  595.    atom operator[] (char*);
  596.    };
  597.  
  598. extern atom_storage atoms;
  599.  
  600.  
  601.  
  602. [LISTING SIX]
  603.  
  604. /*****************************************************
  605. File: DEFINE.CPP     Copyright 1989 by John M. Dlugosz
  606.    deal with definitions once they are parsed
  607. *****************************************************/
  608.  
  609. #include "usual.hpp"
  610. #include <stream.hpp>
  611. #include "atom.hpp"
  612. #include "node.hpp"
  613. #include "define.hpp"
  614.  
  615. bool local_level= FALSE;
  616.  
  617. def_node_list global_stuff;
  618. struct p_list_struct {
  619.    def_node_list* l;
  620.    p_list_struct* next;
  621.    };
  622. static p_list_struct *p_list;
  623. def_node_list* completed_def_list;
  624.  
  625. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  626.  
  627. void store_thing (type_node* t, atom name, int storage_class, int param)
  628. {
  629. /* 'param' is passed through from the grammar.  If 1, this is a declaration
  630.    for a local or global object.  If 2, this is part of a parameter list */
  631. def_node* n= new def_node (name, storage_class, t);
  632.  
  633. // file it away somewhere
  634. switch (param) {
  635.    case 1:
  636.       if (name == -1) {
  637.          // >> I need to get a standard error reporter
  638.          cout << "abstract declarator ignored\n";
  639.          }
  640.       global_stuff.add (n);
  641.       break;
  642.    case 2:
  643.       // >> check it over
  644.       p_list->l->add(n);
  645.       break;
  646.    }
  647. }
  648.  
  649. /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
  650.  
  651. void parameter_list (int x)
  652. {
  653. p_list_struct* p;
  654. if (x) {
  655.    p= new p_list_struct;
  656.    p->next= p_list;
  657.    p->l= new def_node_list;
  658.    p_list= p;
  659.    }
  660. else {
  661.    p= p_list;
  662.    p_list= p_list->next;
  663.    completed_def_list= p->l;
  664.    delete p;
  665.    }
  666. }
  667.  
  668.  
  669.