Interpreter

From CS 61A Wiki
Jump to: navigation, search

An interpreter is a program that translates user input into computable data, then outputs desired results. It evaluates input by first separating user input into a sequence of tokens and analyzing them, a technique called parsing, then evaluating the disjointed expression. Evaluating is often a complex process of applying functions to combine elements until the expression is completely simplified. The interpreter will will recursion to reach the most primitive elements of the expression before attempting to apply functions on them.

For example, the expression (+ (* 3 4) 5) will be separated into ['(', '+', '(', '*', 3, 4, ')', 5, ')']. The interpreter will recurse into the most deeply nested case, (* 3 4), and evaluate it by applying * to 3 and 4. The expression will now be (+ (12 5). Now the interpreter will apply + to 12 and 5, resulting in an output of 17.

Parsing

Parsing is the process of generating expression trees from raw text input[1]. User input in Scheme consists of nested and grouped elements conjoined by functions. A typical mathematical expression would look like (+ 3 4), where the function preceeds the elements. Since the input is text based, the interpreter will need to break it into individual elements then create Pair objects that represent the expression. A (+ 3 4) input would become ['(' , '3' , '4' , ')'], then be converted to Pair("+", Pair('3', Pair('4', nil))). With this Pair object representation, the interpreter can now evaluate it.

Eval/apply

Calculator

Main article: Calculator

References

  1. http://composingprograms.appspot.com/pages/34-interpreters-for-languages-with-combination.html#expression-trees