News for hackers. Stuff that matters.
Re:Show HN: How to write a recursive descent parser by Drup on Monday March 20, 2017 @11:05AM (#13914789)
I don't understand why so many people glorify hand-written parsers. Maybe because they never used good parser generators (not unlike type systems and Java) ?

Personal opinion: writing parsers is the least interesting part of an interpreter/compiler, and your grammar should be boring if you want your syntax to be easy to understand by humans.

Boring, in this case, mean LL(*), LR(1), or another well known class. Just pick a damn parser generator and get the job done quickly, so you can spend time on the really difficult tasks. The grammar in this article is LR(1) and is trivial to implement in yacc-like generators, locations tracking and error messages included.

Bonus point: since your grammar stays in a well known class, it's much easier for other people to re-implement it. You can't introduce bullshit ambiguous extensions to your grammar (C typedefs, anyone ?). This article gives a good explanation of this: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...

Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @11:49AM (#13915150)
Hello, I work on the C# compiler and we use a handwritten recursive-descent parser. Here are a few of the more important reasons for doing so:

* Incremental re-parsing. If a user in the IDE changes the document, we need to reparse the file, but we want to do this while using as little memory as possible. To this end, we re-use AST nodes from previous parses.

* Better error reporting. Parser generators are known for producing terrible errors. While you can hack around this, by using recursive-descent, you can get information from further "up" the tree to make your more relevant to the context in which the error occurred.

* Resilient parsing. This is the big one! If you give our parser a string that is illegal according to the grammar, our parser will still give you a syntax tree! (We'll also spit errors out). But getting a syntax tree regardless of the actual validity of the program being passed in means that the IDE can give autocomplete and report type-checking error messages. As an example, the code "var x = velocity." is invalid C#. However, in order to give autocomplete on "velocity", that code needs to be parsed into an AST, and then typechecked, and then we can extract the members on the type in order to provide a good user experience.

My personal opinion is that everyone should just use s-expressions. Get rid of this whole debate :P

Re:Show HN: How to write a recursive descent parser by Drup on Monday March 20, 2017 @01:09PM (#13915817)
While I agree with you those 3 points are extremely important, it turns out there is at least one parser generator that can do all of it: http://gallium.inria.fr/~fpottier/menhir/

It supports both incremental parsing and an API to inspect and recover incomplete ASTs (which powers Merlin, the IDE-like thing for OCaml). It provides stellar debugging features for ambiguous grammars and a way to have good error messages (which is used in compcert's C parser and facebook's reason).

So, it's not impossible. Most parser generators are not that good, though.

Re:Show HN: How to write a recursive descent parser by Arelius on Monday March 20, 2017 @04:31PM (#13917422)
Yeah, so we can spend a long time trying to find a parser generator that can solve all of our problems in the language that we use, which may or may not exist. Or you could just spend the same time to just write the parser. It turns out that writing a parser just isn't that hard, and in the time that you spend wavering on which parser generator to use, you could have most of your parser done.
Re:Show HN: How to write a recursive descent parser by wtetzner on Monday March 20, 2017 @11:09PM (#13919557)
> and in the time that you spend wavering on which parser generator to use, you could have most of your parser done.

Maybe, but if you want all of the features mentioned above (incremental parsing etc.), then writing a parser becomes much more complicated.

Re:Show HN: How to write a recursive descent parser by bd82 on Tuesday March 21, 2017 @08:17AM (#13921483)
Or you could take the middle ground and use a library meant to make it easier to create hand built parsers. as opposed to a library that generates a parser for you.

* Repo: https://github.com/SAP/chevrotain

* Online Playground: http://sap.github.io/chevrotain/playground/

This handles the repetitive parts such as lookahead functions creation or Parse Tree building, while also providing advanced features such as error recovery or syntactic content assist (auto complete).

* ECMAScript family of languages supported (JavaScript/TypeScript/CoffeeScript).

Re:Show HN: How to write a recursive descent parser by fooker on Tuesday March 21, 2017 @06:13AM (#13920942)
Not really, it is rather easy to hack features into a recursive descent parser. That is is the main reason almost all production compilers are written that way.

With a parser generator, it quickly becomes a game of designing your language and its semantics around the limitations of the generator you are using.

Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @01:27PM (#13915990)
That is super impressive! I can't find the part on incomplete AST or AST reuse in their reference docs though.
Re:Show HN: How to write a recursive descent parser by dsp1234 on Monday March 20, 2017 @06:19PM (#13918149)
Details about the "incremental" mode are listed in the documentation PDF[0] at section 9.2

Here are the first couple of paragraphs:

"In this API, control is inverted. The parser does not have access to the lexer. Instead, when the parser needs the next token, it stops and returns its current state to the user. The user is then responsible for obtaining this token (typically by invoking the lexer) and resuming the parser from that state. The directory demos/calc-incremental contains a demo that illustrates the use of the incremental API.

This API is “incremental” in the sense that the user has access to a sequence of the intermediate states of the parser. Assuming that semantic values are immutable, a parser state is a persistent data structure: it can be stored and used multiple times, if desired. This enables applications such as “live parsing”, where a buffer is continuously parsed while it is being edited. The parser can be re-started in the middle of the buffer whenever the user edits a character. Because two successive parser states share most of their data in memory, a list of n successive parser states occupies only O(n) space in memory."

There does not appear to be a specific mention of having the partial AST available.

[0] - linked from their front page and available at http://gallium.inria.fr/~fpottier/menhir/manual.pdf

Re:Show HN: How to write a recursive descent parser by def-lkb on Monday March 20, 2017 @06:23PM (#13918175)
Hi,

I did a part of the incremental parsing in Menhir and the whole recovery aspect. I can try to explain a bit. My goal was Merlin (https://github.com/ocaml/merlin/), not research so there is no paper covering the work I am about to describe. Also as of today only incrementality and error message generation are part of upstream version of Menhir, but the rest should come soon.

# Incrementality, part I

The notion of incrementality that comes builtin with Menhir is slightly weaker than what you are looking for.

With Menhir, the parser state is reified and control of the parsing is given back to the user. The important point here is the departure from a Bison-like interface. The user of the parser is handled a (pure) abstract object that represents the state of the parsing. In regular parsing, this means we can store a snapshot of the parsing for each token, and resume from the first token that has changed (effectively sharing the prefix). But on the side, we can also run arbitrary analysis on a parser (for error message generation, recovery, syntactic completion, or more incrementality...).

# Incrementality, part II

Sharing prefix was good enough for our use case (parsing is not a bottleneck in the pipeline). But it turns out that a trivial extension to the parser can also solve your case.

Using the token stream and the LR automaton, you can structure the tokens as a tree:

- starts with a root node annotated by the state of the automaton

- store each token consumed as a leaf in that tree

- whenever you push on the automaton's stack, enter a sub-level of the tree (annotated by the new state), whenever you pop, return to the parent node

This gives you the knowledge that "when the parser is in state $x and $y is a prefix of the token stream, it is valid to directly reduce the subtree $z".

In a later parse, whenever you identify a known (state number, prefix) pair, you can short-circuit the parser and directly reuse the subtree of the previous parse.

If you were to write the parser by hand, this is simply memoization done on the parsing function (which is defunctionalized to a state number by the parser generator) and the prefix of token stream that is consumed by a call.

In your handwritten parser, reusing the objects from the previous parsetree amounts to memoizing a single run (and forgetting older parses). Here you are free to choose the strategy: you can memoize every run since the beginning, devise some caching policy, etc (think about a user (un)commenting blocks of code, or switching preprocessor definitions: you can get sharing of all known subtrees, if this is of any use :)).

So with part I and II, you get sharing of subtrees for free. Indeed, absolutely no work from the grammar writer has been required so far: this can all be derived by the parser generator (with the correctness guarantees that you can expect from it, as opposed to handwritten code). A last kind of sharing you might want is sharing the spine of the tree by mutating older objects. It is surely possible but tricky and I haven't investigated that at all.

# Error messages

The error message generation is part of the released Menhir version. It is described in the manual and papers by F. Pottier (like http://dl.acm.org/citation.cfm?doid=2892208.2892224, PDF available on http://gallium.inria.fr/~fpottier/biblio/pottier_abstracts.h...).

I might be biased but contrary to popular opinions I think that LR grammars are well suited to error message generation.

The prefix propery guarantees that the token pointed out by the parser is relevant to the error. The property means that there exist valid parses beginning with the prefix before this token. This is a property that doesn't hold for most backtracking parsers afaik, e.g PEG.

Knowledge of the automaton and grammar at compile time allow a precise work on error messages and separation of concerns: the tooling ensures exhaustivity of error coverage, assists in migration of error messages when the grammar is refactored, or can give an explicit description of the information available around a given error.

This is not completely free however, sometimes the grammar needs to be reengineered to carry the relevant information. But you would have to do that anyway with a handwritten parser and here the parser generator can help you....

If you have such a parser generator of course :). Menhir is the most advanced solution I know for that, and the UX is not very polished (still better than Bison). It is however a very officient workflow once you are used to it.

So LR is not the problem, but existing tools do a rather poor job at solving that kind of (real) problems.

# Recovery

In Merlin's, recovery is split in two parts.

The first is completion of the parsetree: for any prefix of a parse, it is possible to fill holes in the tree (and thus get a complete AST).

This is done by a mix of static analysis on the automaton and user guidance: for major constructions of the AST, the grammar writer provide "dummy" constructors (the node to use for erroneous expressions, incomplete statement, etc). The parser generator then checks that is has enough information to recover from any situation, or point out the cases it cannot handle.

It is not 100% free for the grammar writer, but for a grammar such as OCaml one it took less than an hour of initial work (I remember only a few minutes, but I wasn't measuring properly :)). It is also a very intuitive step as it follows the shape of the AST quite closely.

The second part is resuming the parse after an error (we don't fill the whole AST every time there is an error; before filling holes we try to look at later tokens to resume the parse). There is no big magic for that part yet, but the heuristic of indentation works quite well: constructions that have the same indentation in source code are likely to appear at the same depth in the AST, and this is used to decide when to resume consuming tokens rather than filling the AST. I have a few lead for more disciplined approaches, but the heuristic works so well that it isn't an urgency.

# Conclusion

I would say that if I had to write a parser for a language for which a reasonable LR grammar exists, I will use a (good) parser generator without hesitation. For the grammars of most programming languages, LR is the sweet spot between parsing expressivity and amenability to static analysis.

Re:Show HN: How to write a recursive descent parser by amelius on Monday March 20, 2017 @06:53PM (#13918347)
Nice! By the way, I think the Dragon Book needs an update on incremental parsing :)
Re:Show HN: How to write a recursive descent parser by PaulHoule on Monday March 20, 2017 @12:40PM (#13915566)
Another problem I have with parser generators is that they often have an awful API.

For instance, working in a OO language such as C#, I often want to turn the parse into an AST build out of idiomiatic objects.

Most compiler-compilers use the same "callback hell" interface that was used for the original yacc in the 1970's. Thus you wind up writing error-prone code.

Conceptually, the grammars used in compiler-compilers aren't that much more complex than regexes (you just have named sub-expressions, the possibility of recursion, and possibly some specification of associativity) Yet, regexes are probably used 100x more in application software development.

In many systems programming areas I think often using unergonomic tools is a badge of pride, it proves how smart you are, so I think ergonomics are often not taken seriously by those who develop the tools.

Re:Show HN: How to write a recursive descent parser by electrum on Monday March 20, 2017 @09:00PM (#13918961)
ANTLR4 automatically generates a visitor for your grammar that you can use to translate into your own idiomatic objects: http://jakubdziworski.github.io/java/2016/04/01/antlr_visito...

We use this in Presto for parsing SQL and generating an immutable AST:

https://github.com/prestodb/presto/blob/master/presto-parser...

https://github.com/prestodb/presto/blob/master/presto-parser...

Re:Show HN: How to write a recursive descent parser by specialist on Monday March 20, 2017 @03:11PM (#13916822)
I'm curious about your incremental re-parsing strategy.

I wasn't smart enough to figure out how to adapt these strategies to my LL(k) grammars (late 90s). Maybe someone's figured this out.

Efficient and Flexible Incremental Parsing TIM A. WAGNER and SUSAN L. GRAHAM

https://www.researchgate.net/profile/SL_Graham/publication/2...

Re:Show HN: How to write a recursive descent parser by maxbrunsfeld on Monday March 20, 2017 @06:39PM (#13918258)
FWIW, I'm developing a library based on the technique outlined in this paper (and others by Time Wagner). Like the original paper, it uses LR(1) (and GLR), not LL(k).

The library itself is here: https://github.com/tree-sitter/tree-sitter

and here are some existing grammars:

  * https://github.com/tree-sitter/tree-sitter-javascript
  * https://github.com/tree-sitter/tree-sitter-go
  * https://github.com/tree-sitter/tree-sitter-ruby
Re:Show HN: How to write a recursive descent parser by YeGoblynQueenne on Monday March 20, 2017 @12:22PM (#13915417)
Out of curiosity, how many people do you have working on the parser?
Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @12:48PM (#13915629)
We don't have specific people that do parsing; if your feature needs changes to the parser, then you make those changes.
Re:Show HN: How to write a recursive descent parser by stcredzero on Monday March 20, 2017 @02:33PM (#13916501)
One nice thing about using recursive descent, is that your parser "is just a normal program." It's also a potential problem, but every substantive project needs coding standards anyhow.
Re:Show HN: How to write a recursive descent parser by kodfodrasz on Monday March 20, 2017 @12:40PM (#13915569)
I guess 12 or more poeple are on the new keyword team, always ready to jump on a new language feature added. After all it happens every 3-5 years.

Adding a new keyword to a parser is a huge work, even tests need to be written!

hint: irony

Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @12:59PM (#13915735)
The best part about going open source was being able to outsource the bikeshedding discussions to the community!

(Just kidding, we still do them internally too)

Re:Show HN: How to write a recursive descent parser by Jare on Monday March 20, 2017 @12:54PM (#13915687)
> My personal opinion is that everyone should just use s-expressions.

Aren't S-expressions particularly problematic for providing autocomplete hints?

Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @01:02PM (#13915755)
I don't see why they would be any better or worse than another grammar choice.

It might be true that s-expressions would make people prefer certain semantic decisions that would be difficult to analyze for autocomplete.

Re:Show HN: How to write a recursive descent parser by Jare on Monday March 20, 2017 @02:38PM (#13916543)
To clarify: do you think there are sets of semantic decisions using S-expressions that would still "get rid of the whole debate", and not make autocomplete harder in practice?

(not that it's important of course, but your remark made me curious, and the reactions to my question even more so)

Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @03:28PM (#13916955)
Autocomplete is most commonly used on structures in order to find out which fields and methods that structure contains.

If you used an s-expression based grammar that still had fields and methods, then you'd get the exact same experience.

    foo.bar. <- autocomplete here
vs

    (foo.bar.)
            ^ autocomplete here
Re:Show HN: How to write a recursive descent parser by Flow on Monday March 20, 2017 @04:02PM (#13917206)
Except that in some Lisps where you have multi-methods or generated field accessor methods you'd probably would write it backwards. Maybe like this:

    (. (bar foo) ...)
      ^ cursor is here
Re:Show HN: How to write a recursive descent parser by lemming on Monday March 20, 2017 @07:36PM (#13918567)
I develop Cursive, an IDE for Clojure code. I handle this for Java interop in a couple of ways. Cursive does type inference (or propagation, really) in the editor, so if you have enough type hints it knows what the type of a symbol is. This allows a few tricks (| is the caret):

If you've already typed the form and are just changing the head symbol, you're golden:

  (.myMeth| my-object)
If Cursive can accurately determine the type of my-object, you'll only see the relevant completions, i.e. methods from that type.

If you're using Clojure's threading forms, Cursive understands that:

  (-> my-object .myMeth|)
also works.

Otherwise, if you're typing out a new form you can do:

  (my-object .myMeth|)
and when you auto-complete the forms will be switched around to:

  (.myMethod my-object |).
Re:Show HN: How to write a recursive descent parser by jkcxn on Tuesday March 21, 2017 @02:31AM (#13920276)
Maybe a stupid question because I don't know much clojure but I'm curious. How can you be sure that -> is threading macro and my-object is what you think it is at compile time? Can't macros change the entire meaning of an expression?
Re:Show HN: How to write a recursive descent parser by lemming on Tuesday March 21, 2017 @06:38AM (#13921035)
That's not a stupid question at all, and yes they can. Cursive works using static analysis rather than runtime introspection, so I need to teach it how macro forms work. This uses an extension API internally which will eventually be open so that users can add support for their own forms or forms in libs they use. Cursive uses the information about the macro forms to do symbol resolution, so that's currently a best effort in the presence of forms it doesn't understand yet. It works pretty well though since Clojure doesn't tend to use as many macros as, say, Racket. Doing full resolution means that I can distinguish clojure.core/-> from some other symbol with the same short name, it's not just using the -> text.

One correction - this is all done at edit time, not compile time. At compile time there's no issue since all macros are expanded to the core language.

Re:Show HN: How to write a recursive descent parser by Jare on Monday March 20, 2017 @09:18PM (#13919025)
Thank you all for your comments. Swapping the forms is pretty neat!
Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @04:51PM (#13917554)
Sure. That's a property of the language, not S-Expressions.

It's just like how SQL decided to write all their queries backwards making it impossible to do good autocomplete.

Re:Show HN: How to write a recursive descent parser by dragonwriter on Monday March 20, 2017 @01:06PM (#13915791)
Lisps tend to be because of dynamic typing and macros; s-expressions themselves don't seem to add any particular difficulty.
Re:Show HN: How to write a recursive descent parser by fiddlerwoaroof on Monday March 20, 2017 @03:49PM (#13917103)
Common Lisp via slime has quite good autocomplete because it extracts the information from a running system and doesn't have to infer it from the source code.
Re:Show HN: How to write a recursive descent parser by breatheoften on Monday March 20, 2017 @02:00PM (#13916250)
Are there any statically typed S-expression languages?
Re:Show HN: How to write a recursive descent parser by glenda on Monday March 20, 2017 @02:08PM (#13916314)
Typed Racket is the only one I've come across but I'm sure there are a few more.
Re:Show HN: How to write a recursive descent parser by munificent on Monday March 20, 2017 @03:17PM (#13916870)
Shen is another one:

http://www.shenlanguage.org/

There are also a ton of hobby languages that are statically typed and use s-exprs so the author doesn't have to spend as much time on syntax.

Re:Show HN: How to write a recursive descent parser by shanemhansen on Monday March 20, 2017 @04:25PM (#13917375)
Clojure does allow type annotations that are used to avoid reflection. https://clojure.org/reference/java_interop#Java%20Interop-Ty...

    (defn len2 [^String x]
      (.length x))
Re:Show HN: How to write a recursive descent parser by bbcbasic on Monday March 20, 2017 @12:20PM (#13915392)
Thanks it's great to hear from someone that makes the tools I use everyday.

> My personal opinion is that everyone should just use s-expressions. Get rid of this whole debate :P

C# 8 maybe?

Re:Show HN: How to write a recursive descent parser by tyoverby on Monday March 20, 2017 @12:49PM (#13915642)
The "best" part about project Roslyn is that if someone wanted to make an s-expression frontend, they could plug that into the compiler.
Re:Show HN: How to write a recursive descent parser by marxidad on Monday March 20, 2017 @12:32PM (#13915498)
Untyped S-Expressions would be taking a step back from a C# perspective.
Re:Show HN: How to write a recursive descent parser by e12e on Monday March 20, 2017 @01:55PM (#13916211)
I don't see how s-expressions are inheritently less "typed" than utf-8 text?

Have a compiler target dialect that expects "(int 5)" and "(int x)" have a type-inference step that target such "typed" s-expressions?

Re:Show HN: How to write a recursive descent parser by UK-AL on Monday March 20, 2017 @11:16AM (#13914872)
There's a reason nearly every actually used programming language parser is hand rolled.

It's easier for adding errors messages, debugging and diagnostics tools. I know modern parser generators can do this as well. It's just easier in a recursive descent parser.

Learning to use parser generator is a learning experience in itself. Most can be pretty complicated to use, once you get past the basics. Yet nearly every programmer can understand a recursive descent parser. You can debug them using standard breakpoints for example. Yet parser generators can output quite difficult error messages, unless you have had a parser education.

In practical implementations, recursive descent can be optimised to be really fast, and to use a low amount of memory.

Re:Show HN: How to write a recursive descent parser by wruza on Monday March 20, 2017 @11:31AM (#13914989)
>I know modern parser generators can do this as well

Can you please list them here? These without build/runtime dependencies on java and other non-default platforms.

That alone would make the whole thread.

Re:Show HN: How to write a recursive descent parser by paulddraper on Monday March 20, 2017 @02:28PM (#13916467)
ANTLR has hooks you can use to help the error message.

Though it uses Java. What is a "default platform"?

Re:Show HN: How to write a recursive descent parser by userbinator on Monday March 20, 2017 @09:53PM (#13919193)
Yet nearly every programmer can understand a recursive descent parser.

...and I also hypothesise that nearly every programmer will come up with some form of recursive descent parser if asked to parse a recursive language --- without ever having heard of the term "recursive descent" nor parser generators. It's the intuitive, "natural" solution to the problem.

Re:Show HN: How to write a recursive descent parser by dukoid on Monday March 20, 2017 @11:10AM (#13914835)
Because the problem is not parsing alone, but doing type checks / ambiguity resolution during parsing and linking up the parse tree with type information etc.

See http://stackoverflow.com/questions/6319086/are-gcc-and-clang...

Also, you people may just want to learn how to build a parser.

Shameless plug if you need a small but flexible expression parser for java: https://github.com/stefanhaustein/expressionparser

Re:Show HN: How to write a recursive descent parser by Drup on Monday March 20, 2017 @11:16AM (#13914878)
My point is precisely that, if you are creating your language from scratch, you shouldn't have to do that. Those are mistake needed because the C grammar is full of cruft (and the C++ one is even worse).

It's much better, for a new language, to separate type checking from parsing completely, and to avoid any ambiguity.

Re:Show HN: How to write a recursive descent parser by PaulHoule on Monday March 20, 2017 @12:47PM (#13915625)
In theory yes, in practice, if you want to make a serious improvement in the ergonomics of programming languages for "ordinary" folks, you have to face up to the fact that natural languages don't make an artificial distinction between different aspects of language.
Re:Show HN: How to write a recursive descent parser by Ericson2314 on Monday March 20, 2017 @11:37AM (#13915053)
> Because the problem is not parsing alone, but doing type checks / ambiguity resolution during parsing and linking up the parse tree with type information etc.

Holy shit, people think that's a good idea? Pipelines please!

Re:Show HN: How to write a recursive descent parser by munificent on Monday March 20, 2017 @12:19PM (#13915383)
It's often faster to do as much as you can in a single pass, and language front ends are one of those areas where squeezing every last drop of performance out still really matters.
Re:Show HN: How to write a recursive descent parser by Drup on Monday March 20, 2017 @01:17PM (#13915889)
It's actually faster to separate things, because you will be able to implement them cleanly. Having a good pipeline such as "text -> AST -> typed AST -> IR -> .... -> ASM/VM code" is very valuable.

The costy parts are the middle layer optimization anyway. Typechecking time, for a well written type checker, is not that big.

Re:Show HN: How to write a recursive descent parser by Ericson2314 on Tuesday March 21, 2017 @11:29AM (#13923052)
I think incremental compilation is a far more elegant and efficient way to shorten debug cycles.

Also makes IDE stuff easier too.

Re:Show HN: How to write a recursive descent parser by masklinn on Monday March 20, 2017 @11:18AM (#13914891)
> Maybe because they never used good parser generators (not unlike type systems and Java) ?

Is there such a thing as a "good parser generator" where "good" includes "generates at least decent error messages"?

> Personal opinion: writing parsers is the least interesting part of an interpreter/compiler, and your grammar should be boring if you want your syntax to be easy to understand by humans.

Hardly. Humans have way less trouble with ambiguity than computers do, as demonstrated by, well, the entire history of programming languages. If syntactic simplicity and regularity were what humans seeked, the primary languages in use would be Lisps, Forths and Smalltalks, not C derivatives.

Re:Show HN: How to write a recursive descent parser by marcosdumay on Monday March 20, 2017 @11:29AM (#13914971)
What are those "good error messages" in the parsing stage you keep talking about?

I don't remember I've ever used a language that reported anything different from "syntax error at line X" at this stage.

Re:Show HN: How to write a recursive descent parser by btilly on Monday March 20, 2017 @11:59AM (#13915224)
As a random example from Perl, Unmatched ( in regex... is the error when you open a capturing group in a regex and fail to close it.

In a recursive descent parser, this type of error is very easy to generate because working top down you know what you are in the middle of trying to do when you hit the error. But a bottom up parser lacks that context - it just knows where it was when it got stuck.

Re:Show HN: How to write a recursive descent parser by megous on Monday March 20, 2017 @11:43AM (#13915112)
You can get a parser generator to automagically list you expected (non-)terminals at this point. It may not be helpful though, depending on the location of the error. But it is something at least.
Re:Show HN: How to write a recursive descent parser by stcredzero on Monday March 20, 2017 @02:19PM (#13916392)
writing parsers is the least interesting part of an interpreter/compiler, and your grammar should be boring if you want your syntax to be easy to understand by humans.

In my (admittedly limited) experience, most grammars for programming languages that are supposed to be easy on humans end up being harder to parse. (See below) One notable exception is, of course, Smalltalk.

One criticism I have of this article, is that it is written in a way that obscures the fact a top-down parser is an LL(k) parser. I'd posit that sticking to an LL(1) grammar is a great way to wind up with a simpler syntax that lacks sticky syntactic sugar that will be hard to optimize and build software tool for later on. (AT least for your personal learning hobby project. But in that case, at least use a separate Lexer!)

You can't introduce bullshit ambiguous extensions to your grammar

Ruby: http://po-ru.com/diary/ruby-parsing-ambiguities/

Re:Show HN: How to write a recursive descent parser by munificent on Monday March 20, 2017 @03:22PM (#13916906)
> One criticism I have of this article, is that it is written in a way that obscures the fact a top-down parser is an LL(k) parser.

Yes, I worry a lot that I conveniently designed Lox to be LL(1) which is why the parsing is so straightforward, but I don't spend a lot of time telling the reader about that fact.

At the very end, there's an aside that hints at that, but that's about it. Unfortunately, the chapter is quite long already, and it's hard to even start talking about what makes one syntax easier to parse than another without having to go pretty deep into lookahead, LL(k), left-factoring, etc.

So, for better or worse, I chose to leave it out. I look at this book as a guided tour of the language space. The reader may not know that they are being carefully herded away from the sketchy parts of town and not realize that things may appear cleaner and safer than they actually are when you start exploring on your own.

At the same time, it does ensure that their first experience in the area is a happy, positive one. My hope is that that will give them enough momentum to explore more, run into some of those nasty spots, and still have the fortitude to overcome them.

Re:Show HN: How to write a recursive descent parser by zeptomu on Monday March 20, 2017 @02:50PM (#13916645)
> I don't understand why so many people glorify hand-written parsers. [...]

I would say because they make the easy things easier, but the hard things harder.

If one tries to do something more elaborated, like getting a data structure for the AST (most tutorials just build simple "accepters" which I find unacceptable) and passing it to different functions - which is a standard procedure in an interpreter or compiler - things are not so trivial anymore and you need to know your generator really well and hope that your use case is supported.

Another approach are parser generators like you find in functional languages, and I really like them, as you do not have to learn an additional language and they compose incredible well. They can blow-up your memory requirements but this is another story.

Re:Show HN: How to write a recursive descent parser by marssaxman on Tuesday March 21, 2017 @04:57PM (#13926147)
I've never used a parser generator that was worth the extra time and hassle incurred by adding code generation and another implementation language into the project. Parsing just isn't that hard, and having your parsing code written in the same language as the rest of your compiler pays off over the long run.
Re:Show HN: How to write a recursive descent parser by specialist on Monday March 20, 2017 @03:02PM (#13916753)
To better understand how generated parsers work. ANTLR LL(k) thru LL(*) is largely a black box for me. I can't say writing my own helped my ANTLR skills. But hopefully I'm doing less trial and error now.
Re:Show HN: How to write a recursive descent parser by camus2 on Monday March 20, 2017 @11:58PM (#13919774)
> I don't understand why so many people glorify hand-written parsers.

it is a learning exercise. Once you have written one, you can choose to go for yacc and co, or stick with hand written ones.

Re:Show HN: How to write a recursive descent parser by zzzcpan on Monday March 20, 2017 @12:27PM (#13915452)
I don't understand your complaint, it's faster and easier to implement a recursive descend parser, than to use a yacc-like parser generator. It's not much of a choice, isn't it?
Re:Show HN: How to write a recursive descent parser by btilly on Monday March 20, 2017 @12:31PM (#13915493)
If you know the toolchains, that is backwards. It is faster and easier to use a parser generator, and easier to figure out what it is doing when you read one. Plus it performs better.

But recursive descent gives you more flexibility and better error messages.