Creating a Small Interpreter
The goal is to sketch out a language that’s just barely powerful enough to write some classic programs, notably one that calculates the Fibonacci sequence recursively. You know, the one that you always screw up at job interviews. To this end we’re going to need the usual print and variable assignment statements, arithmetic and boolean expressions, loop and conditional constructs and, most importantly, functions. This language is actually part of Dhaka’s test suite – look at the tests prefixed with ‘chittagong’. Realize that this is not a tutorial on designing a good programming language – it’s just a demonstration of Dhaka’s features.
An Overview of the Grammar
The grammar is too long to describe in a detailed fashion (see test/chittagong/chittagong_grammar.rb), but this is
how the overall structure of a program is declared:
for_symbol(Dhaka::START_SYMBOL_NAME) do program %w| opt_terms main_body opt_terms | end for_symbol('main_body') do single_main_body_statement %w| main_body_statement | multiple_main_body_statements %w| main_body terms main_body_statement | end for_symbol('main_body_statement') do main_body_simple_statement %w| simple_statement | function_definition %w| def function_name ( arg_declarations ) terms function_body terms end | main_body_if_statement %w| if expression terms main_body terms end | main_body_if_else_statement %w| if expression terms main_body terms else terms main_body terms end | main_body_while_statement %w| while expression terms main_body terms end | end
A program is simply a series of main body statements, separated by terms, which are newline characters. Return statements aren’t allowed in the main body. Function body statements are very similar, except they don’t allow function definitions, but do allow return statements.
Further along the same file, we specify the basic expressions allowed in the language. The operators are a subset of the Ruby operators and work more or less like they do in Ruby.
for_symbol('expression') do negation %w| ! expression | equality_comparison %w| expression == expression | greater_than_comparison %w| expression > expression | less_than_comparison %w| expression < expression | addition %w| expression + expression | subtraction %w| expression - expression | multiplication %w| expression * expression | division %w| expression / expression | power %w| expression ^ expression | literal %w| numeric_literal | function_call_expression %w| function_name ( arg_list ) | variable_reference %w| var_name | parenthetized_expression %w| ( expression ) | negated_expression %w| - expression |, :prec => '*' end
When creating a parser for this grammar, the generator reports a whole bunch of shift-reduce conflicts (80 to be exact). This is due to the manner in which we specify the expansions for expression, which is very ambiguous, but has the benefit of being compact. The conflicts that
arise are all resolved by the precedences specified in the grammar.
Creating a Lexer Specification
The lexical structure of this language is complicated enough that writing a tokenizer by hand would be tedious. Instead, we will generate the lexer by specifying the regular expression patterns that correspond to the various tokens:
class ChittagongLexerSpecification < Dhaka::LexerSpecification KEYWORDS = %w| print if else end while def return | for_pattern('==') do create_token('==') end %w| = - ! > < , + * ( ) / ^ |.each do |char| for_symbol(char) do create_token(char) end end for_pattern("\n") do create_token('newline') end for_pattern(' ') do # ignore whitespace end for_pattern('\w+') do if KEYWORDS.include? current_lexeme.value create_token current_lexeme.value else create_token 'word_literal' end end for_pattern('\d*(\.\d+)?') do create_token('numeric_literal') end end
The interesting bit here is the part that handles keywords. When the lexer sees a word token, it transfers control to the block that we defined here:
for_pattern('\w+') do if KEYWORDS.include? current_lexeme.value create_token current_lexeme.value else create_token 'word_literal' end end
The block simply checks if the value of the currently recognized lexeme is a member of the KEYWORDS array – if so, then it creates a keyword token, otherwise a word_literal token with the value of the lexeme.
The Evaluator
To store variables we need a table of some sort, called a frame. Since we have functions in our language, each function scope must have its own frame. In other words, the runtime environment must have a stack of frames. This functionality can be achieved readily with an array of hashes. For storing function names and definitions, a global table suffices, since functions will not be subject to scoping, achieved, once again, with a hash. The last piece is an output stream that the print statement and exceptions can print to. These are either injected or created in the evaluator’s initialize method:
def initialize(stack, output_stream) @stack = stack @function_table = {} @output_stream = output_stream end
Probably the two most interesting evaluation rules are the ones for defining and evaluating functions. In the dice roller and bracket packing examples, the result of evaluating a node depended on the results of evaluating its child nodes. For example, when evaluating addition, we wanted to know the evaluation results of the subtrees of each operand. When processing a function definition, however, we cannot evaluate the body of the function. Instead we must store it, so that it can be evaluated later. This is how function definition statements are processed:
for_function_definition do function_name = evaluate(child_nodes[1]) arg_declarations = evaluate(child_nodes[3]) body = child_nodes[6] @function_table[function_name] = Function.new(arg_declarations, body) ChittagongSuccessResult.new(nil) end
The only trick here is in the third line of the block where we assign the child node directly to the body without wrapping it in a call to evaluate. We’re actually storing the parse tree of the function body in a hash keyed by the function name so we can evaluate it at a later time. Not much can go wrong when you’re processing a function definition – the grammar takes care of enforcing all the rules, so as long as the code parses, it’s okay. The logic for evaluating function calls, however, is more complex, since we need to check for exceptions:
def checked_function_call function_name = evaluate(child_nodes[0]) return ChittagongExceptionResult.new("Undefined function #{function_name}", child_nodes[0]) unless @function_table.has_key?(function_name) arg_values = evaluate(child_nodes[2]) return arg_values if arg_values.exception function = @function_table[function_name] return ChittagongExceptionResult.new( "Wrong number of arguments", child_nodes[1] ) unless function.args.size == arg_values.result.size new_frame = {} function.args.zip(arg_values.result).each do |arg_name, arg_value| new_frame[arg_name] = arg_value end @stack << new_frame result = evaluate(function.body) @stack.pop result end
First we check to see if the function is defined, and if not, raise an exception (note that an exception in our mini-language is not a Ruby exception, just an instance of ChittagongExceptionResult which is returned to the caller). Next, we evaluate the arguments, and if the result is an exception, pass it up to the caller. If not, we check to see if the number of arguments passed to the function call matches the declaration of the function and create a new exception if that is not the case. If everything is okay so far, we create a new stack frame and bind the argument values to the function’s argument declarations on this frame. We push the new frame onto the stack, evaluate the function body, store the result, pop the new frame off the stack and return the result to the caller.
Tying it together
The last component is something that wires the Lexer, Parser and Evaluator together. This component, called the Driver for lack of a better name, checks the result of each step to see if an error occurred, in which case it pretty-prints the exception and the source, indicating where the error was caused. The most important method is run:
def run(program) parse_result = ChittagongParser.parse(ChittagongLexer.lex(program)) case parse_result when Dhaka::TokenizerErrorResult return tokenize_error_message(parse_result.unexpected_char_index, program) when Dhaka::ParseErrorResult return parse_error_message(parse_result.unexpected_token, program) end evaluation_result = ChittagongEvaluator.new([{}], output_stream = []). evaluate(parse_result) if evaluation_result.exception return (output_stream << evaluation_error_message(evaluation_result, program)). join("\n") end return output_stream.join("\n") end
The result of each step, if it contains an error, also contains the information about the portion of the source that the error came from. In the event of an error while lexing the input, a TokenizerErrorResult can be queried for the location in the source of the unexpected character. Similarly, a ParseErrorResult can be queried for the unexpected token. The evaluator we defined returns the parse tree node that it was attempting to evaluate when it encounters an error.
Using this driver, a test for variable scoping looks like this:
def test_variable_scope program = " x = 1 def bar(n) print 999 end def foo(n) bar(x) end foo(2) " assert_equal( "Undefined variable x: x = 1 def bar(n) print 999 end def foo(n) bar(>>>x) end foo(2) ", @driver.run(program)) end
Finally, we can write our doubly-recursive Fibonacci function:
def test_recursive_fibonacci program = " def fib(n) if n == 0 return 1 end if n == 1 return 1 end return fib(n-1) + fib(n-2) end x = 0 while x < 9 print fib(x) x = x + 1 end " assert_equal(["1.0", "1.0", "2.0", "3.0", "5.0", "8.0", "13.0", "21.0", "34.0"].join("\n"), @driver.run(program)) end