From: Robert Feldt <feldt@...>
Date: 2001-03-16T23:07:59+09:00
Subject: [ruby-talk:12745] Re: Parser? (a bit long)

On Fri, 16 Mar 2001 jjthrash@pobox.com wrote:

> If I may ask, what does your parser allow/do?
> 
Short answer: Parses Ruby code in a string to an abstract syntax tree
(AST) without you having to build the tree by hand.

Long answer:
The Ruby parser is one example in rockit (Ruby Object-oriented Compiler
construction toolKIT), a lib of compilation-related classes I started
develop as a part of RubyVM (see previous posts on this). Rockit will take
a textual description of your grammar and give you back a parser (or the
Ruby code for a parser). This is much like yacc, bison etc. but you don't
need to write action code; the parser will give you back an abstract
syntax tree (using a special way to specify the AST in the grammar). This
is good when compiling since you will want to make multiple passes over
some tree structure; the parser can as well build it for you as you having
to do it by hand. It's flexible even if it will not be the fastest
approach if you have a specific "translation" goal in mind.

Current status is that the parser generator in rockit bootstraps itself
and works correctly with some small grammars (couple of calculators and a
minibasic interpreter). It doesn't work correctly with the Ruby
grammar since I haven't implemented any conflict resolution
(precendence and associativity for operators most notably). So this is
still vaporware ;-), with some decision to be taken and some code to be
written. So I won't make it more vaporish by telling you whats planned
after that... :-)

Below you'll find an example of a grammar and interpreter for minibasic
(well it can handle Bignum's so just a tad more powerful than traditional
Basic... :-)) together with example basic code. Sorry for the long lines
wreaking up to formatting.

Regards,

Robert

----------------------------------
Rockit grammar for minibasic:
----------------------------------
Tokens
  blank      = /(( )|(\t)|(\v))+/                     [:IGNORE]
  identifier = /[A-Z]([A-Z]|\d)*/
  number     = /\d+/
  string     = /"[^\r\n]*"/
  new_line   = /(\r\n)|(\r)|(\n)/

Productions
  statements -> statement+         [Statements: statements]
  statement  -> 'IF' condition 'THEN' new_line
                  statements
                  optional_else?
                'ENDIF' new_line

[If: _,condition,_,_,statements,optelse,_,_]
             |  'FOR' identifier ':=' expression 'TO' expression new_line
                  statements
                'NEXT' new_line 

[For: _,ident,_,from,_,to,_,statements,_,_]
             |  'READ' identifier new_line
                                   [Read: _,ident,_]
             |  'PRINT' expression new_line
                                   [PrintExp: _,expression,_]
             |  'PRINT' string new_line
                                   [PrintString: _,string,_]
             |  'PRINTLN' new_line [PrintLn]
             |  identifier ':=' expression new_line
                                   [Assignment: ident,_,expression,_]
  optional_else -> 'ELSE' new_line statements
                                   [Else: _,_,statements]
  condition -> expression '<' expression
				   [LessThan: left,_,right]
            |  expression '>' expression
				   [GreaterThan: left,_,right]
            |  expression '=' expression
				   [Equal: left,_,right]
  expression -> value              [Value: val]
             |  value '+' value    [Plus: left,_,right]
             |  value '-' value    [Minus: left,_,right]
             |  value '*' value    [Mul: left,_,right]
             |  value '/' value    [Div: left,_,right]
             |  value 'MOD' value  [Mod: left,_,right]
  value -> number                  [Constant: num]
        |  identifier              [Identifier: ident]
        |  '(' expression ')'      [Paran: _,expr,_]

----------------------------------
Minbasic interpreter in Ruby:
----------------------------------
require 'minibasic_parser'
parser = MiniBasic.parser
$vars = Hash.new(0)  # For variables and their values. Default value is 0.

def mb_eval(ast)
  case ast.node_name
  when "Statements"
    ast.statements.each {|statement| mb_eval(statement)}
  when "If"
    if mb_eval(ast.condition) # What is true and false in basic?
      mb_eval(ast.statements)
    elsif ast.optelse
      mb_eval(ast.optelse)
    end
  when "For"
    from, to = mb_eval(ast.from), mb_eval(ast.to)
    (from..to).each do |i|
      $vars[ast.ident.lexeme] = i
      mb_eval(ast.statements)
    end
  when "Read"
    print "? "; STDOUT.flush
    $vars[ast.ident.lexeme] = STDIN.gets.to_i   # Error catching?!
  when "PrintExp"
    print mb_eval(ast.expression).inspect; STDOUT.flush
  when "PrintString"
    print ast.string.lexeme[1..-2]; STDOUT.flush
  when "PrintLn"
    print "\n"; STDOUT.flush
  when "Assignment"
    $vars[ast.ident.lexeme] = mb_eval(ast.expression)
  when "Else"
    mb_eval(ast.statements)
  when "LessThan"
    mb_eval(ast.left) < mb_eval(ast.right)
  when "GreaterThan"
    mb_eval(ast.left) > mb_eval(ast.right)
  when "Equal"
    mb_eval(ast.left) == mb_eval(ast.right)
  when "Value"
    mb_eval(ast.val)
  when "Plus"
    mb_eval(ast.left) + mb_eval(ast.right)
  when "Minus"
    mb_eval(ast.left) - mb_eval(ast.right)
  when "Mul"
    mb_eval(ast.left) * mb_eval(ast.right)
  when "Div"
    mb_eval(ast.left) / mb_eval(ast.right) # Catch div by 0?
  when "Mod"
    mb_eval(ast.left) % mb_eval(ast.right) # Catch mod by 0?
  when "Constant"
    ast.num.lexeme.to_i
  when "Identifier"
    $vars[ast.ident.lexeme]
  when "Paran"
    mb_eval(ast.expr)
  end
end

File.open(ARGV[0], "r") do |bf|
  ast = delete_unnamed_nodes(parser.parse(bf.read))
  mb_eval(ast)
end

------------------------
Minibasic example:
------------------------
PRINT "I can sum even numbers."
PRINTLN
PRINT "At what number should I start summing"
READ START
PRINT "At what number should I stop"
READ STOP
SUM := 0
FOR I := START TO STOP
  IF (I MOD 2) = 0 THEN
    SUM := (SUM + I)
  ENDIF
NEXT
PRINT "The sum of all even numbers between "
PRINT START
PRINT " and "
PRINT STOP
PRINT " is = "
PRINT SUM