Lecture 3. ArithLang – Arithmetics
Lecture 3. ArithLang – Arithmetics
January 27, 2021
Overview
I A language that implements float/integer arithmetic
I Design decision: prefix, infix and postfix
I Interpreter: Java
I 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
I Prefix: Operators are written before their operands. Operators act
on the two nearest values on the right. (Lisp, Scheme uses prefix
forms)
+ + A * B C D
* + A B + C D
+ + 1 2 3
I Infix: Operators are written in-between their operands.
1 + 2 + 3
I Postfix: Operators are written after their operands. Operators act
on values immediately to the left of them.
A B C * + D +
A B + C D + *
2 3 4 + * 5 *
1 2 + 3 +
Prefix, Infix, – and postfix have the same advantages over infix notation:
I 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.
I 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
Infix Expression Prefix Expression Postfix Expression
A + B * C + D + + A * B C D A B C * + D +
(A + B) * (C + D) * + A B + C D A B + C D + *
A * B + C * D + * A B * C D A B * C D * +
A + B + C + D + + + A B C D A B + C + D +
ArithLang Interpreter
I input: a program, output: a value or error
I read, evaluate and print three steps (see Interpreter.java)
I implemented a visitor design pattern
Interpreter – code overview
I Interpreter.Java:
I entry point, the beginning of the program
I eval.valueOf(p) is the entry point for Evaluator
I Evaluator.java:
I Takes program, p as input and generates output
I Each type of expression has a ”visit” function in Evaluator
I AST.java:
I Stores the data structure AST, each AST is a program that can be
an expression
I In other words, ASTs are the implementation of the parse trees
I AST has different types of nodes starting with program, expression …
I 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)
I Value.java:
I defines types of the values in the programs
ArithLang Syntax and Its Implentation
Interpreter – Read Phase
I lexical analysis: identify tokens and their types
I parsing: constructing parse trees and convert them to (abstract
syntax tree (AST)
Arithlang Syntax
Interpreter – Read Phase
I arithlang.g (antlr syntax): check antlr cheat sheet to understand the
symbols in the grammar file
I antlr: parser generator
I you can see generated ArithLangLexer.java and ArithLangParser.java
under build/generated-src/…
I some other useful links: entire document, locals
see some examples of grammar rules
https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687036/ANTLR+Cheat+Sheet
https://www.antlr.org/
https://github.com/antlr/antlr4/blob/master/doc/actions.md
https://github.com/antlr/antlr4/blob/master/doc/actions.md
ArithLang Semantics and Its Implentation
Interpreter – Evaluate Phase
I Goal: convert AST to value
I Process like recursive tree traversal: to find value of program “(* 3
(+ 4 2))”, we first find value of sub-expressions “3” and “(+ 4 2)”
I PL semantics is essentially a systematically defined recursive
traversal strategy:
I What to do at a AST node?
I How to traverse sub AST nodes?
I 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)
I public class Evaluator implements Visitor〈Value〉
I Value valueOf(Program p) {
return (Value) p.accept(this); }
I 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
I ArithLang: a language only implements arithmetic
I Design decisions: infix, prefix, postfix
I Syntax: arithlang.g and its implementation in Antlr
I Semantics: formal inference rules and its implementation in Visitor
patterns