2011-06-16 12 views
13

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.Đ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ó?

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.

Parsers/Grammars Hierarchy

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!

Trả lời

8

"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ó.

+0

thx. Vì vậy, bằng cách sử dụng GLR, nó sẽ có thể phân tích bất kỳ CFG, với một ngữ pháp đơn giản như nó có thể được, cho một cây phân tích đơn giản tương tự. Sau đó phát sinh một câu hỏi: GLR = LR (*)? Hơn nữa, bằng cách sử dụng trình phân tích cú pháp GLR, bạn sẽ không cần ngữ pháp của mình để giảm lượng uốn, phải không? – dader

+1

Về mặt kỹ thuật có. Có những CFG khiến GLR có hành vi theo cấp số nhân và do đó bạn vẫn phải bẻ cong một số. Như một quy luật chung, hành vi này là khá hiếm. Bạn sẽ thấy khi bạn xây dựng các trình phân tích cú pháp đôi khi bạn muốn thêm các ràng buộc ngữ nghĩa bên ngoài những gì CFG có thể làm (xem xét kết hợp nhiều đầu lặp Fortran DO với cùng câu lệnh CONTINUE bằng cách khớp số dòng), và bạn vẫn phải uốn cong ngữ pháp một số. Nhưng cuối cùng, bạn bẻ cong ngữ pháp một LOT ít hơn với GLR. Có, GLR có "vô hạn lookahead", nó có thể làm bất cứ điều gì LR (*) có thể làm. –

+0

ok cho GLR làm bất cứ điều gì LR (*) có thể làm, nhưng tôi có nghĩa là ngược lại, không LR (*) xử lý toàn bộ các CFG như GLR không? Tôi hỏi vì câu trả lời sẽ tạo ra một trong những điểm 2: liệu tập hợp các ký tự LR (*) có bằng (bao gồm và được bao gồm bởi) tập hợp của tất cả các CFG không? – dader