News for hackers. Stuff that matters.
Re:Writing Your Own Programming Language by throwaway2016a on Thursday November 10, 2016 @10:15AM (#12921014)
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 whole "grow your own parser" method doesn't scale to more complex languages (you need better tooling for that and/or a lot firmer grasp of the concepts) and I would be concerned that people would try to extend this tutorial and go down a rabbit hole.

Edit: I know this from experience because when I was in high school I wrote a compiler this way (let's call it the naive way). And then in college I learned how to do it with BNF and code generators and the difference in maintainability and code complexity between the two is ridiculous. I would never do it the old way again, even for a toy language.

Re:Writing Your Own Programming Language by vidarh on Thursday November 10, 2016 @10:44AM (#12921324)
> Most more complex languages you'd use something like lex and yacc which would add quite a bit more overhead to the tutorial.

Very few production compilers use lex/yacc type parsers, because error handling and recovery is painful. Most end up with hand-written recursive-descent parsers.

Re:Writing Your Own Programming Language by acchow on Thursday November 10, 2016 @12:22PM (#12922268)
But most compilers have a parser. Scheme doesn't need one ;)

http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

Re:Writing Your Own Programming Language by protomikron on Thursday November 10, 2016 @01:01PM (#12922636)
Why is it so often stated, that Scheme doesn't need a parser? I mean the AST is simpler then in other languages, but at the end of the day, you have to parse SEXPs, don't you?

I mean let's say you evaluate

  > (+ 2 3)
You have to parse the string "(+ 2 3)" and will then evaluate it to 5?
Re:Writing Your Own Programming Language by richard_todd on Thursday November 10, 2016 @01:38PM (#12922952)
... reading sexp's is technically parsing but it is so far removed from something like a C parser that it's really not the same animal. I mean, you can write a function to build a list from a sexp in a few minutes, while even a basic hand-written C parser will take days/weeks/months depending on your familiarity.

So, that's a reason why it is said. (edit: also, if the course implements scheme IN scheme, then you don't need a parser because the host scheme can do it for you.)

Re:Writing Your Own Programming Language by protomikron on Thursday November 10, 2016 @01:51PM (#12923078)
> ... reading sexp's is technically parsing but it is so far removed from something like a C parser that it's really not the same animal.

Yeah it is obviously a lot easier to parse than traditional, imperative languages like C. I just do not like the phrase, as it gives this "magic" vibe to Scheme. I mean its syntax is beautiful and simple, but there is definitely no magic there.

Re:Writing Your Own Programming Language by nickpsecurity on Thursday November 10, 2016 @09:15PM (#12926846)
McCarthy's basic evaluator for LISP in a page or two in a high-level language (esp LISP). That's not magic but good design gets plenty close. ;)
Re:Writing Your Own Programming Language by mncharity on Thursday November 10, 2016 @11:37PM (#12927890)
"It's easy to parse scheme" is one of those pretty stories that is often repeated but untrue. A similar one is "it's easy to implement scheme in scheme".

It is true for toy compilers of language subsets, and those are often done. And few people ever explore real scheme compiler internals.

The readers in real scheme compilers are generally a large pile of ugly code. A decade or so ago, I recall Bigloo's was the cleanest I'd found, with a regular expression based parser framework. I can't quickly find the files to link. But after wading through many other implementations, it was a breath of fresh air. But not simple, and not small.

Here's a quick quote from a Chicken changelog: "2.7 Fix several bugs (expt, integer?, rational?, <=, >=, eqv?, -) found by importing the number tests from Gauche and writing an extensive test for number syntax edge cases. Complete rewrite of number parser (it should fully conform to the R7RS superset of R5RS number syntax now)."

Re:Writing Your Own Programming Language by acchow on Thursday November 10, 2016 @04:22PM (#12924497)
we mean it doesn't need a parser in the traditional sense of a LR or LL grammar (or more complicated) with generated table or even a hand-rolled parser with lookahead.

Sure, it needs a "parser" in the sense of a FSA + a stack.

Re:Writing Your Own Programming Language by DonaldFisk on Thursday November 10, 2016 @01:13PM (#12922720)
The read function the parser.
Re:Writing Your Own Programming Language by JoelMcCracken on Friday November 11, 2016 @10:09AM (#12931252)
I was recently reading http://book.realworldhaskell.org/read/using-parsec.html, which made me think about this very thing. I never liked working with parser generators because they felt so unwieldy, but I wondered if a system like parsec might be extensible enough to simplify the entire process greatly.
Re:Writing Your Own Programming Language by vidarh on Friday November 11, 2016 @10:34AM (#12931495)
Yes, libraries/frameworks like that are certainly easier to work with than generators.
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @10:36AM (#12921235)
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.
Re:Writing Your Own Programming Language by kd0amg on Thursday November 10, 2016 @10:47AM (#12921352)
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 by btilly on Thursday November 10, 2016 @12:11PM (#12922156)
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 by kd0amg on Thursday November 10, 2016 @01:40PM (#12922977)
Yes, NFA! DFA only if it's LL(1).
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @11:38AM (#12921892)
Right, with the syntax I chose there ends up being, IIRC, 6 different forms (<op>, <op> <arg1>, 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 by ejanus on Thursday November 10, 2016 @12:25PM (#12922299)
Is regular grammar same as context-free grammar?
Re:Writing Your Own Programming Language by oldmanhorton on Thursday November 10, 2016 @02:10PM (#12923238)
It is not - see https://en.wikipedia.org/wiki/Chomsky_hierarchy for the where these terms come from. Context-free grammars are strict supersets of regular grammars and cover the vast majority of programming language constructs.
Re:Writing Your Own Programming Language by ejanus on Thursday November 10, 2016 @12:21PM (#12922255)
Is your codebase public? I would like to take a look.
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @02:10PM (#12923240)
Sure. It's a work in progress, my latest changes are not on Github yet, I'll probably push tonight.

Keep in mind it's a personal project, the assembler is written in not the prettiest idiosyncratic Python.

https://github.com/jbchouinard/sixteen/