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

41–50 of 95 posts

Re: Writing Your Own Programming Language

#41

Post by acchow »

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

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

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

#42

Post by ejanus »

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…

Is regular grammar same as context-free grammar?

Re: Writing Your Own Programming Language

#43

Post by bloaf »

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.

If I were going to write a programming language for myself, I would lay out the following challenge to myself:

> You are only allowed to store the AST and variable names found by parser. The input to the lexer is not allowed to be persistent.

To do this, your lexer would need to be in some sense invertible, capable of both producing a source-code-representation of an AST given some naming metadata, as well as converting that source-code-representation back to names+AST.

I think that would make the lexing + parsing task worthy of an 80% article.

Re: Writing Your Own Programming Language

#44

Post by protomikron »

acchow wrote: post #41
vidarh wrote: post #20

Earlier quoted context omitted.

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

But most compilers have a parser. Scheme doesn't need one ;) http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

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

#45

Post by protomikron »

gshubert17 wrote: post #39
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 a…

TECS is a wonderful book! I think it was one of the most enjoyable books about CS I have ever read.

Re: Writing Your Own Programming Language

#46

Post by DonaldFisk »

protomikron wrote: post #44
acchow wrote: post #41

Earlier quoted context omitted.

But most compilers have a parser. Scheme doesn't need one ;) http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

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?

The read function the parser.

Re: Writing Your Own Programming Language

#47

Post by psewell »

No. First, understand what the language is for (if nothing, stop here...). Second, make the main design choices (expressiveness of type system, level of control of mutability or lack thereof, etc.). Third, design the type system, with a view to type inference. Fourth, design and define the semantics. Do those last two in a way that will let you test your implementation against these definitions automatically. Fifth, think about sufficiently efficient implementation strategies. Sixth, pick a syntactic style that will be familiar to most of your users. Seventh, design the actual syntax. Eighth, implement it. Ninth, try it out on users and go back to the start. Tenth, rest.

Re: Writing Your Own Programming Language

#48

Post by richard_todd »

protomikron wrote: post #44
acchow wrote: post #41

Earlier quoted context omitted.

But most compilers have a parser. Scheme doesn't need one ;) http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

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?

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

#49

Post by kd0amg »

btilly wrote: post #37
kd0amg wrote: post #21

Earlier quoted context omitted.

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.

Yes, NFA! DFA only if it's LL(1).

Re: Writing Your Own Programming Language

#50

Post by duaneb »

zeveb wrote: post #22
tscs37 wrote: post #17

Earlier quoted context omitted.

I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head) It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

> It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y. That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.

I think you mean lisp-1 (or something). Lisp as a whole is a, erm, genus of languages.
Post reply on HN