[ruby-talk:13627] Re: Parser? (a bit long)

Robert,
Cool!  I anticipate the major release of this rockit Ruby parser
generator very much.  A couple of questions: does it resemble Perl's
parse::recdescent in any way? (if you happen to know about it.)  Is it
a top-down or bottom-up design?  Is the grammar LL(n) or non-LL?

Thanks,
Eric


On Fri, 16 Mar 2001 23:07:59 +0900, Robert Feldt
<[e-mail]> wrote:

>On Fri, 16 Mar 2001 [e-mail] 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
>
>