Tính năng backtracking hoạt động như thế nào trong peg.js (ví dụ)?

Question

Tôi đã xác định tối thiểu Peg.js ngữ pháp sau:

start = "A1"/"A123" 

mà bạn có thể thử in the sandbox.

Tôi đã dự kiến ​​sẽ khớp "A1" cũng như "A123" (theo ý niệm của tôi về cách hoạt động của backtracking). Nhưng đây không phải là trường hợp: ngữ pháp nhận ra "A1" nhưng không phải là "A123".

Lưu ý: Tôi không tìm kiếm lời khuyên "đảo ngược thứ tự các điều khoản của bạn" như trong câu hỏi có liên quan How to transform a simple grammar into something which works in PEG.js (expected "a" but "a" found). Thay vào đó, tôi đang tìm hiểu hành vi mà tôi thấy và lý do tại sao trường hợp này không thể áp dụng tính năng backtracking của Peg.js. Để giải thích lý do tại sao việc đảo ngược thứ tự các điều khoản của tôi không hiệu quả, hãy xem ví dụ thực tế hơn bên dưới.

---

Để biết ví dụ thực tế hơn, hãy xem xét phân tích đơn vị. Ngữ pháp nên nhận biết các đơn vị số liệu (như "m", "mol") với các tiền tố tùy chọn, như "mm", "mmol", cũng như các đơn vị không phải số liệu như "yr", "week" hoặc "mo".

Ngữ pháp Peg.js sau đây sẽ không nhận ra "mol" vì nó bị vấp phải "mo" và không quay lại. (Thay đổi thứ tự từ ngữ không giúp; hay đúng hơn, sẽ gây ra "mo" để được công nhận tại các chi phí của "mol" hoặc "mmol".)

start = nonmetric/metric/prefix metric 
metric = "mol"/"l"/"m"/"g" 
nonmetric = "yr"/"mo"/"week"/"day"/"hour" 
prefix = "m"/"k"/"c" 

tôi có thể làm điều analagous trong ANTLR với thành công tốt đẹp:

grammar units; 
start : nonmetric | metric | prefix metric; 
metric : 'mol' | 'l' | 'm' | 'g'; 
nonmetric : 'yr' | 'mo' | 'week' | 'day' | 'hour'; 
prefix : 'm' | 'k' | 'c'; 

Answer 1

Vấn đề là với khái niệm backtracking. Trình phân tích cú pháp PEG không quay lại giống như các trình phân tích cú pháp gốc đệ quy khác hoặc Prolog. Thay vào đó, khi đối mặt với một sự lựa chọn, một trình phân tích cú pháp PEG sẽ thử mọi tùy chọn cho đến khi một thành công. Khi một thành công, nó sẽ cam kết nó bất kể quy tắc được gọi như thế nào.

Từ Wikipedia article:

Không giống như trong văn phạm tiếng bối cảnh tự do và biểu thức thông thường, tuy nhiên, các nhà khai thác luôn cư xử cách thèm khát, tiêu thụ càng nhiều đầu vào như có thể và không bao giờ thụt lùi.

Những gì bạn yêu cầu trong trường hợp phức tạp giống như được yêu cầu trong this question. Câu trả lời cho đến nay là Có: bạn phải tinh chỉnh các quy tắc trong ngữ pháp PEG để đảm bảo rằng tùy chọn dài nhất luôn được đối sánh trước, ngay cả khi kết quả là ngữ pháp hơi xấu xí.

Một cách để tinh chỉnh văn phạm tiếng PEG là sử dụng lookaheads (đó là một trong những lý do chính tại sao lookaheads được đặc trưng trong PEG):

start = nonmetric/metric/prefix metric 
metric = "mol"/"l"/!"mo" "m"/"g" 
nonmetric = "yr"/!"mol" "mo"/"week"/"day"/"hour" 
prefix = !("mol"/"mo") "m"/"k"/"c" 

Answer 2

này là do thiết kế. Bạn có thể chỉ định đúng đơn đặt hàng hoặc các quy tắc sẽ được sử dụng để đối sánh.

Các trích dẫn từ bản gốc white paper:

Những công cụ này không làm cho thiết kế cú pháp ngôn ngữ dễ dàng, tất nhiên. Tại nơi cần phải xác định xem hai lựa chọn thay thế có thể có trong một CFG không rõ ràng, PEG trình bày các nhà thiết kế ngôn ngữ với sự thách thức tương tự như để xác định xem hai lựa chọn thay thế trong biểu thức ‘/’ có thể được sắp xếp lại hay không mà không ảnh hưởng đến ngôn ngữ. Câu hỏi này là thường xuyên hiển nhiên, nhưng đôi khi không phải là, và không thể phân tích nói chung. Tuy nhiên, với việc phát hiện sự mơ hồ trong CFG, chúng tôi hy vọng tìm các thuật toán tự động để xác định độ nhạy thứ tự hoặc độ nhạy cảm trong các tình huống thông thường.

Trong trường hợp đơn giản này, PEG.js có thể thông minh hơn một chút và nhận ra rằng các quy tắc bạn chỉ định không rõ ràng. Có thể có giá trị cho ask tác giả.