Updated 2011-10-19 14:28:35 by dkf

GPS - Fri Jul 12, 2002: I've been curious about how interpreters work, and in particular how they evaluate sequences and magically return a result. The other day I looked at a little mathematical expression evaluator [1] and the concept finally made sense. I came up with the following Tcl prototype to teach me how it works and verify my thoughts. Using a method similar to this a person could probably write a Tcl-like interpreter.
  #!/bin/tclsh8.3
  #version 1 July 12, 2002 
  proc push {arPtr val} {
    upvar $arPtr ar
    set len $ar(length)
    incr len
    set ar($len) $val
    set ar(length) $len
  }
  
  proc pop {arPtr} {
    upvar $arPtr ar
    set len $ar(length)
  
    if {![info exists ar($len)]} {
      return -code error "no element to pop"
    }
    set res [set ar($len)]
    unset ar($len)
    incr len -1
    set ar(length) $len
    return $res
  }
  
  proc evaluate {str} {
    array set operandStack {length 0}
    array set operatorStack {length 0}
  
    set digit ""
    set paren 0
    set parenStr ""
    set count 1
    foreach char [split $str ""] {
      if {$paren} {
        
        if {$char == "("} {
          incr count
        } elseif {$char == ")"} {
          incr count -1
          if {$count == 0} {
            set res [evaluate $parenStr]
            set count 1
            set paren 0
            set parenStr ""
            puts "sub eval $res"
            push operandStack $res
          }
        } else {
          append parenStr $char
        }
        continue
      }
  
      if {$char == "("} {
        set paren 1
      } elseif {$char == "."} {
        append digit $char
      } elseif {[string is digit $char]} {
        append digit $char
      } elseif {[string is space $char]} {
        if {$digit != ""} {
          push operandStack $digit
          set digit ""
        }
      } elseif {$char == "+"} {
        push operatorStack $char
      } elseif {$char == "-"} {
        push operatorStack $char
      } elseif {$char == "*"} {
        push operatorStack $char
      } elseif {$char == "/"} {
        push operatorStack $char
      }
    }
    
    if {$digit != ""} {
      push operandStack $digit
    }
    
    parray operandStack
    parray operatorStack
    puts "----"
    while {$operandStack(length) > 1} {
    
      set num2 [pop operandStack]
      set num1 [pop operandStack]
      set op [pop operatorStack]
  
      switch -- $op {
        "+" {
          push operandStack [expr {$num1 + $num2}]
        }
  
        "-" {
          push operandStack [expr {$num1 - $num2}]
        }
  
        "*" {
          push operandStack [expr {$num1 * $num2}]
        }
  
        "/" {
          push operandStack [expr {$num1 / $num2}]
        }
      }
    }
    if {$operatorStack(length) > 0} {
      return -code error "invalid expression: $str"
    }
    puts "returning $operandStack(1)"
  
    return $operandStack(1)
  }
  
  proc main {} {
    puts [evaluate "100 + 200 + (20 / 4) + (20.0 / 300) + 5"]
  }
  main

For an example of C code which parses Tcl commands, and C code with parses like expr does, see "Scratch" in the CriTcl library - README [2], download [3]. It has similarities with the above, yet also some differences and tricks. -jcw