Hacker News Reader

Delphi's IDE implements its code completion etc. using the real compiler parser, and has done for over a decade. The chief "tricks" are skipping method bodies other than the one the cursor is in, and otherwise having a fast parser (hand-written recursive descent / operator precedence hybrid in Delphi's case).

But completion / analysis etc. is still triggered on a pause after typing - it's not fast enough to run on every keystroke, not least because of basic reasons like having to page in referenced modules.

I agree that parsers or grammars should be reusable. I'd put parsers ahead of grammars, because frequently in practice there are some ambiguities around the edges in production grammars that are resolved using type and semantic analysis. What you want is something which can turn the text into a parse tree with the thorniest ambiguities already resolved.

Of course, doing interesting analysis with that tree is still pretty awkward if you have things like overloads in your language, to take a single example which needs pretty complete type analysis to resolve correctly in all cases.

But completion / analysis etc. is still triggered on a pause after typing - it's not fast enough to run on every keystroke, not least because of basic reasons like having to page in referenced modules.

Well, not to mention that you wouldn't want to be corrected after each keystroke anyway. "Yes, I know 'whil' is not correct, that's "why" I'm about to type an 'e'".

I actually wish there was more of a delay in Qt Creator's syntax highlighting - of course the stuff I'm working right now isn't correct yet.

With a fast parsing algorithm, you could parse as a programmer types, unlike the current syntax highlighting editors which use only rough pattern matching instead of having a real parse tree. Imagine seeing syntax errors the moment you type them.

That's what Xcode 4 does with the new Clang/LLVM machinery inside.

Instead of using our extra CPU power to parse with less efficient algorithms, I think we should use our extra CPU power to integrate parsing more deeply into our editors/IDEs. With a fast parsing algorithm, you could parse as a programmer types, unlike the current syntax highlighting editors which use only rough pattern matching instead of having a real parse tree.

Don't Eclipse/Visual Studio/Emacs Semantic/etc. already do this? The struct trick you mention would be new to me, but unless I'm missing something, seeing syntax errors the moment you type them and getting context-sensitive completion are features that have been available since before I started programming (in 2002).

ambiguity is useful for error recovery/error detection. also, some languages have ambiguity in their syntax (ML). I don't buy the 'optimization' argument. there is no reason we cannot have our cake and eat it - ambiguity and incremental parsing.

as for incremental parsing in ides, you may enjoy this thesis: http://jeff.over.bz/papers/2006/ms-thesis.pdf

finally;

I think parser-generators are unpopular because people would prefer to just write code, rather than compile something else to automatically generated code that is nigh on unreadable.

I think the popularity of regexes is due in part to the ease of which they can be embedded or used within the host language - either with syntactic sugar, or simply as a library.

combinators (parsec especially) hit a sweet spot of being able to write code that handles parsing succinctly, without having to conflate your build or auto-generate source.

i'd really prefer a library I can load and manipulate the grammar from, over yet another syntax and compiler in my tool chain.

(ps. (i'm saddened by the lack of left recursion support in gazelle))

> I think parser-generators are unpopular because people would prefer to just write code, rather than compile something else to automatically generated code that is nigh on unreadable.

I agree that generating source code is annoying, which is why Gazelle does not do it. It takes a VM approach instead; the parser is either interpreted or JIT-ted.

> I think the popularity of regexes is due in part to the ease of which they can be embedded or used within the host language - either with syntactic sugar, or simply as a library.

That is exactly what Gazelle is trying to do.

> i'd really prefer a library I can load and manipulate the grammar from, over yet another syntax and compiler in my tool chain.

Gazelle always loads its grammars at runtime. There's a compiler also, but it just generates byte-code that the runtime loads. But you can run the compiler at run-time too if you want.

If you'd rather build a grammar programmatically than use a syntax meant for it, more power to you (Gazelle will support it). But that doesn't seem to match your regex case: people specify regexes with a special syntax, not by building up an expression tree manually. The latter seems like a lot of work to me, and such grammars will not be reusable from other languages, but that might not be important to you.

> (ps. (i'm saddened by the lack of left recursion support in gazelle))

What is a case where you would really miss it, that isn't addressed by a repetition operator (*) or an operator-precedence parser?

I would like to say: awesome!

And yes most of my left recursion fetish would be covered by an operator precedence parser/left corner parser

> I think parser-generators are unpopular because people would prefer to just write code, rather than compile something else to automatically generated code that is nigh on unreadable.

Also, a manual lexer/parser can introduce context when necessary. E.g. Python has significant whitespace. The lexer (with context knowledge of indentation width) can easily emit indent/dedent tokens, so the grammar is context free. With a tool like ANTLR you have to do wierd stuff to parse Python.

Programming languages older than 10 years or so are usually not context-free. For example C needs context to parse "A*B", because the meaning depends on whether "A" is a type or a variable. Recent programming languages usually try to be LL(1), which is why the keywords "var", "val", and "def" become so popular.

> The biggest thing that could be improved about parsing IMO is for grammars to be reusable.

This is not solely about parsing. There is the semantic analysis phase afterwards, which is just as hard. In your example "sizeof(struct MyStruct) = 96" must be related to the type definition of MyStruct. Then the compilation target must be asked for the sizes of the primitive types inside the struct. Effectively, the IDE could as well execute the compiler (with a parameter not to generate code) and parse the output.

Maybe an IDE wants a complete frontend as a library. Feed in the file, retrieve the AST. Insert callbacks for warnings and errors instead of printing to stderr.

An interesting problem would be to reparse parts of a file. The parser would have to get an AST node and a file position, to "resume" parsing from there. This only works, if there is no context apart from the AST, though.

It's nice to see such optimism yet I have to (hopefully respectfully) criticize to your approach.

I used to work in the same office as Bob Jervis who wrote Turbo C back in the day, and he said he never uses parser generators. Clearly something is wrong if the tools that have all the weight of the theory and formalisms are losing to coding parsers by hand.

When a number of really smart people do something, there might just be reason for it. They might be wrong too but if you're going to call them wrong, perhaps you should first take the time to figure why they do what they do first.

One thing that should be a red flag is that lots of people still write parsers manually instead of using tools.

Wait! People write programs manually too instead of automatic program constructors. It might be OK.

The thing about "manually" constructing a parser is that it not a terribly difficult task once one has a strong grasp of the relation between languages specification and recursion. Manually constructing a recursive descent parser also doesn't involve throwing out the formal specification of the language. Rather, you transform your language specification until you shape it into a set of productions which can be captured by a series of recursive function calls (essentially taking the language to Greibach Normal Form but there are a number of short cuts you can take once you're comfortable with this process). It is not a ad-hoc affair but it does allow you make add ad-hoc optimizations for the particular actions that are needed or not-needed in the results of your parsing.

The road block to any reusability in parsers is that a language's grammar exists at a different logical level than a single function, object or piece of data.

Specifically, two programs that parse the same grammar would likely need to do different things at different times in the parsing process. The simplest thing to create the code for each of these programs separately and then let the compiler optimize the code, tossing out the things I don't need.

But any "general purpose" parser library more or less has taken the code and fully compile it - turn it into an AST or the equivalent and then let the programmer deal with the results (the way Python or Ruby do reflection). Such an approach work for some things but it inherently isn't going to be very fast because it doesn't which parts of the code the final user is not concerned with.

Just consider. The simple way of removing a single "i" tag from strings like "<i>help me</i> he said" is never going to be "load XML parser, issue commands, close XML parser". A single loop removing the offending character is going to beat this "algorithm" a thousand times over. Manual parser generation more or less allows you to boil down your parser to this.

Qt creator finds syntax errors as I type and I remember Visual Studio doing the same. I don't think either uses the same parser as their respective compilers because they have to be more forgiving - otherwise they would fail to arrive at the piece of code you're actually editing but I could be wrong. I know most syntax highlighting is custom written but again, isn't that hard to custom write.

> They might be wrong too but if you're going to call them wrong, perhaps you should first take the time to figure why they do what they do first.

Right back at'cha. You have criticized my approach without understanding it.

> Specifically, two programs that parse the same grammar would likely need to do different things at different times in the parsing process. [...] But any "general purpose" parser library more or less has taken the code and fully compile it - turn it into an AST or the equivalent and then let the programmer deal with the results

Actually, that's not what Gazelle does. If that were the best you could do, I'd agree with you.

At its lowest layer, Gazelle offers event-based parsing. It's like SAX, where the approach you have described is like DOM.

The way you would remove a single "i" tag from a string is by registering a callback that gets called when "i" is encountered, and another callback that gets called when the corresponding closing tag is encountered.

And once I've optimized Gazelle to generate really fast machine code, I doubt your "single loop" is going to beat me. For example, did you know that with SSE you can do 16 byte-wise compares in a single instruction? Are you going to put SSE instructions in your "single loop"?

Finally, your "single loop" is probably not going to correctly handle the case where the "i" tag is inside a CDATA section, and is therefore not actually an "i" tag at all. This is the biggest problem with ad hoc parsers -- nobody seems to realize how incomplete/buggy they are.

> Wait! People write programs manually too instead of automatic program constructors. It might be OK.

I think a better analogy would be: you would know C compilers weren't good enough if people were always writing in assembly instead. Writing a parser manually instead of using an abstraction like a CFG is like writing in assembly language.

> Just consider. The simple way of removing a single "i" tag from strings like "<i>help me</i> he said" is never going to be "load XML parser, issue commands, close XML parser". A single loop removing the offending character is going to beat this "algorithm" a thousand times over. Manual parser generation more or less allows you to boil down your parser to this.

However, the parser-way might enable you code to handle tricky XML stuff. E.g. namespaces: "<html:i>help me</html:i>".

Either can be useful depending on the situation.

A just-in-time compiler would be able to do the quick loop also if this loop ran somewhat frequently.

The point is each of these approaches makes sense in a given context and so you can't say that any of them are relative "hacks" or "stone-age" or whatever.

I could imagine a future language/system that would allow a few XML-parser commands on a line to be translated into a single loop. But we aren't there yet - the solution isn't in just algorithms but the whole development. Haberman's "program" of improving parsing is noble. The problem is he's articulated as simply bolting algorithms in and you need more than that (ie, you need a language that can lots of compile-time futzing about).

Visual Studio is very often confused at edit-time. The parser should not be more forgiving, it should just remember the parts that once were correct but are now invalidated by further edits. That way, updates that keep local correctness would continue to work even if some parts prevented the correct parsing of the whole file.

> Imagine seeing syntax errors the moment you type them.

Eclipse does that. Or are you talking specifically only about C?

Resharper for Visual Studio (a refactoring tool) uses Antlr to parse the C# code.

There is an off-the-shelf C++ parser. IIRC it costs about $100k per year.

I forgot the name, but this is it:

http://www.edg.com/index.php?location=c_frontend