51–60 of 105 posts
For many people, and I include myself in that group, the class in compiler and language design is where all of the concepts being taught in CS came together into a bigger and more rich picture. A common observation that it was like learning "how" music was written rather than just "playing" music. That said, everyone who learns to program usually learns more than one language. For me, it was after about the fifth lan…
Check out "Writing An Interpreter In Go" https://interpreterbook.com/ It uses Golang to make an interpreter for a simple C-Style language and it's "only" 200 pages long. I'm about a third in and my head is smoking.
By using Lisp-y language you can ignore the tedious and uninteresting task of parsing for the real meat of compiling and (some) optimizing.
There is much good advice given by others here regarding the implementation of languages. However, if you really want to get into language design, there is one area that you should/need to understand (as far as I am concerned) and that is how to specify the meaning of your language and its constructs. If this is not done, you end up with too many gotchas and special cases in how you will do things. I have found too m…
You pose the question but don't seem to answer it - this area is called semantics, and there are several approaches and notations you can use. Types and Programming Languages by Pierce is the most common starting point.
Take a top-down approach, and focus on semantics over syntax.
If you want to design a new language, think of a moderately sized representative example of a problem you have day-to-day, and write a sketch of a program in the magical pseudocode you wish you were able to write. It doesn’t have to be a big problem, or a big language, just a concrete problem domain.
Then, piece by piece, investigate the details of how to make that notation work in reality: how do you parse, typecheck, optimise, compile, and implement a runtime for it? Figure out the smallest set of core primitive operations needed to express the semantics of your language—that’s your core calculus, which you can prove things about or use as an intermediate representation in your compiler.
In addition, a productive strategy for producing an actual implementation, followed in some compiler courses, is to build your compiler (or interpreter) in such a way that you always have a working implementation at every step—of a language that starts small and grows over time.
For example, write a program that takes in a “hello world” or other primitive program written in your language, and just produces the expected output without any analysis—the result of the program, or a binary (machine code, .NET/JVM bytecode, &c.) with the right behaviour. Then, incrementally add features—outputting other messages, doing other things than simple input/output, evaluating complex terms, rejecting invalid programs, and ultimately taking advantage of the semantic features that make your language unique. This style of development helps encourage you to write a test suite of increasingly complex example programs, which are an essential part of a language implementation—you don’t need to follow strict rules like TDD, but you do need to test everything.
Specifically Chapter 5 - Language Structures and Compilers
Write a simple interpreter for a C-like language by parsing it into a syntax tree, constructing a stack of symbol tables, and evaluating the nodes.
Once that works, write a version that emits code for a stack-based virtual machine (a simple stack machine written concisely might eat just a few screenfuls of code).
When that works, symbolically evaluate the stack bytecode into variable references, pick a simple architecture (I like MSP430 for this but ARM will do) do a trivial register allocator, implement register spill to the stack, and emit real code.
Then read Lisp In Small Pieces.
Worked OK for me!
A surprising amount of the complexity you might perceive in a "real" programming language just comes down to how expressions are parsed.