5 ms·

Programming Your Own Language in C++

110 points by etrevino 10y ago

packetslave 10y ago
Cached version, since we appear to have hugged their database to death. http://web.archive.org/web/20160616053900/http://accu.org/index.php/journals/2252 http://web.archive.org/web/20160616053900/http://accu.org/in...
- warriorkitty 10y ago
  I just love how sites get unavailable after getting to the top of the HN. :)
n00b101 10y ago
How does this contrast with recursive descent parser?
- jfoutz 10y ago
  ANTLR generates a recursive descent parser. The value is, it's easier to compare (hopefully) your EBNF to the antlr spec than it is to compare your EBNF to lower level code.
  - PeCaN 10y ago
    Doesn't ANTLR usually generate a bottom-up parser? I've never used ANTLR but it would be very odd to generate a recursive descent parser; LR grammars are parsed bottom-up (presumably the ‘LR’ in ‘ANTLR’). Bottom-up parsers are nigh unreadable by mortals.
    - chubot 10y ago
      ANTLR generates top down parsers which use a few different algorithms, including Parr's LL(star) algorithm and the new ALL(star) algorithm for antlr 4: https://scholar.google.com/scholar?cluster=11340764028758422091&hl=en&as_sdt=2005&sciodt=0,5 https://scholar.google.com/scholar?cluster=11340764028758422... https://scholar.google.com/scholar?cluster=7030592786096225431&hl=en&as_sdt=0,5&sciodt=0,5 https://scholar.google.com/scholar?cluster=70305927860962254... The ANTLR acronym is explained here and doesn't have anything to do with LR grammars: http://www.antlr.org/ http://www.antlr.org/
partycoder 10y ago
If you are serious about making your own programming language, I would strongly suggest to target the LLVM.
- jcbeard 10y ago
  If in C++, LLVM + Flex/Bison still the most productive for me. I've tried lots of other compiler compilers, but they're still the best once you learn them. If anybody is bored, I put together a simple word count example a long time ago that has taken on a life of its own: https://github.com/jonathan-beard/simple_wc_example https://github.com/jonathan-beard/simple_wc_example
- spriggan3 10y ago
  > If you are serious about making your own programming language, I would strongly suggest to target the LLVM. Strange advice given the state of LLVM on platforms such as windows. Both Swift and Crystal, LLVM based don't run on windows for instance. LLVM gives you more quickly but at the cost of portability.
  - Ono-Sendai 10y ago
    LLVM works fine on Windows.
wcrichton 10y ago
This article shows a lot of the silliness in both a) writing compilers in C++ and b) re-creating well-worn compilers tools like parsers from scratch. 1. Their definition of values in the language (unfortunately called "Variables") is a product (class) over all possible types: class Variable { ... double numValue; string strValue; vector<Variable> tuple; string action; string varname; Constants::Type type; }; This means each value at runtime has a large memory footprint, as each instance of a value contains slots for all possible types even though only one will ever be filled. Sum types solve this problem. 2. The author intermixes parsing and code generation. This makes it difficult to implement any kind of optimizations, even for an interpreter. For example, in order to do function inlining in the author's language, you would have to manually inline calls in every single part of the code generator instead of having IR transformations as separate modules (see: LLVM). It also tightly couples the two pieces of the compiler, making it difficult to change parsing strategies without rewriting the code generator for instance. 3. It took the author nearly 5000 lines of C++ to write an interpreter for a simple Javascript-like scripting language. Some of this is due to the verbosity of C++, and some is due to the needless effort of reimplementing parsing from scratch. I implemented a similar language in <1k lines of Rust [1], and I'm sure that others could do even better in Haskell or OCaml. On top of that, the author's claimed benefit of extensibility requires writing large amounts of boilerplate. [1] https://github.com/willcrichton/lia https://github.com/willcrichton/lia
- pcunite 10y ago
  Some people make things while other discuss the theory. Each has their place. There would be nothing to improve if people don't try.
- chubot 10y ago
  At the risk of stating the obvious -- in C and C++, unions solve that problem.
  - catnaroek 10y ago
    You still need to roll your own tagged unions by hand. Algebraic data types solve that problem.
chachram 10y ago
antlr's c++ backend is pretty good for complex projects

110 points by etrevino 10y ago

Cached version, since we appear to have hugged their database to death. http://web.archive.org/web/20160616053900/http://accu.org/index.php/journals/2252 http://web.archive.org/web/20160616053900/http://accu.org/in...

warriorkitty 10y ago
I just love how sites get unavailable after getting to the top of the HN. :)

n00b101 10y ago

How does this contrast with recursive descent parser?

jfoutz 10y ago
ANTLR generates a recursive descent parser. The value is, it's easier to compare (hopefully) your EBNF to the antlr spec than it is to compare your EBNF to lower level code.
- PeCaN 10y ago
  Doesn't ANTLR usually generate a bottom-up parser? I've never used ANTLR but it would be very odd to generate a recursive descent parser; LR grammars are parsed bottom-up (presumably the ‘LR’ in ‘ANTLR’). Bottom-up parsers are nigh unreadable by mortals.
  - chubot 10y ago
    ANTLR generates top down parsers which use a few different algorithms, including Parr's LL(star) algorithm and the new ALL(star) algorithm for antlr 4: https://scholar.google.com/scholar?cluster=11340764028758422091&hl=en&as_sdt=2005&sciodt=0,5 https://scholar.google.com/scholar?cluster=11340764028758422... https://scholar.google.com/scholar?cluster=7030592786096225431&hl=en&as_sdt=0,5&sciodt=0,5 https://scholar.google.com/scholar?cluster=70305927860962254... The ANTLR acronym is explained here and doesn't have anything to do with LR grammars: http://www.antlr.org/ http://www.antlr.org/

partycoder 10y ago

If you are serious about making your own programming language, I would strongly suggest to target the LLVM.

jcbeard 10y ago
If in C++, LLVM + Flex/Bison still the most productive for me. I've tried lots of other compiler compilers, but they're still the best once you learn them. If anybody is bored, I put together a simple word count example a long time ago that has taken on a life of its own: https://github.com/jonathan-beard/simple_wc_example https://github.com/jonathan-beard/simple_wc_example
spriggan3 10y ago
> If you are serious about making your own programming language, I would strongly suggest to target the LLVM. Strange advice given the state of LLVM on platforms such as windows. Both Swift and Crystal, LLVM based don't run on windows for instance. LLVM gives you more quickly but at the cost of portability.
- Ono-Sendai 10y ago
  LLVM works fine on Windows.

wcrichton 10y ago

This article shows a lot of the silliness in both a) writing compilers in C++ and b) re-creating well-worn compilers tools like parsers from scratch. 1. Their definition of values in the language (unfortunately called "Variables") is a product (class) over all possible types: class Variable { ... double numValue; string strValue; vector<Variable> tuple; string action; string varname; Constants::Type type; }; This means each value at runtime has a large memory footprint, as each instance of a value contains slots for all possible types even though only one will ever be filled. Sum types solve this problem. 2. The author intermixes parsing and code generation. This makes it difficult to implement any kind of optimizations, even for an interpreter. For example, in order to do function inlining in the author's language, you would have to manually inline calls in every single part of the code generator instead of having IR transformations as separate modules (see: LLVM). It also tightly couples the two pieces of the compiler, making it difficult to change parsing strategies without rewriting the code generator for instance. 3. It took the author nearly 5000 lines of C++ to write an interpreter for a simple Javascript-like scripting language. Some of this is due to the verbosity of C++, and some is due to the needless effort of reimplementing parsing from scratch. I implemented a similar language in <1k lines of Rust [1], and I'm sure that others could do even better in Haskell or OCaml. On top of that, the author's claimed benefit of extensibility requires writing large amounts of boilerplate. [1] https://github.com/willcrichton/lia https://github.com/willcrichton/lia

pcunite 10y ago
Some people make things while other discuss the theory. Each has their place. There would be nothing to improve if people don't try.
chubot 10y ago
At the risk of stating the obvious -- in C and C++, unions solve that problem.
- catnaroek 10y ago
  You still need to roll your own tagged unions by hand. Algebraic data types solve that problem.

chachram 10y ago

antlr's c++ backend is pretty good for complex projects