"cr88192"  wrote:   
   >  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.   
   >   
      
      
   Thank you for your reply. Can I understand your opinion as "parsing is   
   much easier than CS, because CS may include more relations, e.g.   
   logical, temporal relations, to be satisfied" ?   
      
   However, to solve a CS problem, I think one of the most important   
   thing is the efficiency problem, due to the possible combination   
   explosion. While, for parsing, due to the "dead" production where the   
   constraint is just checking one token by one, efficient parsing   
   algorithm can be performed.   
      
   So, parsing can be seen as a subset of CS. Production is a strong   
   constraint.   
      
   How to improve efficiency in CS problem, can somebody give me some   
   general methods/ideas?   
      
   [ 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)