Writing a Compiler Compiler – Insight on Use and Features

... how do I calculate the Relative Virtual Address of the block, and the Offset (lower 12 bits) on the Type Offset entry that follows that block header?

Microsoft - PE Format (05/30/2018):

"Base Relocation Block

Each base relocation block starts with the following structure:

Offset      Size      Field      Description

---

   0              4          RVA      The image base plus the page RVA is added to each offset to create the VA where the base relocation must be applied.

   4              4           BS         The total number of bytes in the base relocation
block, including the Page RVA and Block Size fields and the Type/Offset fields that follow.

 

The Block Size field is then followed by any number of Type or Offset field entries. Each entry is a WORD (2 bytes) and has the following structure:

Offset      Size      Field      Description

---

   0             4b        Type      Stored in the high 4 bits of the WORD, a value that indicates the type of base relocation to be applied. For more information, see Base Relocation Types.

   0            12b       Type      Stored in the remaining 12 bits of the WORD, an offset from the starting address that was specified in the Page RVA field for the block. This offset specifies where the base relocation is to be applied.

...

".

Example code is in BinUtils.

You can find testing code in binutils/ld/testsuite/ld-cygwin.

I would suggest you use your Lexer construct as more of a generator, rather than identifying all the tokens at once and sending an entire list to the parser. Your lexer could simply declare an interface with a .NextToken() or .Next() (and probably .Backup()) method and anytime the Parser requires a new token, it could simply call one of those methods.

If your language requires lookahead tokens, you could simply keep a list of lookahead tokens on the Parser and always lag N number of tokens behind the Lexer's current token.

As far as actual parsing techniques are concerned, you should probably consider recursive descent parsing. In my opinion, these are typically the easiest types of parsers to code by hand and are conceptually the simplest parsers to understand.

Recursive descent parsing typically works by matching one terminal grammar production to a function or method. So if you have a grammar production for a variable declaration like var x := 1, your method could look something like this:

// Grammar Production:
//   'var' Identifier ':=' Expression
private Declaration ParseDeclaration() {
    Declaration decl = new Declaration();

    if (!Expect(TokenType.Var)) {
        throw new ParseError("Expected 'var' keyword");
    }

    decl.Identifier = ParseIdentifier();

    if (!Expect(TokenType.AssignmentEquals)) {
        throw new ParseError("Expected token ':='");
    }

    decl.Expression = ParseExpression();
    return decl;
}

For each production in your grammar, you could define a method like that one and recursively construct your parse tree. It ends up being a really elegant system to code, rather than trying to match productions using token patterns. You can use the power of your programming language's call stack to control flow and handle repetition and parsing errors. Shunting yard is challenging to generalize to non expression grammar rules too, so I don't recommend you go down that path.

P.S. I'm sorry, I don't know Scala syntax offhand, so I opted to just use a Java/C# type of syntax.