Grammatik mit geschweiften Klammern

Question

Ich versuche, DCG-Grammatik in Prolog und erfolgreich bis zu einem Punkt zu lösen, ich bin bei der Bewertung der Ausdrücke mit Klammern wie diese stecken. expr( T, [’(’, 5, +, 4, ’)’, *, 7], []),

expr(Z) --> num(Z).
expr(Z) --> num(X), [+], expr(Y), {Z is X+Y}.
expr(Z) --> num(X), [-], expr(Y), {Z is X-Y}.
expr(Z) --> num(X), [*], expr(Y), {Z is X*Y}.
num(D) --> [D], {number(D)}.

eval(L, V, []) :- expr(V, L, []).

Answer 1

Die von Prologs DCG-Grammatiken implementierten Parser sind rekursiv-absteigende LL( etwas ) (prädiktive) Grammatiken. Sie geht die Eingabe von links nach rechts durch und erzeugt dabei eine Ableitung ganz links. Sie sind einfach zu erstellen, aber die Grammatik muss einigen Einschränkungen genügen:

Sie können nicht linksrekursiv sein. Eine unendliche Rekursion kann/wird die Folge sein. Dies bedeutet, dass mindestens ein Symbol (Token) aus dem Eingabestrom entfernt werden muss, bevor ein rekursiver Pfad verfolgt werden kann. Die Umstrukturierung von Grammatiken zur Beseitigung von Linksrekursionen ist eine recht mechanische, wenn auch mühsame Übung. Wie man das macht, steht in jedem anständigen Compiler-Buch.

Der Vorrang von Operatoren ist normalerweise in die Struktur der Grammatik selbst eingebaut. Die folgende BNF-Notation zeigt eine Möglichkeit, eine rekursive Deszendenzgrammatik für das Parsen/Auswerten einfacher arithmetischer Ausdrücke zu definieren:

ArithmeticExpression     : AdditiveExpression
                         ;

AdditiveExpression       : MultiplicativeExpression
                         | MultiplicativeExpression '+' AdditiveExpression
                         | MultiplicativeExpression '-' AdditiveExpression
                         ;

MultiplicativeExpression : ExponentialExpression
                         | ExponentialExpression '*' MultiplicativeExpression
                         | ExponentialExpression '/' MultiplicativeExpression
                         | ExponentialExpression '%' MultiplicativeExpression
                         ;

ExponentialExpression    : UnaryExpression
                         | UnaryExpression '^' ExponentialExpression
                         ;

UnaryExpression          : '-' UnaryExpression
                         | AtomicExpression
                         ;

AtomicExpression         : '(' ArithmeticExpression ')'
                         | ['0'..'9']+
                         ;

Der Begriff auf jeder Stufe der Operatorpriorität wird aus Ausdrücken der nächsthöheren Prioritätsstufe gebildet. Ein beliebiger arithmetischer Ausdruck ist also nur ein einziger additiver Ausdruck.

Jeder additive Ausdruck besteht aus einem oder mehreren multiplikativen Ausdrücken, die durch Additions- und Subtraktionsoperatoren verbunden sind.

Jeder multiplikative Ausdruck besteht aus einem oder mehreren exponentiellen Ausdrücken, die durch Multiplikations-, Divisions- und Restoperatoren verbunden sind.

Jeder Exponentialausdruck ist ein unärer Ausdruck mit einem optionalen Exponentenoperator, gefolgt von einem weiteren unären Ausdruck.

Jeder unäre Ausdruck ist entweder ein atomarer Ausdruck oder ein unäres Minus gefolgt von einem anderen unären Ausdruck.

Jeder atomare Ausdruck ist entweder ein beliebiger arithmetischer Ausdruck, der in Klammern eingeschlossen ist, oder ein Integer-Token ohne Vorzeichen.

Die Übersetzung der obigen Ausführungen in die DCG-Syntax von Prolog sollte trivial sein. Wie man den Begriff, der durch jede Klausel in der Grammatik repräsentiert wird, auswertet, sollte selbsterklärend sein.

Answer 2

Dies ist eines der seltsamsten Dinge, die ich in der Geschichte von Prolog beobachtet habe. Nämlich, dass eine falsche Ausdruckssyntax schon seit Ewigkeiten herumgezeigt wird. Die falsche Syntax findet sich bereits in der DEC10 Prolog Dokumentation und die Fehlanpassung wird sichtbar, wenn wir uns eine Regel ansehen:

 expr(Z) --> num(X), "/", expr(Y), {Z is X/Y}.
 etc..

Dadurch wird der Divisionsoperator xfy, sollte aber yfx lauten. So wird mit der obigen Regel wird ein Ausdruck 10/2/5 als 10/(2/5) gelesen und führt zu 25 als Ergebnis. Tatsächlich sollte das Beispiel aber als (10/2)/5 gelesen werden was zu 1 als Ergebnis führt.

Das Problem ist, dass die korrekte Syntax rekursiv wäre. Und DCG hat Probleme mit linksrekursiven Regeln. Der Prolog Interpreter würde bei einer linksrekursiven Regel einfach in eine Endlosschleife laufen rekursiven Regeln durch wiederholten Aufruf von expr/3 in eine Endlosschleife geraten:

 expr(Z) --> expr(X), "/", num(Y), {Z is X/Y}
 etc..

Die Lösung besteht also darin, die linke Rekursion zu eliminieren, indem man einen Akkumulator und zusätzliche Regeln. Ich weiß nicht, ob diese Methode im Allgemeinen funktioniert, aber im vorliegenden Fall funktioniert sie sicher. Die korrekte und in der Tiefe erste ausführbare Regel würde also lauten:

 expr(Y) --> num(X), expr_rest(X,Y).

 expr_rest(X,T) --> "/", !, num(Y), {Z is X/Y}, expr_rest(Z,T).
 etc..
 expr_rest(X,X).

Die obige Grammatik ist eine etwas anspruchsvollere DCG. Sie ist nicht mehr reines Prolog, da sie den Schnitt (!) verwendet. Aber wir könnten den Schnitt eliminieren, zum Beispiel durch einen Push-Back, etwas in den folgenden Zeilen. Der Push-Back ist wiederum eine komplizierte komplizierte Angelegenheit, die in einer DCG-Einführung erklärt werden müsste, und wir müssten ein Stoppzeichen am Ende eines Ausdrucks einfügen, damit damit es funktioniert:

 etc..
 expr_rest(X,X), [C] --> [C], {not_operator(C)}.

Wir könnten auch nicht auf die Länge des Schnitts oder den Push-back eingehen. eingeben und damit leben, dass der Parser beim Backtracking zusätzliche Aufgaben übernimmt, in diesem Fall unnötige, Arbeit macht. Das Fazit lautet also wahrscheinlich, obwohl das Beispiel nicht korrekt ist, ist es einfach genug, um DCG zu erklären zu erklären, ohne dass man zu viel fortgeschrittenes Wissen über DCG braucht.

Interessanterweise wird die fehlende Klammersyntax kaum beeinträchtigt durch die Abschaffung der linken Rekursion. Fügen Sie einfach hinzu:

 num(X) --> "(", !, expr(X), ")".

Ups, schon wieder ein Schnitt!

Mit freundlichen Grüßen

Der vollständige Code kann hier eingesehen werden: http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/06_bench/09_programs/10_calculator/01_calculator.p.html

P.S.: Anstatt die linke Rekursion zu eliminieren, könnten wir auch mit einer Form der Tabellierung arbeiten können.

Answer 3

Es funktioniert einfach. Allerdings ist es nicht einfacher als Yacc/Bison.

%?-eval('11*(7+5-2)^2*(11+8)').
eval(A) :- lex(A,L), evallist(L).

%?-evallist([11,*,'(',7,+,5,-,2,')',^,2,*,'(',11,+,8,')']).
evallist(L) :- e(R,L,[]),write(R),!.

e(N) --> t(N1), erest(N1,N).

erest(N1,N) --> [+], !, t(N2), {N3 is N1+N2}, erest(N3,N);
                [-], !, t(N2), {N3 is N1-N2}, erest(N3,N).
erest(N,N) --> [].

t(N) --> f(N1), trest(N1,N).

trest(N1,N) --> [*], !, f(N2), {N3 is N1*N2}, trest(N3,N);
                [/], !, f(N2), {N3 is N1/N2}, trest(N3,N).
trest(N,N) --> [].

f(N) --> n(N);
     n(N1), [^], f(N2), {N is N1**N2}.

n(N) --> ['('], !, e(N), [')'];
     [-], !, e(N1), {N is -N1};
     num(N). 

num(N) --> [N], {number(N)}.

lex(A,NL) :- 
  atom_chars(A,L), lex0(_,L,NL).

lex0(S,L,NL) :-
  L=[], (number(S), NL=[S], !; NL=[]), !;
  L=[E|R], (d(E,N), (number(S), !; S=0), S1 is S*10+N, lex0(S1, R, NL), !;
     lex0(_,R,NR), (number(S), NL=[S|[E|NR]], !;
        NL=[E|NR])).

d(I,N) :- 
  char_code(I,C), C > 47, C < 58, N is C - 48.

Answer 4

Das Hinzufügen dieser Klausel scheint zu funktionieren: num(D) --> ['('], expr(D), [')'].

Answer 5

Dank @vladimir lidovski und basierend auf der BNF-Notation (und auf meinen Bedürfnissen) habe ich sie erweitert, um auch logische Ausdrücke einzubeziehen. Hier ist mein Code (Um den vollständigen Interpreter zu sehen, besuchen Sie meine Trottelpaket ):

cond_expre(T) -->  and_expre(E1), or_rest(E1,T).     

or_rest(E1,T) -->  [punct('|'),punct('|')],!, and_expre(E2),   {V  = (\/,E1,E2)}, or_rest(V,T).
or_rest(T,T) --> [].

and_expre(T) --> equality_expre(E1), and_rest(E1,T).
and_rest(E1,T) --> [punct(&),punct(&)], !, equality_expre(E2), {V  = (/\,E1,E2)}, and_rest(V,T).
and_rest(T,T) --> [].

equality_expre(T) -->   relat_expre(E1), equality_rest(E1,T).   
equality_rest(E1,T) --> equality_op(Op) ,!,  relat_expre(E2), {  V=(Op,E1,E2)}, equality_rest(V,T).
equality_rest(T,T) --> [].

relat_expre(T) --> atomic_texpre(E1), relat_rest(E1,T). 
relat_rest(E1,T) -->  relat_op(Op) ,!, atomic_texpre(E2) , { V=(Op,E1,E2) },relat_rest(V,T).
relat_rest(T,T) --> [].

atomic_texpre(T) -->  arith_expre(T); [punct('(')], !, cond_expre(T), [punct(')')]      .
arith_expre(V) --> expre(V).

equality_op(==)         --> [punct(=),punct(=)]. 
equality_op(\=)        --> [punct(!),punct(=)]. 
relat_op(>=)        --> [punct(>),punct(=)]. 
relat_op(>)         --> [punct(>)]. 
relat_op('=<')        -->  [punct(<),punct(=)]. 
relat_op(<)         --> [punct(<)]. 

expre(N) --> multiplicative(N1), additive_rest(N1,N).

additive_rest(N1,N) --> [punct('+')], !, multiplicative(N2), {N3 = (+,N1,N2)}, additive_rest(N3,N);  
                        [punct('-')], !, multiplicative(N2), {N3 = (-,N1,N2)}, additive_rest(N3,N).
additive_rest(N,N) --> [].

multiplicative(N) --> atomic(N1), multiplicative_rest(N1,N).
multiplicative_rest(N1,N) --> [punct('*')], !, atomic(N2), {N3 = (*,N1,N2)}, multiplicative_rest(N3,N);
                                [punct('/')], !, atomic(N2), {N3 = (/,N1,N2)}, multiplicative_rest(N3,N);   
                                [punct('%')], !, atomic(N2), {N3 = (mod,N1,N2)}, multiplicative_rest(N3,N).
multiplicative_rest(N,N) --> [].

atomic(N) --> [punct('(')], !, expre(N), [punct(')')];  num(N). 
num(N) --> pl_constant(N).

pl_constant(num(N))     --> pl_integer(N), !.
pl_constant(id(X))       --> identifier(X), {call(id(X,_)) }. %Not sure if I remember what it does but I think, the right most call I wrote to assure that the variable is already registered in the cache so that a value can later be retrieved from it  

pl_integer(X)              --> [number(X)]. %the value on the right works together with a tokenizer library ->  :- use_module(library(tokenize)). It's basically a token labled as a number. Same with the next line.
identifier(X)              --> [word(X)].