Lecture 3. ArithLang – Arithmetics
January 27, 2021
Overview
A language that implements float/integer arithmetic
Design decision: prefix, infix and postfix
Interpreter: Java
Arithlang syntax and semantics, and their implementations
Note. Syntax, semantics, design desicisions of ArithLang are taken from the language Scheme.
Interpreter Demo
Prefix, Infix, Postfix
Prefix: Operators are written before their operands. Operators act on the two nearest values on the right. (Lisp, Scheme uses prefix forms)
++A*BCD
*+AB+CD ++123
Infix: Operators are written in-between their operands. 1+2+3
Postfix: Operators are written after their operands. Operators act on values immediately to the left of them.
ABC*+D+
AB+CD+*
234+*5* 12+3+
Prefix, Infix, Postfix
Pre- and postfix have the same advantages over infix notation:
unambiguous: infix notation requires precedence and associativity rules to disambiguate it, or adding extra parentheses. As long as the number of arguments to each operator are known in advance, both prefix and postfix notation are entirely unambiguous:
”* + 5 6 3” is (5+6)*3, cannot be interpreted as 5+(6*3), whereas parenthesis is required to achieve with infix.
supports operators with different numbers of arguments without variation of syntax. ”unary-op 5” and ”ternary-op 1 2 3” both work fine, but need special syntax to make them work in infix.
Infix, Prefix and Postfix Expresssions
Infix Expression A+B*C+D
(A + B) * (C + D) A*B+C*D A+B+C+D
Prefix Expression ++A*BCD * + A B + C D +*AB*CD +++ABCD
Postfix Expression ABC*+D+ A B + C D + * AB*CD*+ AB+C+D+
ArithLang Interpreter
input: a program, output: a value or error
read, evaluate and print three steps (see Interpreter.java) implemented a visitor design pattern
Interpreter – code overview
Interpreter.Java:
entry point, the beginning of the program
eval.valueOf(p) is the entry point for Evaluator
Evaluator.java:
Takes program, p as input and generates output
Each type of expression has a ”visit” function in Evaluator
AST.java:
Stores the data structure AST, each AST is a program that can be
an expression
In other words, ASTs are the implementation of the parse trees
AST has different types of nodes starting with program, expression …
Implementing the Visitor design pattern: visitor interface at line 100,
input is different type of AST nodes and output is either a value (Evaluator) or a string (Formatter)
Value.java:
defines types of the values in the programs
ArithLang Syntax and Its Implentation
Interpreter – Read Phase
lexical analysis: identify tokens and their types
parsing: constructing parse trees and convert them to (abstract syntax tree (AST)
Arithlang Syntax
Interpreter – Read Phase
arithlang.g (antlr syntax): check antlr cheat sheet to understand the symbols in the grammar file
antlr: parser generator
you can see generated ArithLangLexer.java and ArithLangParser.java
under build/generated-src/…
some other useful links: entire document, locals
see some examples of grammar rules
ArithLang Semantics and Its Implentation
Interpreter – Evaluate Phase
Goal: convert AST to value
Process like recursive tree traversal: to find value of program “(* 3 (+ 4 2))”, we first find value of sub-expressions “3” and “(+ 4 2)”
PL semantics is essentially a systematically defined recursive traversal strategy:
What to do at a AST node?
How to traverse sub AST nodes?
Completeness: traversal must be defined for each kind of AST nodes, otherwise programs will get stuck.
Arithlang Semantics: Legal Value
Interpreter – Evaluate Phase (visitor patterns)
Interpreter – Evaluate Phase (visitor patterns)
public class Evaluator implements Visitor⟨Value⟩
Value valueOf(Program p) {
return (Value) p.accept(this); }
public Value visit(Program p) { return (Value) p.e().accept(this); } public Value visit(AddExp e) public Value visit(NumExp e)
…
Semantics: Number
Semantics: Addition
Semantics: Subtraction
Semantics: Multiplication and Division
Semantics: Evaluate a Program
value of a program p is the value of its inner expression e
let p be a program and e be an expression
Review
ArithLang: a language only implements arithmetic
Design decisions: infix, prefix, postfix
Syntax: arithlang.g and its implementation in Antlr
Semantics: formal inference rules and its implementation in Visitor patterns