У меня есть строка
input = "maybe (this is | that was) some ((nice | ugly) (day |night) | (strange (weather | time)))"
Как лучший метод в Ruby для парсинга этой строки?
Я подразумеваю, что сценарий должен смочь создать sententes как это:
возможно, это - некоторая ужасная ночь
возможно, это было некоторой хорошей ночью
возможно, это было некоторым странным временем
И так далее Вы поняли...
Я должен считать строковый символ символом и создать конечный автомат со стеком для хранения значений круглой скобки для более позднего вычисления или являюсь там лучшим подходом?
Возможно, готовое, из библиотеки поля для такой цели?
Попробуйте Treetop. Это 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 строках кода. Помогло?