Kanocc

Kanocc is a Ruby-framework for parsing and translating for context-free grammars.

Kanocc tries to be 'scripty': Emphasis is on ease of use and seamless integration with your Ruby programs. Performance is a secondary concern - so you probably won't use Kanocc to do a production quality C++ compiler.

I imagine that Kanocc could be useful, for example, when your program is reading input that is best analyzed using parsing techniques, or if you create a small domain specific language.

Unlike compiler-compilers such as yacc or bison, Kanocc doesn't produce an intermediate file (like a c-program) to be run through a compiler to produce an executable. Kanocc reads your grammar and parses and executes your input in one run. Hence it's name.

In the following it's assumed that you have knowledge of parsers, grammars and syntax-directed translation. If not, you'll have to do some reading. There is a lot of literature you can choose from. In particular I recommend Compilers: Principles, Techniques and Tools (The Dragonbook), which was where I learned about the subject. Also, the Bison manual contains much useful information.

It is also assumed that you have working knowledge of Ruby

class A
  def initialize
    puts "In A's initializer..."
  end
end

A.new

In A's initializer...

Kanocc is available as a gem from RubyForge. From the command-prompt, do:

gem install kanocc

and then in your Ruby-scripts:

require 'rubygems'
require 'kanocc'

In our example we defined a class Number, extending Kanocc::Token.

By calling Kanocc::Token.pattern we tell Kanocc how Numbers look. The method pattern must be given a regular expression as argument.

By referring to Number in our rules, we make Kanocc look for Number during lexical scanning.

Obviously, string literals (such as "(", "exit", "\n",..) doesn't need to have patterns attached. All you have to do is mention them in grammarrules, and Kanocc will look for them in the input.

Tokens must always have a parameterless initialize method, so that Kanocc knows how to create instances.

class Num < Kanocc::Token 
  attr_reader :val 
  pattern(/0x[0-9A-F]+/) { @val = @m[0].hex } # Hex notation
  pattern(/\d+/) { @val = @m[0].to_i}  # Decimal notation 
end

"0xA3 + 7"

By default Kanocc considers anything that matches the regular expression /\s/, whitespace.

You may redefine this, if you wish, by calling the method Kanocc::Kanocc#set_whitespace. set_whitespace takes a list of regular expressions as argument.

For example, to define that spaces, tabs and anything from a '#' to lineending is whitespace, you can do:

  myParser.setWhitespace(/ /, /\t/, /#.*/)

- or, if you prefer:

  myParser.setWhitespace(/ |\t|#.*/)

You have all the power of Ruby regular expressions at your disposal here.

If you're very observant, you'll have noticed that the literal "\n" which we used in our example above is also whitespace. This is ok. If a part of input can be recognized both as a token and as whitespace, Kanocc will prefer to emit a token. ^[1]

In our example we defined 3 classes: Expr, Term and Factor, each of them extending Kanocc::Nonterminal. This is how we tell Kanocc about the nonterminals of our grammar.

Inside each class definition we make calls to the static method rule. With this we define the grammarrules belonging to that that particular nonterminal. For examle, we told Kanocc about the rule:

  
Expr ::= Expr "+" Term

with the call

rule(Expr, "+", Term) {@val = @rhs[0].val + @rhs[2].val}

The arguments to rule must be nonterminals (that means: classes that inherit from Kanocc::Nonterminal), tokens (classes that inherit from Kanoc::Token) or strings.

Nonterminals must always have a parameterless initialize method so Kanocc can create instances of them.

Expr ::= Expr "+" Term

In our example above, we used an unambigous grammar.

We might, however, prefer the following ambigous grammar:

Expr ::= Expr '+' Expr
       | Expr - Expr
       | Expr * Expr
       | Expr / Expr
       | '(' Expr ')'
       | Number

This grammar is ambigous. For example it doesn't specify whether to interpret the expression 8 - 2 * 3 as (8 - 2) * 3 or 8 - (2 * 3) .

To control this you assign precedence to your grammarules. This is done by following the call to rule by a call to

Nonterminal.precedence

with an integer as argument. Default precedence is 0, so if you give a precedence > 0 you increase precedence - i.e make Kanocc more inclined to use the production.

Using precedence, we can rewrite our example to:

require "rubygems"   
require "kanocc"

class Number < Kanocc::Token 
  attr_reader :val 
  pattern(/\d+/) { @val = @m[0].to_i} 
end
         
class Expr < Kanocc::Nonterminal 
  attr_reader :val 
        
  rule(Expr, "+", Expr) { @val = @rhs[0].val + @rhs[2].val}
  rule(Expr, "-", Expr) { @val = @rhs[0].val - @rhs[2].val}
  rule(Expr, "*", Expr) { @val = @rhs[0].val * @rhs[2].val}; precedence -1
  rule(Expr, "/", Expr) { @val = @rhs[0].val / @rhs[2].val}; precedence -1
  rule("(", Expr, ")") { @val = @rhs[1].val}
  rule(Number) {@val = @rhs[0].val}
end

myParser = Kanocc::Kanocc.new(Expr) 
 
puts myParser.parse('3 + 4 - 2').val 
puts myParser.parse('8 - 2 * 3').val 

The two calls to precedence gave the rules for multiplication and division lower precedence.

When mathematicians talk about operators and precedence they say that multiplication operators have higher precedence than addition operators. Also traditional parser-generators like yacc or bison would have you asign a higher precedence to '*'. Why then do we assign a lower precedence to multiplication?

The reason for this quirk is that the Earley parsing algorithm, which is employed by Kanocc, constructs the parse tree top-down. The Earley parser must find a way to expand the nonterminal Expr to the string '8 - 2 * 3'. This can be done in two ways:

            Expr
           /  | \
          /   |  \
        Expr '-'  Expr
        /        /  | \
       /        /   |  \
   Number    Expr  '*'  Expr
     |        |          |
    '8'       |          |
            Number     Number
              |          |
             '2'        '3'

or

            Expr
           /  | \
          /   |  \
        Expr '*'  Expr
       /  | \        \
      /   |  \        \
   Expr  '-'  Expr   Number
    |          |       |
    |          |      '3'
  Number     Number
    |          |
   '8'        '2' 

Clearly, what we want is the first variant, so we need to make Kanocc choose the expansion

  Expr --> Expr '-' Expr

before

  Expr --> Expr '*' Expr

Therefore we must give multiplication rules a lower precedence.

Consider the expression: 8 - 5 + 3. Given our grammar, Expr may expand to that in 2 ways:

            Expr
          /  |   \
         /   |    \
       Expr '+'   Number
      /  | \         |
    /    |  \       '3'
 Number '-' Number
   |          |
  '8'        '5'
  

or

       Expr
     /  |  \
    /   |   \
Number '-'   Expr
  |         /  |  \
 '8'       /   |   \
       Number '+'  Number
         |           |
        '5'         '3'

  

By default, Kanocc will choose the first variant, which is well in tune with the fact that operators '+' and '-' are left associative. If you look at the parse trees above, you'll notice that the topmost Expr of the first tree has it's rightmost nonterminal (Number) expand to '3' - one token - while the topmost Expr of the second tree has it's rightmost nonterminal (Expr) expand to '5' '+' '3' - a sequence of three tokens. You can control this by declaring wether Kanocc should expand the rightmost grammarsymbol of a rule to as much or as little as possible. By default Kanocc expands the rightmost grammarsymbol of a rule to as little as possible. If you want to change that, eg. have your addition-operators be right-associative, you can declare rules to derive right. You might do:

.
.

class Expr < Kanocc::Nonterminal
  rule(Expr, "+", Expr) { @val = @rhs[0].val + @rhs[2].val}; derives_right
  rule(Expr, "-", Expr) { @val = @rhs[0].val - @rhs[2].val}; derives_right
 end

.
.

If Kanocc is expanding a nonterminal and has several rules to choose from and they all derive right, it will choose to expand by the rule whos rightmost symbol can expand to the longest sequence of input tokens.

Once you have your tokens and nonterminals in place, the rest is simple: Construct an instance of Kanocc::Kanocc with the startsymbol of your grammar as argument.

Then call Kannoc#parse with the input as argument, and Kanocc will try to reduce the input to the given startsymbol. If succesful, an instance of that startsymbol will be returned.

In our example:

myParser = Kanocc::Kanocc.new(Expr)
puts myParser.parse('8 - 3 * 2').val

did that.

Rather than abort parsing when an error is discovered, it can be nice to be able to skip an error and continue parsing, so that at least all (or most of) the errors in input can be reported in one run.

Kanocc has a special nonterminal Kanocc::Error which may be used on the right-hand-side of rules. Error can expand to anything, and rules containing Error on their right-hand-side will have a precedence of negative infinity. In other words: A rule containing Error will only be used if Kanocc can see no other way to reduce the input to the start symbol.

Using Kanocc::Error we can rewrite our example to:

require "rubygems"
require "kanocc"

class Number < Kanocc::Token
attr_reader :val
pattern(/\d+/) { @val = @m[0].to_i}
end


class Expr < Kanocc::Nonterminal
  attr_reader :val

  rule(Expr, "+", Expr) { @val = @rhs[0].val + @rhs[2].val}
  rule(Expr, "-", Expr) { @val = @rhs[0].val - @rhs[2].val}
  rule(Expr, "*", Expr) { @val = @rhs[0].val * @rhs[2].val}; precedence -1
  rule(Expr, "/", Expr) { @val = @rhs[0].val / @rhs[2].val}; precedence -1
  rule("(", Expr, ")") { @val = @rhs[1].val}
  rule(Number) {@val = @rhs[0].val}
end

class Line < Kanocc::Nonterminal
  rule(Expr, "\n") {puts @rhs[0].val}
  rule(Kanocc::Error, "\n") {puts "Sorry - didn't understand: " + @rhs[0].str.inspect}
end

class Program < Kanocc::Nonterminal
  rule(zm(line))
end

Kanocc::Kanocc.new(Program).parse <<-EOI
  3 + 4 - 2
  8 - 2 * 3
  8 * + 3
  2 + 3 * 2
EOI

This should produce:

  5
  2
  Sorry - didn't understand: "  8 * + 3"
  8

To facillitate error messaging, an instance of Kanocc::Error will have set two instance variables:

In our example, @program would reference the string :

<<-EOT
exit
EOT

, @start and @end would have the values 23 and 34 respectively, so that @program[@start, @end] would give

"  8 * + 3 "