[ale] [OT] Writing a parser

[Joe Knapka]

Here's a concrete example of the difference between a lexer
and a parser. Given the string:

  The dog chased the cat.

A lexer produces a stream consisting of the syntactically-significant
tokens in the string:

"The", "dog", "chased", "the", "cat"

A parser takes the token stream and discovers its syntactic
structure:

               S
               |
      NP-------+------VP
      |               |
DET---+---N           |
 |        |      V----+--------NP
The      dog     |             |
               chased     DET--+---N
                           |       |
                          the     cat

Often something as simple as Python's string.split() method will work
fine as a lexer, and if the data you're looking at is formatted in a
tabular way, a lexer is all you need.  You only need a parser if the
data has nontrivial structural relationships between tokens.  In
general, parsing is NP-complete, but it's extremely unusual (when
dealing with machine-generated data) to encounter situations that
involve the icky parts of that complexity domain.

Cheers,

-- Joe

Kevin Krumwiede <kjkrum at comcast.net> writes:

> I am working on a program to capture data from a MUD (actually, TW2002).
>  I've looked at the source for a couple parsers, including one made
> specifically for that game, but because they are generated code I'm
> having a lot of difficulty understanding how they work.  
> 
> The gist of what I do understand is this (and somebody please tell me if
> I'm wrong): parsers generally take a string of text and return a numeric
> code signifying what pattern (if any) the text matches.  A program can
> then use that code to decide how to process the text.  I assume that
> sophisticated parsers take into account the preceding context of the
> text when evaluating its pattern.
> 
> I am completely lost when it comes to the input languages of parser
> generators.  Anyone know of a good tutorial?
> 
> Thanks,
> Krum
> _______________________________________________
> Ale mailing list
> Ale at ale.org
> http://www.ale.org/mailman/listinfo/ale
> 
> 

-- 
Resist the feed.
--
If you really want to get my attention, send mail to
jknapka .at. kneuro .dot. net.