Lambda the Ultimate

The idea of a "catch all" rule, as Peri suggested, crossed my mind... maybe I need to take a look at the language machine. My experience thus far is limited to LR, LALR, and Packrat parser generators. Packrat is definitely my favorite of the three from an ease of rule development standpoint. In that system, my concern is that a catch-all rule would be defined like...

known-language-constructs -> declaration / block / ... / unknown-construct

unknown-construct -> any-character+

How do I limit the extent of the catch-all to only cover the text that can't be understood? Once the misunderstood region starts, where does it end? Is this something that can be implemented within the expression grammar itself, or will I need to extend the actual parsing algorithm? Or maybe this is something that the language machine would handle better and I should look at it more closely.

Just so everyone knows, I'm thinking about this parser in the context of a syntax-aware text editor, where the format of the language being edited could be described by attaching properties to text based on a grammar description written by the user... so assuming I could perform the parse on every keystroke (I have no idea how possible this is), I would need to handle intermediate stages where code constructs aren't completely typed out, so that if a programmer is entering code in the midst of existing valid code, the syntax-aware features on the code they have already written aren't compromised by their partially composed addition.

I guess I could ignore parse errors on text that has already been interpreted in one way, but I was hoping for something more robust. Thanks for all your suggestions. I'm going to take a look at various links over the next few days but I thought I'd clarify the issue.

The catch-all rule is just a rule like any other - as I said, the language machine itself has no concept of a syntax error - it just applies the rules that you give it in the same way that a java virtual machine or a physical machine just executes your programs. So it's entirely up to you to decide what the catch-all rule should do.

In fact the grok rulesets that I've put up demonstrate this.

The catch-all rule in the filtering translator (which doesn't flag an error) just consumes one symbol and copies it to the output. So the main analysis then tries to match an expression at the character position one on from where it failed to match. That's the behaviour you want if you are really looking for grammatical patterns that are embedded in ordinary text with no clear delimiter that says where they are.

The catch-all rule in the other two rulesets (groklm and grokreg) skips the rest of the line. This method is pretty crude, and can lead to several successive lines being flagged, but its easy to do. One trouble with sophisticated error recovery is that detailed error messages which identify the wrong error are more confusing than a simple 'eh?' which tells you where to start looking. You on the whole know what you were trying to say. It doesn't, and it's often not easy for it to guess.

I've never tried to write a syntax-aware text editor. The language machine does does operate symbol by symbol, and is intended to be capable of being embedded in other (license compatible) applications, so it might do the trick.

I think you could use the not (!) operator to limit the extent. Something like:

String = "\"" (!"\"" any)* "\""

or

EOF = !any

In this case not doesn't consume anything from the stream and any consumes exactly 1. Also, not would return true at the end of the stream. So with your above example you could do:

known-language-constructs -> ...
unknown-construct -> (!known-language-constructs any)+

I'm not convinced that inventing something fancier would significantly improve the quality of error messages.

The purpose of skipping tokens up to the next likely "synchronization point" (e.g. a semicolon or an end bracket) is generally not to improve the quality of error messages. Rather, it gives the compiler a better chance to report multiple errors at once. So, ideally, instead of compile-fix-compile-fix-compile-fix the programmer would compile-fix-fix-fix-compile. The disadvantage is that these attempts at error recovery can lead to spurious errors getting reported.

My compiler does report multiple errors at once, and I think the effect is good enough. Perhaps this depends on the language being parsed.

I tried now to introduce parse errors in a big source file and look at the error messages. I expected mismatched brackets to cause the worst damage. Well, adding or removing opening or closing braces of toplevel definitions merely yields messages at appropriate points. Only when there are too few opening braces or too many closing braces inside a long function, the parser ends the function prematurely, treats the rest of its body as toplevel definitions, and the compiler complains about many unknown names (of local variables defined above the premature end).

Adding an extra closing bracket of any kind fools the parser, which terminates too many pending subexpressions before eating the bracket, even if the given kind of bracket was not expected there at all. Perhaps this could be improved somehow.

Other changes yield well localized errors and don't seem to require any sophisticated synchronization to avoid many false messages after them. Except for mismatched brackets the messages usually don't explain the nature of the error though, only the location is correct.