Tôi tự hỏi nếu ANTLR v3, trình bày thuật toán phân tích cú pháp nội bộ của nó là "LL (*)" là đại diện đầy đủ của các trình phân tích ngữ pháp PEG (phân tích ngữ pháp phân tích ngữ pháp).LL (*) so với các trình phân tích cú pháp PEG: sự khác biệt là gì?
Có sự khác biệt nào không?
ANTLR article sai về PEG.
LL (*) là một tập hợp con của DCFG (Ngữ pháp ngữ pháp xác định miễn phí), là một tập hợp con của CFG (Ngữ cảnh miễn phí ngữ cảnh).
PEG thể diễn tả bối cảnh văn phạm tiếng nhạy cảm như A{n}B{n}C{n}, trong đó A và B và C tất cả xảy ra n lần. Dưới đây là định nghĩa:
s := &(x C) A+ y/ε
x := A x B/A B
y := B y C/B C
Nhưng không có cách nào để xác định ngữ pháp như vậy trong CFG (bằng chứng liên quan đến bơm bổ đề). Vì vậy, PEG không phải là tập hợp con CFG. Liệu PEG có thay thế CFG không? Tôi không biết.
Hai khác biệt chính giữa LL (*) và PEG:
LL (*) chỉ có thể lookahead một mô hình DFA, trong khi PEG có thể lookahead một mẫu đệ quy. Ví dụ, trong PEG bạn có thể tra cứu các parens lồng nhau trong khi LL (*) không thể.
Toán tử lựa chọn / trong PEG là lựa chọn ưu tiên (hoặc "sở hữu"), có nghĩa là nếu bạn có quy tắc A/AB, nó sẽ không bao giờ đến bên tay phải AB. Trong LL (*) cho một quy tắc A | AB, có thể khớp với AB.
Nếu bạn có một ngữ pháp PEG không có dấu nhìn hoặc mẫu lookahead của bạn có thể được giảm thành DFA, thì nó có thể được dịch sang LL (*). Nếu không, nó là không thể.
Theo các công cụ được liệt kê here ANTLR là một đại diện đầy đủ của một phân tích cú pháp PEG:
ANTLR, một máy phát điện phân tích cú pháp cũng như thành lập bởi Terence Parr, hỗ trợ tính năng PEG rộng và kết hợp sưu tập điện phân tích với các kỹ thuật phân tích cú pháp LL .
Có tồn tại một số phần mở rộng đệ quy bên trái đệ quy, được, rõ ràng, không được hỗ trợ bởi ANTLR. –
Trong ANTLR, bạn có thể bật backtracking toàn cầu trên tất cả các quy tắc sản xuất trong ngữ pháp của mình, để cho k >= 1 bạn có thể phân tích khá giống với PEG. Tất nhiên, vì tất cả các backtracking tiềm năng, thời gian chạy của phân tích cú pháp xuống cấp. Với chi phí của bộ nhớ (một số) bạn cũng có thể cho phép ghi nhớ, làm cho nó hoạt động giống như một trình phân tích cú pháp Packrat, có thể phân tích đầu vào theo thời gian tuyến tính.
Vì vậy, không, không có nhiều sự khác biệt với ANTLR và PEG/Packrat (với các tùy chọn phù hợp được bật!).
ANTLR và PEG không giống nhau. Đó là câu hỏi lý thuyết, và tôi nghĩ nó sẽ là tốt nhất để bạn tham khảo this paper được viết bởi Terrence Parr, nơi anh ta chỉ ra điểm khác biệt giữa ANTLR và PEG và một số ưu điểm của chiến lược phân tích cú pháp LL (*). Tôi không muốn cho bản thân mình tự do diễn giải những gì anh ấy viết ở đó, nhưng tốt hơn hết là bạn nên đọc toàn bộ bài báo.
404-ed. Bạn có thể cung cấp liên kết được cập nhật không? – chakrit
Ngữ pháp PEG của bạn chưa đúng. Nó cũng sẽ phân tích cú pháp A {n} B {n + 1} C {n + 1}. – CoronA
@CoronA Cảm ơn bạn đã chỉ ra, tôi đã chỉnh sửa câu trả lời bằng ngữ pháp được cập nhật để đảm bảo rằng C xảy ra ngay sau A {n} B {n}. – luikore