Comment by jblow

10 years ago

To get the parentheses right, you have to parse the language.

There is an extensive body of literature on parsing that goes back decades. Most of it I don't think is that useful. But some of it is about parallel parsing. If you are interested, there are quite a number of people with something to say about it. However, the speed wins in practice are not very big.

On the other hand, if you just write the parser so that it's fast to begin with, you don't really have a problem. The language I am working on parses 2.5 million lines of code per second on a laptop, and I have only spent a couple of hours working on parser speed. To do this it does go in parallel, but it goes parallel in the obvious way using ordinary data structures (1 input file at a time as a distinct parallel unit). So it's not "parallel parsing" in the algorithmic sense.

Why do you need to parse the language to get parens correct? For most languages, comments and strings will need to be considered, but neither of these requires doing a full parse.

Of course, I don't disagree with your point that a fast parser makes making a distinction here less useful. However that number sounds interestingly large, without context, do you have more info I can read about it?

  • Parsers don't often handle degenerate cases very well, but degenerate cases are quite common in text editing. (Think about how often work in progress code might actually parse correctly.)

    Lexers/tokenizers handle degenerate cases very well (after many years of being used for syntax highlighting in IDEs), and some parsers intended for IDE consumption are getting much better at dealing with degenerate cases (the Roslyn family and Typescript in my experience have some very interesting work put into this area), but most parsers still have a long way to go. (Especially, because many of the most common parser-generators themselves have never bothered to concern themselves with degenerate cases.)

    • You make a good point (not only is parsing unnecessary, lexing-only/"ad hoc" analysis can be more resilient for many of the tasks in an editor), however your phrasing makes it sound like you're disagreeing with me, but I don't understand with which part of my comment. Could you expand?

      1 reply →