home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / DEMOS / DEMO7.H < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-12  |  2.0 KB  |  107 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "tree.h"
  5.  
  6.  
  7. /*                     DEMO7
  8.  
  9.     In this demo we show how the AND/OR search algorithms can be used
  10.     to implement a simple top-down parser.
  11.  
  12. */
  13.  
  14.  
  15.  
  16. /*                     ITEM_, RULE_, LEX_
  17.  
  18.     First, we declare an enum ITEM_ to represent the syntactic categories.
  19.     Next, we define a struct to represent DCG rules and a struct to represent
  20.     words in the lexicon.
  21.  
  22. */
  23.  
  24. enum ITEM_
  25. {
  26.     VOID,
  27.     S,
  28.     VP,
  29.     IV,
  30.     TV,
  31.     SV,
  32.     NP,
  33.     SNP,
  34.     N,
  35.     DET,
  36.     CN,
  37. };
  38.  
  39. typedef struct RULE_
  40. {
  41.     int
  42.         num;
  43.     ITEM_
  44.         head,
  45.         *tail;
  46. } RULE_;
  47.  
  48. typedef struct LEX_
  49. {
  50.     ITEM_
  51.         head;
  52.     char
  53.         *tail;
  54. } LEX_;
  55.  
  56.  
  57.  
  58. /*               ELEMENT_
  59.  
  60.     Class element is a representation of the nodes generated during the
  61.     search, it serves as an abstraction of the syntactic categories.
  62.     Note that we implement expand() instead of do_operator() because
  63.     there isn't a fixed number of operators for this problem (every DCG
  64.     rule may rewrite a syntactic category to one or more new syntactic
  65.     categories).
  66.  
  67. */
  68.  
  69. class ELEMENT_ : public ORNODE_
  70. {
  71.     public:
  72.         ELEMENT_(ITEM_);
  73.         ITEM_ get_item() const;
  74.  
  75. // implementation of virtual functions
  76.         int equal(const VOBJECT_ &) const;
  77.         void display() const;
  78.         NODE_ *expand(int) const;    // we use expand() instead of do_operator
  79.     private:
  80.         ITEM_
  81.             item;    // syntactic category
  82. };
  83.  
  84.  
  85.  
  86. /*            PARSE_
  87.  
  88.     Because we want to perform a depth-first search of and AND/OR tree
  89.     we define a class PARSE_, derived from AODEPTH_TREE_. As a consequence
  90.     we must implement function is_terminal().
  91.  
  92. */
  93.  
  94. class PARSE_ : public AODEPTH_TREE_
  95. {
  96.     public:
  97.         PARSE_(char **, ELEMENT_ *);
  98.         int is_terminal(const AONODE_ &);
  99.     private:
  100.         char
  101.             **string;       // text string to be passed
  102.         int
  103.             index;          // index to this string
  104. };
  105.  
  106.  
  107.