Paul Batum

So you probably noticed I haven't been posting much about the parsing stuff lately and thats because I stopped working on it. I got to the point where wikipedia + lecture notes isn't quite cutting it and I've been unable to find a resource that tackles the subject matter in a way I am comfortable with. A good textbook could make a big difference and there are a few out there that look promising but my heart is not in it at the moment. I'm somewhat torn in between wanting to finish the projects I start and making sure that I am enjoying the projects. However the simple fact is that this plan of less video games and more programming/reading/learning is only sustainable if I am really enjoying the work. My intention is to come back to the compilers stuff in a few months and spend time looking at some of the programs out there that make compiler/interpreter development easier. Previously I avoided this because I wanted to learn the fundamentals and I found this to be worthwhile. It was never my intention to implement an actual compiler or interpreter completely from scratch, although I had hoped to get somewhat further than I did. In any case, the topic that holds my interest at the moment is that of a web development framework called Ruby on Rails. Rails interests me for a number of reasons but I think the primary driver is frustration with ASP.NET at work. I have read about the model-view-controller pattern but never actually worked with it first hand so I am curious about how it compares to developing with web forms. Rather than downloading and configuring Rails locally I am making use of Heroku - they provide free Rails hosting with an integrated development environment. I'm sure you will hear how I'm finding it soon enough.

The test that was failing was this one:

 def test_left_compound # "((500*20)+16)"
 tokens = [LeftParenToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new(), AdditionToken.new(), IntegerToken.new(16), RightParenToken.new()]
 assert(tokens_are_valid(tokens))
end

lookup[:E][LeftParenToken] = [:lpar, :E, :rpar, :T]

After reading about some different types of parsers, I decided to have a go at LL(1). This means the parser works Left-to-right, generates the Leftmost derivation and looks one token ahead. The basic idea of LL(1) is to build a stack of symbols that represent the derived expression by using a lookup table that tells you what rule to apply based on the current symbol and current token. Not all context free grammars can be parsed using LL(1) but I think the calculator's grammar can, with some modification. Lets break the work into some smaller steps:

1. Modify the grammar I described last week to support LL(1) parsing.
2. Modify the tokens_are_valid method to use LL(1) to verify whether the token stream is well formed. Given that I already have tests for tokens_are_valid, I will know that I am already on the right track once the existing tests are passing with the new implementation.
3. Add syntax tests for parentheses. Watch them fail.
4. Modify the tokens_are_valid implementation to make the new tests pass. Once this is happening we are done with using LL(1) for syntax verification and can move on to using LL(1) to actually do the parsing.
5. Modify the build_tree method to use LL(1) and watch the operator precedence tests fail because my grammar doesn't deal with the precedence issue.
6. Fix the grammar to support operator precedence, make the corresponding changes to the lookup table and watch the tests pass.
7. Add evaluation tests for parentheses . I think these babies should automatically work if I've done the other steps right.

class AdditionToken < OperatorToken
def symbol
 return :plus
end
end

class Symbol
def non_terminal?
 return (self == :T || self == :E)
end
end

class EndToken
def symbol
 return :end
end
end

def create_lookup_table()
lookup = {}
lookup[:E] = {}
lookup[:E][IntegerToken] = [:int,:T]
lookup[:E][LeftParenToken] = [:lpar, :E, :rpar]
lookup[:T] = {}
lookup[:T][AdditionToken] = [:plus, :E]
lookup[:T][SubtractionToken] = [:minus, :E]
lookup[:T][MultiplicationToken] = [:multiply,:E]
lookup[:T][DivisionToken] = [:divide, :E]
lookup[:T][RightParenToken] = []
lookup[:T][EndToken] = []
return lookup
end

def tokens_are_valid(tokens)
tokens = tokens.dup
symbols = [:E]
lookup = create_lookup_table()

# The symbol and token arrays can be used as stacks if the contents is first reversed.
# An end token/symbol is appended to each before they are reversed.
tokens.push(EndToken.new())
tokens.reverse!
symbols.push(:end)
symbols.reverse!

while(tokens.size > 0)
 current_symbol = symbols.pop() #The current symbol will always be consumed. Safe to pop.
 current_token = tokens.last #The current token won't necessarily be consumed, cannot pop it yet.
 if(current_symbol.non_terminal?)
 result = lookup[current_symbol][current_token.class]
 return false if result.nil? 
 symbols.push(result.reverse)
 symbols.flatten! 
 else
 return false if current_symbol != current_token.symbol
 tokens.pop()
 end 
end

return true
end

irb(main):001:0> x = [1,2,3]
=> [1, 2, 3]
irb(main):002:0> y = x.reverse
=> [3, 2, 1]
irb(main):003:0> x
=> [1, 2, 3]
irb(main):004:0> x.reverse!
=> [3, 2, 1]
irb(main):005:0> x
=> [3, 2, 1]

class ParenthesesSyntaxTests < Test::Unit::TestCase
def test_surround_one_number # "(1)"
 tokens = [LeftParenToken.new(),IntegerToken.new(1), RightParenToken.new()]
 assert(tokens_are_valid(tokens))
end 

def test_surround_operation # "(1+2)"
 tokens = [LeftParenToken.new(),IntegerToken.new(1), AdditionToken.new(), IntegerToken.new(2), RightParenToken.new()]
 assert(tokens_are_valid(tokens))
end

def test_left_compound # "((500*20)+16)"
 tokens = [LeftParenToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new(), AdditionToken.new(), IntegerToken.new(16), RightParenToken.new()]
 assert(tokens_are_valid(tokens))
end

def test_right_compound # "(16+(500*20))"
 tokens = [LeftParenToken.new(), IntegerToken.new(16), AdditionToken.new(), LeftParenToken.new(), IntegerToken.new(500), MultiplicationToken.new(), IntegerToken.new(20), RightParenToken.new() , RightParenToken.new()]
 assert(tokens_are_valid(tokens))
end

def test_empty_parens_error # "()"
 tokens = [LeftParenToken.new(), RightParenToken.new()]
 assert(!tokens_are_valid(tokens))
end

def test_wrong_order_error # ")2("
 tokens = [RightParenToken.new(), IntegerToken.new(1), LeftParenToken.new()]
 assert(!tokens_are_valid(tokens))
end

def test_no_operator_adjacent_to_paren_error # "1+2(3+4)"
 tokens = [IntegerToken.new(1), AdditionToken.new(), IntegerToken.new(2), LeftParenToken.new(), IntegerToken.new(3), AdditionToken.new(), IntegerToken.new(4), RightParenToken.new()]
 assert(!tokens_are_valid(tokens))
end

end

I started writing a post on the work I've done this week but soon realised that it would be useful to explain grammars a bit more before continuing. After all, it is possible that some of you went to the Wikipedia page for context-free grammars and were (like me) unable to curb the involuntary reflex to close the tab as soon as that stack of ugly math symbols came into view. Anyway, lets get to it. To make a grammar you need the following:

1. One or more terminal symbols.
2. One or more non-terminal symbols.
3. A start symbol (must be non-terminal).
4. Production rules that relate a non-terminal symbol to a set of symbols.

This series on writing a program that can evaluate simple arithmetic expressions is all about baby steps. I have no idea what I'm doing in terms of the problem space and I'm similarly ignorant of my tool, Ruby. But I'm making progress and have a good idea of what is next:

• expand number support to the rationals
• report the position of a syntax error when found
• implement support for parentheses

There are a few loose ends to tie up and then the first pass of the calculator is complete. If you've forgotten where I was up to, here is a quick reminder:

• The calculator falls over when the numbers get big because I implemented the tree evaluation in a educational but less than practical manner.
• Whitespace should be ignored.
• The codebase needs a general cleanup.

class OperatorToken
 attr_reader :multitive, :value

 def evaluate(container_node)
 return do_operation(container_node.left_child.evaluate(), container_node.right_child.evaluate())
 end 
end

class AdditionToken < OperatorToken
 def initialize()
 @value = "+"
 @multitive = false
 end

 def do_operation(left_child_value, right_child_value)
 return left_child_value + right_child_value
 end 
end

 def test_spaces
 assert_equal([14,"+",62,"*",127], tokenize_for_value(" 14 +62* 127 ") ); end

C:\Users\Paul>irb
irb(main):001:0> require 'calculator_v1'
=> true
irb(main):002:0> calculate "10 + 2*6"
=> 22
irb(main):003:0> calculate "1000000000000000000000000000000000-1"
=> 999999999999999999999999999999999
irb(main):004:0> calculate "x-1"
=> "Syntax Error"
irb(main):005:0>

Lets start off with some tests:

class EvaluateTests < Test::Unit::TestCase
 def test_1
 assert_equal(1, calculate("1"))
 end
 
 def test_add
 assert_equal(3, calculate("1+2"))
 end
 
 def test_subtract
 assert_equal(3, calculate("7-4"))
 end
 
 def test_multiply
 assert_equal(6, calculate("3*2"))
 end
 
 def test_divide
 assert_equal(3, calculate("6/2"))
 end
 
 def test_negative_result
 assert_equal(-1, calculate("1-2"))
 end
 
 def test_multitive_before_additive
 assert_equal(14, calculate("4*3+2"))
 assert_equal(14, calculate("2+3*4"))
 assert_equal(10, calculate("4+3*2"))
 end
 
 def test_left_to_right
 assert_equal(8, calculate("12-6+2"))
 assert_equal(4, calculate("12/6*2"))
 end
end

def calculate(expression)
 tokens = tokenize(expression)
 root_node = build_tree(tokens)
 return root_node.evaluate()
end

class BinaryTreeNode
 def evaluate()
 return @token.evaluate(self)
 end
end

class IntegerToken < Token
 def evaluate(containerNode)
 return @value
 end
end

class OperatorToken
 def evaluate(containerNode)
 case @value
 when "+"
 return containerNode.lhs.evaluate() + containerNode.rhs.evaluate()
 when "-"
 return containerNode.lhs.evaluate() - containerNode.rhs.evaluate()
 when "*"
 return containerNode.lhs.evaluate() * containerNode.rhs.evaluate()
 when "/"
 return containerNode.lhs.evaluate() / containerNode.rhs.evaluate()
 end
 end
 end
end

class OperatorToken < Token
 attr_reader :major
 
 def initialize(value)
 @value = value
 @eval_method = Fixnum.instance_method(value)
 case @value
 when "+","-" 
 @major = false
 when "*","/"
 @major = true
 end
 end
 
 def evaluate(containerNode)
 bound_method = @eval_method.bind(containerNode.lhs.evaluate()) 
 return bound_method.call(containerNode.rhs.evaluate())
 end
end

>ruby calculator.rb
Loaded suite calculator
Started
........................
Finished in 0.022 seconds.

24 tests, 37 assertions, 0 failures, 0 errors
>Exit code: 0

def stress_test()
 expressions = generate_expressions(100)
 rejects = []
 expressions.each do |exp|
 rejects << exp if (eval(exp) != calculate(exp)) 
 end
 return rejects
end
 
def generate_expressions(count)
 expressions = []
 operators = ["+","-","*","/"] 
 count.times do
 exp = (rand(100) + 1).to_s
 rand(10).times do
 exp << operators[rand(4)]
 exp << (rand(100) + 1).to_s
 end 
 expressions << exp
 end
 return expressions
end

def test_really_big_number
 assert_equal(1000000000000000000001, calculate("1000000000000000000000+1"))
end

>ruby calculator.rb
Loaded suite calculator
Started
........E................
Finished in 0.02 seconds.

1) Error:
test_really_big_number(EvaluateTests):
TypeError: bind argument must be an instance of Fixnum
calculator.rb:55:in `bind'
calculator.rb:55:in `evaluate'
calculator.rb:12:in `evaluate'
calculator.rb:118:in `calculate'
calculator.rb:209:in `test_really_big_number'

25 tests, 37 assertions, 0 failures, 1 errors
>Exit code: 1

Its been a few days since the last post in this series, mostly because this step was trickier than the previous few and partly because once I had the tree building working I couldn't resist adding the evaluation step. This was actually a good thing, because it helped me discover a mistake I made with the tree building and saved me from making a fool of myself by posting some broken crap (writing unit tests should have theoretically prevented this but I suck at them). Anyway, lets get on with it. I need to define the data structure the tree will be built from. I tried enhancing the tokens to act as the tree nodes themselves, but it made the tree manipulations more complicated. Instead I decide to keep it simple:

class BinaryTreeNode
attr_accessor :lhs, :rhs, :token

def initialize(token)
@token = token
end

def leaf?
return @lhs == nil && @rhs == nil
end
end

def create_parent(target_node, operator, integer)
new_node = BinaryTreeNode.new(operator)
new_node.lhs = target_node
new_node.rhs = BinaryTreeNode.new(integer)
return new_node
end

• the root node if the operator is a + or - or if the root node is the only node or if the root operator is a * or /.
• the root node's right hand child in other cases (the operator is a * or / and the other conditions don't apply).

def build_tree(tokens)
tokens = tokens.dup
root_node = BinaryTreeNode.new(tokens.shift) 

while(tokens.size > 1)
 operator = tokens.shift
 integer = tokens.shift 
 if(root_node.leaf? || !operator.major || root_node.token.major)
 # If the root_node is the only node or if we have a '+' or '-'
 # OR if the root operator is '*' or '/' then append to root
 root_node = create_parent(root_node, operator, integer) 
 else
 # We have a * or /, append to root.rhs 
 root_node.rhs = create_parent(root_node.rhs, operator, integer) 
 end
end

 return root_node
end

(Continues from the previous post) So now I have an array of these token objects that I want to build into a binary tree. I said yesterday that I would not handle syntax errors in this first version but I have since realised that I was only talking about a particular type of syntax error: one that occurs at the lexical level. For example, the string "32+65-chocolate" is not an expression I expect my lexer to handle. Now if I was writing a lexer for a language that allows variable declarations, the aforementioned string might be valid because the previous line was "chocolate=6". That however, is outside the scope of this exercise so for now "chocolate" does not lex. So with that said, its time to discuss the other type of syntax error that springs to mind. Here are some examples:

• 1+
• 2*+3
• -4

class SyntaxTests < Test::Unit::TestCase
def test_disallow_end_with_operator
tokens = [IntegerToken.new("1"), OperatorToken.new("+")]
assert(!tokens_are_valid(tokens))
end

def test_disallow_two_consecutive_operators
tokens = [IntegerToken.new("2"), OperatorToken.new("*"), OperatorToken.new("-"), IntegerToken.new("3")]
assert(!tokens_are_valid(tokens))
end

def test_disallow_start_with_operator
tokens = [OperatorToken.new("-"), IntegerToken.new("4")]
assert(!tokens_are_valid(tokens))
end
end

def tokens_are_valid(tokens)
return false
end

def test_allow_two_numbers
tokens = [IntegerToken.new("2"), OperatorToken.new("+"), IntegerToken.new("6")]
assert(tokens_are_valid(tokens))
end

def test_allow_three_numbers
tokens = [IntegerToken.new("73"), OperatorToken.new("*"), IntegerToken.new("56"), OperatorToken.new("-"), IntegerToken.new("94")]
assert(tokens_are_valid(tokens))
end

>ruby calculator.rb
Loaded suite calculator
Started
FF..........
Finished in 0.009 seconds.

1) Failure:
test_allow_three_numbers(SyntaxTests) [calculator.rb:81]:
<false> is not true.

2) Failure:
test_allow_two_numbers(SyntaxTests) [calculator.rb:76]:
<false> is not true.

12 tests, 12 assertions, 2 failures, 0 errors
>Exit code: 1

def tokens_are_valid(tokens)
return false if(tokens.empty?)
return false if(tokens.first.class != IntegerToken)
return false if(tokens.last.class != IntegerToken)

expect_next_is_integer = true
tokens.each do |token|
 token_is_integer = (token.class == IntegerToken)
 return false if(expect_next_is_integer != token_is_integer) 
 expect_next_is_integer = !expect_next_is_integer
end

return true
end

>ruby calculator.rb
Loaded suite calculator
Started
............
Finished in 0.001 seconds.

12 tests, 12 assertions, 0 failures, 0 errors
>Exit code: 0

def test_integer_operator_integer
assert_equal([193,"*",671], tokenize_for_value("193*671") ); end

class IntegerToken
attr_reader :value
def initialize(value)
@value = value.to_i()
end
end

class OperatorToken
attr_reader :value
def initialize(value)
@value = value
end
end

definitions = []
definitions << [/^\d+/, IntegerToken]
definitions << [/^\+/, OperatorToken]
definitions << [/^\-/, OperatorToken]
definitions << [/^\*/, OperatorToken]
definitions << [/^\//, OperatorToken]

 tokens = []
lastSize = 0
# Track the number of remaining characters in the expression.
# If we manage to go through all the regular expressions without
# getting a match then we can parse no more.
while(expression.size != lastSize)
lastSize = expression.size
definitions.each do |regex, token_type|
# Do a match with the regex against the string, remove the
# characters that match and put them into lexmeme
lexmeme = expression.slice!(regex)
if (lexmeme)
 # We got a match, create a new token and break out of
 # the regex loop to preserve the regex ordering.
 tokens << token_type.new(lexmeme)
 break
end
end
end

return tokens

def tokenize_for_value(expression)
tokens = tokenize(expression)
return tokens.map { |t| t.value }
end

>ruby calculator_source.rb
Loaded suite calculator_source
Started
.......
Finished in 0.001 seconds.

7 tests, 7 assertions, 0 failures, 0 errors
>Exit code: 0

My first exercise for learning how compilers work is to write a program that takes a string containing a mathematical expression and evaluates the result e.g. "2+3*7" => 23. I will be implementing it using Ruby and will write unit tests as I go. Since my goal is to learn the underlying concepts of compiler construction, I am avoiding any libraries/functionality provided by Ruby that would make it too easy. The first implementation will ignore whitespace and accept strings containing integers and the 4 standard operators (plus, minus, multiply, divide). The second implementation will report syntax errors and accept decimal numbers and parentheses. According to my research on Wikipedia, this exercise can be broken into the following steps:

1. lexical analysis (identifying the tokens that appear in the string)
2. syntactic analysis (assembling the tokens into a tree)
3. semantic analysis (evaluating the tree for a result)