gistfile1.rb

# Classic recursive-descent parser for expressions
# Inefficient, boilerplate and hardcoded,
# but close to grammar rules and easy to understand
  def expression
    if @tokens.first.type == :minus
      Node.new(Token.new(:unary_minus, @tokens.shift.value)).add_child(additive_expression)
    else
      additive_expression
    end
  end

  def additive_expression
    node = multiplicative_expression
    while @tokens.first.type == :plus || @tokens.first.type == :minus
      node = Node.new(@tokens.shift).add_child(node).add_child(multiplicative_expression)
    end
    node
  end

  def multiplicative_expression
    node = boolean_binary_expression
    while @tokens.first.type == :multiply || @tokens.first.type == :divide
      node = Node.new(@tokens.shift).add_child(node).add_child(boolean_binary_expression)
    end
    node
  end

  def boolean_binary_expression
    node = not_expression
    while @tokens.first.type == :and || @tokens.first.type == :or
      node = Node.new(@tokens.shift).add_child(node).add_child(not_expression)
    end
    node
  end

  def not_expression
    @tokens.first.type == :not ? Node.new(@tokens.shift).add_child(base) : base
  end

  def base
    token = @tokens.shift
    if token.type == :num || token.type == :id
      Node.new(token)
    elsif token.type == :lp
      node = expression
      if @tokens.first.type == :rp
        @tokens.shift
        node
      else
        error 'Ожидалась закрывающая скобка', @tokens.first.index
      end
    else
      error 'Ожидалось число, идентификатор или скобка', token.index
    end
  end