Code for Reading 19

You can also download a ZIP file containing this code.

Seems to be necessary to have a triple-backtick block at the start of this page,
otherwise all the pre/code tags below aren't syntax highlighted.
So create a hidden one.

import { IntegerExpression, Constant, Plus } from './IntegerExpression';
import { Parser, ParseTree, compile, visualizeAsUrl } from 'parserlib';

// the grammar
export const grammar:string = `
@skip whitespace {
    expr ::= sum;
    sum ::= primary ('+' primary)*;
    primary ::= constant | '(' sum ')';
}
constant ::= [0-9]+;
whitespace ::= [ \\t\\r\\n]+;  // <-- note that backslashes must be escaped
`;

// the nonterminals of the grammar
export enum IntegerGrammar {
    Expr, Sum, Primary, Constant, Whitespace,
}

// compile the grammar into a parser
export const parser: Parser<IntegerGrammar> = compile(grammar, IntegerGrammar, IntegerGrammar.Expr);

/**
 * Parse a string into an expression.
 * @param string string to parse
 * @returns IntegerExpression parsed from the string
 * @throws ParseError if the string doesn't match the IntegerExpression grammar
 */
export function parse(input: string): IntegerExpression {
    // parse the example into a parse tree
    const parseTree: ParseTree<IntegerGrammar> = parser.parse(input);
    console.log("parse tree:\n" + parseTree);

    // display the parse tree in a web browser, for debugging only
    console.log(visualizeAsUrl(parseTree, IntegerGrammar));

    // make an AST from the parse tree
    const expression: IntegerExpression = makeAbstractSyntaxTree(parseTree);
    console.log("abstract syntax tree:\n" + expression);
    
    return expression;
}

/**
 * Convert a parse tree into an abstract syntax tree.
 * 
 * @param parseTree constructed according to the grammar in IntegerExpression.g
 * @returns abstract syntax tree corresponding to parseTree
 */
function makeAbstractSyntaxTree(parseTree: ParseTree<IntegerGrammar>): IntegerExpression {
    switch (parseTree.name) {
    case IntegerGrammar.Expr: // expr ::= sum;
        {
            const child: ParseTree<IntegerGrammar> = parseTree.children[0];
            return makeAbstractSyntaxTree(child);
        }

    case IntegerGrammar.Sum: // sum ::= primary ('+' primary)*;
        {
            const children: Array<ParseTree<IntegerGrammar>> = parseTree.childrenByName(IntegerGrammar.Primary);
            let expression: IntegerExpression = makeAbstractSyntaxTree(children[0]);
            for (let i = 1; i < children.length; ++i) {
                expression = new Plus(expression, makeAbstractSyntaxTree(children[i]));
            }
            return expression;
        }

    case IntegerGrammar.Primary: // primary ::= constant | '(' sum ')';
        {
            const child: ParseTree<IntegerGrammar> = parseTree.children[0];
            // check which alternative (constant or sum) was actually matched
            switch (child.name) {
            case IntegerGrammar.Constant:
                return makeAbstractSyntaxTree(child);
            case IntegerGrammar.Sum:
                return makeAbstractSyntaxTree(child); // in this case, we do the same thing either way
            default:
                throw new Error("should never get here");
            }
        }

    case IntegerGrammar.Constant: // constant ::= [0-9]+;
        {
            const n: number = parseInt(parseTree.text);
            return new Constant(n);
        }
        
    default:
        throw new Error("should never get here");
    }
}

function main() {
    const input = "54+(2+ 89)";
    // const input = "TODO"; // different parse tree, same AST
    // const input = "TODO"; // different parse tree, different AST, same AST leaf nodes (54, 2, 89 in that order)
    // const input = "TODO"; // parse tree with fewest possible "primary" nodes, same AST leaf nodes in order

    console.log(input);
    const expression: IntegerExpression = parse(input);
    const value: number = expression.value();
    console.log("value " + value);
}

if (require.main === module) {
    main();
}

import { Parser, ParseTree, compile, visualizeAsUrl } from 'parserlib';

/** Immutable type representing an integer arithmetic expression. */
export interface IntegerExpression {
    // Data type definition
    //    IntegerExpression = Constant(n:number)
    //                        + Plus(left:IntegerExpression, right:IntegerExpression)
    //                        + Times(left:IntegerExpression, right:IntegerExpression)

    /** @returns the computed value of this expression */
    value(): number;
}

export class Constant implements IntegerExpression {
    
    // Abstraction function
    //    AF(n) = the integer n
    // Rep invariant
    //    true
    // Safety from rep exposure
    //    all fields are immutable and final
    
    /** Make a Constant. */
    public constructor(private readonly n: number) {
    }
    
    public value(): number {
        return this.n;
    }
    
    public toString(): string {
        return "Constant(" + this.n + ")";
    }
}

export class Plus implements IntegerExpression {
    
    // Abstraction function
    //    AF(left, right) = the expression left + right
    // Rep invariant
    //    true
    // Safety from rep exposure
    //    all fields are immutable and final
    
    /** Make a Plus which is the sum of left and right. */
    public constructor(private readonly left: IntegerExpression,
                       private readonly right: IntegerExpression) {
    }
    
    public value(): number {
        return this.left.value() + this.right.value();
    }
    
    public toString(): string {
        return "Plus(" + this.left + "," + this.right + ")";
    }
}

export class Times implements IntegerExpression {
    
    // Abstraction function
    //    AF(left, right) = the expression left * right
    // Rep invariant
    //    true
    // Safety from rep exposure
    //    all fields are immutable and final
    
    /** Make a Times which is the product of left and right. */
    public constructor(private readonly left: IntegerExpression,
                       private readonly right: IntegerExpression) {
    }
    
    public value(): number {
        return this.left.value() * this.right.value();
    }
    
    public toString(): string {
        return "Times(" + this.left + "," + this.right + ")";
    }
}