Coding

Pushdown Automaton in CoffeeScript

grammar

I decided to continue my CoffeeScript education by translating another homework assignment from C/C++ to CoffeeScript.  For my first CoffeeScript experiment, I simulated a deterministic finite automaton.  This time the simulated machine will be a pushdown automaton that accepts the language described by the context free grammar pictured to the left.

If you are unfamiliar with reading context free grammars, don’t worry, this one is pretty easy to understand.  The language generated by this grammar is similar to selection statements in C/C++.  In other words, you can use this grammar to correctly generate pairs of “if-else” statements.  Its simplified so we don’t have to worry about the predicate that follows the “if” statements or the body of code to execute when the predicate is true or false.  The only thing we are concerned about is whether every “else” follows an “if” somewhere earlier in the input.  Here’s an example of a correct sequence:

if
  if
  else
else

But since we don’t want to worry about whitespace or newlines either, we’ll feed the input to the machine as a flattened string: “ififelseelse”.

Here’s an example of an incorrect sequence:

if
else
else

It’s easy to see that there are too many “else” tokens.  To tell the difference between the valid sequence and an invalid one, the machine will have to count the number of “if” tokens and make sure there is one for every “else”.  They don’t have to balanced though.  This is also a valid sequence:

if
  if
    if
    else

Finite automata cannot solve this problem because they have no way to keep track of how many “if” tokens were encountered.  But pushdown automata have a stack which we can use to track the “if”s.

For the sticklers out there, I’ll note that the grammar is ambiguous because there is no way to distinguish between the above sequence and one like this:

if
  if
    if
else

In other words, the grammar doesn’t capture the nesting.  Both sequences flatten to “ifififelse”.  This would make this grammar somewhat difficult to use if you actually wanted to express some logic with it.  However, it has no effect on our ability to create pushdown automata that accept “ifififelse” while rejecting “ifififelseelseelseelse”.

Implementation

You can download the source from this gist.

The transition function for deterministic finite automata only need to supply the machine with the next state to move to.  In the previous example, I built the result state right into the rule object.  For pushdown automata, the transition function must supply both a new state, and a set of symbols to add to the machine’s stack.  So, we start with a function that returns an object to hold this information for us:

createResult = (state, symbols) -> {
  resultState: state
  pushSymbols: symbols.reverse()
}

When specifying the stack symbols to push, the textbook way to do so is to write the symbols down in the opposite order they will be pushed.  In other words, in the array [ A, B, C ], “C” will be pushed, followed by “B” and finally “A”.  This function reverses the given symbols so that this convention can be kept when specifying result objects.

Next we have a function to generate rule objects:

createRule = (state, input, symbol, result) -> {
  currentState: state
  inputChar: input
  stackSymbol: symbol
  ruleResult: result
  match: (s, i, y) -> 
    true if (this.currentState == s &&
             this.inputChar == i &&
             this.stackSymbol == y)
}

The rule needs to know the machine’s current state, the character read from the input, and the symbol read from the top of the machine’s stack.  The match function compares its own values with the three values supplied by the machine and returns true when they match.  This time there is only one function to create rules, and no algorithm coded into the example for generating the rule set.  For the DFA, the set of rules was larger, and the logic for automating their generation was fairly obvious, so generating the whole set saved a lot of typing.  But the set of rules for the PDA is smaller, and the logic was not immediately obvious to me, so I didn’t bother.

Next we have a function that returns machine objects.

createMachine = (rules, startState, initialSymbol, finalStates) -> {
  transitionRules: rules
  currentState: startState
  symbolStack: [ initialSymbol ]
  acceptanceStates: finalStates
  update: (r) ->
    this.symbolStack.push x for x in r.pushSymbols
    this.currentState = r.resultState
  read: (c) ->    
    return -1 if this.currentState == -1
    y = this.symbolStack.pop()
    for rule in this.transitionRules
      if rule.match this.currentState, c, y
        return this.update rule.ruleResult
    # no rules matched, enter dead configuration
    this.symbolStack.push y
    this.currentState = -1
  readAll: (s) -> this.read x for x in s.split ''  
  acceptedInput: () -> this.currentState in this.acceptanceStates
}

The machine takes a set of rules, an initial state, the first symbol to push onto the stack and a set of final states.  Like the DFA, it has an acceptedInput method which indicates whether current state of the machine is a member of the acceptanceStates collection.  The readAll convenience function is the same as the it was in the simpler machine.  For the read function, we have the same basic logic, but with a couple of twists.

First, the machine does not require that a rule exists to match every possible input.  If it can’t match the input to a rule, it enters a “dead configuration” at the bottom of the read method.  A guard clause at the beginning of the method checks for the dead configuration and bails out if the machine is already dead.  Next, we remove the top symbol from the stack.  By always removing the symbol, it makes erasure very simple later on, just do nothing and the symbol is erased.  After retrieving the stack symbol, we have the info we need to match the transition rule.  In the DFA example, I used a counted loop to iterate over the collection, but this time I tried a for … in loop.  Not sure what the CoffeeScript lingo for that is, and I’d be interested to see if this loop could be rewritten as a list comprehension.  I think it’s a step up from the counted loop anyway.

I experimented with the CoffeeScript REPL and confirmed that JavaScript does indeed short-circuit out of the loop when it hits the return statement.  It’s a good thing too, since this time I relied on that behavior.  When no rule matches, the short circuit is not hit, the machine restores the stack and enters the dead configuration.  When a rule does match, the machine calls its own update method with the rule result as the argument.  The update method pushes the result symbols onto the stack, then updates the machine state.  While writing this method on coffeescript.org and watching the JavaScript as it generated, I noticed that every method is a function by default.  The result of the last statement is used as the return value if there is no explicit return statement.  I suppose I could simulate a void subroutine by returning null explicitly, but for this example I thought it would be neat to allow the updated state to propagate up the stack and into a collection returned from the readAll method.

Next we have a method that builds and runs the machine for a given test string.

runMachine = (s) ->
  selectStmtRules = [
   createRule 0, 'i', 'S', createResult 3, [ 'A', 'S' ]
   createRule 3, 'f', 'A', createResult 1, [ 'B' ]
   createRule 1, 'i', 'S', createResult 3, [ 'A', 'S' ]
   createRule 1, 'i', 'B', createResult 3, [ 'A', 'B' ]
   createRule 1, 'e', 'B', createResult 2, [ 'C', 'D', 'E' ]
   createRule 2, 'l', 'C', createResult 2, [ ]
   createRule 2, 's', 'D', createResult 2, [ ]
   createRule 2, 'e', 'E', createResult 1, [ ]
  ]

  machine = createMachine selectStmtRules, 0, 'S', [ 1 ]
  history = machine.readAll s
  alert "Accepted: " + machine.acceptedInput() + " States: " + history.join ", "

Here, we build the machine rules necessary to recognize our grammar, then pass the rules to the createMachine function to build the machine.  The grammar, as specified, is easy to translate into transition rules.  For example, the rules S –> iA|iAB and A->fS|f taken together mean that when we start reading we must read an “i” followed by an “f’.  Once we have read the “f” we can quit, or we can read another “if’, or process a “B”.  The B is the entry point into the rules that describe the “else” token.

Translating this into a PDA means that we should start the machine with an S on the stack.  When we start the machine, “S” is the only production rule in the grammar we can use.  The machine starts in state 0, so our first rule says that if we are in state 0, and we read an ‘S’ off the stack, then we can read an “i” from the input and transition.  Since there is only one rule for state 0, it follows that we must read an “i” or the machine will die.  If we do read an “i” then the machine goes to state 3 and pushes an ‘S’ followed by an ‘A’ onto the stack.  Now that the “A” is on the stack, we can only use production rules from the grammar that have “A” on the left side.  Both of these rules start with the letter “f”, so we only need to have one rule in order to require that the next expected character is read.  So, if we are in state 3 and we have an ‘A’ on the stack and read an “f” we transition to state 1, and push a “B” on the stack.  And so on.

The machine accepts the input whenever it reaches state 1.  After it reads the first “i”, “f”, it can stop reading and accept the input.  Once there is a “B” on the stack, the machine can read another “if”, or start reading an “else”.  It reads the else by replacing the “B” with the symbols that represent the grammar rules for the “lse” part of the “else” statement, then erasing them as each required character is read.  When the machine is done reading “else” the “B” is gone—the “if” it represented has been matched with its partner and can’t be used again.  Whenever  the number of “if” and “else” tokens are balanced, “S” will be back on the top of the stack, and so the machine is allowed to generate more “B”s from state 1.

After building the machine, the runMachine function feeds the test string into the readAll method, then lets us know whether the machine accepted the input.  It also shows us the history of the machine’s state changes.

Finally I run some test strings through the machine like this:

runMachine "ifelse"
runMachine "ifelseelse"
runMachine "ififelseelse"
runMachine "ifi"

In these examples, the first and third are correct and others aren’t.  As expected, the machine correctly identifies the acceptable strings.  This time around my implementation was a little cleaner and came in at 55 lines.  Like the DFA this didn’t take long and was easier than the C/C++ implementation.  I think its safe to say that it took me longer to write up this article than it took to write the code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s