A “grue”some look at Statemachine and Treetop

In this blog entry, dear reader, we examine the statemachine and treetop gems via an old standby, a Zork imitation. And, despite the title, you won’t find a grue.

$ ruby adventure.rb
This is the beginning. Like all tales, there's a beginning, a middle and an
end....

Paths lead n.

What do you want to do?
n

This is a path in the forest, it looks fairly well travelled.  You see a
clearing to the east

Paths lead w, n, e, s.

What do you want to do?
e

This is a clearing.  You can actually see the sky here.  Compared to the deep
dark forest, it seems a relief. A path can be seen to the west.

Paths lead w, n, e, s.

You see the following: letter.

What do you want to do?
get letter

Ok, you pick up the letter.

What do you want to do?
w

This is a path in the forest, it looks fairly well travelled.  You see a
clearing to the east

Paths lead w, n, e, s.

What do you want to do?
w

You're lost in the depths of the forest.  You're not sure where you are, nor how
to get out of there.

Paths lead w, n, e, s.

What do you want to do?
quit

$ ruby adventure.rb

This is the beginning. Like all tales, there's a beginning, a middle and an

end....

Paths lead n.

What do you want to do?

This is a path in the forest, it looks fairly well travelled. You see a

clearing to the east

Paths lead w, n, e, s.

What do you want to do?

This is a clearing. You can actually see the sky here. Compared to the deep

dark forest, it seems a relief. A path can be seen to the west.

Paths lead w, n, e, s.

You see the following: letter.

What do you want to do?

get letter

Ok, you pick up the letter.

What do you want to do?

This is a path in the forest, it looks fairly well travelled. You see a

clearing to the east

Paths lead w, n, e, s.

What do you want to do?

You're lost in the depths of the forest. You're not sure where you are, nor how

to get out of there.

Paths lead w, n, e, s.

What do you want to do?

quit

Statemachine is used for creating, as you no doubt have guessed, statemachines. Treetop is a parser generator. A zork-like game is a fairly useful simple example of how to use both.

Statemachine

Let’s start with a state diagramme:

Basically we have three states: Begin, Main, and Done. We can transition from one state to another in a variety of ways, as shown by the arrows. The text with the transition shows the events which can trigger the transition. Statemachine uses two basic types of statements to describe these state changes (what follows is simplified from the actual code):

    def setup_machine
      @machine = Statemachine.build do
        trans :start, :begin, :main, :enter
        state :main do
          event :move, :main, :move
          on_entry :check_if_transition_needed
        end
        context AdventureContext.new()
      end
      @machine.context.statemachine = @machine
    end

def setup_machine

@machine = Statemachine.build do

trans :start, :begin, :main, :enter

state :main do

event :move, :main, :move

on_entry :check_if_transition_needed

end

context AdventureContext.new()

end

@machine.context.statemachine = @machine

end

trans is used to move from one state to another upon the receipt of an event. Thus,
trans :start, :begin, :main, :enter can be interpreted as “From the start state, transition to the main state when you receive a begin event. In so doing, invoke the enter method.”
Likewise, the block starting with state :main contains code which handles events, as well as invoking a method (check_if_transition_needed) on entrance of the state. event :move, :main, :move may be read as “Within the context of the main state, when a move event is received, transition to main, invoking the move method.”

The check_if_transition_needed is something of a hack — without it setting the state within a state transition wasn’t working properly (so we couldn’t go to the “done” state and exit).

The invoked methods are performed by the object which is declared to be the context — namely an instance of AdventureContext. The last line, @machine.context.statemachine = @machine, allows our context to interract with the statemachine.

Grammar

I’ve chosen to use treetop for my grammar. Let’s take a look at the grammar:

grammar Adventure

# The commands fall in these categories
   rule command
     describe_inside / describe / help / move / quit / take / put / inventory
   end

 # nodes must always be parenthesized to be associated with a block
  rule help
    ("help" / "help" space name) {
     def eval(statemachine)
       statemachine.send(:help)
     end
    }
  end

  # This is a convenience method; to declare what a name is
  rule name
    ([A-Z] [a-z]*) / [a-z]+
  end

  # Likewise, this declares spaces -- it makes the grammar easier to read
  rule space
    ' '+
  end

  # This one's a little complex; we can match two forms
  rule take
   ((take_verb space item take_from) / (take_verb space item) ) {
     def eval(statemachine)
        if (self.respond_to? :take_from)
           statemachine.send(:take_from, item.text_value, take_from.container.text_value)
        else
           statemachine.send(:take, item.text_value)
        end
     end
   }
  end

  rule take_from
    space out space container
  end

  # This one's a little complex; we can match two forms
  rule put
   ((put_verb space item put_into) / (put_verb space item) ) {
     def eval(statemachine)
        if (self.respond_to? :put_into)
           statemachine.send(:put_into, item.text_value, put_into.container.text_value)
        else
           statemachine.send(:put, item.text_value)
        end
     end
   }
  end

  rule put_into
    space into space container
  end

  rule inventory
   ( "inventory" / "i" ) {
      def eval(statemachine = nil)
          statemachine.send(:inventory)
      end
   }
  end

  rule describe_verb
    "describe" / "look" / "examine"
  end

  rule something
   space "at"? space* name
  end

  rule describe_inside
    describe_verb space into space name {
      def eval(statemachine = nil)
        statemachine.send(:look, name.text_value, true)
      end
    }
  end

  rule describe
   ( (describe_verb something) / (describe_verb) ) {
       def eval(statemachine = nil)
          thing = (self.respond_to? :something) ? something.name.text_value : nil
          statemachine.send(:look, thing)
       end
     }
  end

  rule quit
     "quit" {
        def eval(statemachine)
          statemachine.send(:quit)
      end
     }
   end

  rule move
    (direction / "go" space direction / "move" space direction) {
      def eval(statemachine)
        direction ||= text_value.downcase
        statemachine.move(direction)
      end
    }
  end

  rule direction
    ( 'north' / 'south' / 'east' / 'west' / [nsew] ) {
      def eval(statemachine)
        statemachine.move(text_value.downcase)
      end
    }
  end

  rule out
    "from" / ("out" space "of") / "out"
  end

  rule item
    name
  end

  rule container
   name
  end

  # Below the order is very important -- it matches the first thing
  # so in needs to come last, otherwise it can't match
  # 'into' or 'inside'
  rule into
    "into" / "inside" / "in"
  end

  rule take_verb
    "take" / "get"
  end

  rule put_verb
    "put" / "place" / "drop"
  end

end

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

grammar Adventure

# The commands fall in these categories

rule command

describe_inside / describe / help / move / quit / take / put / inventory

end

# nodes must always be parenthesized to be associated with a block

rule help

("help" / "help" space name) {

def eval(statemachine)

statemachine.send(:help)

end

}

end

# This is a convenience method; to declare what a name is

rule name

([A-Z] [a-z]*) / [a-z]+

end

# Likewise, this declares spaces -- it makes the grammar easier to read

rule space

' '+

end

# This one's a little complex; we can match two forms

rule take

((take_verb space item take_from) / (take_verb space item) ) {

def eval(statemachine)

if (self.respond_to? :take_from)

statemachine.send(:take_from, item.text_value, take_from.container.text_value)

else

statemachine.send(:take, item.text_value)

end

}

end

rule take_from

space out space container

end

# This one's a little complex; we can match two forms

rule put

((put_verb space item put_into) / (put_verb space item) ) {

def eval(statemachine)

if (self.respond_to? :put_into)

statemachine.send(:put_into, item.text_value, put_into.container.text_value)

else

statemachine.send(:put, item.text_value)

end

}

end

rule put_into

space into space container

end

rule inventory

( "inventory" / "i" ) {

def eval(statemachine = nil)

statemachine.send(:inventory)

end

}

end

rule describe_verb

"describe" / "look" / "examine"

end

rule something

space "at"? space* name

end

rule describe_inside

describe_verb space into space name {

def eval(statemachine = nil)

statemachine.send(:look, name.text_value, true)

end

}

end

rule describe

( (describe_verb something) / (describe_verb) ) {

def eval(statemachine = nil)

thing = (self.respond_to? :something) ? something.name.text_value : nil

statemachine.send(:look, thing)

end

}

end

rule quit

"quit" {

def eval(statemachine)

statemachine.send(:quit)

end

}

end

rule move

(direction / "go" space direction / "move" space direction) {

def eval(statemachine)

direction ||= text_value.downcase

statemachine.move(direction)

end

}

end

rule direction

( 'north' / 'south' / 'east' / 'west' / [nsew] ) {

def eval(statemachine)

statemachine.move(text_value.downcase)

end

}

end

rule out

"from" / ("out" space "of") / "out"

end

rule item

name

end

rule container

name

end

# Below the order is very important -- it matches the first thing

# so in needs to come last, otherwise it can't match

# 'into' or 'inside'

rule into

"into" / "inside" / "in"

end

rule take_verb

"take" / "get"

end

rule put_verb

"put" / "place" / "drop"

end

All grammars start with the keyword grammar and the word which follows is the name used for the parser’s class. So, grammar Adventure creates an AdventureParser class. Within the grammar block exist a series of rules. Personally, I think that they’re easier to understand than BNF.

One interesting piece that caused me some grief — the rules are order dependant. If you have a rule that can match “in” or “inside”, “inside” has to come before “in” — otherwise it will error when you try to parse “inside”. However, in debugging parsers, irb is very helpful:

$ irb
>> require 'rubygems'
=> true
>> require 'treetop'
=> true
>> Treetop.load('adventure')
=> AdventureParser
>> p = AdventureParser.new
=> #
>> p.parse "look outside backpack" #this should fail
=> nil
>> p.failure_reason
=> "Expected one of  , into, inside, in, at at line 1, column 6 (byte 6) after "
>> p.parse "look inside backpack"
=> SyntaxNode+DescribeInside1+DescribeInside0 offset=0, "look inside backpack" (describe_verb,space,eval,name,into):
  SyntaxNode offset=0, "look"
  SyntaxNode offset=4, " ":
    SyntaxNode offset=4, " "
  SyntaxNode offset=5, "inside"
  SyntaxNode offset=11, " ":
    SyntaxNode offset=11, " "
  SyntaxNode offset=12, "backpack":
    SyntaxNode offset=12, "b"
    SyntaxNode offset=13, "a"
    SyntaxNode offset=14, "c"
    SyntaxNode offset=15, "k"
    SyntaxNode offset=16, "p"
    SyntaxNode offset=17, "a"
    SyntaxNode offset=18, "c"
    SyntaxNode offset=19, "k"
>>

$ irb

>> require 'rubygems'

=> true

>> require 'treetop'

=> true

>> Treetop.load('adventure')

=> AdventureParser

>> p = AdventureParser.new

=> #

>> p.parse "look outside backpack" #this should fail

=> nil

>> p.failure_reason

=> "Expected one of , into, inside, in, at at line 1, column 6 (byte 6) after "

>> p.parse "look inside backpack"

=> SyntaxNode+DescribeInside1+DescribeInside0 offset=0, "look inside backpack" (describe_verb,space,eval,name,into):

SyntaxNode offset=0, "look"

SyntaxNode offset=4, " ":

SyntaxNode offset=4, " "

SyntaxNode offset=5, "inside"

SyntaxNode offset=11, " ":

SyntaxNode offset=11, " "

SyntaxNode offset=12, "backpack":

SyntaxNode offset=12, "b"

SyntaxNode offset=13, "a"

SyntaxNode offset=14, "c"

SyntaxNode offset=15, "k"

SyntaxNode offset=16, "p"

SyntaxNode offset=17, "a"

SyntaxNode offset=18, "c"

SyntaxNode offset=19, "k"

There are other methods to use for finding failures, but failure_reason is very helpful most of the time. However, if there’s an issue with grammar, such as “in” coming before “inside” it has issues.

Locations and Items

I have chosen to set up my map within a yaml file. It’s split into two pieces — the first defines the locations and the second the items and their properties. In order to keep my yaml file as dry as possible, I’m only including things that are “special” about a location or an item — things which differ from the defaults.

Locations have the following properties:

Property	Default	Description
name (inferred)	“”	Location’s name
description	“”	Description of the location
paths	[]	Paths away from the current location
items	[]	Items which are contained in this location
transition	nil	Any transitions which might occur from moving to this location — these include victory or failure conditions.

So a location might look like this in the yaml file:

---
locations:
  start:
    description: "This is the beginning. Like all tales, there's a beginning, a middle and an end...."
    paths:
      n: forest_path

---

locations:

start:

description: "This is the beginning. Like all tales, there's a beginning, a middle and an end...."

paths:

n: forest_path

Items have the following properties:

Property	Default	Description
name (inferred)	“”	The name of the item
description	“”,	The description
take	true,	Can the item be taken?
container	false,	Can the item hold other items?
droppable	true	Can the item be dropped?

So an item might look like this:

---
items:
  letter:
    description: "It's an old letter.  It is addressed and has an uncancelled stamp."

---

items:

letter:

description: "It's an old letter. It is addressed and has an uncancelled stamp."

The Source

Finally we have our source code. It’s pretty straightforward, so I’ll not talk about it here, but if anyone has questions, please comment.

Running the Code

First off, be sure you’ve installed the treetop and statemachine gems. You can do so via:

sudo gem install statemachine
sudo gem install treetop

1 2	sudo gem install statemachine sudo gem install treetop

From there you can download the files and unarchive them into a directory. adventure1.tgz

Then run it via

ruby adventure.rb

1	ruby adventure.rb

Where to go from here?

Well, there’s a few things to add…. Save and restore for one. Scoring for another. Combat, if you wanted as well. But as a demonstration of statemachine and treetop, I think this does a pretty good job.

EDIT: Fixed an error in adventure.rb

4 comments

Skip to comment form ↓

Matt Smith

September 6, 2008 at 10:59 am (UTC -5) Link to this comment

Thanks! This is one of the best tutorials on Treetop that I have seen. It cleared some things up for me.
Matt Williams

September 6, 2008 at 9:48 pm (UTC -5) Link to this comment

Most welcome. Glad it was useful for you. Truth be told, I learned a good bit from it too. It took a bit to get the grammar working for me.
jarodzz

October 11, 2008 at 2:13 pm (UTC -5) Link to this comment

can you share any other debugging info here?

I couldn’t find any useful info on the project page.

it’s a little bit miss-leading there.

my @parser.failure_reason always output nil for me.

it took me 4 days, still i couldn’t make it work .sigh~
Matt Williams

October 13, 2008 at 3:35 pm (UTC -5) Link to this comment

Yes, there’s not a lot of debugging info. One thing that I’ve found is that if your grammar isn’t constructed “properly”, it won’t complain and you won’t get proper output from the @parser.failure_reason. I’d suggest starting with a small subset of your parser, make sure that works, and build from there.

Good luck, and please feel free to ask more questions

Ramblings

Musings of Matt Williams

A “grue”some look at Statemachine and Treetop

Statemachine

Grammar

Locations and Items

The Source

Running the Code

Where to go from here?

Like this:

Related

4 comments

Matt Smith

Matt Williams

jarodzz

Matt Williams

Leave a Reply Cancel reply

Subscribe to Blog via Email

Recent Posts

Top Posts & Pages

Archives

Categories

Copyright

Ramblings

Musings of Matt Williams

A “grue”some look at Statemachine and Treetop

Statemachine

Grammar

Locations and Items

The Source

Running the Code

Where to go from here?

Share this:

Like this:

Related

4 comments

Matt Smith

Matt Williams

jarodzz

Matt Williams

Leave a Reply Cancel reply

Subscribe to Blog via Email

Recent Posts

Top Posts & Pages

Archives

Categories

Copyright