21–30 of 105 posts
Then continue enhancing that tiny language, add more features.
Start with an interpreter, they are easier to grasp. You can always add a compiler later.
I grabbed Scheme R5RS standard and started implementing it in Kotlin: https://github.com/kovrik/scheme-in-kotlin
Then added more Clojure-like and Racket-like features, plus some Kotlin features.
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.
Other books burn a lot of time on things like lexing and parsing; this one does not. In the lisp tradition, it assumes s-expressions and gets to the juicy bits of programming language semantics immediately: lexical scope, first class functions, objects, etc.
Types and Programming Languages (TAPL) is required reading, in my opinion: https://www.cis.upenn.edu/~bcpierce/tapl/
Absolutely not for a markdown parser, which is what the author is asking about to get started
Markup languages are not generally thought of as programming languages, but maybe that's an archaic view.
At any rate, 90% of the material in this thread is way overkill if all one wants to do is parse Markdown.
[1] https://ferret-lang.org/ [2] https://nakkaya.com/2011/06/29/ferret-an-experimental-clojur... [3] https://nakkaya.com/2010/08/24/a-micro-manual-for-lisp-imple...
Beautiful Racket[0] is a good starting point that covers a lot of nice small examples that incrementally build up your understanding of the different components involved in making languages. And it uses Racket[1], which incorporates the idea of crafting many small "domain-specific" languages to solve different problems into its entire philosophy[2]. [0] https://beautifulracket.com/ [1] https://racket-lang.org/ [2] ht…
I suggest "Programming Languages: Application and Interpretation", available free here: http://cs.brown.edu/courses/cs173/2012/book/ It's an undergraduate-level programming languages class textbook. Other books burn a lot of time on things like lexing and parsing; this one does not. In the lisp tradition, it assumes s-expressions and gets to the juicy bits of programming language semantics immediately: lexical scope,…
A few other tips:
* Use a parser generator. Parsing is more or less a solved problem; get it out of the way as fast as possible.
* Writing a language that compiles to another language is very helpful as you can often borrow the underlying language's implementation of a feature. Doubly helpful if you can leverage the underlying language's libraries for things like syscalls.
* Make a todo list (I like Trello for this) full of self-contained tasks. Pick one at a time, think through how you would implement that feature, and go to work. Compilers look like a lot of work in the beginning, but if you take one step at a time, one day you'll look back and have accomplished more than you realize. The list can also be helpful to avoid scope creep; add any new ideas to your backlog and deal with them later.
* Write unit tests, as you'll very likely want to refactor something down the line. Once your compiler becomes complex enough, add functional tests that verify entire programs can compile and run and produce the expected output.
Now add error handling (i.e., unrecognized operators, or stack underflow condition) -- figure out what you want to do, such as crash the interpreter with an error message, or return an error and let the user continue.
Now, read up on the Shunting Yard algorithm. This lets you take a regular (infix) math expression, and convert it to RPN (postfix) notation, which you can then feed directly into the RPN interpreter ("stack machine") that you just wrote.
Now look at handling parentheses, which should be covered in the same explanation of the Shunting Yard algorithm.
Next, add in variables in the original stack language, and figure out what minimal changes to the second piece (the algebraic expression parser) you need to do to get it to handle variables.
Finally, add in functions, and you have a simple language. I followed this exact formula when putting together a toy language many years ago, after which I learned how much I didn't know that I didn't know about language design. But I know enough now for a second shot.
Oh, and some other resources to study that may help -- Look for the reference books for the Postscript language. The "Blue" book teaches you Postscript, and I believe it is the "Red" book that tells you enough of the internals for you to write your own Postscript interpreter (or to at least get inspiration on creating you own version of a Stack machine interpreter).
A Forth or a Lisp are simple tasks for an experienced programmer, and even basic ones are really satisfying imho. Seeing simple constructs work in an hour of coding really feels great. I implemented more complex languages (with types) for work which were more like DSLs but in languages less suited for the type of DSL we required, but I find most pleasure doing little Forth (like [1]) or Lisp likes when I am waiting f…
The vast majority of languages are parsed into ASTs of some form, and Lisp is basically directly programming in AST data structures that are executable. Seeing that source code is basically just another data structure to be manipulated and converted was the major "Ah hah!" moment in demystifying compilers for me.
Forth is a great lower-level representation of nested expression evaluation, and sheds a lot of light on how to organize that evaluation in your code generation, converting foo(bar(baz(val),blort(val2))) into a linear stream of operations. Even for register machines, Forth's stack represents the intermediate values that must be retained between expressions in either registers or memory.
Once this basis of how programming languages work is established, then the ideas of new programming language design from the source code perspective can be explored in practical terms.