The stages of evaluation are as follows:
Tokenization:: input a string and output a list of strings and numbers; for example, The 17-character string "(= (+ 3 55) 21)" should yield the following list of eight strings: (list "(" "=" "(" "+" 3 55 ")" 21 ")"). This can be done using a finite state machine with side effects; but you can do it any way you like.
Parsing: Input a list of strings and numbers, and output a nested list reflecting its original structure. For example, the input (list "(" "=" "(" "+" 3 55 ")" 21) should yield the output (list "=" (list "+" 3 5) 21). This can be done using a push down automaton; but you can do it any way you like.
Evaluate: Input a nested list of strings and numbers and output a number or true or false. For example, the input (list "=" (list "+" 3 5) 21)should yield an output of false. This can be done using recursion (there is no other reasonable way).
This means in Racket your eval function should look like this:
(def (eval s) (evaluate (parse (tokenize s))))
Email your commented source code as a single file to [email protected] by midnight on May 15.
Grading will be as follows:
correct tokenizer: 25%
correct parser: 25%
correct evaluator: 25%
clear, concise documentation: 25%
Your documentation should include instructions on how to compile and test your program. If your project is incomplete, include in your documentation a description of which parts work and how to test them.
and this a pseudo code given for tokenizer
1 Input string
2 Variables: state = 'empty', chars = , tokens = , nextSate, nextChar (last two have no initial value)
3 while string is not empty:
Set nextChar equal to the first character of string
Set nextState equal to trans(state, nextChar) (trans is a helper function you must write)
If pushChar(state, nextState) then
push nextChar onto the back of chars. (pushCar is a Boolean helper function you must write)
If pushToken(state, nextState) then
push maketoken(chars) onto the back of tokens (maketoken is a helper function you must write. It converts strings to either strings or numbers).
set chars to the empty list
remove the first character from string
set state equal to nextState
4 return tokens
#lang racket (define read-input(string)) (define state "empty") (define chars '()) (define tokens '()) (define nextChar " " ) (define nextState " ") (define (trans state nextChar) (cond [(equal? state " ") (cond [(equal? nextChar #\i) "i-if"] [(equal? nextChar #\+) "addition"] [(equal? nextChar #\*) "multiplication"] [(equal? nextChar #\=) "equals"] [(char-numeric? nextChar) "num"] [else "error"])] [(equal? state "number") (if (char-numeric? nextChar) "number" " ")] [(equal? state "i-if") (if (equal? nextChar #\f) "f-if" "error")] [else "error"] )) ;(define (pushChar state nextState) ;)/> ;(define (maketoken chars) ;)/> ;(define (pushToken state nextState) ;)/>
I am having trouble implementing
the functions above that have been commented out, can someone tell how to make sense of the pseudocode for part 3 4 and 5.