From: cr88192@hotmail.com   
      
    wrote in message   
   news:47c94aae$1@news.unimelb.edu.au...   
   > Hello, I am a new hand. I want to know:   
   >   
   > What is the difference between Constraint Satisfaction and Parsing?   
   >   
   > Parsing is just a sub-set of CS?   
   >   
      
   unless you are talking of very different things than I am thinking:   
   they are almost completely different.   
      
   so, to satisfy constraints, you satisfy constraints. this is essentially a   
   "logic" problem...   
   take relations, and by some means, try to work out the values...   
      
   in most constraint solvers I have dealt with (the weaker "real-time"   
   variety), the usual approach is for the constraints to be essentially   
   directed (they are more like dynamic/interconnected assignments than actual   
   mathematical relations), so that putting in values for some input variables,   
   automatically provides values for many of the output variables (and   
   potentially somewhat limits the possible values of some other variables).   
      
      
   now, to parse something, you decompose it into tokens and build a parse   
   tree.   
   this is usually a recursive problem (in recursive-descent parsers at least,   
   which is about all I really use). I can't say much for more elaborate algos,   
   such as LALR, but in simple cases, the parsing process is a dead simple task   
   of checking tokens, recursing, and building trees...   
      
   simple example:   
      
   leaf-expr:   
       read token;   
       is a special keyword? parse and return for keyword;   
       is opening paren? parse and return compound expression;   
       is a name? return a 'name' node;   
       is numeric? return a numeric node.   
      
   unary-expr:   
       examine token;   
       is unary op?   
           read token;   
           call unary-expr;   
           build unary node from token and expr;   
           return new node.   
       parse and return leaf-expr.   
      
   binary-expr:   
       parse unary expr (l);   
       examine token (t);   
       while t is binary op   
           read token (t);   
           parse unary-expr (r);   
           build new expr (l) using t, l, and r;   
       return l.   
      
   ....   
      
      
   with a little fudging (and the addition of context dependencies) one finds   
   this basic approach scales even to the likes of parsing languages like C and   
   C++...   
      
      
   > Thanks.   
   >   
      
   [ comp.ai is moderated ... your article may take a while to appear. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)