Combinators (Was Re: Application letters at the Haskell workshop: suggestion)

Eray Ozkural (exa)
Sun, 16 Sep 2001 17:44:24 +0300

Hash: SHA1

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) <>
Comp. Sci. Dept., Bilkent University, Ankara
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see