Combinators (Was Re: Application letters at the Haskell workshop: suggestion)
Eray Ozkural (exa)
Sun, 16 Sep 2001 17:44:24 +0300
-----BEGIN PGP SIGNED MESSAGE-----
On Sunday 16 September 2001 04:30 pm, Frank Atanassow wrote:
> A bit off-topic, but after some experience using combinator parsers in
> Haskell (not just Parsec) where the lexical and syntactical bits were done
> in the same grammar, I concluded that the traditional separation between
> the two, a la Lex and Yacc, does indeed have its merits for just this
> reason: by stratifying the grammar you introduce an abstraction boundary
> which, I think, agrees better with the way programmers, at least, have
> learned to reason about syntax.
I don't think so. Trying to separate those into distinct functions is messy.
Using combinators is elegant, and if you've read any papers about them you
should have seen that you don't need to emit any "abstract syntax trees" or
such. The more complex the language is, more benefits there are in a unified
formalism. In NLP, people have shown excellent uses of such formalisms. There
are works that span all the way from phonology to semantics.
That is, established convention is not necessarily the right way to
accomplish a task.
- From a theoretical view point, it is most desirable to be concise and
abstract which is what combinatorial parsers seem to facilitate. They fit
surprisingly well to the functional programming paradigm, and they are a good
way to denote compositional semantics.
About context sensitive grammars, I don't have a code that would show how it
is done for the kind of "context-sensitivity" found in programming languages
but perhaps somebody could make a small demonstration?
I won't avoid advertising some of my personal opinion. You see, trying to
separate syntax and semantics in a compiler is only blind devotion to
Chomsky's non-sense preachings in linguistics. There is no such thing in the
world. There is syntax only if there is semantics. I recall an account of how
gcc people had to go back and forth between syntax and semantics. Too many
kludges to get it right. The truth is that:
a) semantics is as formal as syntax
b) syntax in most cases is a shadow of semantics
Therefore, formalizing both at once is reasonable. Of course, this is the
naive explanation and the whole debate goes a lot further but I guess it is
enough for an already off-topic discussion.
Eray Ozkural (exa) <email@example.com>
Comp. Sci. Dept., Bilkent University, Ankara
GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org
-----END PGP SIGNATURE-----