Làm cách nào để tạo câu từ ngữ pháp chính thức?

Question

Cách phổ biến để tạo câu từ ngữ pháp là gì?

Tôi muốn một thuật toán phân loại ngược lại với trình phân tích cú pháp. Đó là, được đưa ra một ngữ pháp ngữ pháp chính thức (nói LL), tôi muốn tạo ra một câu tùy ý phù hợp với ngữ pháp đó. Tôi sử dụng câu ở đây để ngụ ý bất kỳ nội dung văn bản hợp lệ nào, do đó, nó thực sự có thể là toàn bộ chương trình (ngay cả khi chương trình không có ý nghĩa gì - miễn là nó chính xác về cú pháp).

Ví dụ ngữ pháp:

program : <imports> NEWLINE? <namespace> 
imports : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)* 
... 

Ví dụ tạo chương trình:

import jkhbhhuob 
import aaaaa888_ 

namespace u8nFGubgykb 
{ class ui0op_np { ... } 
} 

Answer 1

Tôi không biết rằng có một thuật toán "phổ biến" để thực hiện việc này. Tạo chương trình ngẫu nhiên được sử dụng trong lập trình di truyền để bạn có thể tìm kiếm một hệ thống GP ngữ pháp dựa trên và xem cách chúng xử lý thế hệ chương trình. Tôi sẽ làm một thuật toán tạo quy tắc đệ quy như mã giả:

void GenerateRule(someRule) 
{ 
    foreach (part in someRule.Parts) 
    { 
    if (part.IsLiteral) OutputLiteral(part); 
    if (part.IsIdentifier) Output(GenerateIdentifier(part))); 
    if (part.IsRule) GenerateRule(part.Rule); 
    } 
} 

Giả thiết bạn đã đọc tất cả các phần vào một số cấu trúc dữ liệu. Bạn cũng cần phải xử lý các lần lặp lại (tạo ngẫu nhiên số lần chúng xuất hiện) và các quy tắc tùy chọn (lật một đồng xu để xem chúng có ở đó hay không).

---

Chỉnh sửa: Oh, và nếu quy tắc có nhiều tùy chọn, bạn chỉ cần chọn một trong các tùy chọn để thực hiện và xử lý theo cùng một cách. Vì vậy, nếu một số quy tắc là (Literal | Variable), bạn sẽ chọn ngẫu nhiên giữa hai.

Answer 2

không phải là một câu trả lời, nhưng hãy kiểm tra mục wikipedia trên hệ ngữ pháp: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

nó mô tả một số chung thuật toán được sử dụng.

Answer 3

Đề xuất đầu tiên của tôi sẽ là tìm kiếm đầu tiên. Chỉ cần thiết lập biểu đồ quy tắc và tìm kiếm thông qua các quy tắc đó. Bạn sẽ bắt đầu phun ra các chương trình bắt đầu từ những người nhỏ nhất có thể, và từ từ nhận được lớn hơn. Tuy nhiên, bạn sẽ thấy rằng ngữ pháp của bạn sẽ nhổ ra nhiều chương trình theo cấp số nhân cho một số quy tắc nhất định và bạn có thể sẽ không nhận được quá 30 mã thông báo trong một chương trình bằng DFS.

Vấn đề với tìm kiếm độ sâu đầu tiên là thứ hai bạn có quy tắc đệ quy trái, tìm kiếm của bạn sẽ bị kẹt trong một vòng lặp vô hạn.

Một vấn đề lớn khác là các chương trình cú pháp chính xác là một chặng đường dài từ các chương trình đúng ngữ nghĩa. Việc tạo kiểu sau có khả năng hoàn toàn không khả thi trong tất cả trừ các trường hợp cơ bản nhất.

Answer 4

Trong khi ý tưởng rất hay (trước đây tôi đã nghĩ nhiều), thực tế là nếu không có một số dữ liệu mẫu và/hoặc tấn ràng buộc máy phát/giới hạn nỗ lực, thì đó là một công việc khá lớn.

Bạn chỉ có thể tìm các mẫu viết bằng tay dễ dàng hơn. :)

Answer 5

Off đỉnh đầu của tôi:

Tôi muốn làm việc một cách đệ quy (về cơ bản đối lập với một phân tích cú pháp phong nha đệ quy) sử dụng một số chẩn đoán về những việc cần làm với dãy ((...): lẽ chọn một cách ngẫu nhiên) optionals (?: xem [], bên dưới), lặp lại ('' Phân bố Poisson?). Literals ("...") được viết đơn giản cho đầu ra, và subtokens (`<...> ') tạo ra một đệ quy.

Điều này không quá khó trừ khi bạn muốn đảm bảo một số loại bảo hiểm hoàn chỉnh. Thậm chí sau đó, chỉ cần tạo một số bó dữ liệu sẽ là trợ giúp ...

---

[*] Bạn cần phải bao gồm optionals ít hơn 50% thời gian để ngăn chặn thoái vô hạn khi xử lý các rules như

nonterm: otherstuff <nonterm>? 

Good catch bởi plinth.

Tương tự như vậy với sự lặp lại, hãy ném một bản phân phối hội tụ mạnh mẽ.

---

Trước tiên, bạn cần phân tích ngữ pháp đầu vào nếu ngữ cảnh được trình bày dưới dạng BNF như sau. Điều đơn giản nhất để làm là sử dụng ánh xạ (name, string), sau đó bắt đầu với mã thông báo mức cao nhất (bạn có thể giả định là mã thông báo đầu tiên ...).

này mang đến cho bạn:

("chương trình", "< nhập khẩu > NEWLINE <namespace>? ")

(" nhập khẩu", ("nhập khẩu" < định danh > NEWLINE) *)

...

Các bạn bắt đầu với "chương trình", nhấn "< nhập >" để bạn tái diễn ... khi quay lại, lịch sử "NEWLINE?", vì vậy hãy ném xúc xắc và viết hay không, nhấn "< không gian tên >" để tiếp tục ... trên bạn đã hoàn thành.

---

Tôi thấy tự nghi ngờ rằng điều này đã được thực hiện trước đây. Nếu bạn chỉ cần đầu ra, tôi sẽ tìm kiếm trên web ... Có lẽ http://portal.acm.org/citation.cfm?doid=966137.966142, mặc dù số lượng lớn các trình tạo phân tích cú pháp có thể làm lộn xộn không gian tìm kiếm ... Hãy thử this paper.

BTW-- Trường đại học địa phương có thể có đăng ký trực tuyến với các tạp chí này, vì vậy bạn có thể tải chúng miễn phí bằng cách đăng ký tại thư viện.

Answer 6

Vấn đề bạn sẽ có là bản chất đệ quy của biểu đồ là sao cho bạn có thể tạo đúng ngữ pháp có kích thước vô hạn. Bạn có thể sẽ muốn làm một cái gì đó như thiết lập một băm của các loại nút trong ngữ pháp của bạn với số lượng và giới hạn của bao nhiêu lần bạn đang cho phép mình để nhấn nút đó.Sau đó, tìm kiếm đầu tiên chiều sâu đến nội dung trái tim của bạn.

Answer 7

Giải pháp của bạn nên tuân theo cấu trúc quy tắc của ngữ pháp. Làm thế nào để bạn tạo ra một lời nói ngẫu nhiên cho mỗi điều sau đây?

• ga biểu tượng
• biểu tượng không thuộc đầu cuối
• Chuỗi các bên tay phải
• Choice của bên cánh tay phải
đóng cửa
• sao của bên cánh tay phải

này sẽ tất cả rõ ràng hơn nhiều nếu bạn viết ra cấu trúc dữ liệu bạn sử dụng để trình bày ngữ pháp. Cấu trúc của tập hợp các chức năng phát lại đệ quy lẫn nhau của bạn sẽ phản ánh cấu trúc dữ liệu đó rất chặt chẽ.

Xử lý đệ quy vô hạn hơi khó khăn một chút. Cách dễ nhất là tạo ra một luồng các lời nói và giữ một đoạn cắt sâu. Hoặc nếu bạn đang sử dụng một ngôn ngữ lười biếng như Haskell, bạn có thể tạo ra tất cả lời nói và bóc ra nhiều thứ hữu hạn tùy thích (một vấn đề phức tạp hơn câu hỏi gốc nhưng rất thú vị).

Answer 8

Như thường lệ, tôi sẽ cố gắng chống lại việc phát minh lại bánh xe. Tôi đã viết một trong số này cho bộ lắp ráp ARM, nhưng tôi đang ghi lại là hối hận về nó (Phần mềm: Thực hành và Trải nghiệm tháng 4 năm 2007):

“Xem lại, một trình tạo biểu thức không có giá phải có được sử dụng để tạo ra các hướng dẫn lắp ráp ARM ngẫu nhiên để so sánh. Thay vào đó, một kịch bản Perl được xây dựng theo từng bước, lấy từng định nghĩa lệnh ARM và tạo các cá thể. Tuy nhiên, lợi thế của phương pháp tiếp cận nội bộ gia tăng là những thay thế đơn giản đã phát hiện ra các lỗi đơn giản, và việc săn tìm lỗi có thể tiến hành từng bước một. ”

Tôi sợ tôi không nhớ điều gì đã khiến tôi thay đổi ý định, và tôi nghi ngờ nó sẽ có liên quan đến nhu cầu cụ thể của bạn, nhưng tôi đề nghị tìm kiếm khó khăn hơn cho một giải pháp từ trước. Nó đòi hỏi ít kỷ luật để viết những thứ như thế này, nhưng nó luôn mất nhiều thời gian hơn bạn mong đợi.

Answer 9

Dưới đây là một ví dụ Python sử dụng NLTK:

from nltk import parse_cfg, ChartParser 
from random import choice 

def produce(grammar, symbol): 
    words = [] 
    productions = grammar.productions(lhs = symbol) 
    production = choice(productions) 
    for sym in production.rhs(): 
     if isinstance(sym, str): 
      words.append(sym) 
     else: 
      words.extend(produce(grammar, sym)) 
    return words 

grammar = parse_cfg(''' 
S -> NP VP 
PP -> P NP 
NP -> Det N | Det N PP | 'I' 
VP -> V NP | VP PP 
V -> 'shot' | 'killed' | 'wounded' 
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog' 
P -> 'in' | 'outside' 
''') 

parser = ChartParser(grammar) 

gr = parser.grammar() 
print ' '.join(produce(gr, gr.start())) 

Ví dụ được chuyển thể từ book. Các câu được tạo ra là cú pháp chính xác nhưng vẫn là tổng số vô nghĩa.