डीसीजी में बाएं रिकर्सन को हटा रहा है - प्रोलॉग

Question

मुझे इस व्याकरण में बाएं रिकर्सन के साथ एक छोटी सी समस्या है। मैं प्रोलॉग में इसे लिखने की कोशिश कर रहा हूं, लेकिन मुझे नहीं पता कि बाएं रिकर्सन को कैसे हटाया जाए।

<expression> -> <simple_expression> 
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression> 
<simple_expression> -> <function> 
<function> -> <function> <atom> 
<function> -> <atom> 
<atom> -> <number> | <variable> 

<binary_operator> -> + | - | * |/

expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }. 
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }. 
simple_expression(SExpr) --> function(Func), { SExpr = Func }. 
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }. 
function(Func) --> atom(At), { Func = At }. 

मैंने ऐसा कुछ लिखा है, लेकिन यह बिल्कुल काम नहीं करेगा। इस कार्यक्रम को काम करने के लिए इसे कैसे बदला जाए?

Answer 1

आपके प्रोग्राम के साथ समस्या वास्तव में रिकर्सन छोड़ दी गई है; यह हटा दिया जाना चाहिए अन्यथा आप अनंत लूप में अटक जाएगा

तत्काल छोड़ दिया प्रत्यावर्तन को निकालने के लिए आप के साथ फार्म के प्रत्येक नियम

A->A a1|A a2|....|b1|b2|....

बदल देते हैं:

A -> b1 A'|b2 A'|.... 
A' -> ε | a1 A'| a2 A'|.... 

तो समारोह

function -> atom, functionR. 
funtionR -> []. 

wiki page

Answer 2

@ थानोसक्यूआर का उत्तर काफी अच्छा है, लेकिन डीसीजी की तुलना में अधिक सामान्य संदर्भ पर लागू होता है, और पार्स ट्री में बदलाव की आवश्यकता होती है। प्रभावी रूप से, पार्सिंग का 'परिणाम' हटा दिया गया है, यह अच्छा नहीं है।

यदि आप अभिव्यक्ति पर पार्सिंग में रुचि रखते हैं, तो मैंने here कुछ उपयोगी पोस्ट किया है।

Answer 3

समस्या तब उत्पन्न होती है जब आप पिछड़े चेनिंग का उपयोग कर रहे हैं। आगे की श्रृंखला में सीधे बाएं रिकर्सिव व्याकरण नियमों से निपटना संभव है। फॉर्म के व्याकरण नियम प्रदान किए गए:

NT ==> NT' 

एक चक्र न बनाएं। आप सहायक कंप्यूटेशंस का उपयोग भी कर सकते हैं, यानी {}/1, यदि आप उन्हें शरीर के गैर-टर्मिनलों के बाद रखते हैं और यदि सिर में गैर-टर्मिनलों में विशेष रूप से सहायक गणनाओं में पैरामीटर नहीं होते हैं। यानी नीचे की स्थिति।

:- use_module(library(minimal/chart)). 
:- use_module(library(experiment/ref)). 

:- static 'D'/3. 

expr(C) ==> expr(A), [+], term(B), {C is A+B}. 
expr(C) ==> expr(A), [-], term(B), {C is A-B}. 
expr(A) ==> term(A). 

term(C) ==> term(A), [*], factor(B), {C is A*B}. 
term(C) ==> term(A), [/], factor(B), {C is A/B}. 
term(A) ==> factor(A). 

factor(A) ==> [A], {integer(A)}. 

यहाँ चार्ट पार्सर के स्रोत कोड के लिए एक link है:

यहाँ एक उदाहरण छोड़ दिया पुनरावर्ती व्याकरण कि पूरी तरह से आगे श्रृंखलन में इस तरह से काम करता है। इस लिंक से आगे के चेनर का स्रोत कोड भी पाया जा सकता है। निम्नलिखित एक उदाहरण सत्र में दिखाया गया है:

?- use_module(library(minimal/hypo)). 

?- chart([1,+,2,*,3], N) => chart(expr(X), N). 
X = 7 

दौरान चार्ट पार्सर पार्स करने के लिए एक नीचे से ऊपर फैशन में एक चार्ट भर जाएगा। उपरोक्त प्रस्तुतियों में प्रत्येक गैर-टर्मिनल पी/एन के लिए तथ्यों पी/एन + 2 होंगे। उपर्युक्त उदाहरण के लिए चार्ट का नतीजा यहां दिया गया है:

:- thread_local factor/3. 
factor(3, 4, 5). 
factor(2, 2, 3). 
factor(1, 0, 1). 

:- thread_local term/3. 
term(3, 4, 5). 
term(2, 2, 3). 
term(6, 2, 5). 
term(1, 0, 1). 

:- thread_local expr/3. 
expr(3, 4, 5). 
expr(2, 2, 3). 
expr(6, 2, 5). 
expr(1, 0, 1). 
expr(3, 0, 3). 
expr(7, 0, 5). 

Answer 4

कई प्रोलॉग सिस्टम टैबलिंग प्रदान करते हैं। टैबलिंग समाप्ति को कई स्थितियों में बाएं रिकर्सिव व्याकरण तक भी बढ़ाया जा सकता है। यहाँ एक समाधान है कि नए SWI-Prolog पेश सुविधा का उपयोग करता है:

:- use_module(library(tabling)). 
:- table expr/3. 
:- table term/3. 
:- table factor/3. 

expr(C) --> expr(A), [+], term(B), {C is A+B}. 
expr(C) --> expr(A), [-], term(B), {C is A-B}. 
expr(A) --> term(A). 

term(C) --> term(A), [*], factor(B), {C is A*B}. 
term(C) --> term(A), [/], factor(B), {C is A/B}. 
term(A) --> factor(A). 

factor(A) --> [A], {integer(A)}. 

इस feature के बाद से अपेक्षाकृत SWI-Prolog में नया है, इसलिए इस समय जब आप डिबग मोड पर स्विच के लिए केवल काम करता है:

?- debug. 

?- phrase(expr(X), [1,+,2,*,3], []). 
X = 7