Learn how to define grammars and abstract syntax trees for the Interpreter Pattern in TypeScript, including grammar rules, AST construction, and parsing techniques.
In this section, we will delve into the process of defining grammars and constructing abstract syntax trees (ASTs) to represent the structure of languages or expressions within the Interpreter Pattern. This is a crucial step in implementing the Interpreter Pattern effectively, as it lays the foundation for parsing and interpreting complex expressions.
Formal grammars are essential for defining the syntax of a language. They provide a set of rules that describe how sentences in a language are constructed. Grammars are typically composed of:
Consider a simple arithmetic expression grammar:
+, -, *, /, (, ), numberExpression, Term, FactorExpression -> Term | Expression + Term | Expression - TermTerm -> Factor | Term * Factor | Term / FactorFactor -> number | ( Expression )ExpressionIn TypeScript, we can represent grammar rules using classes and interfaces. This allows us to create a structured representation of the grammar that can be used to build an AST.
Let’s define classes for the arithmetic expression grammar:
1// Base interface for all expressions
2interface Expression {
3 interpret(): number;
4}
5
6// Terminal expression for numbers
7class NumberExpression implements Expression {
8 constructor(private value: number) {}
9
10 interpret(): number {
11 return this.value;
12 }
13}
14
15// Non-terminal expression for addition
16class AddExpression implements Expression {
17 constructor(private left: Expression, private right: Expression) {}
18
19 interpret(): number {
20 return this.left.interpret() + this.right.interpret();
21 }
22}
23
24// Non-terminal expression for subtraction
25class SubtractExpression implements Expression {
26 constructor(private left: Expression, private right: Expression) {}
27
28 interpret(): number {
29 return this.left.interpret() - this.right.interpret();
30 }
31}
32
33// Non-terminal expression for multiplication
34class MultiplyExpression implements Expression {
35 constructor(private left: Expression, private right: Expression) {}
36
37 interpret(): number {
38 return this.left.interpret() * this.right.interpret();
39 }
40}
41
42// Non-terminal expression for division
43class DivideExpression implements Expression {
44 constructor(private left: Expression, private right: Expression) {}
45
46 interpret(): number {
47 return this.left.interpret() / this.right.interpret();
48 }
49}
An AST is a tree representation of the abstract syntactic structure of source code. Each node in the tree denotes a construct occurring in the source code. The AST reflects the hierarchical structure of the grammar.
To manually construct an AST, you instantiate the appropriate classes and connect them according to the grammar rules.
1// Example: Constructing the AST for the expression "3 + (4 * 5)"
2const expression = new AddExpression(
3 new NumberExpression(3),
4 new MultiplyExpression(
5 new NumberExpression(4),
6 new NumberExpression(5)
7 )
8);
9
10console.log(expression.interpret()); // Outputs: 23
Parsing is the process of analyzing a string of symbols, conforming to the rules of a formal grammar. There are various techniques for parsing, such as recursive descent parsing, which is a top-down parsing approach.
Recursive descent parsing involves writing a set of recursive functions, one for each non-terminal in the grammar. These functions process the input string and build the corresponding AST.
1class Parser {
2 private tokens: string[];
3 private currentTokenIndex: number = 0;
4
5 constructor(input: string) {
6 this.tokens = input.match(/\d+|\+|\-|\*|\/|\\(|\\)/g) || [];
7 }
8
9 parseExpression(): Expression {
10 let left = this.parseTerm();
11 while (this.currentToken() === '+' || this.currentToken() === '-') {
12 const operator = this.currentToken();
13 this.nextToken();
14 const right = this.parseTerm();
15 if (operator === '+') {
16 left = new AddExpression(left, right);
17 } else {
18 left = new SubtractExpression(left, right);
19 }
20 }
21 return left;
22 }
23
24 parseTerm(): Expression {
25 let left = this.parseFactor();
26 while (this.currentToken() === '*' || this.currentToken() === '/') {
27 const operator = this.currentToken();
28 this.nextToken();
29 const right = this.parseFactor();
30 if (operator === '*') {
31 left = new MultiplyExpression(left, right);
32 } else {
33 left = new DivideExpression(left, right);
34 }
35 }
36 return left;
37 }
38
39 parseFactor(): Expression {
40 if (this.currentToken() === '(') {
41 this.nextToken();
42 const expression = this.parseExpression();
43 this.nextToken(); // consume ')'
44 return expression;
45 } else {
46 const number = parseInt(this.currentToken(), 10);
47 this.nextToken();
48 return new NumberExpression(number);
49 }
50 }
51
52 currentToken(): string {
53 return this.tokens[this.currentTokenIndex];
54 }
55
56 nextToken(): void {
57 this.currentTokenIndex++;
58 }
59}
60
61// Example usage
62const parser = new Parser("3 + (4 * 5)");
63const ast = parser.parseExpression();
64console.log(ast.interpret()); // Outputs: 23
To better understand how the AST represents the hierarchical structure of the grammar, let’s visualize it using a diagram.
graph TD;
A["AddExpression"]
B["NumberExpression: 3"]
C["MultiplyExpression"]
D["NumberExpression: 4"]
E["NumberExpression: 5"]
A --> B
A --> C
C --> D
C --> E
Description: This diagram illustrates the AST for the expression “3 + (4 * 5)”. The root node is an AddExpression, which has two children: a NumberExpression for 3 and a MultiplyExpression. The MultiplyExpression further has two children: NumberExpression for 4 and 5.
A well-defined grammar is crucial for the effectiveness of the Interpreter Pattern. It ensures that the language or expressions being interpreted are unambiguous and can be consistently parsed into an AST. This allows for reliable interpretation and execution of the language constructs.
To deepen your understanding, try modifying the code examples to include additional operators, such as exponentiation (^). Update the grammar, classes, and parser to support this new operator. Experiment with different input expressions to see how the AST changes.
Defining grammars and constructing ASTs are foundational steps in implementing the Interpreter Pattern. By understanding these concepts and techniques, you can effectively parse and interpret complex expressions in TypeScript. Remember, this is just the beginning. As you progress, you’ll build more sophisticated interpreters for various languages and domains. Keep experimenting, stay curious, and enjoy the journey!