articleLet's talk about state machines

finnianr's picture
Contents

Introduction

Lately I wrote a small utility to augment the editing capabilities of EiffelStudio. At it's core is a simple finite state machine for parsing a files contents at the line level rather than the word level.

Concept of a finite state machine

In computer science, a finite state machine is a programming abstraction used to model the behaviour of a system that has a finite number of states, an elevator or a coffee machine for example. The machine can transit from one state to another, typically triggering some event or action. This change is refered to as a transition. For example the coffee machine detects that the cup is nearly full and stops the flow of liquid. One of the most common examples of a state machine is a code parser.

State machines and Eiffel agents

Eiffel agents are very useful for writing state machine programs and can be used to model both the state of the machine and the transition action. The following class found in Eiffel-Loop is a very simple state machine that is surprisingly useful for many applications. It traverses a linear sequence of data objects, starting in an initial state and finishing either when the state becomes final or when the end of the line has been reached. To change the state of the machine all you have to do is assign the state attribute another agent with an open operand of type G. This defines both the state of the machine and the action to be taken when in that state.

 

Some technical points

  • The class EL_PROCEDURE was written expressly for the purpose of detecting whether two procedures represent the same routine using only the 'encaps_rout_disp' pointer attribute. But you do need to remember to force a C compilation in EiffelStudio for it to work.
  • The operands are set using a class tuple attribute rather than state.call ([item]) in order to reduce garbage collection.

A state machine for line processing

A useful implementation of EL_STATE_MACHINE is the following class which can be used to process lines of text from a file or some other source.

 

A utility example

Here is presented a utility illustrating the use of EL_PLAIN_TEXT_LINE_STATE_MACHINE. It operates on an Eiffel source file expanding a shorthand notation for common coding patterns as follows.

1. Expand feature codes

Expand lines beginning with @f xx where xx is a two letter code representing one of the standard feature group catagories: Access, Element Change, etc. Lines beginning with @f {xx will be expanded as feature {NONE} -- For example:   expands as  

2. Expand argument assignments

Expand routines containing shorthand for attribute assignments, inserting an assignment line. For example this shorthand code   will be expanded as  

3. Expand setter notation

Expand the notation for set attribute procedures so for example this code:    

4. Sort features alphabetically

Reorder features within a group so the names will appear in alphabetical order in the EiffelStudio feature view.

Feature editor class

This is code for the top level class that achieves all that using the EL_PLAIN_TEXT_LINE_STATE_MACHINE class.  

A vCard splitter

This example is used for splitting a monolithic addressbook in vCard file format, into one file per contact. This is to satisfy the requirements of some Nokia phones like the Asha 300.

 

EL_ASTRING

Anyone wondering what the EL_ASTRING class is about should read ISO-8859 is dead, long live ISO-8859. Last year I made the brave (or foolish) decision to use it throughout Eiffel-Loop. So far I am happy with the results but I am aware it may turn some people off using Eiffel-Loop, but I hope I am wrong about this.

I will make news about EL_ASTRING the subject of another article.

Addendum

I feel I should apologise that this is not immediately downloadable from . This is because I use an NTFS partition for my code on Linux to make it easier to do cross platform development. The downside is I need to run a script to copy the source trees into a Linux partition and fix the file permissions etc. I need to fix this broken script before I can share the code. Will post a comment when this is done.

Comments

What about UTF-8?

finnianr's picture

In anticipation of the question, what if the source is encoded as UTF-8?

A. EL_FILE_LINE_SOURCE changes it's encoding if it finds a BOM at the file start. EL_PLAIN_TEXT_FILE encodes accordingly writing a BOM if required.

Syndicate content