Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My first fifteen compilers

composition.al

Post reply on HN
Print view View original

31–40 of 77 posts

Re: My first fifteen compilers

#31

Post by eatonphil »

austincheney wrote: post #26

I find many people tend to use the terms parser and compiler almost interchangeably, which is a horrid mistake. These terms are not the same and are not related. So, lets get clear on terminology: * lexer: A scanner. It runs code, typically as a string, through an evaluator and builds pieces based upon known language syntax rules. * parser: A rule evaluator. Parsers typically use lexers to reason about code and then…

Lexers split a program (string) into groups of characters as a list of tokens. Lexical analysis has nothing to do with syntax. Canonically, syntax and grammar are the same thing and parsers deal with that. A parser looks for patterns of tokens that match up to a grammar rule. If all the grammar rules that compose a correct program are parsed, a parser produces an AST that the compiler can act on. Otherwise the parser errors out due to a programmer syntax error.

Re: My first fifteen compilers

#32

Post by mhh__ »

I think the nanopass concept - e.g. lots of well defined IRs passing through a pipeline - is a very good idea for teaching, but I'm interested to see how well it performs and also whether, from the programmers perspective, whether this simplifies code or adds unneeded complexity (Specifically, whether they can be optimized quite as well as a big monolithic compiler).

I'm currently writing a compiler framework - nothing big, as a learning project, and I think I shall try integrate this idea in some way. I feel it would be particularly useful for compiler backends like GCC or LLVM because having well defined pipelines etc. means that one can hook into the framework cleanly (Potentially a huge saving in compile times, e.g. not having to cart around unneeded libraries/symbols).

Re: My first fifteen compilers

#33

Post by wtetzner »

mseebach wrote: post #28
sjrd wrote: post #18

Earlier quoted context omitted.

That's unfortunately not my experience. I'm appalled every time someone tells me "But Scala.js is not a compiler, it's a transpiler, since it compiles to JS!" I assume other language users and authors suffer the same kind of comments on a regular basis.

I'd argue that it's a compiler if it treats JS as a lower language - that the output is simply an intermediate artefact for executing Scala on a JS engine, and not meant for human consumption. If, on the other hand, the output is meant to be developed further by hand, if the output is considered an equivalent and not lower representation, then it's a transpiler.

> If, on the other hand, the output is meant to be developed further by hand, if the output is considered an equivalent and not lower representation, then it's a transpiler.

Which is also still a compiler.

Re: My first fifteen compilers

#34

Post by mhh__ »

mickronome wrote: post #29

I've always thought of compilers as usually lossy graph rewriters with input and output data structures usually being 'flatter' in some sense. Maybe a both simplistic and vague model, but it has served me well enough the few times I needed to build one. This isn't meant to validate or invalidate any other view or definition, but I'm curious if there are any good counter examples or theoretical reasons for characteris…

I can't think of any reason to contradict that as a abstract description of a compiler, although the standard - Practical? - definition of a compiler is probably the more useful of the two.

Graph rewriting is probably a little bit niche, e.g. AFAIK most compilers don't describe what they do as graph rewriting. Perhaps because many compilers do a lot of their work on linear data structures (which are part of a larger graph) like Basic Blocks.

Re: My first fifteen compilers

#35

Post by austincheney »

eatonphil wrote: post #31
austincheney wrote: post #26

I find many people tend to use the terms parser and compiler almost interchangeably, which is a horrid mistake. These terms are not the same and are not related. So, lets get clear on terminology: * lexer: A scanner. It runs code, typically as a string, through an evaluator and builds pieces based upon known language syntax rules. * parser: A rule evaluator. Parsers typically use lexers to reason about code and then…

Lexers split a program (string) into groups of characters as a list of tokens. Lexical analysis has nothing to do with syntax. Canonically, syntax and grammar are the same thing and parsers deal with that. A parser looks for patterns of tokens that match up to a grammar rule. If all the grammar rules that compose a correct program are parsed, a parser produces an AST that the compiler can act on. Otherwise the parser…

The boundaries between lexers and parsers differ by the parser in question.

Grammar and syntax are also different, particularly with regards to XML based languages. Syntax are the rules which define the language while grammars are the conventions that define the context in which artifacts in a language instance are interpreted. Whether a language requires terminating semicolons or curly braces are syntax rules. Whether there is an object schema or namespace concern is a grammar issue.

Parsers commonly produce abstract syntax trees (AST), but can produce output in a variety of formats. I prefer parse tables personally. To say that a parser must produce as AST is rather short-sided and inexperienced.

While parsers typically rely upon lexers and compilers typically rely upon parsers there is no law proclaiming computation must occur in that flow. Lexers, parsers, and compilers are all separate steps that can act independently provided a sufficient configuration.

Re: My first fifteen compilers

#36

Post by wtetzner »

Athas wrote: post #23

I am very fascinated by this notion of teaching compilers by starting at code generation and working backwards from there. I've read about nanopass compilers before, but do they also work well if the compiler is written in a statically typed language? They clearly will for passes that do not change the program representation, but my experience is that it is awkward to define large amount of similar-but-slightly-diffe…

I think you end up needing macros even in statically typed languages to make it convenient. Even the nanopass framework uses macros to define the different representations.

Re: My first fifteen compilers

#37

Post by mseebach »

wtetzner wrote: post #33
mseebach wrote: post #28

Earlier quoted context omitted.

I'd argue that it's a compiler if it treats JS as a lower language - that the output is simply an intermediate artefact for executing Scala on a JS engine, and not meant for human consumption. If, on the other hand, the output is meant to be developed further by hand, if the output is considered an equivalent and not lower representation, then it's a transpiler.

> If, on the other hand, the output is meant to be developed further by hand, if the output is considered an equivalent and not lower representation, then it's a transpiler. Which is also still a compiler.

I would argue that it isn't, if it is, then what's the distinction between a compiler and a transpiler?

Re: My first fifteen compilers

#38

Post by ckok »

Most compilers sort of work this way, except that they don't have an intermediate format. They take source, turn it into tokens, turn it into a tree of sorts, run several passes over it till the end result is reached (whatever the target is).

My own compilers turn 4 different input languages in the same parser tree (Hand written tokenizers/parsers), do several passes over it until it has a very base set of instructions left, at which point it generates code for whatever backend was picked.

The only big difference is that the process outlined in the article has an actual textual intermediate format, if I understand it correctly. Sounds like a lot of work of extra work with little gain, a simpler approach might be to have "ToString" method working on all nodes on all levels that' outputs info clear enough to understand from within a debugger.

Re: My first fifteen compilers

#39

Post by capnrefsmmat »

mhh__ wrote: post #32

I think the nanopass concept - e.g. lots of well defined IRs passing through a pipeline - is a very good idea for teaching, but I'm interested to see how well it performs and also whether, from the programmers perspective, whether this simplifies code or adds unneeded complexity (Specifically, whether they can be optimized quite as well as a big monolithic compiler). I'm currently writing a compiler framework - nothi…

Chez Scheme [0] is written using the nanopass framework, and it's regarded as one of the fastest Scheme compilers in existence [1]. Before it was rewritten to use the nanopass system, Chez's compiler was known for its performance in terms of lines of code compiled per second; the rewrite slowed it down a bit, but the quality and performance of generated machine code improved. Andy Keep and Kent Dybvig wrote a paper about the project [2]. I haven't browsed the Chez source, but it's a good way to answer your question.

[0] https://github.com/cisco/ChezScheme

[1] http://ecraven.github.io/r7rs-benchmarks/benchmark.html

[2] https://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf

Re: My first fifteen compilers

#40

Post by capnrefsmmat »

ckok wrote: post #38

Most compilers sort of work this way, except that they don't have an intermediate format. They take source, turn it into tokens, turn it into a tree of sorts, run several passes over it till the end result is reached (whatever the target is). My own compilers turn 4 different input languages in the same parser tree (Hand written tokenizers/parsers), do several passes over it until it has a very base set of instructio…

It's not that there's a textual intermediate format: just a defined intermediate tree structure. Some examples are given in the nanopass framework documentation [0]. So it's not that the input language is processed into an intermediate format, which is printed to a string and then read by the next pass; the intermediate languages are all in various forms of trees. See also the paper on writing Chez Scheme as a nanopass system [1].

[0] https://docs.racket-lang.org/nanopass/index.html

[1] https://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf

Post reply on HN