Ruby On Rails in UA/Ruby 1.8, 1,9/Математический парсер

02 июля 2009, 14:52   Математический парсер
DimaS
Dmitry Solonina
Живет: Nikolaev,UKR
Сообщений: 139
Рейтинг: 30.0
Рег: 17 апр. 2007

  •  
Была как-то задача написать свой парсер для обработки формул (написать простенький аналог электронной таблицы). Естественно поставили сжатые сроки. Покапавшишь в нете нашел вот такой небольшой и интересный парсер, конечно пришлось еще много чего добавить, новые операнды, условия и т.д. Хотел бы поделиться с вами (первоисточник :http://lukaszwrobel.pl/blog/math-parser-part-1-introduction) За основу берутся 3 класса: token, lexer и parser (предлагаю их разделить на три файла, впрочем, кому как нравится). Класс token - содержит множество знаков (сложение, вычитание, ...) и результат вычисления Класс lexer - использует класс token и позволяет провести лексический анализ выражения Класс parser - использует класс lexer и проводит непосредственно лексический анализ выражения Собственно скрипт token.rb
class Token
  Plus     = 0
  Minus    = 1
  Multiply = 2
  Divide   = 3
  
  Number   = 4
  
  LParen   = 5
  RParen   = 6
  
  End      = 7
  
  attr_accessor :kind
  attr_accessor :value
  
  def initialize
    @kind = nil
    @value = nil
  end

  def unknown?
    @kind.nil?
  end
end
lexer.rb
require 'token'

class Lexer
  def initialize(input)
    @input = input
    @return_previous_token = false
  end
  
  def get_next_token
    if @return_previous_token
      @return_previous_token = false
      return @previous_token
    end
    
    token = Token.new
    
    @input.lstrip!

    case @input
      when /\A\+/ then
        token.kind = Token::Plus
      when /\A-/ then
        token.kind = Token::Minus
      when /\A\*/ then
        token.kind = Token::Multiply
      when /\A\// then
        token.kind = Token::Divide
      when /\A\d+(\.\d+)?/
        token.kind = Token::Number
        token.value = $&.to_f
      when /\A\(/
        token.kind = Token::LParen
      when /\A\)/
        token.kind = Token::RParen
      when ''
        token.kind = Token::End
    end
    
    raise 'Unknown token' if token.unknown?
    @input = $'

    @previous_token = token
    token
  end
  
  def revert
    @return_previous_token = true
  end
end
parser.rb
require 'lexer'

class Parser
  def parse(input)
    @lexer = Lexer.new(input)
    
    expression_value = expression

    token = @lexer.get_next_token
    if token.kind == Token::End
      expression_value
    else
      raise 'End expected'
    end
  end
  
  protected
  def expression
    component1 = factor

    additive_operators = [Token::Plus, Token::Minus]

    token = @lexer.get_next_token
    while additive_operators.include?(token.kind)
      component2 = factor
      
      if token.kind == Token::Plus
        component1 += component2
      else
        component1 -= component2
      end

      token = @lexer.get_next_token
    end
    @lexer.revert

    component1
  end
  
  def factor
    factor1 = number
    
    multiplicative_operators = [Token::Multiply, Token::Divide]
    
    token = @lexer.get_next_token
    while multiplicative_operators.include?(token.kind)
      factor2 = number
      
      if token.kind == Token::Multiply
        factor1 *= factor2
      else
        factor1 /= factor2
      end
      
      token = @lexer.get_next_token
    end
    @lexer.revert

    factor1
  end
    
  def number
    token = @lexer.get_next_token
    
    if token.kind == Token::LParen
      value = expression
      
      expected_rparen = @lexer.get_next_token
      raise 'Unbalanced parenthesis' unless expected_rparen.kind == Token::RParen
    elsif token.kind == Token::Number
      value = token.value
    else
      raise 'Not a number'
    end
    
    value
  end
end
ну и вызов осуществляется следующим принципом
require 'parser'

parser = Parser.new
begin
  puts parser.parse('(2+2)*2')
rescue RuntimeError
  puts 'Error occured: ' + $!
end
Вместо чисел конечно возможно использование переменных (собственных), так как было например в моей задаче. Например (device1+device2)*2.35, где device1 - значение поля с ID=1 из таблицы devices Благодарю за внимание
IDE я нахожуся?
02 июля 2009, 15:03   RE: Математический парсер
romb
Roman V. Babenko
Живет: Kyiv,UKR
Сообщений: 931
Рейтинг: 152.0
Рег: 22 апр. 2008
Его блог
  •  
Dmitry Solonina Интересно. Но смущает вот этот кусок
case @input
   when /\A/ then
     token.kind = Token::Plus
уверен, что так должно быть ? ИМХО таким постам место в личном блоге :-)
http://romanvbabenko.com Если в споре не родилась истина, то, по крайней мере, один из спорящих бесплоден. Rails 2.3.3 Gnu\Linux Debian\Lenny Mongrel, MySql, SQLite GEdit, MCEdit FireFox 3.0 (FireBug) Git
02 июля 2009, 15:39   RE: Математический парсер
dseverin
dseverin
Живет:
Сообщений: 32
Рейтинг: 20.0
Рег: 24 апр. 2009

  •  
Dmitry Solonina ну нормальная такая quick-and-dirty вариация на тему простого рекурсивного спуска для калькулятора ага, с парой багов (не осиливает parser.parse("-1+(-2+2)*3") ) и очепятком:
case @input
   when /\A\x2b/ then # forum bug: backslash plus sign - \ + - is cut by code highlighter. wtf?
     token.kind = Token::Plus
02 июля 2009, 15:43   RE: RE: Математический парсер
DimaS
Dmitry Solonina
Живет: Nikolaev,UKR
Сообщений: 139
Рейтинг: 30.0
Рег: 17 апр. 2007

  •  
Roman V. Babenko Работает, но ты можешь удалить =)
IDE я нахожуся?
02 июля 2009, 15:46   RE: RE: Математический парсер
DimaS
Dmitry Solonina
Живет: Nikolaev,UKR
Сообщений: 139
Рейтинг: 30.0
Рег: 17 апр. 2007

  •  
dseverin начало есть, кому нужно тот если захочет, то доработает, если не найдет другого решения
IDE я нахожуся?
02 июля 2009, 16:04   RE: RE: RE: Математический парсер
romb
Roman V. Babenko
Живет: Kyiv,UKR
Сообщений: 931
Рейтинг: 152.0
Рег: 22 апр. 2008
Его блог
  •  
Dmitry Solonina Что удалить ? Зачем ? Я говорю, что в коде ошибка для определения оператора "+".
http://romanvbabenko.com Если в споре не родилась истина, то, по крайней мере, один из спорящих бесплоден. Rails 2.3.3 Gnu\Linux Debian\Lenny Mongrel, MySql, SQLite GEdit, MCEdit FireFox 3.0 (FireBug) Git
02 июля 2009, 16:10   RE: RE: RE: RE: Математический парсер
DimaS
Dmitry Solonina
Живет: Nikolaev,UKR
Сообщений: 139
Рейтинг: 30.0
Рег: 17 апр. 2007

  •  
Roman V. Babenko а, да Рома спасибо. Проглотило тег, сейчас поправлю
IDE я нахожуся?
02 июля 2009, 16:14   RE: RE: RE: RE: Математический парсер
DimaS
Dmitry Solonina
Живет: Nikolaev,UKR
Сообщений: 139
Рейтинг: 30.0
Рег: 17 апр. 2007

  •  
Roman V. Babenko Это нужно у Руслана уже спросить, почему проглотило. Код вставлял из работающего файла
IDE я нахожуся?
02 июля 2009, 16:18   RE: RE: RE: RE: RE: Математический парсер
romb
Roman V. Babenko
Живет: Kyiv,UKR
Сообщений: 931
Рейтинг: 152.0
Рег: 22 апр. 2008
Его блог
  •  
Dmitry Solonina Поправим.
http://romanvbabenko.com Если в споре не родилась истина, то, по крайней мере, один из спорящих бесплоден. Rails 2.3.3 Gnu\Linux Debian\Lenny Mongrel, MySql, SQLite GEdit, MCEdit FireFox 3.0 (FireBug) Git