mutualRecursionStackTooDeep.rb

# An example of Mutual Recursion.

# A simple lexer for our parser.  We only return tokens for :numbers
# and +, - and new lines.
class Lexer
  attr_reader :token, :type

  def initialize(stream)
    @stream = stream
    @tokens = []
  end

  def advance
    @token = @tokens.shift || get_more_tokens
    @type = (@token =~ /^\d/) ? :number : @token
  end

  private

  def get_more_tokens
    line = @stream
    if line
      @tokens = line.scan(%r{\d+|[-+*/\(\)]}) + ["\n"]
    else
      @tokens = []
    end
    @tokens.shift
  end
end

# A very simple expression parser.  We can handle expressions like:
#
#     3
#     1+2
#     (1+2-3)
#     100 - (4 + (45 - 5))
#
class ExpressionParser
  class ParseError < StandardError
  end

  def initialize(lexer)
    @lexer = lexer
  end

  # Parse a single expression.
  def parse_expression
    result = parse_term
    loop do
      case type
      when '+'
        advance
        result = result + parse_term
      when '-'
        advance
        result = result - parse_term
      else
        break
      end
    end
    result
  end

  # Parse a term (i.e. a number or a parenthesized expression).
  def parse_term
    if type == :number
      result = parse_number
    elsif @lexer.type == "("
      advance
      result = parse_expression
      if type == ")"
        advance
      else
        expected("a closing parenthesis")
      end
    else
      expected("an expression")
    end
    result
  end

  # Parse a single number
  def parse_number
    if type == :number
      result = token.to_i
      advance
    else
      expected("a number")
    end
    result
  end

  private

  def type
    @lexer.type
  end

  def token
    @lexer.token
  end

  def advance
    @lexer.advance
  end

  def expected(what)
    fail ParseError, "Expected #{what}, got: <#{@lexer.token.inspect}>"
  end
end

x = ''
10000.times{ x<<'(' }
x << '5+2'
10000.times { x<<')' }
lexer = Lexer.new(x)
parser = ExpressionParser.new(lexer)
lexer.advance
while lexer.token
  result = parser.parse_expression
  puts "The answer is: #{result}"
  break
end