Điều gì về ngữ pháp luận và trình phân tích cú pháp tối thiểu để nhận ra nó?

Question

Tôi đang cố gắng tìm hiểu cách tạo trình biên dịch. Để làm như vậy, tôi đọc rất nhiều về ngôn ngữ không có ngữ cảnh. Nhưng có một số điều tôi không thể tự mình đạt được.

Vì đó là trình biên dịch đầu tiên của tôi, có một số thực tiễn mà tôi không biết. Câu hỏi của tôi được yêu cầu với ý tưởng để xây dựng một trình tạo trình phân tích cú pháp, không phải trình biên dịch cũng không phải là từ khóa. Một số câu hỏi có thể hiển nhiên ..

Trong số lần đọc của tôi là: Bottom-Up Parsing, Top-Down Parsing, Formal Grammars. Hình ảnh được hiển thị đến từ: Miscellanous Parsing. Tất cả đều đến từ lớp Stanford CS143.

Sau đây là các điểm:

0) Làm thế nào để (mơ hồ/rõ ràng) và (trái-đệ quy/phải đệ quy) ảnh hưởng đến nhu cầu cho một thuật toán này hay cách khác? Có cách nào khác để hội đủ điều kiện một ngữ pháp không?

1) Ngữ pháp mơ hồ là ngữ pháp có nhiều cây phân tích cú pháp. Nhưng không nên lựa chọn một dẫn xuất từ ​​bên trái hoặc tận cùng bên phải dẫn đến sự độc đáo của cây phân tích cú pháp?

[EDIT: Giải đáp here]

2.1) Nhưng vẫn còn, được sự mơ hồ của ngữ pháp liên quan đến k? Tôi có nghĩa là đưa ra một LR (2) ngữ pháp, là nó mơ hồ cho một LR (1) phân tích cú pháp và không mơ hồ cho một LR (2) một?

[CHỈNH SỬA: Không, không phải vậy, ngữ pháp LR (2) nghĩa là trình phân tích cú pháp sẽ cần hai mã thông báo để chọn quy tắc phù hợp để sử dụng. Mặt khác, một ngữ pháp mơ hồ là một ngữ pháp có thể dẫn đến một số cây phân tích. ]

2.2) Vì vậy, một trình phân tích LR (*), miễn là bạn có thể tưởng tượng nó, sẽ không có ngữ pháp mơ hồ chút nào và sau đó có thể phân tích toàn bộ các ngôn ngữ tự do ngữ cảnh?

[EDIT: Được trả lời bởi Ira Baxter, LR (*) ít mạnh hơn GLR, ở chỗ nó không thể xử lý nhiều cây phân tích cú pháp. ]

3) Tùy thuộc vào câu trả lời trước, những gì sau có thể tự mâu thuẫn. Xem xét phân tích cú pháp LR, làm các ngữ pháp mơ hồ kích hoạt xung đột giảm-giảm? Một ngữ pháp rõ ràng có thể kích hoạt một ngữ pháp không? Trong cùng một cách, những gì về giảm bớt xung đột?

[EDIT: đây là nó, ngữ pháp mơ hồ dẫn đến thay đổi-giảm và giảm bớt xung đột. Bởi contrapositive, nếu không có xung đột, ngữ pháp là không rõ ràng. ]

4) Khả năng phân tích ngữ pháp đệ quy trái là lợi thế của trình phân tích cú pháp LR (k) trên LL (k), đó có phải là sự khác biệt duy nhất giữa chúng?

[CHỈNH SỬA: có. ]

5) Đưa ra G1:

G1 : 
S -> S + S 
S -> S - S 
S -> a 

5,1) G1 được trái recursive cả hai, phải đệ quy, và mơ hồ, tôi phải không? Nó là một LR (2) ngữ pháp? Người ta sẽ làm cho nó rõ ràng:

G2 : 
S -> S + a 
S -> S - a 
S -> a 

5.2) G2 vẫn còn mơ hồ? Trình phân tích cú pháp cho G2 có cần hai lookaheads không?Bởi factorisation chúng tôi có:

G3 : 
S -> S V 
V -> + a 
V -> - a 
S -> a 

5.3) Bây giờ, một phân tích cú pháp cho G3 chỉ cần một lookahead? Các bộ phận truy cập để thực hiện các phép biến đổi này là gì? LR (1) trình phân tích cú pháp tối thiểu có được yêu cầu không?

5.4) G1 còn lại đệ quy, để phân tích nó với một phân tích cú pháp LL, một nhu cầu để biến nó thành một quyền đệ quy ngữ pháp:

G4 : 
S -> a + S 
S -> a - S 
S -> a 

sau đó

G5 : 
S -> a V 
V -> - V 
V -> + V 
V -> a 

5,5) Liệu G4 cần ít nhất một trình phân tích cú pháp LL (2)? Chỉ G5 có thể phân tích cú pháp bằng trình phân tích cú pháp LL (1), G1-G5 định nghĩa cùng một ngôn ngữ và ngôn ngữ này là (a (+/- a)^n). Có đúng không?

5.6) Đối với mỗi ngữ pháp G1 đến G5, bộ tối thiểu mà nó thuộc về là gì?

6) Cuối cùng, vì nhiều ngữ pháp khác nhau có thể xác định cùng một ngôn ngữ, làm thế nào để chọn ngữ pháp và trình phân tích cú pháp liên quan? Là kết quả phân tích cú pháp cây imortant? Ảnh hưởng của cây phân tích là gì?

Tôi đang hỏi rất nhiều và tôi không thực sự mong đợi câu trả lời hoàn chỉnh, dù sao bất kỳ trợ giúp nào cũng sẽ được đánh giá rất cao.

Thx để đọc!

Answer 1

"Nhiều ngữ pháp có thể xác định cùng một ngôn ngữ, cách một người chọn ..."?

Thông thường, bạn chọn một trong những đáp ứng các tiêu chí sau:

• khái niệm đơn giản như bạn có thể làm cho nó (ám chỉ: nhỏ hơn so với những người khác)
• theo dõi các thuật ngữ trong cuốn hướng dẫn tham khảo langauge nếu có thể
• số tiền ít nhất của uốn để đáp ứng những hạn chế của máy phát điện phân tích cú pháp của bạn

Đó cuối cùng có thể làm cho một mớ hỗn độn của sự đơn giản về khái niệm của bạn, và biểu đồ của bạn về các kiểu phân tích cú pháp khác nhau hiển thị số lượng các vấn đề khác nhau mà bạn phải đối mặt tùy thuộc vào lựa chọn của bạn-của-máy phát điện. Điều này càng trầm trọng hơn bởi thực tế là sự lựa chọn thường được thực hiện tốt trước khi bạn thực sự chọn ngữ pháp.

Một cách để giảm tối đa ngữ pháp là chọn trình tạo trình phân tích cú pháp xử lý ngữ pháp hoàn toàn không có ngữ cảnh. GLR parsing có lợi thế rất quan trọng này. Tôi đã sử dụng nó trong 15 năm và đã thực hiện hàng chục langauges thực sự với nó.