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

31–40 of 95 posts

Re: Writing Your Own Programming Language

#31

Post by vidarh »

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 agree, which is why I started my own series, as lmm mentioned, with showing simple ways of (ab)using gcc to figure out how to do simple/primitive code-generation, and built up from that, instead of building down from lexing/parsing.

Lexing/parsing is important of course, but it's been done to death, and for most of the simple types of languages people tend to use for teaching, it's a simple problem.

Code generation, on the other hand, is still pretty poorly covered, in my opinion, and something people tend to struggle with a lot more, even if you resort to tools like LLVM (and that's fine if that's what you want, but I'd argue you should try a lower level approach at least once to understand some of the challenges)

Re: Writing Your Own Programming Language

#32

Post by vidarh »

lmm wrote: post #7
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…

Not having to deal with a statement/expression distinction makes it a lot easier. Functional languages often have a simpler syntax with fewer special cases. (Though there are other languages like this e.g. Smalltalk)

I agree in general.

Though Wirth-ian languages, like Pascal, Modula-II and Oberon are good examples of languages that are very simple to parse despite not being functional. Though they are slightly more complx than some functional languages, you can prototype a hand-written parser for them in a day if you've got a bit of experience..

E.g. the Oberon-07 grammar takes up 1.5 pages of BNF [1]of which the first third of a page or so represent the lexer symbols (you don't need a separate lexer module for most of these languages).

[1] Page 166 and 17 of the language report (which incidentally only spends 17 pages to describe the entire language...) https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Repor...

Re: Writing Your Own Programming Language

#33

Post by greenshackle2 »

inimino wrote: post #11
keithb- wrote: post #9

Earlier quoted context omitted.

I think you're asking the right questions. I would assume that your class targeted Lisp because SICP uses it. While that is a great resource, it is light on details when it comes to the end game: runtime. If you are developing a language today and you aren't considering runtime, then you are just writing macros. Lexing, and parsing are not trivial tasks, but powerful tooling already exists for these. Compiling means…

I'm not sure what you mean by "runtime" here and I'm having a little trouble seeing what you're getting at.

Runtime means program execution, basically.

With steps 1 and 2, you're just translating between different program representations. You could hand-write your programs as syntax trees directly if you really wanted to, and you wouldn't even need those steps. It would be a bit more work, but not insanely so; Lisp syntax looks a lot like a syntax tree already, and some people are perfectly happy writing Lisp.

Step 3 is where you go from 'code' in one form or another (usually AST), to an actual process that's executing on the machine, either through interpretation or compilation. It's where most of the magic happens. You have to turn your AST into a series of machine instructions that will i) do what the code says ii) in an efficient manner.

Sometimes achieving i) at all is hard; it's not immediately clear how to implement certain high level operations using machine instructions. Sometimes there are obvious ways to do it, but there are also much less obvious ways that are much faster (more efficient). Finding those ways is 'optimization'.

Unlike steps 1 and 2, which can be done by hand relatively easily, trying to execute your program by hand, for any non-trivial program, would be an absolute nightmare.

(The exception is very low level languages, like assembly, where your language maps almost 1-to-1 with machine instructions. In that case step 3 is trivial. But if you're designing a language today it's probably not an assembly language.)

Re: Writing Your Own Programming Language

#35

Post by kd0amg »

jedimastert wrote: post #10
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.

What is the problem there? I'm confused by your comment

One problem is that syntax is just one (rather shallow) part of the design of a programming language, but it's one that gets a lot of attention because everyone who's used two programming languages can tell that it's a point where languages differ. Semantics (rules about what blobs of syntax mean) is a much more interesting way for languages to differ, but most "build a language" tutorials I (and probably GP) have seen don't seem aware that there are even decisions to be made there. The "your own" bit in the title is also a bit upsetting for a post that hands the reader a language and its implementation instead of talking about something of the reader's own design.

Re: Writing Your Own Programming Language

#36

Post by greenshackle2 »

kd0amg wrote: post #21
greenshackle2 wrote: post #18

Earlier quoted context omitted.

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 eliminatio…

Right, with the syntax I chose there ends up being, IIRC, 6 different forms (, , etc.), which can't be nested. Some of those forms share patterns which could be described as a nested grammar, but I just abstracted them in the parser code as functions (i.e. functions to parse patterns that show up in multiple forms).

I did use a lexer. I wrote an assembler before without using a lexer; using the lexer isn't that much simpler IMO, but it makes it more robust and makes it much easier to systematically catch syntax errors and produce meaningful errors.

Re: Writing Your Own Programming Language

#37

Post by btilly »

kd0amg wrote: post #21
greenshackle2 wrote: post #18

Earlier quoted context omitted.

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 eliminatio…

Don't you mean an NFA?

If there is an ambiguity in the grammar that takes some time to resolve, a recursive descent parser can easily take exponential time. What tail call elimination does is keep you from having a giant call stack, but does not fix the potential (though rare) performance disaster.

Re: Writing Your Own Programming Language

#38

Post by [deleted] »

kd0amg wrote: post #21
greenshackle2 wrote: post #18

Earlier quoted context omitted.

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 eliminatio…

[deleted]

Re: Writing Your Own Programming Language

#39

Post by gshubert17 »

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…

TECS (The Elements of Computing Systems) devotes 2 chapters out of 12 to writing a compiler for a Java-like language. Lexical analysis is more complex, with operators and identifiers and comments in addition to parentheses, numbers, and the letter 's'.

TECS provides a skeleton of a recursive descent parser, with about a dozen different methods to write. The Java-like language has many different kinds of expressions and statements, and this is reflected in the complexity of the parser.

At first the output is an XML tree. Code generation gets an entire chapter. Some of the chapters are straightforward, less than 6 hours of work. But the harder chapters have taken me around 15 hours each. YMMV, but this gives one some idea of the differences between functional languages and procedural languages.

Re: Writing Your Own Programming Language

#40

Post by ejanus »

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.

Is your codebase public? I would like to take a look.
Post reply on HN