Loại trình phân tích cú pháp nào cần thiết cho ngữ pháp này?

Question

Tôi có một ngữ pháp mà tôi không biết loại phân tích cú pháp nào tôi cần để phân tích cú pháp khác ngoài tôi không tin rằng ngữ pháp là LL (1). Tôi nghĩ rằng tôi cần một phân tích cú pháp với backtracking hoặc LL (*) của một số loại. Ngữ pháp tôi đã nảy ra (có thể cần một số viết lại) là:

S: Rules 
Rules: Rule | Rule Rules 
Rule: id '=' Ids 
Ids: id | Ids id 

các ngôn ngữ tôi đang cố gắng để tạo ra trông giống như sau:

abc = def g hi jk lm 
xy = aaa bbb ccc ddd eee fff jjj kkk 
foo = bar ha ha 

Zero hoặc nhiều Rule có chứa một trái số nhận dạng được theo sau bởi một dấu bằng được theo sau bởi một hoặc nhiều số nhận dạng. Phần mà tôi nghĩ rằng tôi sẽ gặp vấn đề khi viết một trình phân tích cú pháp là ngữ pháp cho phép bất kỳ số lượng id nào trong Quy tắc và cách duy nhất để biết khi nào Quy tắc mới bắt đầu là khi nó tìm id =, điều này sẽ yêu cầu backtracking.

Có ai biết phân loại ngữ pháp này và phương pháp phân tích cú pháp tốt nhất, cho một số được viết bằng tay trình phân tích cú pháp không?

Answer 1

Ngữ pháp tạo số nhận dạng theo sau là dấu bằng được theo sau bởi chuỗi số nhận dạng hữu hạn là thông thường. Điều này có nghĩa là các chuỗi trong ngôn ngữ có thể được phân tích cú pháp bằng cách sử dụng biểu thức DFA hoặc cụm từ thông dụng. Không cần các trình phân tích cú pháp không xác định hoặc LL (*) ưa thích.

Để thấy rằng ngôn ngữ là thường xuyên, chúng ta hãy Id = U {một: một ∈ Γ}, trong đó Γ ⊂ Σ là tập hợp các ký tự có thể xảy ra trong định danh. Ngôn ngữ bạn đang cố gắng để tạo ra được ký hiệu bằng các biểu thức chính quy

• Id⁺ = (Id⁺) ^* Id ⁺

Setting Γ = {a, b, ..., z}, ví dụ về chuỗi trong ngôn ngữ của biểu thức chính quy là:

• nhìn = tôi đang trong một ngôn ngữ thông thường
• hey = có nghĩa là tôi có thể được công nhận bởi một DFA
• mát = hoặc thậm chí là một biểu thức chính quy

không cần phải phân tích ngôn ngữ của bạn sử dụng các kỹ thuật phân tích cú pháp mạnh mẽ. Đây là một trường hợp phân tích cú pháp bằng cách sử dụng cụm từ thông dụng hoặc DFA vừa phù hợp vừa tối ưu.

chỉnh sửa:

Gọi biểu thức chính quy trên R.Để phân tích cú pháp R^*, tạo DFA công nhận ngôn ngữ của R^*. Để thực hiện việc này, hãy tạo NFA công nhận ngôn ngữ của R^* bằng thuật toán có thể đạt được từ định lý của Kleene. Sau đó chuyển đổi NFA thành DFA bằng cách sử dụng cấu trúc tập hợp con. DFA kết quả sẽ nhận ra tất cả các chuỗi trong R^*. Cho một đại diện của DFA xây dựng bằng ngôn ngữ thực hiện của bạn, những hành động cần thiết - ví dụ,

• Thêm nhận dạng qua phân tích cú pháp để phía bên tay phải của báo cáo kết quả khai hiện đang được phân tích
• Thêm tuyên bố cuối cùng câu lệnh được phân tích cú pháp thành danh sách các khai báo được phân tích cú pháp và sử dụng số nhận dạng cuối được phân tích cú pháp để bắt đầu phân tích một tuyên bố khai báo mới

có thể được mã hóa thành các trạng thái của DFA. Trong thực tế, sử dụng định lý Kleene và xây dựng tập con có lẽ không cần thiết cho một ngôn ngữ đơn giản như vậy. Tức là, bạn có thể chỉ cần viết một trình phân tích cú pháp với hai hành động trên mà không cần thực hiện một automaton. Với một ngôn ngữ thường xuyên phức tạp hơn (ví dụ, cấu trúc từ vựng của một ngôn ngữ lập trình), việc chuyển đổi sẽ là lựa chọn tốt nhất.