Tell us about your compiler!

keleshev · June 24, 2020, 7:11pm

Which language you are using to write it, and which language does it compile? What are your struggles? What are your successes?

Apos · July 12, 2020, 7:16am

I’m planning on compiling this: https://github.com/Apostolique/Vyne-Language. I’ll develop the language more as I go through the book. My original plan was to use C#, but maybe you’ll convince me to try TypeScript.

I’ve been meaning to work on the compiler for a while, but it’s hard to balance all my projects.

No successes yet, but the draft was interesting. I never considered ARM as a possible compilation target so this should be interesting.

keleshev · July 12, 2020, 7:37am

@Apos Vyne looks interesting! I would recommend to use whatever language you’re most comfortable in. It’s challenging enough to write a compiler, and making one in a new language is even harder. The kind of TypeScript that is in the book should match well to C#.

stn · July 13, 2020, 9:06am

I’m planning on using Golang which is a large part of my day job. I’m comfortable with it and the level of pedantry it requires seems just about right. I also use Python a lot, but I feel its dynamic nature will hinder me more than it will help.

To me the target language is not interesting (yet). I’m just looking forward to grasping the concepts and making the simplest thing that could possibly work.

keleshev · July 13, 2020, 9:59am

@stn I don’t have a lot of experience with Go, but I think that code in the book should map well to Go. I haven’t used class inheritance (only interface inheritance) exactly for this reason: so that code is portable to languages like Go. Let us know how it goes!

stn · July 13, 2020, 10:17am

@keleshev I will. Looking forward to the rest of the content. Have fun and good luck.

Apos · July 24, 2020, 3:05am

My compiler’s repo will be here: https://github.com/Apostolique/Vyne-Compiler.

keleshev · July 29, 2020, 9:34pm

@Apos any blockers so far?

Apos · July 30, 2020, 5:46am

It’s mostly going well. I started writing a bit of the parser combinators in C#, but I’m finding the generics to be pretty heavy. For example:

github.com

Apostolique/Vyne-Compiler/blob/aef87f7418cfc18015be9bcfb27925c1194a3272/src/Parser.cs#L136


public static Parser<string> SEMICOLON = token(@";");
public static Parser<string> LEFT_PAREN = token(@"[(]");
public static Parser<string> RIGHT_PAREN = token(@"[)]");
public static Parser<string> LEFT_BRACE = token(@"[{]");
public static Parser<string> RIGHT_BRACE = token(@"[}]");

public static Parser<Integer> INTEGER = token(@"[0-9]+").Map(digits => new Integer(Int32.Parse(digits)));
public static Parser<string> ID = token(@"[a-zA-Z_]");
public static Parser<Id> id = ID.Map(x => new Id(x));

public static Parser<Func<AST, Not>> NOT = token(@"!").Map<Func<AST, Not>>(_ => term => new Not(term));
public static Parser<Func<AST, AST, Equal>> EQUAL = token(@"==").Map<Func<AST, AST, Equal>>(_ => (left, right) => new Equal(left, right));
public static Parser<Func<AST, AST, NotEqual>> NOT_EQUAL = token(@"!=").Map<Func<AST, AST, NotEqual>>(_ => (left, right) => new NotEqual(left, right));
public static Parser<Func<AST, AST, Add>> PLUS = token(@"[+]").Map<Func<AST, AST, Add>>(_ => (left, right) => new Add(left, right));
public static Parser<Func<AST, AST, Subtract>> MINUS = token(@"[-]").Map<Func<AST, AST, Subtract>>(_ => (left, right) => new Subtract(left, right));
public static Parser<Func<AST, AST, Multiply>> STAR = token(@"[*]").Map<Func<AST, AST, Multiply>>(_ => (left, right) => new Multiply(left, right));
public static Parser<Func<AST, AST, Divide>> SLASH = token(@"[/]").Map<Func<AST, AST, Divide>>(_ => (left, right) => new Divide(left, right));

public static Parser<AST> expression = Parser<string>.Error<AST>("expression parser used before definition");

public static Parser<List<AST>> args =

And I didn’t get to the interesting stuff yet. Currently looking for ways to simplify that. Also I might have written some of them wrong, I’ll have to test later.

I tested with TypeScript too, but I’m not sold on it yet. It feels too much like JavaScript which I guess is the point, but I have more fun with JavaScript.

keleshev · July 30, 2020, 3:48pm

Yeah, these type annotations are heavy. One thing that comes to mind, is to make the token definitions local to a function. This way, you can take advantage of local type inference. You could write:

var NOT = token(@"!").Map<Func<AST, Not>>(_ => term => new Not(term));

Instead of:

public static Parser<Func<AST, Not>> NOT = token(@"!").Map<Func<AST, Not>>(_ => term => new Not(term));

But that forces you to have all of the parser defined within a single function, I think.

I’m not an expert on C#, so maybe anyone has some better idea?

keleshev · July 30, 2020, 4:10pm

@Apos, by the way, nice idea with using @"\G" and Match(string, int) overload to solve the problem of matching at a specific position in a string.

mukadr · August 3, 2020, 11:08pm

I’m first writing the parser combinator utilities in a separate project, in C# (.NET Core): https://github.com/mukadr/ParseDotNet

The next part will be a compiler for some Pascal dialect, targeting ARM as explained in the book. I’m using my spare time to work on this project and study more about code generation. I would like to do register allocation.

I liked the approach used in the book for writing parsers. It is convenient to test each piece separately.

keleshev · August 4, 2020, 1:11pm

Welcome, @mukadr! Your parser combinators look good. It is interesting to compare with @Apos’ approach. It seems that you’ve decided not to use regular expressions, but instead have several sourse.Match overloads for chars and strings and such? This should also work. It will also be interesting to see if you know a way to combat the verbose type annotations, like in @Apos case:

public static Parser<Func<AST, Not>> NOT = token(@"!").Map<Func<AST, Not>>(_ => term => new Not(term));

mukadr · August 4, 2020, 2:03pm

Yes, it matches chars and ZeroOrMore/OneOrMore concatenate them into a string. So far it seems enough for my needs.

One problem I had with the Parser class was with static methods.

Since Parser has a generic type T, every call to a static method is required to specify the type T.

For example (from @Apos):

public static Parser<string> Whitespace = Parser<string>.Regexp(@"[ \n\r\t]+");

Notice that Parser<string>.Regexp could be written as Parser.Regexp, since it does not depend on the type T.

To solve this issue in C#, one can move the static methods to a different class, like:

public static class ParserFactory
{
    …
    public static Parser<string> Regexp(string regexp, RegexOptions options = RegexOptions.None) {
    …
}

Then you can get rid of the generics:

var parser = ParserFactory.Regexp(…);

There is also “using static" declaration to import all static methods from a class:

using static x.y.ParserFactory;
…
    { 
        var parser = Regexp(…);
    }
…

Unfortunately I could not find a way to simplify the class attributes, since var only works for local variables:

public static Parser<Func<AST, Not>> NOT = …

nerdboy · August 5, 2020, 5:13am

I’m writing my version of the compiler in Nim. It will hopefully compile your language (with a number of restictions) into the ARM assembly that you output. I currently have the AST portion completed as well as a lexer (using the regular expressions you had developed for this). I am currently working on the parser which should glue the other 2 modules.

I do love the fact that built the way you have it - I can easily test the 3 modules separately.

keleshev · August 5, 2020, 9:19pm

Looks like Nim has both variant types and inheritance with dynamic dispatch. Which one did you decide to use for the AST?

nerdboy · August 6, 2020, 4:44am

I used inheritance + dynamic dispatch with my AST. I think it leads to cleaner code.

If I did variants - there are some limitations that drive me nuts (I tried it on some other nim code of mine and found some limitations). I also think that variants means that you would perhaps have one emit procedure that looks at which variant it is and then go from there (so either one big case statement or have it call a specific procedure (which is basically the same thing as dynamic dispatch in the end)).

mukadr · August 7, 2020, 9:03pm

Moved the code to another repository: https://github.com/mukadr/SharpPascal

Doing the parsing in a single method, so I can use var for all declarations: https://github.com/mukadr/SharpPascal/blob/master/src/SharpPascal/Syntax/PascalParser.cs

Thanks to this “functional approach to writing parsers” I’m considering learning F#

keleshev · August 8, 2020, 8:06am

Yep, F# has good type inference and would be a good fit for this. It would look something like this, in your case:

module PascalParser = 

  let mutable currentLine = 1

  let report message = sprintf "%d: %s" currentLine message

  let whitespace =
    OneOrMore(
      Symbol(' ')
        .Or(Symbol('\t'))
        .Or(Symbol('\n').Bind(fun c -> 
          currentLine <- currentLine + 1;
          Constant(c)
    )).Or(Symbol('\r')))

  ...

Where module is similar to a static class.

By the way, nice that you track the current line number. It can be incorporated into the Source class to make it transparent to the user of it.

keleshev · August 8, 2020, 10:00am

@mukadr just thought that because of backtracking, the currentLine++; might be executed erroneously multiple times on the same line.