Martin Sulzmann
We extend the language of arithmetic expression with boolean expressions.
N ::= 0 | 1 | 2
B ::= true | false
V ::= N | B
E ::= V | (E) | E + E | E * E | E && E | E || EYour tasks are.
Implement a parser.
Implement a type inferencer.
You may either use a top-down parser or parser combinator functions. For both cases, rewrite the grammar such that parsing becomes deterministic.
You will also need to extend the AST to represent boolean expressions.
Below you find a top-down parser and type checker for integer expressions. You may take this code and add the necessary extensions (additional code + documentation).
package main
import "fmt"
import "strconv"
// parser with type checker
/*
SYNTAX:
We consider integer expressions of the following form.
N ::= 0 | 1 | 2
E ::= N | (E) | E + E | E * E
As we know the above grammar is ambigous. We make the grammar unambigous
by giving * a higher precedence than +.
E ::= E + T | T
T ::= T * F | F
F ::= N | (E)
The above grammar is unambiguous but not suitable for top-down parsing.
We remove left-recursion and obtain the following grammar.
E ::= T E2
E2 ::= + T E2 |
T ::= F T2
T2 ::= * F T2 |
F ::= N | (E)
N ::= 0 | 1 | 2
In your project, you need to carry out the above steps
for the enriched expression language that includes Boolean expressions.
TYPES:
We demand that integer expressions must be well-typed.
We don't consider variables which makes the typing rules rather simple.
i is an integer (covers 0, 1, 2)
(Int) -------------------------
|- i : int
|- e1 : int |- e2 : int
(+) -------------------------------
|- e1 + e2 : int
|- e1 : int |- e2 : int
(*) -------------------------------
|- e1 * e2 : int
Typing rules are defined in terms of ASTs.
In the above, we write
e1 + e2
to refer to the AST
+
/ \
e1 e2
In your project, you need to extend the typing rules to include Boolean expressions,
and you need to extend the implementation of the infer method (see below).
*/
type Type int
const (
TyIllTyped Type = 0
TyInt Type = 1
TyBool Type = 2
)
func showType(t Type) string {
var s string
switch {
case t == TyInt:
s = "Int"
case t == TyBool:
s = "Bool"
case t == TyIllTyped:
s = "Illtyped"
}
return s
}
// AST
type Exp interface {
pretty() string
infer() Type
}
type Num int
type Mult [2]Exp
type Plus [2]Exp
// pretty print
func (x Num) pretty() string {
return strconv.Itoa(int(x))
}
func (e Mult) pretty() string {
var x string
x = "("
x += e[0].pretty()
x += "*"
x += e[1].pretty()
x += ")"
return x
}
func (e Plus) pretty() string {
var x string
x = "("
x += e[0].pretty()
x += "+"
x += e[1].pretty()
x += ")"
return x
}
// Type inferencer/checker
func (x Num) infer() Type {
return TyInt
}
func (e Mult) infer() Type {
t1 := e[0].infer()
t2 := e[1].infer()
if t1 == TyInt && t2 == TyInt {
return TyInt
}
return TyIllTyped
}
func (e Plus) infer() Type {
t1 := e[0].infer()
t2 := e[1].infer()
if t1 == TyInt && t2 == TyInt {
return TyInt
}
return TyIllTyped
}
// Simple scanner/lexer
// Tokens
const (
EOS = 0 // End of string
ZERO = 1
ONE = 2
TWO = 3
OPEN = 4
CLOSE = 5
PLUS = 6
MULT = 7
)
func scan(s string) (string, int) {
for {
switch {
case len(s) == 0:
return s, EOS
case s[0] == '0':
return s[1:len(s)], ZERO
case s[0] == '1':
return s[1:len(s)], ONE
case s[0] == '2':
return s[1:len(s)], TWO
case s[0] == '+':
return s[1:len(s)], PLUS
case s[0] == '*':
return s[1:len(s)], MULT
case s[0] == '(':
return s[1:len(s)], OPEN
case s[0] == ')':
return s[1:len(s)], CLOSE
default: // simply skip everything else
s = s[1:len(s)]
}
}
}
type State struct {
s *string
tok int
}
func next(s *State) {
s2, tok := scan(*s.s)
s.s = &s2
s.tok = tok
}
// E ::= T E'
func parseE(s *State) (bool, Exp) {
b, e := parseT(s)
if !b {
return false, e
}
return parseE2(s, e)
}
// E' ::= + T E' |
func parseE2(s *State, e Exp) (bool, Exp) {
if s.tok == PLUS {
next(s)
b, f := parseT(s)
if !b {
return false, e
}
t := (Plus)([2]Exp{e, f})
return parseE2(s, t)
}
return true, e
}
// T ::= F T'
func parseT(s *State) (bool, Exp) {
b, e := parseF(s)
if !b {
return false, e
}
return parseT2(s, e)
}
// T' ::= * F T' |
func parseT2(s *State, e Exp) (bool, Exp) {
if s.tok == MULT {
next(s)
b, f := parseF(s)
if !b {
return false, e
}
t := (Mult)([2]Exp{e, f})
return parseT2(s, t)
}
return true, e
}
// F ::= N | (E)
func parseF(s *State) (bool, Exp) {
switch {
case s.tok == ZERO:
next(s)
return true, (Num)(0)
case s.tok == ONE:
next(s)
return true, (Num)(1)
case s.tok == TWO:
next(s)
return true, (Num)(2)
case s.tok == OPEN:
next(s)
b, e := parseE(s)
if !b {
return false, e
}
if s.tok != CLOSE {
return false, e
}
next(s)
return true, e
}
return false, (Num)(0)
}
func parse(s string) Exp {
st := State{&s, EOS}
next(&st)
_, e := parseE(&st)
if st.tok == EOS {
return e
}
return (Num)(0) // dummy value
}
func debug(s string) {
fmt.Printf("%s", s)
}
func test(s string) {
e := parse(s)
fmt.Printf("\n %s", e.pretty())
fmt.Printf("\n %s", showType(e.infer()))
}
func testParserGood() {
fmt.Printf("\n GOOD \n")
test("1")
test("1+0")
test("1 * 2 ")
test(" (1) ")
test(" (1 * (2)) ")
test(" (1 + 2) * 0 ")
}
// Helper functions to build ASTs by hand
func number(x int) Exp {
return Num(x)
}
func plus(x, y Exp) Exp {
return (Plus)([2]Exp{x, y})
// The type Plus is defined as the two element array consisting of Exp elements.
// Plus and [2]Exp are isomorphic but different types.
// We first build the AST value [2]Exp{x,y}.
// Then cast this value (of type [2]Exp) into a value of type Plus.
}
func mult(x, y Exp) Exp {
return (Mult)([2]Exp{x, y})
}
func examplesAST() {
ast1 := plus(mult(number(1), number(2)), number(0))
fmt.Printf("\n %s", ast1.pretty())
fmt.Printf("\n %s", showType(ast1.infer()))
}
func main() {
fmt.Printf("\n")
// testParserGood()
examplesAST()
}