Code for Reading 12

You can also download a ZIP file containing this code.

After downloading and unpacking the ZIP file:

• npm install to install package dependencies;
• npm run to see a list of the ways this code can be run.
  • For example, if npm run shows that there are scripts called foo and bar, you can run the code with either npm run foo or npm run bar.
  • Two conventional script names are test and start. If the code includes one of those script names, then you can omit run and just say npm test or npm start.

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 assert from 'node:assert';

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

// the grammar
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 input 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 IntegerExpression grammar
 * @returns abstract syntax tree corresponding to parseTree
 */
function makeAbstractSyntaxTree(parseTree: ParseTree<IntegerGrammar>): IntegerExpression {
    if (parseTree.name === IntegerGrammar.Expr) {
        // expr ::= sum;
        return makeAbstractSyntaxTree(parseTree.children[0] ?? assert.fail('missing child'));
        
    } else if (parseTree.name === IntegerGrammar.Sum) {
        // sum ::= primary ('+' primary)*;
        const children = parseTree.childrenByName(IntegerGrammar.Primary);
        const subexprs = children.map(makeAbstractSyntaxTree);
        const expression: IntegerExpression = subexprs.reduce((result, subexpr) => new Plus(result, subexpr));
        return expression;
        
    } else if (parseTree.name === IntegerGrammar.Primary) {
        // primary ::= constant | '(' sum ')';
        const child: ParseTree<IntegerGrammar> = parseTree.children[0] ?? assert.fail('missing child');
        // check which alternative (constant or sum) was actually matched
        switch (child.name) {
        case IntegerGrammar.Constant:
            return makeAbstractSyntaxTree(child);
        case IntegerGrammar.Sum:
            return makeAbstractSyntaxTree(child);
            // for this parser, we do the same thing either way (and should really DRY this out)
        default:
            assert.fail(`Primary node unexpected child ${IntegerGrammar[child.name]}`);
        }
        
    } else if (parseTree.name === IntegerGrammar.Constant) {
        // constant ::= [0-9]+;
        const n: number = parseInt(parseTree.text);
        return new Constant(n);
        
    } else {
        assert.fail(`cannot make AST for ${IntegerGrammar[parseTree.name]} node`);
    }
}

export 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);
}

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

/** Immutable type representing an integer arithmetic expression. */
export interface IntegerExpression {
    /** @returns the computed value of this expression */
    value(): number;
}

// Data type definition
//    IntegerExpression = Constant(n:number)
//                        + Plus(left:IntegerExpression, right:IntegerExpression)
//                        + Times(left:IntegerExpression, right:IntegerExpression)

export class Constant implements IntegerExpression {
    
    // Abstraction function
    //    AF(n) = the integer n
    // Rep invariant
    //    true
    // Safety from rep exposure
    //    all fields are immutable and unreassignable
    
    /** 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 unreassignable
    
    /** 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 unreassignable
    
    /** 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 + ")";
    }
}