[ale] [OT] Writing a parser

[Danny Cox]

Krum,

On Thu, 2004-03-18 at 04:18, Kevin Krumwiede wrote:
> 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?

	At the risk of sounding like a broken record ("record"? what's that?),
I'll once again recommend Kerninghan & Pike's book, "The UNIX
Programming Environment".  Their big project, a "high order calculator"
takes you from a rudimentary calcaulator up through one which "compiles"
the code into a "machine" and then executes it.  Along the way, you
learn about yacc (the prececessor of bison), and a brief foray into lex,
but at the time, you could still write faster lexical analyzers
yourself.  I wouldn't try that now against flex, though.  Still, the
book covers many (most) aspects of working with grammers, parsers, and
lexers.

	I'll also say this: when speaking of this class of parsers, one often
reads of a "stack".  When running and given a new token, the engine will
either "shift" (push) onto the stack, or "reduce" by some rule (pop N
matching tokens).  There are really two stacks: one for the symbols
(tokens), and one for the value of those tokens.  This was a major break
through in my head, and I've never actually seen it stated explicitly
anywhere else.  As an example, a token might be "INTEGER", but the value
is "0".

	Good luck!

-- 
kernel, n.: A part of an operating system that preserves the
medieval traditions of sorcery and black art.

Danny