Definite Clause Grammar Expansion

Jan Burse, erstellt 19. Okt 2011 Mögen wir nicht alle Süssigkeiten? Unser vorausgehender Tagebucheintrag zum Thema Zielexpansion hat schon gezeigt wie man diese zur Inline-Ersetzung von Code verwenden kann. Dieser Tagebucheintrag soll zeigen wie wir Zielexpansion zur Versüssung unseres Lebens einsetzen können indem wir die Sprache von normalem Prolog erweitern. Wir werden zeigen wie definite Klausel-Grammatiken (DCGs) mittels der Zielexpansion realisiert werden können. Die neueren Versionen von Jekejeke Prolog kompilieren DCG Grammatiken zu normalem Prolog. Wir werden einen vollständigen Abriss einer Vanilleversion dieser Kompilation geben. DGCs sind eine Erweiterung der kontextfreien Grammatiken. DCGs erlauben die Erstellung von beliebigen Baumstrukturen während dem Parsen und sie erlauben zusätzliche Bedingungen in der Form von Zusatzberechnungen. Während dem Einlesen werden DCG Regeln an Hand des Hauptfunktors (-->)/2 erkannt und dann expandiert. Für unsere Vanilleversion der DCGs werden wir stattdessen den Hauptfunktor (==>)/2 verwenden sodass das Experiment in irgendeinem Prologsystem durchgeführt werden kann. Unsere Vanille DCG wird nur Terminale, Nicht-Terminale und Konjunktionen zur Verfügung stellen. Push-Backs, Aktionen und Kontrollstrukturen befinden sich ausserhalb dem Umfang der Vanille DCG. Uns wird das Beispiel der Akzeptanz von Palindromen begleiten: palin ==> []. palin ==> [_]. palin ==> [Border], palin, [Border]. Das einzige Nicht-Terminal in der obigen Grammatik ist das Grammatikprädikat “palin”. Wir finden weiter eine leere Terminalliste ([]) in der ersten Regel, sowie einzelne Terminale sowohl in der zweiten ([_]) als auch in der dritten Regel ([Border]). Die dritte Regel macht ausserdem Gebrauch von der Grammatikkonjunktion und kombiniert ein einzelnes Terminal, ein Nicht-Terminal und ein weiteres einzelnes Terminal. Das Beispiel kann durch Attribute erweitert werden und so für beiderlei die Syntaxanalyse und –synthese verwendet werden. Entsprechender Beispielcode kann in der Jekejeke Prolog Sprachenreferenz gefunden werden. Die DCG Grammatikregeln sind syntaktischer Zucker für normale Prologregeln. The Kompilierung wird die DCG Grammatikregeln durch normale Prologregeln ersetzten. Im Speziellen werden wir Nicht-Terminale durch ihr Gegenstück mit zwei zusätzlichen Argumenten ersetzen. Eine Konjunktion werden wird durch die Ersetzung ihrer Operanden ersetzen und dabei die zusätzlichen Argumente in Sequenz schalten. Schliesslich werden wir Terminale durch das Prädikat connects/3 ersetzen. Dies entspricht dem ursprünglichen Vorschlag [1]. Das Prädikat connects/3 hat die folgende Definition: connects([X | Y], X, Y). Es gibt nun verschiedene Vorschläge die Kompilation durchzuführen. Der vorläufige Vorschlag [2] schlägt die Realisierung einer eigenen Ersetzungsregel für DCG vor. Ein andersartiger Vorschlag sieht in den Ersetzungsregeln für DCG spezielle Ziel- und Ausdrucksexpansionsregeln. Wir werden dem letzten Vorschlag folgen. Aber werfen wir zuerst einen Blick auf die Realisierung der Ziel- und Ausdrucksexpansionsregeln. Wir können diese sehr einfach halten da wir nur Vanille-Prolog unterstützen müssen. Wir werden die entsprechenden Prädikate desugar_term/2 und desugar_goal/2 taufen. Ihre Definition lautet wie folgt: desugar_term((A :- B), (A :- C)) :- !, desugar_goal(B, C). desugar_term(A, C) :- term_desugaring(A, B), !, desugar_term(B, C). desugar_term(A, A). desugar_goal((A, B), (C, D)) :- !, desugar_goal(A, C), desugar_goal(B, D). desugar_goal(A, C) :- goal_desugaring(A, B), !, desugar_goal(B, C). desugar_goal(A, A). Der Zielexpansionsmechanismus für Vanille-Prolog verfügt über zwei Variationspunkte. Wir können ihn durch die Definition von Regeln für term_desugaring/2 und goal_desugaring/2 erweitern. Die Vanille-DCG Regeln die wir einstöpseln machen Gebrauch von einem Prädikat extend/4. Dieses Prädikat erweitert ein gegebenes Ziel um zwei Argumente. Weitere Details zur Definition können im Attachment zu diesem Tagebucheintrag gefunden werden. Um die Ersetzung durch Zielexpansion zu realisieren, schieben wir einen Ausdruck der Form phrase(G,I,O) vor uns hin, wobei G das Grammatikziel ist und I, O die zusätzlichen Argumente. term_desugaring((P ==> B), (Q :- phrase(B, I, O))) :- extend(P, I, O, Q). goal_desugaring(phrase((A, B), I, O), (phrase(A, I, H), phrase(B, H, O))). goal_desugaring(phrase([A], I, O), connects(I, A, O)). goal_desugaring(phrase([], I, I), true). goal_desugaring(phrase(P, I, O), Q) :- extend(P, I, O, Q). Die beiden Regeln für das Grammatik (==>)/2 und für das Grammatik (,) delegieren eine weitere Expansion an desugar_term/2 und desugar_goal/2. Dies ist möglich da diese Prädikate eine Endrekursion nach dem Aufruf von term_desugaring/2 und goal_desugaring/2 realisieren, wie durch einfache Codeinspektion festgestellt werden kann. Die Zielexpansion wird normalerweise innerhalb der Routine zum Einlesen aufgerufen. Aus Einfachheit verwenden wir ein Prädikat convert/0, das ausdrücklich die ==>/2 Fakten abbildet. ?- convert. Yes ?- listing(palin/2). :- dynamic palin / 2. palin(_A, _A). palin(_A, _C) :- connects(_A, _B, _C). palin(_A, _E) :- connects(_A, _B, _C), palin(_C, _D), connects(_D, _B, _E). Folgende positive und negative Anfragen werden korrekt vom kompilierten Code ausgeführt: ?- palin("anna",[]). Yes ?- palin("bert",[]). No Aus der Zielexpansion für Vanille-Prolog und aus den Regeln für Vanille-DCG last sich eine vollständige Realisierung ableiten. Die vollständige Realisierung benötigt nicht nur zusätzlichen Aufwand um alles von Prolog und DCG abzudecken. Es wird auch nötig sein die Fehlebehandlung zu realisieren. So sollte z.B. die Ausdrucksexpansion einer Variablen zu einem Instanzierungsfehler führen. Wenn wir unser Kompilationsergebnis genauer betrachten, so sehen wir dass wir alle Variablennamen verloren haben. Eine vollständige Realisierung sollte Variablenamen,Ausdruckspositionen, etc.. übertragen um das Debuggen von DCG Code zu unterstützen. Jekejeke Prolog realisiert im Moment nur einen Transfer der Variablenamen. Schliesslich kann einen volle Realisierung das von DEC10 Prolog bekannte Prädikat ‚C‘/3 statt des Prädikats connects/3 benutzen. Das Prädikat ‚C‘/3 ist nicht sehr weit verbreitet unter den Prologsystem Realisierungen. Einige Prologsystem Realisierung benutzen direkt ‚=‘/2 oder versuchen sogar Headunifikation. Dadurch dass von ‚C‘/3 Abstand gehalten wird entgeht den Realisierungen jedoch Erweiterbarkeit wie schon in [1] erläutert. Um einfache Erweiterbarkeit zu gewährleisten haben wir ‚C‘/3 deshalb in Jekejeke Prolog Multifile gesetzt. Dadurch kann der End-Benutzer selbständig zusätzliche ‚C‘/3 Regeln definieren. Referenzen [1] Pereira, F.C.N. and Warren, D.H.D. (1980): Definite Clause Grammars for Language Analysis – A Survey of the Formalism and a Comparison with Augmented Transition Networks, North-Holland Publishing Company, Artificial Intelligence, 13, 231 – 278 http://cgi.di.uoa.gr/~takis/pereira-warren.pdf [2] Moura, P. et al. (2010): ISO/IEC DTR 13211 3:2006, Definite Clause Grammar Rules, Draft, April 1, 2010 http://www.sju.edu/~jhodgson/wg17/Drafts/DCGs/DCGs-DRAFT-2010-04-01.pdf

Kommentare