LL (1) không thể mơ hồ

Question

Làm cách nào để chứng minh rằng không có ngữ pháp LL (1) nào có thể mơ hồ?

Tôi biết ngữ pháp mơ hồ là gì nhưng không thể chứng minh được định lý trên/bổ đề.

Answer 1

Tôi nghĩ nó gần như là kết quả trực tiếp của định nghĩa LL (1). Hãy thử bằng chứng bằng sự mâu thuẫn; giả sử rằng bạn có một ngữ pháp LL (1) không rõ ràng và tìm kiếm một cái gì đó bạn có thể hiển thị là đúng và không đúng sự thật. Như một điểm khởi đầu "bạn luôn biết điều gì khi bạn xử lý đầu vào?"

Vì điều này có vẻ như là một vấn đề về bài tập về nhà và tôi thực sự chưa hoàn thành bài toán nhiều hơn tôi phác thảo ở trên, tôi sẽ dừng ở đó.

Answer 2

Chứng minh rằng không có ngữ pháp mơ hồ nào có thể là ngữ pháp LL (1). Để biết các gợi ý, hãy xem http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf, trang trình bày 18-20. Xem thêm http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, pg. 11 và trước đó.

Answer 3

Đây là bản nháp đầu tiên của tôi tại một bằng chứng. Nó có thể cần một số điều chỉnh tốt, nhưng tôi nghĩ rằng nó bao gồm tất cả các trường hợp. Tôi nghĩ rằng nhiều giải pháp là có thể. Đây là bằng chứng trực tiếp.

(Side lưu ý: đó là một điều đáng tiếc SO không hỗ trợ toán học, chẳng hạn như trong LaTeX.)

Proof

Hãy T và N là bộ thiết bị đầu cuối và không terminal ký tự .

Hãy giữ sau

MaybeEmpty(s) = true <=> s ->* empty 
First(s) = X containing all x for which there exists Y such that s ->* xY 
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ 

Lưu ý rằng một ngữ pháp là LL (1) nếu sau giữ cho mỗi cặp tác phẩm A -> B và A -> C:

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C)) 
2. (First(B) intersect First(C)) = empty 
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty 

Hãy xem xét một ngôn ngữ với LL (1), với A -> B và A -> C. Đó là để nói rằng có một số chuỗi thiết bị đầu cuối TZ thừa nhận nhiều dẫn xuất bằng cách phân biệt các cây phân tích.

Giả sử rằng đạo hàm bên trái đạt đến S ->* TAY ->* TZ. Bước tiếp theo có thể là TAY -> TBY hoặc TAY -> TCY. Do đó ngôn ngữ không rõ ràng nếu cả hai BY ->* Z và CY ->* Z. (Lưu ý rằng kể từ khi A là một tùy ý phi thiết bị đầu cuối, nếu không có trường hợp như vậy tồn tại, ngôn ngữ là không mơ hồ.)

Trường hợp 1: Z = trống

Bằng quy tắc 1 của LL (1) văn phạm tiếng , nhiều nhất một trong B và C có thể lấy được sản phẩm nào (trường hợp không mơ hồ).

Trường hợp 2: Z không trống, và không phải B hay C lấy trống

Bằng quy tắc 2 của LL (1) văn phạm, ít nhất một trong B và C có thể cho phép nguồn gốc hơn nữa vì nhà ga hàng đầu của Z không thể ở cả hai số First(B) và First(C) (trường hợp không rõ ràng).

Trường hợp 3: Z không trống, và một trong hai MaybeEmpty(B) hay MaybeEmpty(C)

Note bằng quy tắc 1 của LL (1) văn phạm, B và C có thể không được cả hai lấy được sản phẩm nào. Giả sử do đó MaybeEmpty(C) là đúng.

Điều này cung cấp hai trường hợp phụ.

Trường hợp 3a: CY -> Y; và Trường hợp 3b: CY ->* DY, trong đó D không trống.

Trong 3a, chúng tôi phải chọn giữa BY ->* Z và CY -> Y ->* Z, nhưng lưu ý rằng First(Y) subset-of Follow(A). Vì Follow(A) không giao nhau First(B), chỉ có một dẫn xuất có thể tiến hành (không mơ hồ).

Trong 3b, chúng tôi phải chọn giữa BY ->* Z và CY ->* DY ->* Z, nhưng lưu ý rằng First(D) subset-of First(C). Vì First(C) không giao nhau với First(B), chỉ có một dẫn xuất có thể tiến hành (không mơ hồ).

Vì vậy, trong mọi trường hợp, đạo hàm chỉ có thể được mở rộng bằng một trong các sản phẩm có sẵn. Do đó ngữ pháp không mơ hồ.