ändern DCG determinis

Question

zu sein, wie man diese gramma ändern

e --> []. 
e --> "*". 
e --> s_e. 
e --> e, s_e. 
s_e --> ("a",e);("b",e). 

Ich weiß nur nicht deterministisch zu sein, wo Schnitt setzen Rückzieher zu vermeiden.

Answer 1

Sie können die letzte Regel wie folgt umschreiben:

s_e --> "a", e. 
s_e --> "b", e. 

Jetzt ist es wahrscheinlich die folgenden Schnitte zu setzen macht Sinn:

s_e --> "a", !, e. 
s_e --> "b", !, e. 

Sie können auch die Schnitte in der Original-Compact Form platzieren mit (;)/2, aber ich finde das Obige transparenter. Das obige ist gültig, wenn s_e nicht mehrfach mal mit der gleichen Eingabeliste aufgerufen wird.

Aber Ihre Grammatik hat einen Fehler, e ist links rekursiv, und s_e wird mehrmals mit der gleichen Eingangsliste aufgerufen werden. Bedeutet Ihre Grammatik wird zum Beispiel Schleife für negative Sätze, d. H. Es wird nicht , sie abzulehnen, und Ihre Grammatik wird nach Redo für eine positive Sätze, das heißt, wenn die Eingabe akzeptiert wurde.

Also müssen Sie zusätzlich die linke Rekursion zu beseitigen, da normale Prolog Tiefe Faust Suche kann nicht damit umgehen. Am einfachsten ist es, es durch richtige Rekursion mit einem neuen Nicht-Terminal zu ersetzen. Nämlich Sie können die Produktionen für e wie folgt schreiben:

e --> s_e, rest_e. 
e --> "*", rest_e. 
e --> []. 

rest_e --> s_e, rest_e. 
rest_e --> "*", rest_e. 
rest_e --> []. 

Und wir können Schnitte setzen auch:

e --> s_e, !, rest_e. 
e --> "*", !, rest_e. 
e --> []. 

rest_e --> s_e, !, rest_e. 
rest_e --> "*", !, rest_e. 
rest_e --> []. 

Auch die obige Grammatik leicht in das Gefühl, dass mehrere leere E-Produktionen geändert wird nicht mehr gehen Sie selbst über s_e in e. Es ist auch mehr gierig, in dem sub e Produktionen sind immer voll geparst. So zum Beispiel der Satz:

aaa 

Wird nur analysiert als:

a(a(a)) 

Und nicht wie:

a(a)a 

Oder:

aa(a) 

Oder:

aaa 

Aber sonst sollte es die gleichen Sätze akzeptieren, als ob die DCG würde Boden ausgeführt werden und würde nicht Probleme mit dem linken Rekursion.

Mit freundlichen Grüßen