Re: Application letters at the Haskell workshop: suggestion
Sat, 15 Sep 2001 15:44:52 -0500, Duncan Coutts <dcoutts@cray.com> pisze:
I've been using a few variants: single error, multiple error and multiple error/warning types. I'm also particularly pleased with one that has an extra combinator which allows seperate 'branches' of an expression to combine all the errors (if there are any). That allows multiple *independant* errors to be returned to the user rather than just the first one.
Parsec does this and similar things. It tries to generate reasonable messages of the form "expecting foo, found bar" or "unexpected bar" annotated with source position, making use of labels of higher level syntactic constructs inserted in the grammar as well as individual characters matched. I was also experimenting with this. Recently I had no time to work on this, but I will finish it sometime. It's surprisingly hard to get right in all cases, and there are non-obvious decisions to take. For example consider the grammar 'A | B C' and input 'BZ'. We should report that Z was found where C was expected, but do we also report that possibly B was found where A was expected? Depending on the situation both choices can make sense. It depends whether the fact that input began with 'B' really means that the user wanted to write 'B C' (e.g. if in reality 'B' = 'class'; one rarely writes 'class' when he wants to define something else) or it's probably an artifact of the grammar and the error is at the beginning (e.g. if 'B' is an identifier and the rest doesn't look like any of things which could begin with an identifier; the user could mean anything, even misspelled a keyword). Consider the grammar 'A B C | A B D' and input 'ABZ'. Should we merge errors to the form "expecting C or D, found Z", even if both occurrences of 'A B' are independent and really produced by more complex subgrammars? What if lengths of matching prefixes differ? What if the grammar creator gave meaningful names to 'A B C' and 'A B D' as a whole, so we can't report the error where the mismatch occurred? Another complication: we definitely want to perform cuts after enough has been successfully parsed, so we don't keep it in memory and won't consider backtracking that far. I managed to do this, slightly differently than Parsec, but the grammar creator must be aware of this and insert annotations improving backtracking sometimes. This impacts error messages a bit. Getting right descriptions of what was expected or unexpected is not trivial. For example when there is no separate lexer, we rarely have anything besides raw characters as "unexpected". We have something more descriptive only if the grammar explicitly calls 'unexpected' after successfully parsing something. We really don't want to give a message like "expecting 'e', found 'i'" when the real cause is "expecting 'then', found 'thickness'". Sometimes the grammar doesn't give a name and uses a character predicate, so we don't have any description to put into error message. Sometimes the grammar should explicitly mark some parts to not report them as expected; I was getting silly errors about expected whitespace or begin of comment, even though I surely know that whitespace is possible almost everywhere and error messages should concentrate on syntactic errors instead. There are many corner cases giving surprising results. For the grammar 'A (comma A)* right_bracket' and input 'A,A,A,A,A,A,A,]' we really don't want to say for each of the commas that it could be right bracket instead, even though it would indeed allow to successfully parse this part, because the real error is probably only at the end. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
Marcin 'Qrczak' Kowalczyk wrote (on 16-09-01 09:30 +0000):
Getting right descriptions of what was expected or unexpected is not trivial. For example when there is no separate lexer, we rarely have anything besides raw characters as "unexpected". We have something more descriptive only if the grammar explicitly calls 'unexpected' after successfully parsing something. We really don't want to give a message like "expecting 'e', found 'i'" when the real cause is "expecting 'then', found 'thickness'".
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. (And that boundary is an ideal place to introduce cuts to prevent backtracking.) IMO, the main advantage to combining the two stages is that you can use the same formalism and, in the case of Haskell-style parsers, that you can modularize the grammar into libraries; but viewing lexemes as non-terminals is mostly a disadvantage. More generally, one might imagine stratifying a large grammar even further, by feeding the parser output to another parser. Traditionally we do this to handle context-sensitive conditions because of limitations in Yacc-style parser technology; for example, static analyzers and type checkers are usually context-sensitive. But if your second-stage parser emits abstract syntax trees, maybe you could have a third-stage parser which emits declaration blocks or modules. -- Frank Atanassow, Information & Computing Sciences, Utrecht University Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands Tel +31 (030) 253-3261 Fax +31 (030) 251-379
-----BEGIN PGP SIGNED MESSAGE----- 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.
[snip] 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. Regards, - -- Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr> Comp. Sci. Dept., Bilkent University, Ankara www: http://www.cs.bilkent.edu.tr/~erayo 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 iD8DBQE7pLrIfAeuFodNU5wRAgMTAJ4oW8qtzMm3/jHrMwcJX/d5lELI8gCfcPs2 TYF01IcfQpHfjNh3nLNQ1JQ= =JEZ2 -----END PGP SIGNATURE-----
Eray Ozkural wrote (on 16-09-01 17:44 +0300):
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.
[snip]
I don't think so. Trying to separate those into distinct functions is messy.
It may well be messy for natural language parsing, as I know little about it, but works well for formal languages, which are after all usually designed with a 2-level stratification in mind. If language designers start ignoring that convention, then stratifying a parser might well become less attractive, but error-reporting would become more difficult too.
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.
I think combinators are elegant too. I'm not saying that we should go back to using Lex and Yacc; I'm just saying that there is an advantage in stratifying your parsers, no matter whether you use combinators or conventional tools. The other two major merits I mentioned, namely using a unified formalism and modularity, are things I don't want to lose. But you don't have to. It's as easy to write a 2-level parser with combinators as it is with Lex/Yacc: you just write a lexer and a syntax parser, and compose them as functions.
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?
Sorry, I don't understand this sentence. By "context-sensitive", I mean analyses such as type inference and strictness analysis which depend on information like the set of free variables in a term, or the principal type of a term, which are not context-free properties.
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.
Since I haven't read Chomsky, it would be hard to prove my blind devotion to his teachings. ;) Frankly I don't see how the syntax vs. semantics question quite fits in here, but for the record I subscribe to the algebraic school of syntax and semantics, particularly Lawvere's view, so I also acknowledge a close relationship between the two. But let's avoid philosophical questions, shall we? -- Frank Atanassow, Information & Computing Sciences, Utrecht University Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands Tel +31 (030) 253-3261 Fax +31 (030) 251-379
Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> writes:
Parsec [uses some variant of the error monad] and similar things. It tries to generate reasonable messages of the form "expecting foo, found bar" or "unexpected bar" annotated with source position, making use of labels of higher level syntactic constructs inserted in the grammar as well as individual characters matched.
I think this illustrates an important point about different approaches to exception handling. Parsing is a great example of where error monads are useful: 1) You expect the errors to be the common case instead of the very unlikely case (so you're willing to expend quite a bit of effort to handle them well). Typecheckers also fit into this category. 2) You really care about what the error message looks like. 3) Your code is either all machine generated (e.g., by happy) or you use combinators (e.g., >>= and return) so it is easy to thread the error monad through and to be consistent about doing it. In these case, I think error monads are the best choice. The Hugs/GHC exception catching that Andy Moran described is aimed at situations where these don't apply. Cases include: 1) Your program has to manipulate some real world (and stateful) object and it is not considered acceptable to leave it in some confused state. Examples include leaving windows open when a GUI equipped program crashes, a control system (like the joystick in a plane or controls in a lift) that suddenly stops responding, leaving a database in an inconsistent state, etc. 2) You write a library (e.g., Fran, HGL, etc.) where (hopefully) carefully written library code (which can be as full of error checks as you want) has to invoke user code and, somehow, recover and, either keep going or shut down cleanly. 3) Someone gives you a great library but their code doesn't use the error monad (or whatever) because the code was developed for a less demanding execution environment. The library is large and rewriting it is daunting. 4) You think you've used the error monad consistently and avoided calling all those "unsafe" Prelude functions like "head", "tail", "minimum", and "div" but you've got no good way of checking and you want your code to be robust. 5) You really don't care much which exception you get - as long as you get one. I think the two approaches complement each other rather well (but, of course, I'm biased...). -- Alastair Reid reid@cs.utah.edu http://www.cs.utah.edu/~reid/
participants (4)
-
Alastair David Reid -
Eray Ozkural -
Frank Atanassow -
Marcin 'Qrczak' Kowalczyk