peg.js (उदाहरण के साथ) में बैकट्रैकिंग कैसे काम करता है?

Question

मैं निम्नलिखित न्यूनतम Peg.js व्याकरण परिभाषित किया है:

start = "A1"/"A123" 

जो आप in the sandbox कोशिश कर सकते हैं।

मैं "ए 1" के साथ-साथ "ए 123" (मेरे बैकट्रैकिंग कार्यों के बारे में मेरी धारणा के अनुसार) से मिलान करने की अपेक्षा करता। लेकिन यह मामला नहीं है: व्याकरण "ए 1" पहचानता है लेकिन "ए 123" नहीं।

नोट: मैं संबंधित प्रश्न How to transform a simple grammar into something which works in PEG.js (expected "a" but "a" found) में "आपकी शर्तों के क्रम को उलट देता हूं" सलाह की तलाश नहीं कर रहा हूं। इसके बजाय, मैं जो व्यवहार देख रहा हूं उसे समझने के लिए देख रहा हूं, और इस मामले में पेग.जेएस का बैकट्रैकिंग क्यों लागू नहीं होता है। मेरी शर्तों के क्रम को उलटाने की व्याख्या के लिए, नीचे यथार्थवादी उदाहरण देखें, इसकी व्याख्या करने के लिए।

---

एक और यथार्थवादी उदाहरण के लिए, इकाइयों को पार्सिंग पर विचार करें। एक व्याकरण को मीट्रिक इकाइयों (जैसे "एम", "एमओएल") को वैकल्पिक उपसर्गों जैसे "मिमी", "एमएमओएल" के साथ-साथ "yr", "week", या "mo" जैसी गैर-मीट्रिक इकाइयों के साथ पहचानना चाहिए।

निम्नलिखित Peg.js व्याकरण "mol" को पहचान नहीं पाएगा क्योंकि यह "mo" खपत हो जाता है, और बैकट्रैक नहीं करता है।

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

मैं ANTLR में analagous बात कर सकते हैं; ("मो" या बल्कि, होगा कारण "मोल" या "mmol" की कीमत पर मान्यता प्राप्त होना बदलने शब्दों के क्रम में मदद नहीं करता।) अच्छा सफलता के साथ:

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

Answer 1

समस्या की अवधारणा उलटे पांव लौटने के साथ है। पीईजी पार्सर्स अन्य रिकर्सिव-डेसेंट पार्सर्स या Prolog की तरह बैकट्रैक नहीं करते हैं। इसके बजाय, जब किसी विकल्प के साथ सामना किया जाता है, तो एक पीईजी पार्सर प्रत्येक विकल्प को तब तक प्रयास करेगा जब तक कि कोई सफल न हो जाए। एक बार सफल होने के बाद, इससे कोई फर्क नहीं पड़ता कि नियम कैसे लागू किया गया था।

Wikipedia article से:

विषय से मुक्त व्याकरण और नियमित अभिव्यक्ति में विपरीत, तथापि, इन ऑपरेटरों हमेशा लालच से व्यवहार करते हैं, संभव है और कभी नहीं उलटे पांव लौटने से जितना इनपुट लेने वाली।

जटिल मामले में आप जो पूछते हैं वह वही है जो this question में पूछा गया है। अब तक का जवाब हां: आपको यह सुनिश्चित करने के लिए पीईजी व्याकरण में नियमों को ट्विक करना होगा कि सबसे लंबा विकल्प हमेशा पहले मिलान हो जाता है, भले ही नतीजा कुछ हद तक व्याकरण हो।

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

इस डिजाइन के द्वारा होता है:

एक तरह से पेग व्याकरण बदलाव करने lookaheads (कि मुख्य कारण lookaheads पेग में दिखाया जा रहा से एक है) का प्रयोग है। यह सही है कि आप सही ऑर्डर या नियमों का उपयोग करने के लिए उपयोग किए जाएंगे।

मूल white paper से बोली:

इन उपकरणों भाषा वाक्यविन्यास डिजाइन, आसान निश्चित रूप से नहीं बनाते हैं। में यह निर्धारित करने की जगह है कि सीएफजी में दो संभावित विकल्प संदिग्ध हैं, पीईजी समान भाषा भाषा डिजाइनरों को यह निर्धारित करने की चुनौती है कि '/' अभिव्यक्ति में दो विकल्प भाषा को प्रभावित किए बिना फिर से व्यवस्थित किया जा सकता है। यह प्रश्न अक्सर स्पष्ट है, लेकिन कभी-कभी नहीं होता है, और सामान्य रूप से अनिश्चित है। सीएफजी में अस्पष्टता की खोज के साथ, हमारे पास की आशा है कि ऑर्डर संवेदनशीलता या सामान्य परिस्थितियों में रूढ़िवादी रूप से असंवेदनशीलता की पहचान करने के लिए स्वत: एल्गोरिदम ढूंढें।

इस साधारण मामले में PEG.js थोड़ा अधिक स्मार्ट हो सकता है और यह पहचान सकता है कि आपके द्वारा निर्दिष्ट नियम अस्पष्ट हैं। शायद ask लेखक के लायक है।