Рубиновая строка синтаксического анализа - PullRequest
Новая
       8

Рубиновая строка синтаксического анализа

5 голосов
/ 04 марта 2010

У меня есть строка 

input = "maybe (this is | that was) some ((nice | ugly) (day |night) | (strange (weather | time)))"

Как в Ruby лучше всего разбирать эту строку?

Я имею в виду, что скрипт должен иметь возможность строить предложения следующим образом:

может быть, это какая-то ужасная ночь

может быть, это была хорошая ночь

может быть, это было какое-то странное время

И так далее, вы поняли ...

Стоит ли читать строку char с помощью char и составлять конечный автомат со стеком для хранения значений в скобках для последующего вычисления, или есть лучший подход?

Может быть, готовая из коробки библиотека для этой цели?

1 Ответ

8 голосов
/ 04 марта 2010

Попробуйте Верх дерева . Это Ruby-подобный DSL для описания грамматик. Парсинг строки, которую вы дали, должен быть довольно простым, и с помощью реального парсера вы легко сможете расширить свою грамматику позже.

Пример грамматики для типа строки, которую вы хотите проанализировать (сохранить как sentences.treetop): 

grammar Sentences
  rule sentence
    # A sentence is a combination of one or more expressions.
    expression* <Sentence>
  end

  rule expression
    # An expression is either a literal or a parenthesised expression.
    parenthesised / literal
  end

  rule parenthesised
    # A parenthesised expression contains one or more sentences.
    "(" (multiple / sentence) ")" <Parenthesised>
  end

  rule multiple
    # Multiple sentences are delimited by a pipe.
    sentence "|" (multiple / sentence) <Multiple>
  end

  rule literal
    # A literal string contains of word characters (a-z) and/or spaces.
    # Expand the character class to allow other characters too.
    [a-zA-Z ]+ <Literal>
  end
end

Для грамматики, приведенной выше, требуется сопроводительный файл, который определяет классы, которые позволяют нам получить доступ к значениям узла (сохранить как sentence_nodes.rb). 

class Sentence < Treetop::Runtime::SyntaxNode
  def combine(a, b)
    return b if a.empty?
    a.inject([]) do |values, val_a|
      values + b.collect { |val_b| val_a + val_b }
    end
  end

  def values
    elements.inject([]) do |values, element|
      combine(values, element.values)
    end
  end
end

class Parenthesised < Treetop::Runtime::SyntaxNode
  def values
    elements[1].values
  end
end

class Multiple < Treetop::Runtime::SyntaxNode
  def values
    elements[0].values + elements[2].values
  end
end

class Literal < Treetop::Runtime::SyntaxNode
  def values
    [text_value]
  end
end

Следующая программа-пример показывает, что разобрать предложение, которое вы дали, довольно просто. 

require "rubygems"
require "treetop"
require "sentence_nodes"

str = 'maybe (this is|that was) some' +
  ' ((nice|ugly) (day|night)|(strange (weather|time)))'

Treetop.load "sentences"
if sentence = SentencesParser.new.parse(str)
  puts sentence.values
else
  puts "Parse error"
end

Вывод этой программы: 

maybe this is some nice day
maybe this is some nice night
maybe this is some ugly day
maybe this is some ugly night
maybe this is some strange weather
maybe this is some strange time
maybe that was some nice day
maybe that was some nice night
maybe that was some ugly day
maybe that was some ugly night
maybe that was some strange weather
maybe that was some strange time

Вы также можете получить доступ к дереву синтаксиса: 

p sentence

Выход здесь .

Вот оно: масштабируемое решение для анализа, которое должно быть достаточно близко к тому, что вы хотите сделать, примерно в 50 строках кода. Это помогает?

...