5 ms·

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 expres

by throwaway2016a 10y ago

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.

greenshackle2 10y ago
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.
- kd0amg 10y ago
  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).
  - greenshackle2 10y ago
    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.
  - btilly 10y ago
    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.
    - kd0amg 10y ago
      Yes, NFA! DFA only if it's LL(1).
  - deleted 10y ago
    [deleted]
  - ejanus 10y ago
    Is regular grammar same as context-free grammar?
    - oldmanhorton 10y ago
      It is not - see https://en.wikipedia.org/wiki/Chomsky_hierarchy 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.
- ejanus 10y ago
  Is your codebase public? I would like to take a look.
  - greenshackle2 10y ago
    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/ https://github.com/jbchouinard/sixteen/
vidarh 10y ago
> 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.
- acchow 10y ago
  But most compilers have a parser. Scheme doesn't need one ;) http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/ http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...
  - protomikron 10y ago
    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?
    - DonaldFisk 10y ago
      The read function the parser.
    - richard_todd 10y ago
      ... 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.)
      - protomikron 10y ago
        > ... 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.

greenshackle2 10y ago

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.

kd0amg 10y ago
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).
- greenshackle2 10y ago
  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.
- btilly 10y ago
  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.
  - kd0amg 10y ago
    Yes, NFA! DFA only if it's LL(1).
- deleted 10y ago
  [deleted]
- ejanus 10y ago
  Is regular grammar same as context-free grammar?
  - oldmanhorton 10y ago
    It is not - see https://en.wikipedia.org/wiki/Chomsky_hierarchy 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.
ejanus 10y ago
Is your codebase public? I would like to take a look.
- greenshackle2 10y ago
  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/ https://github.com/jbchouinard/sixteen/

vidarh 10y ago

> 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.

acchow 10y ago
But most compilers have a parser. Scheme doesn't need one ;) http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/ http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...
- protomikron 10y ago
  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?
  - DonaldFisk 10y ago
    The read function the parser.
  - richard_todd 10y ago
    ... 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.)
    - protomikron 10y ago
      > ... 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.