parser.c

人智算法基本程序

/****************************************************************/
/*    NAME: Konstantinos Roussos                                */
/*    ACCT: knr                                                 */
/*    FILE: Parser2.C                                           */
/*    ASGN: Final                                               */
/*    DATE: Wed Jun  8 22:46:37 1994                            */
/****************************************************************/

/*
 * Copyright 1994, Brown University, Providence, RI
 * See end of file for full copyright information
 */

#include "Parser.H"
#include "LogicNode.H"
#include "Bind.H"
#include <Queue.H>
#include <stdlib.h>
#include <iostream.h>


/****************************************************************/
/*                                                              */
/* Function Name: parse                                         */
/* Parameters:                                                  */
/*   char* string: the string being parsed                      */
/*   int& current_pos: where you are in the string being        */
/*          parsed                                              */
/* Returns: a parsed LogicNode                                  */
/* Effects:                                                     */
/*  This function in effect performs the operation of the reader*/
/* in Lisp. It takes as input a lisp sentence and the creates   */
/* a parse tree. This parse tree is then passed to Bind         */
/* to be evaluated. The parse tree generated by this function   */
/* has three types of nodes                                     */
/*   - a group : which is a list e.g. ( ... )                   */
/*   - a constant : which is a constant   JOE                   */
/*   - a variable : e.g. ?x                                     */
/* The constant and variable are terminals, the group           */
/* can further be evaluated.                                    */
/****************************************************************/



LogicNode* parse(char* string, int& current_pos)
{
   int start = current_pos;              
   LogicNode* var;
   if(string[current_pos] == '(') 
      {
         current_pos++;
         var = new LogicNode(LogicNode::GROUP);
         while(string[current_pos] != ')') 
           {
              if(string[current_pos] == '?')
                 {              // is a variable
                    current_pos++;
                    LogicNode* child = new LogicNode(string[current_pos]);
                    current_pos++;
                    var->insert(child);
                 }
              else if(string[current_pos] == '(') 
                 {              // is a new group 
                    // new sub node in the string
                    // create it and insert it into the tree
                    var->insert(parse(string, current_pos));
                 }
              else if(string[current_pos] == ' ')
                 {
                    // skip white space
                    current_pos++;
                 }
              else 
                 {
                    // Since we go to here it must be a constant
                    // so keep reading the constant in until
                    // you reach white space or ')'
                    int start = current_pos;
                    while((string[current_pos] != ' ') &&
                          (string[current_pos] != ')'))
                       {
                          current_pos++;
                       }
                    // create the new constant
                    LogicNode* child = new LogicNode(&string[start],start,current_pos-1);
                    // add it to the group node
                    var->insert(child);
                    
                 }
           };
        
        current_pos++;
        // set the group symbol to everything between the parens
        var->setSymbol(&string[start], current_pos-start);
        return var;
     }
}                  

/****************************************************************/
/*                                                              */
/* Function Name: unify                                         */
/* Parameters:                                                  */
/*  LogicNode* a,*b, the two sentences which we are trying      */
/*                   to determine if they bind                  */
/*  Queue<Binding,BindCompare>* the bindings made so far        */
/* Returns:<none>                                               */
/* Effects:                                                     */
/****************************************************************/

            
void unify(LogicNode* a, LogicNode* b, Queue<Binding, BindCompare>* binding)
{
   switch(a->type())            // switch on type
      {
      case LogicNode::CONSTANT:
      switch(b->type())
         {
      case LogicNode::CONSTANT:
         if( a->symbol() == b->symbol() ) 
            {
               return;
            }
         else 
            {
               err(a, b);
            };
      case LogicNode::GROUP:  
         err(a, b);
         break;
      case LogicNode::VARIABLE:
         bind(b,a,binding);
         break;
      };
      break;
   case LogicNode::GROUP:
      switch(b->type()) 
         {
         case LogicNode::CONSTANT:
            err(a, b);
         case LogicNode::GROUP: {  // LBH 2/96
            int nexta = a->nextChild(), nextb = b->nextChild();
            while (nexta && nextb) {
              unify(a->child(), b->child(), binding);
              nexta = a->nextChild();
              nextb = b->nextChild();
              }
            if (nexta) while (a->nextChild());
            if (nextb) while (b->nextChild());
            a->unMarkChildren(); b->unMarkChildren();
            return;
            }
         case LogicNode::VARIABLE:
            bind(b,a,binding); 
         }
      break;
   case LogicNode::VARIABLE:
      switch(b->type())
         {
         case LogicNode::VARIABLE:
            bind(a,b,binding);
            break;
      case LogicNode::CONSTANT:
            bind(a,b,binding);
            break;
         case LogicNode::GROUP:
            bind(a,b,binding);
            break;
         }
   }
   return ;
}

/****************************************************************/
/*                                                              */
/* Function Name: bind                                          */
/* Parameters:                                                  */
/* Returns:                                                     */
/* Effects:                                                     */
/*  Attempts to bind two LogicNodes.                            */
/*  LogicNode*&a must be a variable.                            */
/*  LogicNode*&b may or may not be a variable                   */
/* a binds to b if                                              */
/* (1) a is unbound                                             */
/* (2) a is not in b                                            */
/* To check for (1) search through the bindings.                */
/* If a is bound, replace a with the thing a is bound to and    */
/* send the sentence to the unify function                      */
/* To check for (2) search b for a (like the occursp function   */
/*                                   in the text book)          */
/* There is one special case which must be tested for:          */
/*   b is a variable and is already bound, in which case,       */
/*   a has to test for binding against what b is bound to and   */
/*   not b.                                                     */
/*                                                              */
/****************************************************************/

      
void bind(LogicNode*& a, LogicNode*& b, Queue<Binding, BindCompare>* bindings)
{
  
   // is a bound?
   Binding* binding = new Binding(a,0);
   if(bindings->search(binding) == 0) 
      { // no so check wether b is bound
         delete binding;
         binding = new Binding(b,0);
         if((b->type() == LogicNode::VARIABLE
             && (bindings->search(binding) == 0)) || (b->type() != LogicNode::VARIABLE))
            { // b unbound 
               delete binding;
               if (b->search(a) ) // is a part b, i.e. does it occur in a?
                  {
                     cerr << "could not unify " << endl;
                     exit(0);
                  }
               binding = new Binding(a,b); // no, so create the binding
               bindings->insert(binding);  // add it to the bindings
               a = b; // a now points to b
               return;
            }
         else
            { // b bound
               b = binding->substitute(); // since b bound, create a new
                                          // sentence with the thing that
                                          // b is bound to, and try to
                                          // unify that.
               unify(a,b,bindings);
               return;
            }
      }
   else 
      { // a bound
         a = binding->substitute(); // since a bound create a new sentence
                                    // with the thing that a is bound to
                                    // and try to unify the new sentece
         unify(a,b,bindings);
         return;
      }
}

/* This is a small utility function for printing out errors     */
/* and exiting the function calling.                            */
/*                                                              */
void err(LogicNode* a, LogicNode* b) // print out a generic error statement
{
   cerr << "could not unify " << a << " and  " << b;
   exit(0);
}





/*
 * Copyright 1994, Brown University, Providence, RI
 *
 * Permission to use and modify this software and its documentation for
 * any purpose other than its incorporation into a commercial product is
 * hereby granted without fee.  Permission to copy and distribute this
 * software and its documentation only for non-commercial use is also
 * granted without fee, provided, however, that the above copyright notice
 * appear in all copies, that both that copyright notice and this permission
 * notice appear in supporting documentation, that the name of Brown
 * University not be used in advertising or publicity pertaining to
 * distribution of the software without specific, written prior permission,
 * and that the person doing the distribution notify Brown University of
 * such distributions outside of his or her organization. Brown University
 * makes no representations about the suitability of this software for
 * any purpose.  It is provided "as is" without express or implied warranty.
 * Brown University requests notification of any modifications to this
 * software or its documentation.
 *
 * Send the following redistribution information:
 *
 *	Name:
 *	Organization:
 *	Address (postal and/or electronic):
 *
 * To:
 *	Software Librarian
 *	Computer Science Department, Box 1910
 *	Brown University
 *	Providence, RI 02912
 *
 *		or
 *
 *	[e-mail]
 *
 * We will acknowledge all electronic notifications.
 */