của Ruby phân tích chuỗi

Question

Tôi có một chuỗi

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

Làm thế nào là phương pháp tốt nhất trong Ruby để phân tích chuỗi này?

Ý tôi là kịch bản sẽ có thể xây dựng sententes như thế này:

có lẽ đây là một số đêm xấu xí

có lẽ đó là một số đêm đẹp

có lẽ đây là một thời gian kỳ lạ

Và cứ như vậy, bạn đã nhận được điểm ...

Tôi có nên đọc chuỗi char của char và bulid một máy nhà nước với một ngăn xếp để lưu trữ các giá trị ngoặc đơn để tính toán sau này, hoặc là có một cách tiếp cận tốt hơn?

Có thể thư viện sẵn sàng, ngoài thư viện cho mục đích đó?

Answer 1

Hãy thử Treetop. Nó là một DSL giống như Ruby để mô tả ngữ pháp. Phân tích cú pháp chuỗi bạn đã cho nên khá dễ dàng và bằng cách sử dụng trình phân tích cú pháp thực, bạn sẽ dễ dàng mở rộng ngữ pháp của mình sau này.

Một ví dụ ngữ pháp cho các loại chuỗi mà bạn muốn phân tích cú pháp (save as 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 

Ngữ pháp trên cần một file kèm theo đó xác định các lớp học cho phép chúng ta truy cập vào các giá trị nút (lưu dưới dạng 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 

Chương trình ví dụ sau cho thấy việc phân tích cú pháp câu mẫu mà bạn đã đưa ra là khá đơn giản.

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 

Kết quả của chương trình này là:

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 

Bạn cũng có thể truy cập vào cây cú pháp:

p sentence 

The output is here.

Ở đó bạn có: một giải pháp phân tích cú pháp có thể mở rộng sẽ đến khá gần với những gì bạn muốn làm trong khoảng 50 dòng mã. cái đó có giúp ích không?