Stackless & String-processing

[Graham Matthews]

<graham at sloth.math.uga.edu> wrote:
> I don't really see why using parser combinators means that you cannot
> optimise. You are not precluded from using regular expression parsers
> as primitive parsers, nor are you precluded from using LALR(n) parsers
> as primitive parsers. Hence you can optimise those parts of your
> parsing with automaton if you want. So I don't really understand your
> criticism.
Fernando Pereira (pereira at research.att.com) wrote:
: The monadic approach mixes up the search structure for pattern matching
: or parsing (what is elsewhere represented as an automaton) with other
: data processing. Unless your optimizer can solve the halting problem,
: it will not be able to determinize otherwise determinizable control
: structures because it cannot figure out the data dependencies.

You have totally misunderstood what I said. I said "you can have regular
expression parsers as primitive parsers". There is no need for the compiler
to "solve the halting problem". The programmer is free to use regular
expression/automaton techniques where he/she wants. Such parsers take
strings and return ASTs. They can then be combined with other parsers
as if they were primitive parsers. This is purely a programming issue
and has nothing to do with the halting problem, compiler optimisations,
etc. To make it clearer a programmer can do

	p = some_parser_that_uses_automaton :: String -> Ast
	q = some_parser_that_uses_some_other_technique :: String -> Ast
	pq = p <&> q
		where <&> is the combinator that sequences parsers

Where does the halting problem enter into this? The program has to write
the autoton code him/herself, but there are fp tools that do this, much
like for example Yacc.

<graham at sloth.math.uga.edu> wrote:
: > Also as I said parser combinators are really more of a sequencing 
: > technique -- one that applies nicely to parsing.
Fernando Pereira (pereira at research.att.com) wrote:
: Sure, but so what? Automata are too a sequencing technique, usable for
: many other things besides pattern matching and parsing. The fundamental
: difference is that automata-theoretic approaches separate neatly the
: representation of sequences from what one wants to do with the parts of
: those sequences, allowing optimizations that are difficult to obtain
: within general-purpose programs.

I still don't understand why you think the combinator approach is so
inefficient, given that you can have automaton based parsers embedded
in it at will. 

The point of saying that combinators are more a of sequence tool than
a parsing tool is to point out that they are more general than automaton.
You can program much richer sequencing with combinators than you can
with automaton (not suprisingly). For those parts of your parser or
sequenceing where you only need automaton you use automaton as outlined
above. But where you need more powerful sequencing you have it in the
combinator approach.


<graham at sloth.math.uga.edu> wrote:
: > Can you explain why? I don't see it, since you can have reg expr parsers
: > and other such fast parsers as primitive parsers that you combine ...
Fernando Pereira (pereira at research.att.com) wrote:
: Either you put all the interesting stuff in separate primitive parsers,
: in which case I'm not sure what's the point of the monadic approach,

Err isn't this what I said you do ... I said "you can have regular
expression parsers as primitive parsers". The point of the monadic
approach is that is allows you to cleanly program arbitrary sequencing
when you need it. Moreover it makes for sound software engineering,
etc. That too is what I said in the last mail ....

graham
-- 
            The girls is all salty, the boys is all sweet, 
                      the food ain't too shabby 
                    an' they piss in the streets
    In France, way down in France, way on down, way on down in France