home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / DEMOS / DEMO7.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-15  |  4.2 KB  |  180 lines
  1. #include "demo7.h"
  2.  
  3. /*
  4.  
  5.     First we make some simple DCG-like rules and a small lexicon and store
  6.     this information in two arrays, rules[] and lexicon[],  using function
  7.     init().
  8. */
  9.  
  10. ITEM_ *init(int number, ITEM_ start, ...)
  11. {
  12.     ITEM_
  13.         *tmp;
  14.  
  15.     if (!(tmp = (ITEM_ *) malloc(number * sizeof(ITEM_))))
  16.     {
  17.         puts("Error: out of memory data");
  18.         exit(0);
  19.     }
  20.     memcpy(tmp, &start, number * sizeof(ITEM_));
  21.     return(tmp);
  22. }
  23.  
  24. RULE_
  25.     rules[] = {
  26.                 {2, S, init(2, NP, VP)},
  27.                 {1, NP, init(1, SNP)},
  28.                 {2, NP, init(2, DET, N)},
  29.                 {1, VP, init(1, IV)},
  30.                 {2, VP, init(2, TV, NP)},
  31.                 {3, VP, init(3, SV, CN, S)},
  32.                 {VOID, VOID, NULL}
  33.               };
  34.  
  35. LEX_
  36.     lexicon[] = {
  37.                     {TV, "kills"},
  38.                     {SV, "thinks"},
  39.                     {IV, "sleeps"},
  40.                     {SNP, "john"},
  41.                     {N, "man"},
  42.                     {DET, "the"},
  43.                     {CN, "that"},
  44.                     {VOID, NULL}
  45.                 };
  46.  
  47. char        /* to print syntactic categories */
  48.     *table[] = {"void" , "s", "vp", "iv", "tv", "sv", "np", "snp",
  49.                 "n", "det", "cn"};
  50.  
  51.  
  52.  
  53. PARSE_::PARSE_(char **s, ELEMENT_ *start)
  54.     : AODEPTH_TREE_(start, 0)
  55. {
  56.     string = s;
  57.     index = 0;
  58. }
  59.  
  60.  
  61. ELEMENT_::ELEMENT_(ITEM_ it)
  62. {
  63.     item = it;
  64. }
  65.  
  66.  
  67. void ELEMENT_::display() const
  68. {
  69.    printf("%s\n", table[item]);
  70. }
  71.  
  72.  
  73. /*                    EQUAL
  74.  
  75.     We don't really need this function in this class because we are
  76.     performing a tree search, so we can be sure none of the nodes will
  77.     be generated twice; also, nodes won't be compared against a goal
  78.     node. Still, we must define this function because it's pure
  79.     virtual in NODE_.
  80.  
  81. */
  82.  
  83. int ELEMENT_::equal(const VOBJECT_ &) const
  84. {
  85.     return(0);
  86. }
  87.  
  88.  
  89. ITEM_ ELEMENT_::get_item() const
  90. {
  91.     return(item);
  92. }
  93.  
  94.  
  95. /*                    EXPAND
  96.  
  97.     Expanding a node means in this problem that we must find the syntactic
  98.     category that the node represents in the database of rules. Since a rule
  99.     may rewrite the syntactic category to more than one new category we may
  100.     have to, and most of the time will, produce an AND-node.
  101.  
  102. */
  103.  
  104. NODE_ *ELEMENT_::expand(int ) const
  105. {
  106.     AONODE_
  107.         *tmp = NULL,
  108.         *start = NULL;
  109.     int
  110.         i,
  111.         d;
  112.  
  113.     for (i = 0; rules[i].num != VOID; i++)  // find item in rules database
  114.     {
  115.         if (rules[i].head == item)
  116.         {
  117.             if (rules[i].num == 1)          // create OR node
  118.                 tmp = new ELEMENT_(rules[i].tail[0]);
  119.             else
  120.             {
  121.                 tmp = new ANDNODE_();       // create AND node
  122. /* remember that our terminology of AND and OR nodes differs
  123.    from normal usage  */
  124.                 for (d = 0; d < rules[i].num; d++)
  125.                     ((ANDNODE_ *)tmp)->addsucc(new ELEMENT_(rules[i].tail[d]));
  126.             }
  127.  
  128.             tmp->setnext(start);
  129.             start = tmp;
  130.         }
  131.     }
  132.     return(start);
  133. }
  134.  
  135.  
  136. /*                  IS_TERMINAL
  137.  
  138.     To determine if a node may be considered terminal we check if the
  139.     syntactic item to be parsed, which must of course be terminal itself,
  140.     matches the word (pointed to by index) in the input string. Therefore,
  141.     we first locate the syntactic category in the lexicon (if we can't find it
  142.     there this means the syntactic category isn't terminal) and compare the
  143.     word that accompanies it with the word in the input string.
  144.  
  145. */
  146.  
  147. int PARSE_::is_terminal(const AONODE_ &node)
  148. {
  149.     int
  150.         i;
  151.  
  152.     if (!string[index])
  153.     return(0);
  154.  
  155.     for (i = 0; lexicon[i].head != VOID; i++)
  156.         if (lexicon[i].head == ((ELEMENT_ &)node).get_item()
  157.                && !strcmp(lexicon[i].tail, string[index]))
  158.         {
  159.             index++;
  160.             return(1);
  161.         }
  162.  
  163.     return(0);
  164. }
  165.  
  166.  
  167. int main(int argc, char *argv[])
  168. {
  169.     if (argc == 1)
  170.     {
  171.         printf("Usage: %s <string>\n", argv[0]);
  172.         exit(0);
  173.     }
  174.     PARSE_
  175.         sentence(++argv, new ELEMENT_(S));
  176.  
  177.     sentence.generate();
  178.     return(1);
  179. }
  180.