Hacker News Reader

Comment by thomasfoster96 | Hacker News Reader

I started making a language a few months ago. I found Douglas Crockford's parser from his Top Down Operator Precedence paper pretty useful, which is here: http://javascript.crockford.com/tdop/index.html

When looking for resources on making toy languages, most of them said not to bother with a parser and use a pre-built solution. I think they're probably wrong - the parser is actually pretty easy (relative to the rest of the process of getting a language working) and at a stretch, fun.

View on HN

I agree. The parsing step is distracting. I have TONS of questions and all the tutorials do the parsing stuff, and stop at doing integer +/*-, maybe vars, maybe if, maybe basic functions!

I'm doing one, and I'm only working on the AST.

I take the idea from this blog:

http://www.trelford.com/blog/post/interpreter.aspx

And from http://www.itu.dk/people/sestoft/plc/. So I get rid of the parsing, and go directly at "how do type checking?", "How I map vars to the environment?", "How make the debugger???", "So, I can have a AST for INTS, BOOLS... now how let the user create your own types???", "How make possible to do macros? I'm not a LISP!", "I'm on F#. How lift the stuff F# already have to do not doing it again???", "What to do: Erlang actors or GO CSP? and how?", "How do pattern matching", "Auto-instrument the code interpreter with dtrace or similar, and why I think this is good?", "I wanna be a reactive language?", "I decide the language be relational. I strongly believe that is amazing. I don't know yet why and how prove it" and a huge list like this...

I don't have a clean answer yet for some of this questions!

Also, I get rid of the idea of make a compiler, and do a interpreter instead. That is another distraction. I suspect that if later on I turn the interpreter to a bytecode, the step to full compilation will be simple, and without solve several questions about the full language the task of rewrite both the parsing and the compiler is not cool.

I have written a few languages here and there. Hope this helps.

They are all separate parts, and you can do them in any order you want.

I like to think of the language as two parts - syntax and features. How do I want the language to look and what features do I want the language to have? The parser and lexer handle the syntax, and the AST handles the features.

This way, I can play around with the syntax of the language a little later.

I would start with a really simple language:

- add expressions, proper infix support for arithmetic

- variables

- if / else / else if

- scoping / functions

- loops if you don't want to just use recursion

then, you can get more advanced:

- lambda expressions / first class functions / closures

- namespaces or types

- macros. if you can make nice looking lisp-style macros for an infix language i would love you

write it as an interpreter, add an llvm backend.

It should be fun. do a little at a time.

w.r.t. macros, have you looked at Elixir, Rust, Sweet.js?

And Nimrod, and (Open)Dylan (which I feel really deserves more attention right now, it's far from being dead!).

I don't know about Rust, but Elixir, Dylan and Sweet.js have Scheme-style, pattern matching based macro systems while Nimrod is a bit unique in having procedural macros conceptually closer to defmacro from some Lisps.

There are also languages where functions can decide whether to evaluate their arguments or not, in the latter case making them work like macros. Io is an example of such a language.

Anyway, infix languages with nice macro systems do exist, it's just that none of them became popular enough (yet?). Also, programmers tend to fear macros for some reason (probably because of they are in C and similar languages) which makes having macros rather low-priority feature for language designers. But it's perfectly possible to create a (very nice!) macro system for infix language and it's been done.

Yep, I have look at nimrod, julia, and barely at dylan. My target syntax is more like python/julia/elixir, and all with relational programing as first-class.

The thing I'm now is how implement macros (and how deeply), not the syntax, is kinda easy to see the way with lisp, but still not with more "normal" syntax.

Also, I have tough (in a way to provide linq-like capabilities) if could be nice to have this = that (evaluate that and put on this) and this ::= that (get the AST on this and later evalualte this) and let decorate the functions with "fun(test:AST.LogicalOp)", so macros at runtime, not just compile time..

> - add expressions, proper infix support for arithmetic

I'd suggest ignoring precedence rules completely here. It generally simplifies the grammar and parser considerably. It doesn't make the language unworkable, either, as long as you allow for grouping with parentheses - Smalltalk does this and it work rather well.

I'd also try working with libraries like PyParsing first before attempting to use mammoth size parser generators. In my experience, especially for simple grammars, this way you can be done with parsing stage with minimum effort and concentrate on the "features" side.

I should have mentioned that precedence rules are pretty wacky.

I wish that in the languages I have worked on that I could just ignore precedence and use parens, but operator precedence is expected.

More or less my exact plan. Plus modules (like in ADA) or components, a way to do parallel/concurrent programing (CSP, Actors, Coroutines?).

Yes! I write my own recursive descent parsers because my programming languages tend to have incremental execution stories to them (you can see an example at http://research.microsoft.com/en-us/people/smcdirm/managedti...). And writing a recursive descent parser really isn't that hard, plus it gives you more flexibility in tweaking error recovery. It also turns out that in industry, auto generated parsers are rarely used (Java is an exception) given performance and error recovery concerns.

On the topic of precedence parsing, they have some really good properties in an incremental context: you can start parsing anywhere and the results will be the same. The problem is expressiveness, and while I came up with some hacks to push them beyond operators, pure recursive descent is much easier to work with (as I learned from Martin Odersky's scalac compiler).

For me the big advantage of using a parser generator is that they let you write things a bit more declaratively. Bottom up parser generators also have the advantage of being able to recognize some grammars that top down parsers can't and they also detect grammar ambiguities at compile time.

That said, handwritten top down parsers are very tweakable and flexible which can be a big plus. In particular, error recovery and things like semicolon insertion. You also get more control over code size and parser performance.

I can see why people do use a parser generator. For me though, the language I'm making has a fairly simplistic syntax, and I value code size and parser performance more than I should.

I have used lex and yacc over almost 30 years numerous, numerous times. I always regretted the decision later. It's a myopic concession for short-term gain.

The tools generate a monstrous, ugly mess that nobody understands, which is linked into your executable.

When it gets complicated, debugging it is a massage session, where you make changes that you don't entirely understand in hopes that a desired behavioral change comes about.

Here is a debugging fail: you cannot just put a break point on a rule, because it's not a function. The state machine is traversing multiple rules at the same time.

In a recursive-descent parser, you can break on a rule and get a call stack.

If you value parser performance you should use a parser generator. Handwritten parsers rarely approach the performance of a fast table-based generated parser.

The example I was thinking of when I mentioned performance was Lua. Instead of generating a syntax tree the recursive descent parser directly spits out bytecode as it goes, which ends up being a big performance win on large source files.

Taking the other side of the argument in my sibling comment to yours: using a parser generator does not preclude directly spitting out bytecode. You can do that in the parse actions instead of building an AST.

A bottom-up parser like that produced by LALR parser generator could make this slightly more awkward, depending on what you need to generate the bytecode, but an LL(k) parser generator (e.g. Antlr) should let you do most of what you'd do with recursive descent, and in a similar way.

I wonder if exists other ways, and find a obscure reference to "slim binaries":

(Asked here)

https://www.reddit.com/r/Compilers/comments/2o78hd/exist_a_s...

Also, I wonder how NOT lost the info that already have the AST in the bytecode conversion, I even have the crazy idea to store everything in a sqlite database, but I suspect will be slow (to read later in the VM...)

Evaluate code for a stack machine symbolically, and you'll end up with an expression tree. RPN bytecode is a post-order traversal of the underlying expression.

Things get a bit more wrinkly with control flow, but you can design bytecode to make it easier to rehydrate that too.

A hand-written lexer should beat most table-based lexers. Hand-written lexers encode the automaton state in the program counter and encode the transitions in code branches, whereas table-based need to use a separate variable and encode the transitions through an indirection followed by a loop.

Parsers are a different kettle of fish entirely though. You hypothetically compare a handwritten parser with a "fast" generated parser. Presumably a handwritten parser will be faster than a "slow" generated parser?

If the language to be parsed is simple and has no ambiguities that need semantic information to resolve (this is not the case for C, for example, never mind C++), a generated parser may save time. Would it be faster than a handwritten parser? I have my doubts, for similar reasons as lexers. The automaton state is stored implicitly via the program counter, and state transitions are in code: similar arguments apply. If the handwritten parser is doing more busywork, such as a lot of recursion to handle precedence in expressions, then it may be slower. But if it uses precedence parsing just for operators, it can get that back, while not losing the benefits of recursive descent style.

OTOH, if you're trying to parse a fairly ambiguous language, you can save a substantial amount of effort with a parallelized LR parser, something that builds a forest of parse trees and discards options that are no longer feasible when more information comes in: a Tomita or GLR parser. Parsing such languages with recursive descent typically involves a lot of extra work building up semantic info as you go, or parsing a simpler form of the language and rewriting with disambiguation later, after further analysis. But GLR parsing is O(n^3) in the worst case. Hand-written may be a lot more work, but it might also be faster. It depends.

I agree. It's not as hard as one might think. I implemented my own handwritten JS parser using TDOP: https://github.com/higgsjs/Higgs/blob/master/source/parser/p...

I think it's more flexible and maintainable this way. I didn't have to wrestle with odd grammar rules. Implementing the JS "automatic semicolon insertion" with parser generator tools seems like it would have been a cluster headache.

I have to admit I also wrote my own parser because I was keen on implementing some pretty advanced macros in it (which I've almost done already). A lot of those parser generator tools assume you have a nice C-like language syntax.

The more you do yourself, the more you will learn. If you're just learning and not trying to build the next big programming language, try and do some of the low level stuff yourself. Write a parser, write a garbage collector and a virtual machine, re-write the compiler in the language itself. Go hog wild.

that's a great suggestion and seems to be useful tip to get started to writing a new language on our own.

> The more you do yourself, the more you will learn.

This is true once you complete the project, but it seems like it can be dangerous: if you start off your mission to make a programming language by soldering components on a breadboard, say, then, you will learn something, to be sure, but you will probably get so embroiled in preliminaries that you will never learn what you intended to learn. (Of course, sometimes learning something other than what you intended is a good thing ….)

Reply on news.ycombinator.com