9
\$\begingroup\$

I'm trying my hand at developing a compiler and have written a grammar for a simple programming language. A sneak peak at the grammar:

/* calculates fibonacci sequence */
fn fibonacci(n int32) int32 {
    /* termination */
    if n == 0 or n == 1 {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

This code produces the following parse tree (locations omitted for brevity):

[ { kind: 'FunctionDefinition',
    location:
     { start:
        { offset: 40,
          line: 2,
          column: 3 },
       end:
        { offset: 186,
          line: 9,
          column: 4 } },
    name: 'fibonacci',
    parameters:
     [ { name:
          { kind: 'Identifier',
            location:
             { start:
                { offset: 53,
                  line: 2,
                  column: 16 },
               end:
                { offset: 54,
                  line: 2,
                  column: 17 } },
            name: 'n',
            toString: [Function] },
         type:
          { kind: 'NamedType',
            location:
             { start:
                { offset: 55,
                  line: 2,
                  column: 18 },
               end:
                { offset: 60,
                  line: 2,
                  column: 23 } },
            name: 'int32' } } ],
    returnType:
     { kind: 'NamedType',
       location:
        { start:
           { offset: 62,
             line: 2,
             column: 25 },
          end:
           { offset: 67,
             line: 2,
             column: 30 } },
       name: 'int32' },
    body:
     { kind: 'Body',
       location:
        { start:
           { offset: 68,
             line: 2,
             column: 31 },
          end:
           { offset: 186,
             line: 9,
             column: 4 } },
       statements:
        [ { kind: 'ConditionalStatement',
            location:
             { start:
                { offset: 94,
                  line: 4,
                  column: 4 },
               end:
                { offset: 182,
                  line: 8,
                  column: 5 } },
            predicate:
             { kind: 'BinaryOperator',
               location:
                { start:
                   { offset: 97,
                     line: 4,
                     column: 7 },
                  end:
                   { offset: 113,
                     line: 4,
                     column: 23 } },
               lhs:
                { kind: 'BinaryOperator',
                  location:
                   { start:
                      { offset: 97,
                        line: 4,
                        column: 7 },
                     end:
                      { offset: 113,
                        line: 4,
                        column: 23 } },
                  lhs:
                   { kind: 'Identifier',
                     location:
                      { start:
                         { offset: 97,
                           line: 4,
                           column: 7 },
                        end:
                         { offset: 98,
                           line: 4,
                           column: 8 } },
                     name: 'n',
                     toString: [Function] },
                  operator: '==',
                  rhs:
                   { kind: 'Number',
                     location:
                      { start:
                         { offset: 102,
                           line: 4,
                           column: 12 },
                        end:
                         { offset: 103,
                           line: 4,
                           column: 13 } },
                     value: 0 } },
               operator: 'or',
               rhs:
                { kind: 'BinaryOperator',
                  location:
                   { start:
                      { offset: 97,
                        line: 4,
                        column: 7 },
                     end:
                      { offset: 113,
                        line: 4,
                        column: 23 } },
                  lhs:
                   { kind: 'Identifier',
                     location:
                      { start:
                         { offset: 107,
                           line: 4,
                           column: 17 },
                        end:
                         { offset: 108,
                           line: 4,
                           column: 18 } },
                     name: 'n',
                     toString: [Function] },
                  operator: '==',
                  rhs:
                   { kind: 'Number',
                     location:
                      { start:
                         { offset: 112,
                           line: 4,
                           column: 22 },
                        end:
                         { offset: 113,
                           line: 4,
                           column: 23 } },
                     value: 1 } } },
            thenBody:
             { kind: 'Body',
               location:
                { start:
                   { offset: 114,
                     line: 4,
                     column: 24 },
                  end:
                   { offset: 134,
                     line: 6,
                     column: 5 } },
               statements:
                [ { kind: 'ReturnStatement',
                    location:
                     { start:
                        { offset: 120,
                          line: 5,
                          column: 5 },
                       end:
                        { offset: 129,
                          line: 5,
                          column: 14 } },
                    expression:
                     { kind: 'Number',
                       location:
                        { start:
                           { offset: 127,
                             line: 5,
                             column: 12 },
                          end:
                           { offset: 128,
                             line: 5,
                             column: 13 } },
                       value: 1 } } ] },
            elseBody:
             { kind: 'Body',
               location:
                { start:
                   { offset: 140,
                     line: 6,
                     column: 11 },
                  end:
                   { offset: 182,
                     line: 8,
                     column: 5 } },
               statements:
                [ { kind: 'ReturnStatement',
                    location:
                     { start:
                        { offset: 146,
                          line: 7,
                          column: 5 },
                       end:
                        { offset: 177,
                          line: 7,
                          column: 36 } },
                    expression:
                     { kind: 'BinaryOperator',
                       location:
                        { start:
                           { offset: 153,
                             line: 7,
                             column: 12 },
                          end:
                           { offset: 176,
                             line: 7,
                             column: 35 } },
                       lhs:
                        { kind: 'FunctionApplication',
                          location:
                           { start:
                              { offset: 153,
                                line: 7,
                                column: 12 },
                             end:
                              { offset: 164,
                                line: 7,
                                column: 23 } },
                          name: 'fib',
                          args:
                           [ { kind: 'BinaryOperator',
                               location:
                                { start:
                                   { offset: 157,
                                     line: 7,
                                     column: 16 },
                                  end:
                                   { offset: 162,
                                     line: 7,
                                     column: 21 } },
                               lhs:
                                { kind: 'Identifier',
                                  location:
                                   { start:
                                      { offset: 157,
                                        line: 7,
                                        column: 16 },
                                     end:
                                      { offset: 158,
                                        line: 7,
                                        column: 17 } },
                                  name: 'n',
                                  toString: [Function] },
                               operator: '-',
                               rhs:
                                { kind: 'Number',
                                  location:
                                   { start:
                                      { offset: 161,
                                        line: 7,
                                        column: 20 },
                                     end:
                                      { offset: 162,
                                        line: 7,
                                        column: 21 } },
                                  value: 1 } } ] },
                       operator: '+',
                       rhs:
                        { kind: 'FunctionApplication',
                          location:
                           { start:
                              { offset: 166,
                                line: 7,
                                column: 25 },
                             end:
                              { offset: 176,
                                line: 7,
                                column: 35 } },
                          name: 'fib',
                          args:
                           [ { kind: 'BinaryOperator',
                               location:
                                { start:
                                   { offset: 170,
                                     line: 7,
                                     column: 29 },
                                  end:
                                   { offset: 175,
                                     line: 7,
                                     column: 34 } },
                               lhs:
                                { kind: 'Identifier',
                                  location:
                                   { start:
                                      { offset: 170,
                                        line: 7,
                                        column: 29 },
                                     end:
                                      { offset: 171,
                                        line: 7,
                                        column: 30 } },
                                  name: 'n',
                                  toString: [Function] },
                               operator: '-',
                               rhs:
                                { kind: 'Number',
                                  location:
                                   { start:
                                      { offset: 174,
                                        line: 7,
                                        column: 33 },
                                     end:
                                      { offset: 175,
                                        line: 7,
                                        column: 34 } },
                                  value: 2 } } ] } } } ] } } ] } } ]

And the grammar itself:

{
  const tree = new Proxy({}, {
    get(target, kind, receiver) {
      return (extra = {}) => {
        return Object.assign({
          kind,
          location: location(),
        }, extra);
      };
    },
  });

  const left = Symbol('left');
  const right = Symbol('right');

  const reservedWords = [
    'if', 'unless', 'fn', 'not', 'and', 'or', 'while', 'until', 'return',
    'var', 'const'
  ];

  const emptyBody = tree.Body({ statements: [] });

  const binaryOperators = {
    '*': { associativity: left, precedence: 60 },
    '/': { associativity: left, precedence: 60 },
    'mod': { associativity: left, precedence: 60 },

    '+': { associativity: left, precedence: 50 },
    '-': { associativity: left, precedence: 50 },
    '|': { associativity: left, precedence: 50 },
    '&': { associativity: left, precedence: 50 },

    'shl': { associativity: left, precedence: 40 },
    'shr': { associativity: left, precedence: 40 },

    '==': { associativity: left, precedence: 30 },
    '!=': { associativity: left, precedence: 30 },
    '<':  { associativity: left, precedence: 30 },
    '>':  { associativity: left, precedence: 30 },
    '<=': { associativity: left, precedence: 30 },
    '>=': { associativity: left, precedence: 30 },

    'and': { associativity: left, precedence: 20 },
    'or': { associativity: left, precedence: 10 },

    '=': { associativity: right, precedence: 0 },
  };

  function isLeftAssociative(operator) {
    return binaryOperators[operator].associativity === left;
  }

  function isRightAssociative(operator) {
    return binaryOperators[operator].associativity === right;
  }

  function precedenceOf(operator) {
    return binaryOperators[operator].precedence;
  }

  function nth(index, array = null) {
    return (element) => element[index];
  }

  function get(array, index, defaultValue = null) {
    if (Array.isArray(array) && array[index] !== undefined) {
      return array[index];
    }

    return defaultValue;
  }

  function value(v) {
    return () => v;
  }

  function checkNotReserved(word) {
    if (reservedWords.includes(word)) {
      throwSyntaxError(`Unexpected reserved word ${word}.`);
    }
  }

  function throwSyntaxError(message) {
    const error = new Error(message);
    error.location = location();
    error.name = "SyntaxError";

    throw error;
  }

  function toString(characters) {
    if (typeof characters === 'string') {
      return characters;
    }
    if (!Array.isArray(characters)) {
      throw new TypeError(`toString() accepts string or array of strings.`);
    }

    return characters
      .map(toString)
      .join('');
  }

  function toInteger(s, base) {
    // TODO: line numbers in manual errors
    s = toString(s);
    if (s[0] === '_' || s[s.length - 1] === '_') {
      throwSyntaxError('Thousand separators allowed only inside numerals.');
    }

    return parseInt(s.replace(/_/g, ''), base);
  }

  function notEmpty(value) {
    return value !== undefined;
  }

  function operatorsToTree({ head, tail }) {
    tail = tail.map((element) => {
      return {
        operator: element[1],
        rhs: element[3],
      };
    });

    function collect(lhs, minPrecedence) {
      let operator, rhs;

      while (tail.length && precedenceOf(tail[0].operator) >= minPrecedence) {
        const tmp = tail.shift();
        operator = tmp.operator;
        rhs = tmp.rhs;

        let lookahead = tail[0];
        while (
          tail.length &&
          (precedenceOf(lookahead.operator) > precedenceOf(operator) ||
           isRightAssociative(lookahead.operator) &&
           precedenceOf(lookahead.operator) === precedenceOf(operator))
        ) {
          rhs = collect(rhs, precedenceOf(lookahead.operator));
          lookahead = tail[0];
        }

        lhs = tree.BinaryOperator({
          lhs,
          operator,
          rhs,
        });
      }

      return lhs;
    }

    return collect(head, 0);
  }
}

Program
  = _ statements: (TopLevelStatement _)* _
  { return statements.map(nth(0)).filter(notEmpty); }

TopLevelStatement
  = Comment
  { }
  / definition: FunctionDefinition
  { return definition; }

FunctionDefinition
  = "fn" _
    name: Identifier _
    parameters: ParameterList _
    returnType: Type _
    body: Body
  {
    return tree.FunctionDefinition({
      name: String(name),
      parameters,
      returnType,
      body,
    });
  }

ParameterList
  = "(" _ ")"
  { return []; }
  / "(" _ head: NameTypePair tail: (_ "," _ NameTypePair)* _ ")" _
  { return [head].concat(tail.map(nth(3))); }

NameTypePair
  = name: Identifier __ type: Type
  { return { name, type }; }

Body
  = "{" _ statements: (Statement _)* "}"
  { return tree.Body({ statements: statements.map(nth(0)).filter(notEmpty) }); }

Statement
  = Comment
  { }
  / EmptyStatement
  / "return" _ expression: Expression _ StatementTerminator
  { return tree.ReturnStatement({ expression }); }
  / keyword: ConditionalKeyword _
    predicate: Expression _
    thenBody: Body _
    elseBody: ("else" _ Body)?
  {
    predicate = keyword === 'unless'
      ? tree.UnaryOperator({ operator: 'not', operand: predicate })
      : predicate;

    return tree.ConditionalStatement({
      predicate,
      thenBody,
      elseBody: get(elseBody, 2, emptyBody),
    });
  }
  / keyword: LoopingKeyword _
    predicate: Expression _
    doBody: Body
  {
    predicate = keyword === 'until'
      ? tree.UnaryOperator({ operator: 'not', operand: predicate })
      : predicate;

    return tree.LoopingStatement({
      predicate,
      doBody,
    });
  }
  / "var" __
    name: Identifier __
    type: Type _
    initial: ("=" _ Expression)? _
    StatementTerminator
  {
    return tree.VariableDeclaration({
      name,
      type,
      initial: get(initial, 3, null),
    });
  }
  / expression: Expression _ StatementTerminator
  { return tree.ExpressionStatement({ expression }); }

EmptyStatement
  = StatementTerminator
  { return tree.EmptyInstruction(); }

StatementTerminator
  = ";"

Type
  = "pointer" _ "!" _ type: Type
  { return tree.PointerToType({ type }); }
  / "array" _ "(" capacity: Expression ")" _ "!" _ type: Type
  { return tree.ArrayType({ type, capacity }); }
  / name: Identifier
  { return tree.NamedType({ name: String(name) }); }

Expression
  = binaryOperator: BinaryOperator
  { return binaryOperator; }

BinaryOperator
  = head: Primary tail: (_ BinaryToken _ Primary)*
  { return operatorsToTree({ head, tail }); }

Primary
  = "(" _ expression: Expression _ ")"
  { return expression; }
  / application: FunctionApplication
  { return application; }
  / operator: UnaryToken _ operand: Primary
  { return tree.UnaryOperator({ operator, operand }); }
  / identifier: Identifier
  { return identifier; }
  / number: Number
  { return number; }
  / string: String
  { return string; }

FunctionApplication
  = name: Identifier _ args: ArgumentList
  {
    return tree.FunctionApplication({
      name: String(name),
      args,
    });
  }

ArgumentList
  = "(" _ ")"
  { return []; }
  / "(" _ head: Expression tail: (_ "," _ Expression)* _ ")" _
  { return [head].concat(tail.map(nth(3))); }

Identifier "identifier"
  = name: ([a-zA-Z][a-zA-Z0-9"-]*)
  {
    name = toString(name);
    checkNotReserved(name);
    return tree.Identifier({
      name: name,
      toString: value(name),
    });
  }

Number
  = "0x" digits: HexadecimalDigits
  { return tree.Number({ value: toInteger(digits, 16) }); }
  / "0b" digits: BinaryDigits
  { return tree.Number({ value: toInteger(digits, 2) }); }
  / digits: Digits
  { return tree.Number({ value: toInteger(digits, 10) }); }

String
  = '"' string: StringCharacter* '"'
  { return tree.String({ string: toString(string) }); }

StringCharacter
  = "\\\\"
  { return "\\"; }
  / '\\"'
  { return '"'; }
  / "\\n"
  { return "\n"; }
  / "\\r"
  { return "\r"; }
  / "\\t"
  { return "\t"; }
  / "\\b"
  { return "\b"; }
  / "\\x" digits: ([0-9a-fA-F][0-9a-fA-F])
  { return String.fromCharCode(toInteger(digits, 16)); }
  / c: [^"]
  { return c; }

WhiteSpace "white space"
  = ([ \n\r\t]+)
  { }

Comment
  = "/*" (!"*/" .)* "*/"
  { }

_
  = __?

__
  = WhiteSpace

ConditionalKeyword = "if" / "unless"
LoopingKeyword = "while" / "until"
UnaryToken = "+" / "-" / "~" / "not"

BinaryToken
  = "*" / "/" / "mod"
  / "+" / "-" / "|" / "&"
  / "shl" / "shr"
  / "==" / "!=" / "<=" / ">=" / "<" / ">"
  / "and"
  / "or"
  / "="

Digits
  = digits: [0-9_]+
  { return toString(digits); }

HexadecimalDigits
  = digits: [0-9a-fA-F_]+
  { return toString(digits); }

BinaryDigits
  = digits: [01_]+
  { return toString(digits); }

This is my second attempt at PEGs, so feel free to point out beginner mistakes and/or recommend best practices.

\$\endgroup\$
1
\$\begingroup\$

This code looks pretty solid. It utilizes many features like arrow functions, default parameter values, const for any value that doesn't get re-assigned and let for values that can be re-assigned, etc. Comments could be added to help document the code.

Some of the trivial functions could be simplified - e.g.

function value(v) {
  return () => v;
}

Could be simplified to:

const value = v => () => v;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.