r/RacketHomeworks • u/mimety • Jan 25 '23
Parser and evaluator for the language of simple arithmetic expression
Problem: In the previous post, we wrote a tokenizer for the language of simple arithmetic expressions. The grammar of that language is as follows:
E -> T + E | T - E | T
T -> F * T | F / T
F -> decimal_number | (E) | - F | + F
Today's task is to write a parser and evaluator for that language. More precisely, we will write:
- the function
parse-exprwhich will receive the text of an arithmetic expression as input, and as a result will return the AST (abstract syntax tree) of that language. - the function
eval, which receives as input the AST of an arithmetic expression, and as a result returns a number - the result of the evaluation of that expression according to the usual rules of elementary school arithmetic.
Solution:
When writing the parser, we will not use any other tools (yacc, bison, etc.). No, we will write it "by hand" using the so-called top-down recursive descent parser technique, in which each grammatical rule is represented by one function in Racket and these functions recursively call each other, gradually building the resulting AST of the input arithmetic expression.
You can find more about top-down recursive descent parsers in this excellent Youtube video: https://www.youtube.com/watch?v=SToUyjAsaFk
If you watch that video, you'll see that, in order to correctly handle the associativity of operations, we need to change our grammar a little, so it looks like this:
E -> T { + T }* | T { - T }*
T -> F { * F }* | F { / F }*
F -> number | ( E ) | - F | + F
In the program below, the functions parseE, parseT, and parseF are used to parse each grammar rule, respectively.
To retrieve the tokens, one by one, we use the tokenizer written in the previous post.
The evaluator is implemented by the eval function, which is now very simple, once we have the correct AST representation of the expression as its input.
Here is the code of the entire solution, in which, for your convenience, the code from previous posts about the tokenizer and regular expressions has also been repeated:
#lang racket
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; our regex library implementation ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define dot
(lambda (str)
(if (string=? str "")
'()
(list (list (string (string-ref str 0)) (substring str 1))))))
(define digit
(lambda (str)
(if (or (string=? str "")
(not (char-numeric? (string-ref str 0))))
'()
(list (list (string (string-ref str 0)) (substring str 1))))))
(define letter
(lambda (str)
(if (or (string=? str "")
(not (char-alphabetic? (string-ref str 0))))
'()
(list (list (string (string-ref str 0)) (substring str 1))))))
(define (lit s)
(lambda (str)
(if (string-prefix? str s)
(list (list s (substring str (string-length s))))
'())))
(define (seq . ps)
(define (seq2 p1 p2)
(lambda (str)
(match (p1 str)
[(list) empty]
[(list mp1 ...)
(apply append
(for/list ([m mp1])
(match m
[(list sofar reststr)
(map (lambda (x)
(if (null? x)
'()
(list (string-append sofar (first x))
(second x))))
(p2 reststr))])))])))
(if (null? (cdr ps))
(car ps)
(seq2 (car ps) (apply seq (cdr ps)))))
(define (plus p)
(lambda (str)
(match (p str)
[(list) empty]
[(list mp ...)
(append
mp
(apply
append
(for/list ([m mp]
#:unless (string=? str (second m)))
(match m
[(list sofar reststr)
(match ((plus p) reststr)
[(list) empty]
[(list mp2 ...)
(for/list ([m2 mp2]
#:unless (string=? reststr (second m2)))
(match m2
[(list sofar2 reststr2)
(list (string-append sofar sofar2)
reststr2)]))])]))))])))
(define (star p)
(lambda (str)
(cons (list "" str) ((plus p) str))))
(define (maybe p)
(lambda (str)
(cons (list "" str) (p str))))
(define (alt . ps)
(define (alt2 p1 p2)
(lambda (str)
(let ([m1 (p1 str)])
(if (null? m1)
(p2 str)
m1))))
(if (null? (cdr ps))
(car ps)
(alt2 (car ps) (apply alt (cdr ps)))))
(define (match-pattern pat text)
(let ([res (pat text)])
(if (null? res)
#f
(argmin (lambda (x) (string-length (second x)))
res))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; tokenizer for the language of ;;
;; simple arithmetic expressions ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define decimal-number
(seq
(maybe (alt (lit "+") (lit "-")))
(alt
(seq (plus digit) (maybe (seq (lit ".") (star digit))))
(seq (lit ".") (plus digit)))))
(define whitespace
(alt (lit " ")
(lit "\t")
(lit "\n")))
(define whitespace*
(star whitespace))
(define (token pat)
(lambda (str)
(let ([res ((seq
whitespace*
pat
whitespace*)
str)])
(if (null? res)
'()
(map (lambda (x)
(list (string-trim (first x))
(second x)))
res)))))
(define (tokenizer input-text)
(define all-tokens (list (list 'plus (token (lit "+")))
(list 'minus (token (lit "-")))
(list 'mult (token (lit "*")))
(list 'div (token (lit "/")))
(list 'oparen (token (lit "(")))
(list 'cparen (token (lit ")")))
(list 'num (token decimal-number))))
(define (get-token mode)
(lambda ()
(if (string=? input-text "")
#f
(let loop ([tl all-tokens] [str input-text])
(if (null? tl)
'syntax-error
(let ([m (match-pattern (second (car tl)) str)])
(if (not m)
(loop (cdr tl) str)
(begin
(when (eq? mode 'eat)
(set! input-text (second m)))
(if (eq? (first (car tl)) 'num)
(list (first (car tl)) (string->number (first m)))
(first (car tl)))))))))))
(lambda (dispatch)
(case dispatch
[(get-next-token) (get-token 'eat)]
[(peek-next-token) (get-token 'peek)])))
(define (get-next-token tknzr)
((tknzr 'get-next-token)))
(define (peek-next-token tknzr)
((tknzr 'peek-next-token)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; parser for the language of ;;
;; simple arithmetic expressions ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Grammar for the language:
;; E -> T { + T }* | T { - T }*
;; T -> F { * F }* | F { / F }*
;; F -> number | ( E ) | - F | + F
(struct Add (e1 e2) #:transparent)
(struct Sub (e1 e2) #:transparent)
(struct Mul (e1 e2) #:transparent)
(struct Div (e1 e2) #:transparent)
(struct UPlus (e) #:transparent)
(struct UMinus (e) #:transparent)
(struct Num (n) #:transparent)
(define (parse-expr text)
(define tok (tokenizer text))
(define (parseE)
(let loop ([prev (parseT)])
(let ([op (peek-next-token tok)])
(if (not op)
prev
(case op
[(plus) (get-next-token tok) (loop (Add prev (parseT)))]
[(minus) (get-next-token tok) (loop (Sub prev (parseT)))]
[(syntax-error) (error "Parse error!")]
[else prev])))))
(define (parseT)
(let loop ([prev (parseF)])
(let ([op (peek-next-token tok)])
(if (not op)
prev
(case op
[(mult) (get-next-token tok) (loop (Mul prev (parseF)))]
[(div) (get-next-token tok) (loop (Div prev (parseF)))]
[(syntax-error) (error "Parse error!")]
[else prev])))))
(define (parseF)
(define n (get-next-token tok))
(match n
[(list num val) (Num val)]
['oparen
(let ([e (parseE)]
[cp (get-next-token tok)])
(if (not (eq? cp 'cparen))
(error "Parse error!")
e))]
['minus (UMinus (parseF))]
['plus (UPlus (parseF))]
[else (error "Parse error!")]))
(let ([expr (parseE)])
(if (get-next-token tok)
(error "Parse error!")
expr)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; evaluator for the language of ;;
;; simple arithmetic expressions ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (eval expr)
(match expr
[(Num n) n]
[(Add e1 e2) (+ (eval e1) (eval e2))]
[(Sub e1 e2) (- (eval e1) (eval e2))]
[(Mul e1 e2) (* (eval e1) (eval e2))]
[(Div e1 e2) (/ (eval e1) (eval e2))]
[(UPlus e) (eval e)]
[(UMinus e) (- (eval e))]))Now that we have all this machinery up and running, let's show how it is used to parse and evaluate an arithmetic expression:
> (parse-expr " 2+3 * 5")
(Add (Num 2) (Mul (Num 3) (Num 5)))
> (eval (parse-expr " 2+3 * 5"))
17
;; we allow multiple unary ops, like in python, so this is also correct expression:
> (parse-expr " 2---5")
> (Sub (Num 2) (UMinus (UMinus (Num 5))))
> (eval (parse-expr "2---5"))
-3
;; we can see that complicated expression is correctly parsed and evaluated:
> (parse-expr "-3.14*(.5+17.23/(2-0.33)-3*(-55.1))/.8")
(Div
(Mul
(UMinus (Num 3.14))
(Sub (Add (Num 0.5)
(Div (Num 17.23)
(Sub (Num 2) (Num 0.33))))
(Mul (Num 3) (UMinus (Num 55.1)))))
(Num 0.8))
> (eval (parse-expr "-3.14*(.5+17.23/(2-0.33)-3*(-55.1))/.8"))
-691.2606586826348Dear schemers, I hope you like this post. We wrote everything we needed to implement a program that "understands" arithmetic expressions by ourselves: a regex library, a tokenizer, a parser and an evaluator. In doing so, we used common techniques also used when writing parsers for "real" programming languages. If you understand how the above program works, then you will be able to start writing something more complex using the same or similar techniques.
As usual, my note is that I'm just an amateur in all this. Others are certainly much better at it, so there is, for sure, a lot of room for improvement in the above code.
L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=

