# Preface #

OK, so the muse has taken me. I want to write something. I realise 
nobody here really cares, but if you're bored maybe you could take a 
read and tell me what you think.

(Yes, I *know* Haskell sucks and only a total retard would use such a 
stupid and irrelevant language. I think we've covered that one. I'm not 
asking whether you think Haskell is cool, I'm asking what you think of 
my powers of exposition. Does what I've written *make sense*? That's the 
question I'm interested it.)


# Introduction #

There are many common and well-known idioms in OO languages. For 
example, look at any large project and you'll probably find that 
somewhere, somebody has written a class which is nearly complete except 
for a few abstract methods, which all other functionallity is defined in 
terms of. Then they wrote several concrete subclasses that work purely 
by implementing these abstract methods in various ways.

It's such a common technique that it hardly needs describing. Everybody 
who's ever seen OOP will know what this is about.

Haskell is a much rarer language. It has its own idioms, most of which 
are far less well-known. One very widely used technique is the 
construction of "combinator libraries". Such a library consists of a 
small set of primitive "things", and a set of combinators for combining 
simple things into more complex things. Usually there will also be a 
collection of ready-made things which are either very commonly needed or 
non-obvious in construction.

An absolutely classic application of this technique is the contruction 
of text parsers. I'd like to show off the technique by walking you 
through a high-level description of Haskell's "Parsec" library. (There 
will not be any actual Haskell syntax; this is just a description of 
concepts.)


# Parsec #

## Parsing stuff ##

Suppose you want to parse a text string to extract some kind of data 
from it. If you're working in something like Java, right now you're 
probably thinking something along the lines of designing some kind of 
"paser object" that has an "input buffer" and various methods for 
mutating the paser state. Maybe it's based on some sort of finite state 
machine?...

Parsec takes a completely different approach - and that is the subject 
of this text.

The Parsec library defines a "parser" data type. What this actually is 
or how it works doesn't matter; a Parsec client sees only the type name. 
Parsec also provides a Run() function which takes a parser and some text 
and "runs" the paser over it.

There are a few things to explain about parsers. First of all, when a 
parser is run, it can consume zero or more characters. That is, a parser 
can terminate immediately without consuming any input at all, or a 
single parser can swallow millions of characters.

Second, when you run a parser, it can "succeed" or "fail". When a parser 
succeeds, it returns an item of data. This can be of any data type 
(e.g., it could be an integer, a string, or a list of binary trees). 
When a parser "fails", this is not a fatal program error, it just means 
that the parser returns an internal Parsec error description data 
structure. This will become clearer later.

The Run() function returns a structure indicating whether parsing 
succeeded or failed. If successful, it returns whatever the parser 
itself returned. If failed, it returns an opaque error object. There is 
a function to conviniently transform this into human-readable text, but 
you can also programmatically query it (e.g., to get the line number of 
the error so you can hilight it on screen or something).


## The parsers ##

So, that's what a parser "is", in Parsec's terminology. Now, what 
parsers does Parsec actually implement? Well, it implements the following:

- P_Fail(msg) is a parser that always fails immediately, returning "msg" 
as the error message.
- P_Succeed(x) is a parser that always succeeds immediately (i.e., 
consuming 0 characters of input). It always returns the same value, "x".
- P_Any() is a parser that reads 1 character of input and returns that 
character. (It fails with a descriptive message if EOF.)
- P_Char(x) will read 1 character of input and return that character *if 
and only if* that character happens to be "x". Otherwise it fails with 
an error like "unexpected character 'J'; expected 'F'".

(The names are made-up, but Parsec really does have all of these.)

As you can see, these parsers are not so much "simple" as "trivial". 
Their internal implementation is slightly more complex than it would 
immediately seem, but even so, each one is only a few lines of Haskell.

So what can we *do* using these parsers? Well, not a lot, really. To do 
anything useful, we need some combinators...


## The Chain() combinator ##

The first combinator we're going to look at is something that I'm going 
to call Chain(). Consider, for example,

   parserX = Chain(parser1, parser2);

So Chain() takes two parsers and returns a parser (much like "+" takes 
two numbers and returns a number). But what does this new parser *do* 
when you run it?

- First, it runs parser1.
- If parser1 succeeds, its result is thrown away, and parser2 is run.
- If parser2 succeeds, its result is returned as the overall result of 
parserX.

In other words, it runs the first parser and then the second parser. But 
what if one or other parser fails?

- If parser1 fails, parser2 is not run at all, and parserX fails overall 
(with the same error message as parser1).
- If parser1 succeeds but parser2 fails, parserX fails overall (with the 
same error message as parser2).

It should be clear at this point that Chain() is associative - i.e., that

   parserX = Chain(Chain(x, y), z);
   parserY = Chain(x, Chain(y, z));

are two equivilent parsers. It should also be clear that Chain() 
therefore allows us to take an arbitrary number of parsers and "chain 
them together in sequence" to build one big parser that will run the 
component parsers one after another. And, finally, the first time any 
parser fails, all of the following parsers are automatically skipped and 
the overall parser fails. (A bit like throwing an exception - except 
that this is a library feature, not a hard-wired language construct.)

Now, writing Chain(Chain(Chain(...))) gets tedious quickly, so from now 
on I'm going to use a simple shorthand. Instead of "Chain(x, y)", I'm 
going to just write "x >> y". Just remember that it means "execute x and 
then execute y" (with a few additional details, as per above).

Using this new Chain() / ">>" combinator, I can write

   P_Char('H') >> P_Char('E') >> P_Char('L') >> P_Char('P');

which represents a parser which succeeds if the input begins "HELP", and 
fails otherwise. (Note that this includes checking for EOF.) As it 
stands, however, when this parser succeeds it returns 'P', which isn't 
fantastically useful. However, consider the following trick:

   P_Char('H') >> P_Char('E') >> P_Char('L') >> P_Char('P') >> 
P_Succeed("HELP");

Recall that P_Succeed() always succeeds and returns the specified value. 
However, >> will only execute this if all the preceeding parsers 
succeed. In other words, this parser does exactly the same thing as the 
previous one, except that it returns "HELP" instead of just 'P' as its 
result.

It turns out that parsers like the one above are extremely common, so 
Parsec provides us with a shortcut for writing them:

   function P_String(string)
   {
     out = P_Char(string[0]);

     for (int i=1; i < string.size(); i++)
     out = Chain(out, P_Char(string[i]));

     return Chain(out, P_Succeed(string));
   }

Now we can just say P_String("HELP") to generate the above parser. That 
should save us some typing!

So, we now have a parser that can read an arbitrary string, checking for 
EOF at each stage, and output readable error messages. (E.g., if you do 
P_String("HELP") and give it "HEAD", you get "error on line 1, column 3: 
unexpected character 'A'; expected 'L'".)

But this still isn't terribly exciting; a simple string comparison would 
do the same job!


## The Fork() combinator ##

The next combinator is called Fork(). It also takes a pair of parsers 
and returns a parser. However, just like "+" and "-" return different 
numbers, this combinator returns a slightly different parser:

   parserX = Chain(parser1, parser2);
   parserY = Fork(parser1, parser2);

As you know, parserX will run parser1 and then run parser2 only if 
parser1 succeeds. However, parserY runs parser2 only if parser1 *fails*. 
So Chain() means "do this and then to that", whereas Fork() means "do 
this or else do that". Where Chain() combines parsers into a sequential 
chain, Fork() combines parsers into a list of alternatives. For example:

   bool_parser = Fork(P_String("YES"), P_String("NO"));

This parser accepts either the word "YES" *or* the word "NO", and 
returns the word read. (If the input is anything else, it fails.)

So you can now see that when a parser "fails", this is a normal and 
ordinary part of how complex parsers work internally. "Let's parse this 
as an integer. Oh, that failed. OK, let's parse it as a variable. Oh, 
that failed too. OK, so let's parse it as a string literal..."

Notice that if *both* parsers fail, the overall parser fails, but the 
error messages are *merged*. (This is why Parsec errors are intricate 
data structures rather than simple text messages.) For example, if 
Fork(P_Char('X'), P_Char('Y')) were to fail, it might say

   Unexpected character 'J'; expecting 'X' or 'Y'.

The Parsec client gets this functionallity automatically as a 
consequence of merely using Fork(). This makes for easy automatic error 
handling.

Again, Fork() is associative like Chain() is:

   Fork(Fork(x, y), z) === Fork(x, Fork(y, z))

And again, I'm going to write "x <|> y" instead of "Fork(x, y)" from now on.

Using this notation, I can write

   colour_parser =
     P_String("RED")
     <|>
     P_String("GREEN")
     <|>
     P_String("Blue");

This accepts any of the given words, or it fails (with a message like 
"expecting 'RED' or 'GREEN' or 'BLUE'"; the P_String() shortcut 
prettifies the error messages slightly).

By using Chain() and Fork() together, I can define parsers such as

   expression_parser =
     P_Char('X')
     <|>
     (P_Char('[') >> expression_parser >> P_Char(']'));

This parser will accept any of the following strings:

   X
   [X]
   [[[X]]]
   [[[[[[[[X]]]]]]]]

So, basically, an "X" surrounded by any number of square brackets - but 
the open and closing brackets *must* match up! (And if they don't, 
you'll get a helpful error message.) This is slightly less trivial than 
the parsers we've seen so far, but still hardly earth-shattering.


## Optional parsing ##

Take a look at the following parser:

   P_Char('X') <|> P_Succeed('?')

If the next character is an "X", the first parser succeeds and returns 
an "X". However, if it fails, Fork() / "<|>" will run the second parser, 
which doesn't even *look* at the input, it just returns "?".

This turns out to be quite common, so Parsec provides a shortcut:

   function P_Optional(parser, default)
   {
     return Fork(parser, P_Suceed(default));
   }

Using this, I can define the following:

   bracket_parser =
     P_Char('[') >> expression_parser >> P_Char(']');

   expression_parser =
     (P_Char('X') <|> bracket_parser) >>
     P_Optional(expression_parser, "");

This is almost the same as the previous expression parser, except for 
the P_Optional() part. But that part means that now all of the following 
strings will be accepted:

   X
   XXX
   X[X]X
   [[[X[X]X]]]
   [[[X]]]X[[[[X]]]]
   [X[X[[X]]X]X]X

In other words, *any expression* composed of X's and balanced square 
brackets.

This, then, is something that a trivial string compare could not do. 
(Although it wouldn't be hard to manually implement such a parser.)


## Multiple parsing ##

Another thing we could very well want to do is parse multiple copies of 
something. (E.g., a "number" consists of multiple "digits".) This is 
also extremely common, so Parsec provides a shortcut:

   function P_Many1(parser1)
   {
     return (parser1 >> P_Optional(P_Many(parser1), []));
   }

This parses one of something, and then optionally parses some more of 
them by recursively calling itself. This lets you parse >= 1 of 
something; another Parsec shortcut allows >= 0 of something. (Beware of 
infinite loops! This parser must be used cautiously.) There is also a 
variant for parsing exactly N of something.

Another common requirement is to parse a sequence of things with 
seperators/terminators, and Parsec provides shortcuts for those too.


## The SuperChain() combinator ##

So far, most of our parsers don't "return" any interesting data. They 
succeed for some inputs and fail for others, but they don't return much 
data to the caller. (Typically just the last character of input or some 
such.) How about we remedy that?

Consider the following parser:

   parser1 >> parser2

Of course, this is really

   Chain(parser1, parser2)

And I already told you that Chain() will execute the first parser, 
*throw the result away* and then execute the second parser. Well suppose 
we'd actually like a parser that returns *both* results. How do we do that?

Well, it's impossible using Chain(). But there is another combinator 
called SuperChain() that works in a slightly different way:

   SuperChain( <parser> , <function> )

It first runs the parser. If that fails, the whole thing fails, as 
before. But assuming the parser succeeds, SuperChain() takes the 
parser's result and passes it to the function. The function is required 
to return another parser, which SuperChain() then runs.

This has two effects. The first effect is that the function can look at 
the token (or whatever) just read, and perform some completely arbitrary 
algorithm to decide what to do next. It then returns the parser it would 
like to be run next. This allows the implementation of 
"context-sensitive grammers".

For example, in the TeX language, usually commands start with "\". 
However, this is configurable. It can be changed half way through a 
file! (The standard "\verb" command actually does this.) But using 
Parsec, you can write a parser which will be able to cope if the 
character is changed; just write a function that returns a different 
parser! [Actually this is a simplification, but you get the flavour.]

The other thing it allows is a solution to our problem above: we want to 
run two parsers and return both of their results. This can be solved in 
the following way:

   parserX = SuperChain(parser1, foo);

   function foo(x)
   {
     function bar(y)
     {
       return P_Succeed([x, y]);
     }

     return SuperChain(parser2, bar);
   }

When parserX is run, it will run parser1 and pass its result to foo(). 
foo() then returns a SuperChain() parser which runs parser2 and passes 
its result to bar(). Notice that bar() is a nested function within 
foo(), and hence can refer to "x", which is foo's function argument. The 
bar() function simply returns a P_Succeed parser which returns the data 
we want.

In other words, parserX runs parser1 and then parser2 and returns both 
of their results. (Not forgetting that either of these parsers might 
fail, producing an error description, and the flow control is invidibly 
handled by SuperChain() in the same way as Chain() does.)

That seems like an aweful lot of work just to perform such a trivial 
task! Fortunately, since this kind of thing is very common in Haskell, 
it has some special syntax sugar for making it very easy to write. I 
won't use the exact syntax, but suffice it to say the above can be 
written to look something like

   parserX =
     begin
       parser1 --> x;
       parser2 --> y;
       P_Succeed([x, y]);
     end;

which is obviously a lot clearer. Basically

   ...
   parser1;
   parser2;
   parser3;
   ...

becomes calls to Chain(), while

   ...
   parser1 --> x;
   parser2 --> y;
   parser3 --> z;
   ...

becomes calls to SuperChain() with auxhilery functions generated 
inbetween. (You don't need to comprehend the precise algorithm, but 
trust me, it works.)

Using this technology, we can write something like

   bracket_parser =
     begin
       P_Char('[');
       expression_parser --> expr;
       P_Char(']');
       P_Succeed([expr]);
     end;

   X_parser =
     begin
       P_Char('X');
       P_Succeed(['x']);
     end;

   term_parser = X_parser <|> bracket_parser;

   expression_parser =
     begin
       term_parser                       --> term1;
       P_Optional(expression_parser, []) --> term2;
       P_Succeed(term1.join(term2));
     end;

This will parse a string such as "[X[X]X]" and return a list object like 
['X',['X'],'X']. And so, finally, we have a parser that generates a 
nontrivial data structure as its result.


## Caution ##

Suppose you wanted to write a Lambda expression parser. The grammar for 
that looks like this:

   <expression> =
     <var name> |
     "(" <expression> ")" |
     <expression> <expression> |
     "\" <var name > "->" <expression>

You might attempt to implement this as

   expression_parser =
     ...
     <|>
     (
       begin
         expression_parser --> expr1;
         expression_parser --> expr2;
         P_Succeed([expr1, expr2]);
       end;
     )
     <|>
     ...

Don't do that! You have just implemented a "left-recursive grammar", 
which Parsec cannot handle. You must first refactor it to avoid 
left-recursion. To understand why, consider this:

   OK, so how do I parse an expression? OK, well one of the parse rules 
says to start by parsing an expression. OK, so how do I parse an expression?

The parser will sit an in infinite loop, frantically chasing its tail 
and making no progress. The correct solution here is to parse one 
expression and then use P_Optional() to attempt to parse a second one, 
if there is one.

   term_parser = ...

   expression_parser =
     begin
       term_parser --> term1
       P_Optional(expression_parser, empty_expression) --> term2
       ...combine terms...
     end;

Notice how the *first* line parses a single term, while the *second* 
line recursively parses an entire expression. That way expressions of 
arbitrary size are parsable, but the infinite recursion is avoided.


## Error messages ##

Suppose you write an expression parser and tried to parse "123xyz". You 
might get an error like

   "Error on line 1, column 4: Unexpected character 'x'; expecting '0', 
'1', '2', '3', '4', '5', '6', '7', '8' or '9'."

While this error is completely correct technically, it's a tad verbose. 
Once you start writing parsers for sophisticated grammars, you get error 
messages indicating that all sorts of punctuation marks would be legal 
here, but it can become a little overhelming trying to figure out what 
the parser is actually unhappy about.

Parsec provides the P_Name() function. So for example:

   digit_parser =
     P_Name(
       P_Char('0') <|> P_Char('1') <|> ...,
       "digit"
     );

   number_parser = P_Many1(digit_parser);

Now you get the following error message:

   "Error on line 1, column 4: Unexpected character 'x'; expecting digit."

This is much better. In fact, if your "number" parser accepts fractional 
values, you might get

   "Error on line 1, column 4: Unexpected character 'x'; expecting 
digit, '.' or 'e'."

If you like that, fine. If you'd prefer something shorter, you could put 
P_Name() around number_parser instead (or as well!) to give "expecting 
number literal" or something.

The net result is that when some complex parser fails, you can end up 
with something like

   "Unexpected character '#'; expecting variable name, number iteral or 
';'."

(Haskell has to go one better by making P_Name() an *operator* with 
really low precidence, so you're not forced to put your whole parser in 
brackets.)


## Backtracking ##

In the interests of efficiently, Parsec doesn't actually work in 
*exactly* the way I described. Specifically, "backtracking" is 
*disabled* by default, and you must explicitly enable it wherever you 
want it. This enables the implementation of "infinite look-ahead 
grammars", but with the associated overhead only where necessary.

What does all that lot actually mean? Well it means that Fork() doesn't 
work exactly like I described. How it actually works is this:

- The first parser is executed.
- If it succeeds, return its result.
- If it fails *without consuming any input*, run the second parser.
- If the first parser consumes some input and *then* fails, the second 
parser is not tried, and the whole thing fails.

What this means is that Fork() doesn't have to "remember" where the 
first parser started from, and "rewind" the input stream before starting 
the second parser. In particular, this "remembering" process would 
prevent the GC from freeing the memory being used by the input string, 
since Fork() would still hold a pointer to it.

Basically Fork() assumes that a parser can tell from the very first 
character of input whether it's going to succeed or while. And if it 
fails part-way through, that's a real parsing error. (E.g., a number 
parser encountering "123xyz" would be an error.) It will not "backtrack" 
and run the second parser if the first one fails after consuming input. 
The first parser must fail immediately for that to happen.

But what if you *want* backtracking? Well, then you use the P_Try() 
primitive. This takes a parser and returns a parser. It runs that parser 
in such a way that if it fails, P_Try() makes it "look like" it consumed 
no input. In other words, P_Try() does the "remembering" part (with the 
associated cost in RAM usage).

This way, Fork() uses no extra RAM by default, and if you want 
backtracking (and the inevitable increase in RAM usage), you can 
explicitly ask for P_Try().

You only pay for what you use.


## Assorted notes ##

Note that SuperChain() takes an arbitrary *function* as its second 
argument. That function can perform an arbitrarily complex algorithm 
before returning a parser for SuperChain() to run. This means that you 
can write Turing-complete parsers.

In fact, instead of writing an expression parser that *returns* an 
expression, you could in fact write an expression "parser" that actually 
*executes* the expression as it parses it. (Whether you want to do that 
or not depends on what you're attempting to achieve.)

It also means things like being able to select parsers based on input 
already seen. Want a parser that can detect when an undeclared variable 
name appears? Parsec makes it quite easy. I won't go into exactly how, 
but suffice it to say that Parsec can track user-defined data along with 
its own internal state data (e.g., current line number, etc).


# Lies! #

OK, yeah, I admit it. I lied! I said there would be no Haskell syntax, 
but ">>" actually is the real name of the real Haskell function that 
works exactly the way I described. And SuperChain() is actually called 
">>=". And P_Succeed() is called "return". (Notice how that what most 
parsers use it for - to change the parser's return value.) Finally, 
P_Fail() is actually just "fail".

Together, (>>), (>>=) and (return) comprise Haskell's much-feared 
"monad" construct. If you understood the explanation of SuperChain(), 
you just understood how monads work!

Parsec parsers form a monad, and Parsec is therefore a *monadic* 
combinator library. (A very common form.)

The reason that Haskell has the magical syntax for using SuperChain() is 
that in Haskell, I/O is *also* a monad, and I/O is a Rather Common Task. 
(!) Hence the syntax sugar.

A surprising number of other things turn out to be monads as well - even 
things that don't seem remotely similar. But that's a topic for another 
day...


# Financial contracts #

Lest anybody think that combinator libraries are only good for building 
parsers, let me *briefly* present a second example.

Some while ago, apparently a group of Haskell hackers examined the 
problem of describing and valuing financial contracts. Their results 
evidently caused a bit of a stir in the financial community. (I don't 
know to what extent the authors are just blowing their own trumpet.)

What they wrote is a Haskell combinator library for combining contracts. 
They started with the idea that a contract has a financial value 
(negative or positive). Then they added a combinator that makes the 
value of a contract change at a certain point in time.

Next they added a combinator that makes a new contract who's value at 
any time is equal to the sum of the values of its two subcontracts at 
that time. (So, this is similar to Chain().) And then they added a 
combinator that allows you to select one contract *or* the other, but 
not both. (So this is like Fork().)

It should be easy to see that with these few simple operations, it's 
quite easy to build highly complex contracts. It should also be utterly 
clear that algorithmically determining a contract's value at any point 
in time, given any particular combination of selections, is a pretty 
simple task.

The authors claim that their work was hailed as "visionary". Apparently 
no system had hitherto existed for clearing and precisely stating the 
properties of contracts in an abstract and mathematically rigorous way.

I don't know if any of that is true, but I *do* know that when you're 
trying to solve highly complex problems, being able to precisely define 
what the problem actually *is* in the first place would be a very 
significant step forward.

Post a reply to this message

> OK, so the muse has taken me. I want to write something. I realise nobody 
> here really cares, but if you're bored maybe you could take a read and 
> tell me what you think.

I read it, very interesting seeing as I had no idea how a parser works (I 
always wondered how you would go about writing one).

So essentially, you could "just" make one parser object, that consisted of 
many many complex parser objects, to parse something like a POV SDL file? 
Then you would just chuck the POV file at the top level parser object, and 
it would return a nice tree structure of the SDL code?  Hmmmm.

Post a reply to this message

scott wrote:

> I read it, very interesting seeing as I had no idea how a parser works 
> (I always wondered how you would go about writing one).

The more "usual" approach is usually something based around a finite 
state machine - but as I just explained, Parsec works differently. (And 
indeed will parse things t FSM couldn't parse - but that you'll often 
need that.)

> So essentially, you could "just" make one parser object, that consisted 
> of many many complex parser objects, to parse something like a POV SDL 
> file? Then you would just chuck the POV file at the top level parser 
> object, and it would return a nice tree structure of the SDL code?  Hmmmm.

Pretty much, yeah. SDL is complicated by #declare and #macro though. ;-)

For a "normal" programming language, the traditional approach is this:

1. A "tokeniser" takes the input string and splits it into "tokens", 
possibly decorating them slightly. So now you have a flat stream of 
tokens instead of just characters.

2. A "parser" builds a tree-like structure out of the token list, using 
the syntax rules of the language.

3. You pass this tree ("abstract syntax tree") to a compiler or 
interpretter or whatever the hell it is your program wants to do with 
the thing.

Parsec allows you to parse and then tokenise, or do the whole thing in 
one pass. It's up to you. (I didn't mention it, but Parsec supports 
running parsers over lists of *anything*, not just characters. So you 
could in theory parse raw binary if you wanted...)

POV-Ray SDL is complicated because it doesn't have *functions*, it has 
*macros*, which expand at the token level, not the syntax tree level. 
(So, e.g., the contents of a macro can be an incomplete expression.)

Theoretically Parsec can cope with that - but in practice I'm not sure 
how ugly the code would be. IIRC there's a formal grammer available 
online somewhere, right? Some appendix to the user guide or something? 
Maybe I could have a go at implementing it with Parsec. (It'll be 
*large* though! POV-Ray has a lot of keywords...)

Post a reply to this message

Just for giggles, I started trying to implement this in Java. But I 
quickly ended up with 13 classes, almost all of which are about 5 lines 
long.

Parsers are an abstract class. Each primitive parser is a concrete 
subclass. Each parser combinator is a subclass. The parser result is an 
abstract class. Each possible parser result structure is a concrete 
subclass. Parser functions are an interface... My, my, what a lot of 
classes we have there! o_O

It would almost be easier on C++, because then all these tiny classes 
could all be in the same source file. (Plus C++ has the "friend" 
feature, which is eminently useful here.) OTOH, I have no idea how to do 
memory management yet, so that's basically the end of that...

Post a reply to this message

Invisible wrote:

I read it all the way through too. Nicely written, good explanation. I'd 
add a bit at the end that points to the online resources you'd need to 
learn it more completely.  (A few spelling mistakes and a dropped word 
or two also, but that's trivia. :-)

> scott wrote:
> 
>> I read it, very interesting seeing as I had no idea how a parser works 
>> (I always wondered how you would go about writing one).
> 
> The more "usual" approach is usually something based around a finite 
> state machine - but as I just explained, Parsec works differently. (And 
> indeed will parse things t FSM couldn't parse - but that you'll often 
> need that.)

Actually, that's not *quite* right.

An FSM will parse what a regular expression parses, which doesn't 
include (for example) matching nested brackets, because there's no 
arbitrarily-large storage area to hold the count of nested brackets.

A "push-down automaton" (or PDA) is one common way of implementing a 
parser. It's a FSM *with* a stack. This is the sort of thing YACC / 
Bison implements. People use it because you can algorithmically generate 
the FSM from the BNF grammar of the language you want to parse.

What Haskell is using is called a recursive-descent parser: the parser 
basically uses the run-time stack in place of an explicit stack. It's 
best for LALR(1) syntaxes, which means "Look Ahead Left to Right 1 
token". I.e., a language you can parse by running strictly from left to 
right, looking only one element ahead, so you don't need the "P_Try()" 
function. Some languages (like Pascal) are explicitly designed this way 
to make it easy to build a recursive descent parser.

> 1. A "tokeniser" takes the input string and splits it into "tokens", 
> possibly decorating them slightly. So now you have a flat stream of 
> tokens instead of just characters.

The advantage of doing it this way is most tokens can be parsed with a 
regular expression, which is much faster (and leads to *much* smaller 
push-down state machines) than doing it with the same PDA as used by the 
rest of the grammar.

> Parsec allows you to parse and then tokenise, or do the whole thing in 
> one pass. It's up to you. (I didn't mention it, but Parsec supports 
> running parsers over lists of *anything*, not just characters. So you 
> could in theory parse raw binary if you wanted...)

Or you could parse a list of tokens coming from the tokenizer, which is 
what I imagine the authors were thinking. :-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New wrote:

> I read it all the way through too. Nicely written, good explanation.

Thanks. :-)

> I'd 
> add a bit at the end that points to the online resources you'd need to 
> learn it more completely.  (A few spelling mistakes and a dropped word 
> or two also, but that's trivia. :-)

Given that I'm the only person here who knows how to read Haskell 
syntax, a link to the Parsec user manual seemed... a little pointless.

But in case anybody cares:

http://legacy.cs.uu.nl/daan/download/parsec/parsec.html

That's the user's guide. The (very terse!) API reference is here:

http://haskell.org/ghc/docs/latest/html/libraries/

This is all the semi-standard Haskell libraries. The one you're looking 
for is Text.ParserCombinators.Parsec. (It's split into several modules.)

>> The more "usual" approach is usually something based around a finite 
>> state machine - but as I just explained, Parsec works differently. 
>> (And indeed will parse things t FSM couldn't parse - but that you'll 
>> often need that.)
> 
> Actually, that's not *quite* right.
> 
> An FSM will parse what a regular expression parses, which doesn't 
> include (for example) matching nested brackets, because there's no 
> arbitrarily-large storage area to hold the count of nested brackets.
> 
> A "push-down automaton" (or PDA) is one common way of implementing a 
> parser. It's a FSM *with* a stack. This is the sort of thing YACC / 
> Bison implements. People use it because you can algorithmically generate 
> the FSM from the BNF grammar of the language you want to parse.
> 
> What Haskell is using is called a recursive-descent parser: the parser 
> basically uses the run-time stack in place of an explicit stack. It's 
> best for LALR(1) syntaxes, which means "Look Ahead Left to Right 1 
> token". I.e., a language you can parse by running strictly from left to 
> right, looking only one element ahead, so you don't need the "P_Try()" 
> function. Some languages (like Pascal) are explicitly designed this way 
> to make it easy to build a recursive descent parser.

Heh. What do *I* know about parser theory? ;-)

The point is, Parsec will parse just about anything, although as you say 
it "works best" for LALR(1) grammars. It's quite surprising how simple 
and easy to explain the library is - and yet it handles almost anything. 
(I don't know if I made it clear, but Parsec parsers are a state monad.)

>> 1. A "tokeniser" takes the input string and splits it into "tokens", 
>> possibly decorating them slightly. So now you have a flat stream of 
>> tokens instead of just characters.
> 
> The advantage of doing it this way is most tokens can be parsed with a 
> regular expression, which is much faster (and leads to *much* smaller 
> push-down state machines) than doing it with the same PDA as used by the 
> rest of the grammar.

Indeed, the Parsec manual says something similar.

>> Parsec allows you to parse and then tokenise, or do the whole thing in 
>> one pass. It's up to you. (I didn't mention it, but Parsec supports 
>> running parsers over lists of *anything*, not just characters. So you 
>> could in theory parse raw binary if you wanted...)
> 
> Or you could parse a list of tokens coming from the tokenizer, which is 
> what I imagine the authors were thinking. :-)

Precisely that, yes.

Post a reply to this message

Invisible wrote:
> Given that I'm the only person here who knows how to read Haskell 
> syntax, a link to the Parsec user manual seemed... a little pointless.

Oh. I *highly* suggest you put this up on your blog or your web site or 
something like that, for public consumption. Get comments from a lot of 
people, find jobs in Haskell and/or teaching because you can write like 
this, etc.

> Heh. What do *I* know about parser theory? ;-)

I don't know. It seemed like a fair amount. :-)  This is all stuff you 
learn in the first semester of compiler construction class.

> The point is, Parsec will parse just about anything, although as you say 
> it "works best" for LALR(1) grammars. It's quite surprising how simple 
> and easy to explain the library is - and yet it handles almost anything. 
> (I don't know if I made it clear, but Parsec parsers are a state monad.)

Yes. I'm just saying it "works best" because LALR(1) parses without ever 
needing to use P_Try().  I.e., you don't need anything like exceptions 
or input buffers to parse an LALR(1) grammar using the programming 
language's stack - you need enough memory to hold one token, and you can 
output results as soon as any production is recognised, and you only 
need stack space proportional to the most nested expression in your 
input, and you don't need any memory to outlast the parsing of the 
productions you're currently parsing.

Of course, once you add arbitrary function calls and arbitrary buffering 
(via P_Try and SuperCombiner) then you can parse lots more; it just 
takes more code and more memory and potentially global data structures.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Invisible wrote:
> Just for giggles, I started trying to implement this in Java. But I 
> quickly ended up with 13 classes, almost all of which are about 5 lines 
> long.

Java is the kingdom of nouns. Functions are second-class citizens. Even 
downward funargs need to be associated with a class, even if it's 
anonymous and only has one function and no instance variables in it.

Of course implementing a functional application in Java is going to 
suck. :-)

http://steve-yegge.blogspot.com/2006/03/execution-in-kingdom-of-nouns.html

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

>> Given that I'm the only person here who knows how to read Haskell 
>> syntax, a link to the Parsec user manual seemed... a little pointless.
> 
> Oh. I *highly* suggest you put this up on your blog or your web site or 
> something like that, for public consumption. Get comments from a lot of 
> people, find jobs in Haskell and/or teaching because you can write like 
> this, etc.

Heh. I could add it to my blog. Nobody on earth will ever actually read 
it, but sure, I can add it. ;-)

>> Heh. What do *I* know about parser theory? ;-)
> 
> I don't know. It seemed like a fair amount. :-)  This is all stuff you 
> learn in the first semester of compiler construction class.

Now there's a class that sounds interesting... Pity my "Computer 
Science" degree didn't involve anything remotely like that. ;-)

> Yes. I'm just saying it "works best" because LALR(1) parses without ever 
> needing to use P_Try().  I.e., you don't need anything like exceptions 
> or input buffers to parse an LALR(1) grammar using the programming 
> language's stack - you need enough memory to hold one token, and you can 
> output results as soon as any production is recognised, and you only 
> need stack space proportional to the most nested expression in your 
> input, and you don't need any memory to outlast the parsing of the 
> productions you're currently parsing.
> 
> Of course, once you add arbitrary function calls and arbitrary buffering 
> (via P_Try and SuperCombiner) then you can parse lots more; it just 
> takes more code and more memory and potentially global data structures.

Fair enough. ;-)

Figuring out when to use P_Try() is actually quite subtle by the way - 
especially where you have a language where variable names can't be 
resurved words. Parsec actually provides a small module to automatically 
build parsers for common types of expression and language grammars based 
on the options you supply (automates things like reversed word 
recognition, operator precidence, operator associativity, etc.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Heh. I could add it to my blog. Nobody on earth will ever actually read 
> it, but sure, I can add it. ;-)

You would be surprised. At least you can point people to it who 
interview you or something. You *are* looking for a job, yes?

> Now there's a class that sounds interesting... Pity my "Computer 
> Science" degree didn't involve anything remotely like that. ;-)

Don't forget I have an advanced degree. I don't think my undergraduate 
courses covered the theoretical stuff like that either.

> on the options you supply (automates things like reversed word 
> recognition, operator precidence, operator associativity, etc.)

I'm not surprised. :-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

> 1. A "tokeniser" takes the input string and splits it into "tokens", 
> possibly decorating them slightly. So now you have a flat stream of tokens 
> instead of just characters.

Do you need to have some sort of grammar rules though before you can 
tokenise?  I mean what if you have the string "-3*(4-3e-2)+5*-3", the 
tokeniser (if I understand right) needs to correctly decide how to interpret 
those minus signs, needing some rules about what is surrouding it etc.  What 
would be the best way to convert an ASCII string like that into a list of 
tokens?

Post a reply to this message

scott wrote:

> Do you need to have some sort of grammar rules though before you can 
> tokenise?

Yes, definitely.

> I mean what if you have the string "-3*(4-3e-2)+5*-3", the 
> tokeniser (if I understand right) needs to correctly decide how to 
> interpret those minus signs, needing some rules about what is surrouding 
> it etc.  What would be the best way to convert an ASCII string like that 
> into a list of tokens?

Ah yes, the old "is it unary minus or binary minus?" question.

In this case, you'd probably let minus be a token by itself, and let the 
parser decide whether it's unary or binary based on the context when it 
builds the parse tree.

Post a reply to this message

And lo on Tue, 23 Sep 2008 12:32:15 +0100, Invisible <voi### [at] devnull> did  
spake, saying:

> # Preface #
>
> OK, so the muse has taken me. I want to write something.

[smack] Blog!

-- 
Phil Cook

--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com

Post a reply to this message

Phil Cook wrote:

> [smack] Blog!

Meh. Like anybody will read it! :-P

Post a reply to this message

> scott wrote:
> 
>> Do you need to have some sort of grammar rules though before you can 
>> tokenise?
> 
> Yes, definitely.

To see this, consider that in many programming languages, "foo_bar" is a 
single identifier. However, in TeX source code, "_" is [usually] a 
command name and hence should be parsed as a seperate token.

So what constitutes a "token" completely depends on exactly what you're 
trying to tokenise/parse.

Post a reply to this message

scott wrote:
> What would be the best way to convert an ASCII string like that 
> into a list of tokens?

Typically, it's done with regular expressions. And typically, "-37" is 
two tokens in programming language compilers, at least.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

> Typically, it's done with regular expressions. And typically, "-37" is two 
> tokens in programming language compilers, at least.

OK, and then is there only one token for "minus", or are there two for unary 
and binary minus?  ie does the parser decide or the tokeniser?

Post a reply to this message

scott wrote:

> OK, and then is there only one token for "minus", or are there two for 
> unary and binary minus?  ie does the parser decide or the tokeniser?

Varies depending on the rules of whatever you're trying to process, but 
typically it's the parser.

Post a reply to this message

>> OK, and then is there only one token for "minus", or are there two for 
>> unary and binary minus?  ie does the parser decide or the tokeniser?
>
> Varies depending on the rules of whatever you're trying to process, but 
> typically it's the parser.

I'm just curious, because I made a parser like this in C++ once (it was very 
hacky and basically just stepped along the string trying to identify what 
each byte was).  Anyway, it worked ok for things like "-5*(4+2)" etc, but 
crashed with "-(4+2)".  I guess the minus operator should be encoded as its 
own token and then let the parser sort out what it should do.  Maybe I'll 
try a rewrite one day.

Post a reply to this message

scott wrote:

> I'm just curious, because I made a parser like this in C++ once (it was 
> very hacky and basically just stepped along the string trying to 
> identify what each byte was).  Anyway, it worked ok for things like 
> "-5*(4+2)" etc, but crashed with "-(4+2)".  I guess the minus operator 
> should be encoded as its own token and then let the parser sort out what 
> it should do.  Maybe I'll try a rewrite one day.

Yeah, this is one of the tricky edge-cases of expression parsing. 
Operator precidence and unary/binary operators can get pretty ugly. 
(Gets even harder if you want to report meaningful error messages if 
there's an actua syntax error...)

Post a reply to this message

scott wrote:
>> Typically, it's done with regular expressions. And typically, "-37" is 
>> two tokens in programming language compilers, at least.
> 
> OK, and then is there only one token for "minus", or are there two for 
> unary and binary minus?  ie does the parser decide or the tokeniser?

Typically, it's one token. You can't tell (in a language like Pascal) as 
you're parsing tokens. You have to get to the syntax tree before 
figuring out whether it's a unary or binary minus.

In APL, there are two minus signs, one for the operator and one you put 
in front of negative numbers. Which helps more than you'd think because 
all operators are right-associative.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Phil Cook wrote:

> [smack] Blog!

Especially for you...

http://blog.orphi.me.uk/archives/332




PS. OMG - how I have "Especially For You" stuck in my head!! >_<

Post a reply to this message

And lo on Fri, 26 Sep 2008 10:32:23 +0100, Invisible <voi### [at] devnull> did  
spake, saying:

> Phil Cook wrote:
>
>> [smack] Blog!
>
> Especially for you...
>
> http://blog.orphi.me.uk/archives/332

Now hop onto your haskell group and ask their opinion and try to get it  
linked in on various Haskell wiki's etc.

> PS. OMG - how I have "Especially For You" stuck in my head!! >_<

Dibs on being Jason.

-- 
Phil Cook

--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com

Post a reply to this message

Phil Cook wrote:

> Now hop onto your haskell group and ask their opinion and try to get it 
> linked in on various Haskell wiki's etc.

The thought did cross my mind... It might make it to the Haskell Weekly 
News! o_O

>> PS. OMG - how I have "Especially For You" stuck in my head!! >_<
> 
> Dibs on being Jason.

...WTF?

Post a reply to this message

And lo on Fri, 26 Sep 2008 14:29:01 +0100, Invisible <voi### [at] devnull> did  
spake, saying:

> Phil Cook wrote:
>
>> Now hop onto your haskell group and ask their opinion and try to get it  
>> linked in on various Haskell wiki's etc.
>
> The thought did cross my mind... It might make it to the Haskell Weekly  
> News! o_O

Fame at last.

>>> PS. OMG - how I have "Especially For You" stuck in my head!! >_<
>>  Dibs on being Jason.
>
> ...WTF?

Okay, okay I'll be Kylie; sheesh.

-- 
Phil Cook

--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com

Post a reply to this message

> Dibs on being Jason.

What, while Andy is being KM? o_O

Post a reply to this message

>> The thought did cross my mind... It might make it to the Haskell 
>> Weekly News! o_O
> 
> Fame at last.

Heh. I already round out that there's a ticket delaying the release of 
GHC 6.10, and it was opened in response to an email I wrote - a year 
ago! o_O

>>>> PS. OMG - how I have "Especially For You" stuck in my head!! >_<
>>>  Dibs on being Jason.
>>
>> ...WTF?
> 
> Okay, okay I'll be Kylie; sheesh.

Oh, wait - that song was Jason and Kylie??

Post a reply to this message

And lo on Fri, 26 Sep 2008 16:04:02 +0100, Invisible <voi### [at] devnull> did  
spake, saying:

>>>>> PS. OMG - how I have "Especially For You" stuck in my head!! >_<
>>>>  Dibs on being Jason.
>>>
>>> ...WTF?
>>  Okay, okay I'll be Kylie; sheesh.
>
> Oh, wait - that song was Jason and Kylie??

Out of perverse curiosity who did you think it was by?

-- 
Phil Cook

--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com

Post a reply to this message

>> Oh, wait - that song was Jason and Kylie??
> 
> Out of perverse curiosity who did you think it was by?

*shrugs*

It's not something I've spent a lot of time thinking about...

Post a reply to this message

Orchid XP v8 wrote:
>> Oh. I *highly* suggest you put this up on your blog or your web site or
>> something like that, for public consumption. Get comments from a lot of
>> people, find jobs in Haskell and/or teaching because you can write like
>> this, etc.
> 
> Heh. I could add it to my blog. Nobody on earth will ever actually read
> it, but sure, I can add it. ;-)

Does Haskell have a wiki?

Post a reply to this message

Nicolas Alvarez wrote:
> Orchid XP v8 wrote:
>>> Oh. I *highly* suggest you put this up on your blog or your web site or
>>> something like that, for public consumption. Get comments from a lot of
>>> people, find jobs in Haskell and/or teaching because you can write like
>>> this, etc.
>> Heh. I could add it to my blog. Nobody on earth will ever actually read
>> it, but sure, I can add it. ;-)
> 
> Does Haskell have a wiki?

Yeah. Two of 'em, in fact... (The old one that's slowly being closed 
down, and the new one that's a tad sparse stilll.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Darren New wrote:

> Actually, that's not *quite* right.
> 
> What Haskell is using is called a recursive-descent parser: the parser 
> basically uses the run-time stack in place of an explicit stack. It's 
> best for LALR(1) syntaxes, which means "Look Ahead Left to Right 1 
> token". I.e., a language you can parse by running strictly from left to 
> right, looking only one element ahead, so you don't need the "P_Try()" 
> function. Some languages (like Pascal) are explicitly designed this way 
> to make it easy to build a recursive descent parser.

OK, well since you seem to know something about this... using the 
formalisms developed here, how would you go about parsing a grammar that 
can consist of integers, variable names, and + - / * ( ), such that the 
operators have the correct precidence?

I thought I had this working, but it seems that bracketing the 
expressions in unusual but valid ways causes the parser to trip over in 
inexplicable ways. :-(

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> OK, well since you seem to know something about this... using the 
> formalisms developed here, how would you go about parsing a grammar that 
> can consist of integers, variable names, and + - / * ( ), such that the 
> operators have the correct precidence?

  I don't know if this has anything to do with the formalism in question,
but I used the following classical parsing algorithm in my function parser
library, which converts a function string into a series of bytecode commands
which use stack arithmetic. (The parser is able to parse the input with one
single pass, by only seeing one token at a time).

  Basically you create one parsing function for each level of precedence.
You start from the lowest precedence and make each such function call the
function at the next precedence level. The highest precedence level
function is the function that parses one element in the expression.

  Assuming that + and - have the same precedence and are parsed
left-to-right, you write the lowest precedence function like this
(C++'ish pseudocode):

parsePlusMinus(functionString)
{
    parseMulDiv(functionString); // The next higher precedence function.

    token = functionString.nextToken(); // Could be end-of-string
    if(token == '+' or token == '-')
    {
        parseMulDiv(functionString);
        if(token == '+') generateCommand(add);
        else generateCommand(sub);
    }
}

  Basically this divides the function string into parts which are separated
with '+' or '-'. It parses these parts by calling the next higher precedence
function, and then generates the operator command which calculates the sum
or subtraction of those parts. (Since my parser uses stack arithmetic, it
means that these "parts" are values on top of the stack when the
parseMulDiv() function has done its job and returns.)

  The next function is very similar:

parseMulDiv(functionString)
{
    parseElement(functionString); // The next higher precedence function.

    token = functionString.nextToken();
    if(token == '*' or token == '/')
    {
        parseElement(functionString);
        if(token == '*') generateCommand(mul);
        else generateCommand(div);
    }
}

  Now in your syntax the next higher precedence function is the one
which parses a single element. But what about parentheses? Well, here's
the trick: An expression in parentheses *is* a single element: After its
contents have been parsed it generates one single value onto the stack,
exactly as a single element does. The trick is to parse its contents
recursively, as its own expression. That is, something like:

parseElement(functionString)
{
    token = functionString.nextToken();

    if(token == '(')
        parsePlusMinus(functionString); // parse the inner expression
        // When it returns, the ')' will have been read out already

    else if(token == NUMBER)
        generateCommand(push, NUMBER); // push the number onto the stack

    else SyntaxError;
}

  Of course this is highly simplified. For example, it doesn't perform any
syntax correctness checking (eg. that parentheses match). Those require a
bit more logic inside those functions. But you get the basic idea.

  The beauty of this is that with these recursive functions you are able
to parse the function string by reading one token at a time, traversing
the string only once from beginning to end, without ever needing to go
back or perform any look-ahead, yet it still correctly handles operator
precedence and nested expressions in parentheses.

-- 
                                                          - Warp

Post a reply to this message

Invisible wrote:
> Darren New wrote:
> 
>> Actually, that's not *quite* right.
>>
>> What Haskell is using is called a recursive-descent parser: the parser 
>> basically uses the run-time stack in place of an explicit stack. It's 
>> best for LALR(1) syntaxes, which means "Look Ahead Left to Right 1 
>> token". I.e., a language you can parse by running strictly from left 
>> to right, looking only one element ahead, so you don't need the 
>> "P_Try()" function. Some languages (like Pascal) are explicitly 
>> designed this way to make it easy to build a recursive descent parser.
> 
> OK, well since you seem to know something about this... using the 
> formalisms developed here, how would you go about parsing a grammar that 
> can consist of integers, variable names, and + - / * ( ), such that the 
> operators have the correct precidence?

Almost everyone calls these productions "Expressions" and "Terms" and 
"Factors". So googling for "bnf expression term" yields

http://www.seas.upenn.edu/~cit596/notes/dave/bnf4.html

You can see the basic technique.  An expression is terms multiplied 
together, while a term is factors added together, and a factor is a 
variable, a number, or an expression in parens. That gives you the 
precidence and associativity you are looking for.

> I thought I had this working, but it seems that bracketing the 
> expressions in unusual but valid ways causes the parser to trip over in 
> inexplicable ways. :-(

Take the BNF and translate it directly into functions that match those 
other parsers? It's been decades since I did such stuff, so I am not 
really glib enough at this point to just roll it off the fingertips.

Googling for "recursive descent expression parse", I get
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
which covers it well. Note the line
"""
Not only is left recursion eliminated, but the G1 is unambiguous and 
each choice can be made by looking at the next token in the input.
"""
which tells you it's possible to use simple LL(1) parsers to grok it.
The "recursive descent recognition" shows you how to do it with Haskell 
parsers. The next section ("shunting yard") shows you how Yacc/Bison 
builds its table, followed by essentially an implementation of the 
run-time part of Yacc/Bison.

That's actually a pretty good overview page. :-)

HTH!

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New wrote:
> An expression is terms multiplied
> together, while a term is factors added together

Are you sure you didn't get that backwards?

Post a reply to this message

Nicolas Alvarez wrote:
> Darren New wrote:
>> An expression is terms multiplied
>> together, while a term is factors added together
> 
> Are you sure you didn't get that backwards?

No, I'm not. :-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp wrote:

>   I don't know if this has anything to do with the formalism in question,
> but I used the following classical parsing algorithm in my function parser
> library, which converts a function string into a series of bytecode commands
> which use stack arithmetic. (The parser is able to parse the input with one
> single pass, by only seeing one token at a time).
> 
>   Basically you create one parsing function for each level of precedence.
> You start from the lowest precedence and make each such function call the
> function at the next precedence level. The highest precedence level
> function is the function that parses one element in the expression.

>   Now in your syntax the next higher precedence function is the one
> which parses a single element. But what about parentheses? Well, here's
> the trick: An expression in parentheses *is* a single element: After its
> contents have been parsed it generates one single value onto the stack,
> exactly as a single element does. The trick is to parse its contents
> recursively, as its own expression. That is, something like:

>   The beauty of this is that with these recursive functions you are able
> to parse the function string by reading one token at a time, traversing
> the string only once from beginning to end, without ever needing to go
> back or perform any look-ahead, yet it still correctly handles operator
> precedence and nested expressions in parentheses.

This is basically what I did - and it worked exactly right 95% of the 
time. But if you bracket your expressions in odd (but valid) ways, it 
complains.

Oh well, maybe I just made a mistake somewhere... I'll go recheck the code.

It's about now I wish I had a step debugger! ;-)

Post a reply to this message

Invisible wrote:

> This is basically what I did - and it worked exactly right 95% of the 
> time. But if you bracket your expressions in odd (but valid) ways, it 
> complains.

Ah-HAH!

I know what I did wrong. I was looking for brackets at *every* level of 
precidence. The correct behaviour is to look for them *only* at the 
lowest precidence level. Otherwise one of the higher levels gobbles them 
up, and then complains that the seperator is a lower-precidence 
operator. Oops.

OK, now I can bracket my expressions in all sorts of weird ways and the 
parser always seems to give me the correct answer. (But I've said that 
before!) Hmm, I might have to see about writing a formal test harness to 
check whether it "really is" working properly this time...

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> precidence

  You keep using that word...

http://dictionary.reference.com/browse/precedence

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> precidence
> 
>   You keep using that word...
> 
> http://dictionary.reference.com/browse/precedence

Grr... god damned screwy language! :-S

Post a reply to this message

On Tue, 23 Sep 2008 12:32:15 +0100, Invisible wrote:
> Parsec takes a completely different approach - and that is the subject 
> of this text.

What you described -- I didn't read all of it though -- sounds
very much the same as what boost::spirit does in C++.

-- 
Joel Yliluoma - http://iki.fi/bisqwit/

Post a reply to this message

Joel Yliluoma wrote:

> What you described -- I didn't read all of it though -- sounds
> very much the same as what boost::spirit does in C++.

Looking at the Spirit documentation, it *does* indeed look highly 
similar. (Right down to using the ">>" operator for the same purpose 
that Parsec does.)

The difference, of course, is that Spirit uses compile-time template 
insanity to do it's work, whereas Parsec does all its cleverness at 
runtime. (So Spirit is probably faster, and Parsec supports constructing 
user-defined parsers at runtime.)

Post a reply to this message

Invisible wrote:
> So Spirit is probably faster

To run, sure. But it probably takes even longer than your average Boost
library to compile :)

(seriously, many boost libraries are like compiler stress-tests)

Post a reply to this message

Nicolas Alvarez wrote:
> Invisible wrote:
>> So Spirit is probably faster
> 
> To run, sure. But it probably takes even longer than your average Boost
> library to compile :)
> 
> (seriously, many boost libraries are like compiler stress-tests)

Hmm... interesting. Template metaprogramming FTW? :-P

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Nicolas Alvarez wrote:
> > Invisible wrote:
> >> So Spirit is probably faster
> > 
> > To run, sure. But it probably takes even longer than your average Boost
> > library to compile :)
> > 
> > (seriously, many boost libraries are like compiler stress-tests)

> Hmm... interesting. Template metaprogramming FTW? :-P

  Well, one idea (or maybe more a side-effect) of template metaprogramming
is: Why calculate something at runtime if you can do it at compile time?

  It often may result in faster binaries. OTOH there are some huge projects
where compilation times are counted in hours rather than seconds, where
significantly slower compilation times might become an issue.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   Well, one idea (or maybe more a side-effect) of template metaprogramming
> is: Why calculate something at runtime if you can do it at compile time?
> 
>   It often may result in faster binaries. OTOH there are some huge projects
> where compilation times are counted in hours rather than seconds, where
> significantly slower compilation times might become an issue.

I personally tend to prefer longer compile times for shorter runtimes.

OTOH, the largest programs I've ever written probably didn't exceed a 
few hundred lines, so...

Post a reply to this message

Warp wrote:
>   It often may result in faster binaries. OTOH there are some huge projects
> where compilation times are counted in hours rather than seconds, where
> significantly slower compilation times might become an issue.

I remember reading of an Ada project where the customer was complaining 
the vendor's compiler was too slow. The vendor looked at the code, 
basically said "WTF mate?" and pointed out that using packages nested 
dozens of levels deep (the equivalent of templates referring to 
templates recursively dozens of times) are going to be slow to compile, 
and they asked the customer why they picked that technique. The customer 
pointed out that it was in the vendor's sample files. The vendor pointed 
out that *that* sample file was a compiler stress-test designed to 
validate the compiler doesn't choke even under awful programming 
practices. :-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

On Tue, 21 Oct 2008 08:42:48 -0700, Darren New <dne### [at] sanrrcom> wrote:

> The customer 
>pointed out that it was in the vendor's sample files. The vendor pointed 
>out that *that* sample file was a compiler stress-test designed to 
>validate the compiler doesn't choke even under awful programming 
>practices. :-)

LOL
-- 

Regards
     Stephen

Post a reply to this message

Darren New wrote:
> I remember reading of an Ada project where the customer was complaining
> the vendor's compiler was too slow. The vendor looked at the code,
> basically said "WTF mate?" and pointed out that using packages nested
> dozens of levels deep (the equivalent of templates referring to
> templates recursively dozens of times) are going to be slow to compile,
> and they asked the customer why they picked that technique. The customer
> pointed out that it was in the vendor's sample files. The vendor pointed
> out that *that* sample file was a compiler stress-test designed to
> validate the compiler doesn't choke even under awful programming
> practices. :-)
> 

I recall that, couldn't find the exact quote anywhere though.

"WTF? Why the hell are you coding like that?"
"Well, we modelled it after one of your samples"
"That wasn't a sample, that was a compiler stress-test!"

Post a reply to this message

On Mon, 20 Oct 2008 19:27:16 -0200, Nicolas Alvarez wrote:
> Invisible wrote:
>> So Spirit is probably faster
>
> To run, sure. But it probably takes even longer than your average Boost
> library to compile :)
>
> (seriously, many boost libraries are like compiler stress-tests)

It indeed does. Here's an error message I got from gcc
when I was developing a certain project using the Spirit parser.

http://bisqwit.iki.fi/kala/gargantuan-gcc-error-message.bz2
(bzip2 -compressed text for your convenience).

Mind you, that file contains just _one_ error message,
together with its "instantiated from" lines.

-- 
Joel Yliluoma - http://iki.fi/bisqwit/

Post a reply to this message