Hacker News Reader

Comment by laxd | Hacker News Reader

And lose touch with your code and having too deal with problems through a heavily abstracted layer. Great!

You will likely not get a perfect syntax right away. So you will need to iterate on it until you are happy with how it looks and feels, and doing it while developing the compiler yourself will naturally lead to a lot of unnecessary bugs and tech debt.

Alternatively, you iterate using a cheaper method and once you reach a point in which you are content with the syntax, you can consider writing a compiler for it.

You can also avoid iterating on the syntax so you can ship a compiler as fast as possible, but users won't like the syntax and won't use your language.

I have a feeling you haven't worked on parsers or compilers that much if you think you design all of the syntax before building anything

I don't really think of yacc as having much more abstraction than a regex engine -- like in an (NFA-based) regex engine, you're building a big data structure a human wouldn't want to hand-engineer from a declarative specification. (And, like in regexes, you've got good theory backing it.)

You got good theory backing hand-written parsers, and the code is there right in your face. I don't know how a regex engine works.

By "good theory," I mean being able to know properties of the parser as a result of the formalism.

For example, one can prove that any yacc-generated parser never infinite loops and runs in O(n) (at least for the actual parsing; you can write custom code in actions that runs when a construct has been parsed, and of course you can write whatever you want there).

If you hand-write a grammar like the following, you'll end up with an infinite loop without restructuring the grammar; such restructuring is of course much easier if you have written the grammar out, rather than having it implicitly exist in code.

    Expr ::= Expr '[' Expr ']'
    Expr ::= Name
    Expr ::= Int

If you try to naively parse the following, you'll never parse the marked production either. Something like yacc will warn you about this, while an ordinary compiler compiling a hand-written parser won't.

    Stmt ::= Expr ';'
    Stmt ::= Name '=' Expr ';'
    Stmt ::= Expr '[' Expr ']' '=' Expr ';'
    Expr ::= Expr '[' Expr ']'
    Expr ::= Name
    Expr ::= Int

[0] is a good introduction to regex matching, [1] is a good introduction to the algorithm yacc uses, if you want to learn either.

[0]: https://swtch.com/~rsc/regexp/regexp1.html [1]: https://web.archive.org/web/20210507215636/http://web.cs.dal...

> For example, one can prove that any yacc-generated parser never infinite loops and runs in O(n)

Trivial when actually writing the code. And your example of infinite left recursion is basics in parser theory. No one in their right mind would write a hanging program like that, at least not for long.

Left recursion is basic, sure, but it's not a problem for an (LA)LR parser generator like yacc. (Depending on your parse actions, you might even get slightly better memory consumption when using left recursion rather than right recursion.)

Reply on news.ycombinator.com