Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing Your Own Programming Language

github.com

Post reply on HN
Print view View original

21–30 of 95 posts

Re: Writing Your Own Programming Language

#21

Post by kd0amg »

greenshackle2 wrote: post #18
throwaway2016a wrote: post #14

Earlier quoted context omitted.

Because languages like this map so closely to the AST (as someone else pointed out) you don't need to deal with complexities such as look aheads, regular expressions, and formal syntax definitions (BNFs). I suppose this makes it a good getting started point. Most more complex languages you'd use something like lex and yacc which would add quite a bit more overhead to the tutorial. The danger of these tutorials is the…

I'm writing an assembler for a virtual 16 bit CPU I built, and I hesitated on using BNF. It seemed overkill so I ended up hand-rolling a parser; for an assembler it's straightforward enough, but I can easily see how it could get ridiculous to implement a compiler this way.

I hesitated on using BNF. It seemed overkill

Presumably because there's no real nesting of terms in assembly code? Personally, I find BNF so simple that I'd probably still use it for describing the grammar, but lots of parser generator technology is heavier machinery than required (though a recursive descent parser built from a regular grammar is essentially a DFA if your language/compiler offers tail call elimination).

Re: Writing Your Own Programming Language

#22

Post by zeveb »

tscs37 wrote: post #17
drusepth wrote: post #3

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to impl…

I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head) It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

> It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.

Re: Writing Your Own Programming Language

#23

Post by DonaldFisk »

ufo wrote: post #16
drusepth wrote: post #3

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to impl…

It depends on hoe you are writing your compiler. If you are coding in a high level language, then writing an AST interpreter for a functional language is super simple. You just need to mix first-class functions and an unsurprising expression evaluator and you end up with something really expressive. If you are targeting a lower level language like assembly language then I think an imperative language is easier to do…

That's only because the hardware architecture's designed that way. If your target is a stack machine (with no general purpose registers), a functional language would be just as easy if not easier to generate code for.

Re: Writing Your Own Programming Language

#24

Post by tscs37 »

zeveb wrote: post #22
tscs37 wrote: post #17

Earlier quoted context omitted.

I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head) It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

> It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y. That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.

You're right, I always confuse the many forms of LISP to some certain degree...

Re: Writing Your Own Programming Language

#25

Post by DonaldFisk »

zeveb wrote: post #22
tscs37 wrote: post #17

Earlier quoted context omitted.

I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head) It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

> It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y. That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.

Scheme is a Lisp. Lisp is nowadays a language family, built upon a common core: both programs and data are nested lists of symbols; the interpreter executes by recursively calling eval and apply functions.

Re: Writing Your Own Programming Language

#26

Post by vidarh »

lmm wrote: post #4
simono wrote: post #2

Why do bloggers focus on lexing and parsing? These things should not take up 80% of the article about creating a programming language. This fascination with "how" to build something, without considering "what" and "why", seems to be an issue that gets repeated time after time again.

I found http://hokstad.com/compiler a lot easier to understand than any other compiler tutorial I've seen. Writing a compiler the way you'd write any other program. It does end up with e.g. a distinct parser, but only when the reasons that might be a good idea become apparent.

Thanks :)

Though in retrospect I think it should have been two separate series (and I need to write a few more parts; I'm very close to having it compile itself as of last night).

I think it'd have been better to evolve the initial simple language into an equivalently simple language to parse, and kept the long slog towards compiling Ruby as a separate thing.

Especially as that has complicated things enough to be in severe need of various refactoring (which I'm avoiding until it will compile itself, at which point I'll start cleaning it up while insisting on keeping it able to compile itself..).

The parser itself started out conceptually quite clean, for example, but the Ruby grammar is horribly complex, and I keep having to add exeptions that's turned it quite convoluted. I don't doubt it can be simplified with some effort once I have the full picture, but it's not great for teaching.

Re: Writing Your Own Programming Language

#27

Post by davidkellis »

drusepth wrote: post #3

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to impl…

Lisp, or any prefix or postfix language, is relatively easy to parse and execute (in the case of an interpreter) or translate (in the case of a compiler/translator) because its syntactic structure mirrors the abstract syntax tree (AST) that the semantic analysis phase (i.e. the last of the 3 phases identified in the post) will traverse as it either executes (interpreter) or translates (compiler). In other words, the parse tree is nearly identical to the AST. That isn't true of Algol-like languages, and so the syntactic analysis and semantic analysis phases of a compiler/translator of Algol-like languages is more complex. That's why Lisp, or really any prefix or postfix language, is a good first language to implement, as opposed to something like C.

Re: Writing Your Own Programming Language

#28

Post by tel »

drusepth wrote: post #3

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to impl…

Modeling a pipeline of transformations of a well-understood data type it sort of whatever comes right after "hello world" in functional programming. A compiler is a very scaled up version of this, but it certainly fits naturally with the standard ideas of FP.

Re: Writing Your Own Programming Language

#29

Post by marcosdumay »

drusepth wrote: post #3

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to impl…

The simplest languages around are all functional. And most of them are Lisp idioms.

Besides, when writing a compiler, it's always great if you can ignore the possibility of some value changing. It makes implementation much simpler even more if you go into optimizations. And while you can't completely ignore value mutation on Lisp, it is always explicit, what makes an implementer's life easier.

Re: Writing Your Own Programming Language

#30

Post by mamcx »

simono wrote: post #2

Why do bloggers focus on lexing and parsing? These things should not take up 80% of the article about creating a programming language. This fascination with "how" to build something, without considering "what" and "why", seems to be an issue that gets repeated time after time again.

This is a fair complain. I have read dozens of articles on the matter and honestly, parsing and lexing is the less significant aspect of this:

https://news.ycombinator.com/item?id=10793054

https://www.reddit.com/r/coding/comments/2ocw2r/how_to_creat...

    Exactly. I'm in the pursuit of build one. My first questions? How make a REPL, a debugger, how implement pattern matching, type checking, if a interpreter can be fast enough, if possible to avoid to do a whole VM for it, etc...
    Exist a LOT of practical questions that are left as "a exercise for the reader" that need clarifications.
In the end, the parsing steps can be summarized as:

- Do lisp/forth if wanna do the most minimal parsing and do a lisp

Or:

- Use a parse generator, if not care about the quality of this

Or:

- Use a top-down parsing by hand, if wanna some control

ANY OTHER OPTION is non-optimal, and will divert from the task, EXCEPT if you wanna do something novel.

If will let aside the parsing stuff, we can put more in the hard and more rewarding aspects.

Post reply on HN