Parsing von kontextsensitiver Sprache

Question

Ich lese gerade die Definitive ANTLR-Referenz von Terence Parr, in der er sagt:

Semantische Prädikate sind ein leistungsfähiges Mittel zur Erkennung kontextsensitiver Sprachstrukturen, indem sie es ermöglichen Laufzeitinformationen zur Steuerung der Erkennung

Aber die Beispiele in dem Buch sind sehr einfach. Was ich wissen muss, ist: kann ANTLR parsen kontextabhängig Regeln wie:

xAy --> xBy

Wenn ANTLR diese Regeln nicht parsen kann, gibt es dann ein anderes Werkzeug, das sich mit kontextsensitiven Grammatiken befasst?

Answer 1

ANTLR parst nur Grammatiken, die LL(*) sind. Es kann keine Grammatiken für vollständige kontextabhängige Sprachen wie das von Ihnen angegebene Beispiel analysieren. Ich denke, was Parr meinte, war, dass ANTLR parsen kann einige Sprachen, die eine einige (links) Kontextbeschränkungen.

Insbesondere kann man semantische Prädikate für "Reduktionsaktionen" verwenden (wir tun dies für GLR-Parser die von unserem DMS-Software-Reengineering-Werkzeugsatz aber die Idee ist ähnlich für ANTLR, denke ich), um alle Daten zu inspizieren, die der Parser bisher gesammelt hat, entweder als Ad-hoc-Nebeneffekte anderer semantischer Aktionen oder in einem teilweise erstellten Parse-Baum.

Für unser DMS-basiertes DMS-basiertes Fortran-Frontend gibt es eine kontextabhängige Prüfung, um sicherzustellen, dass DO-Schleifen richtig angeordnet sind. Bedenken Sie:

 DO  20, I= ...
   DO 10, J = ...
       ...
20  CONTINUE
10  CONTINUE

Aus der Sicht des Parsers sieht der lexikalische Strom wie folgt aus:

DO  <number> , <variable> =  ...
    DO <number> , <variable> = ...
         ...
<number> CONTINUE
<number> CONTINUE

Wie kann der Parser dann wissen, welche DO-Anweisung zu welcher CONTINUE-Anweisung gehört? (Die Aussage, dass jedes DO mit dem nächstgelegenen CONTINUE übereinstimmt, funktioniert nicht, da FORTRAN eine CONTINUE-Anweisung mit mehreren DO-Köpfen teilen kann).

Wir verwenden ein semantisches Prädikat "CheckMatchingNumbers" auf die Reduktion für die folgende Regel:

block = 'DO' <number> rest_of_do_head newline 
         block_of_statements
         <number> 'CONTINUE' newline ; CheckMatchingNumbers

um zu prüfen, ob die Zahl nach dem Schlüsselwort DO und die Zahl nach dem Schlüsselwort CONTINUE übereinstimmen. Wenn das semantische Prädikat besagt, dass sie übereinstimmen, dann ist eine Reduktion für diese Regel erfolgreich und wir haben den DO-Kopf mit dem korrekten CONTINUE ausgerichtet. Wenn das Prädikat fehlschlägt, wird keine Reduktion vorgeschlagen (und diese Regel wird aus den Kandidaten für das Parsen des lokalen Kontexts entfernt); ein anderer Satz von Regeln muss den Text parsen.

Die eigentlichen Regeln und semantischen Prädikate für die Behandlung von FORTRAN-Schachtelungen mit gemeinsamen Fortsetzungen sind komplexer, aber ich denke, das bringt es auf den Punkt.

Was Sie wollen, ist eine vollständige kontextabhängige Parsing-Engine. Ich weiß, dass Leute sie gebaut haben, aber ich kenne keine vollständigen Implementierungen, und erwarte nicht, dass sie schnell sind.

Ich folgte Das MetaS-Grammatiksystem von Quinn Taylor Jackson Es klang wie ein praktischer Versuch, sich zu nähern.

Answer 2

Es ist vergleichsweise einfach, einen kontextsensitiven Parser in Prolog . Dieses Programm parst die Zeichenkette [a,is,less,than,b,and,b,is,less,than,c] und wandelt sie um in [a,<,b,<,c] :

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :-
    rewrite_system([a,is,less,than,b,and,b,is,less,than,c],X),writeln('\nFinal output:'),writeln(X).

rewrite_rule([[A,<,B],and,[B,<,C]],[A,<,B,<,C]).
rewrite_rule([A,is,less,than,B],[A,<,B]).
rewrite_rule([[A,<,B],and,C,than,D],[[A,<,B],and,A,is,C,than,D]).
rewrite_rule([A,<,B],[[A,<,B]]).

rewritten(A) :- atom(A);bool(A).
bool(A) :- atom(A).
bool([A,<,B,<,C]) :- atom(A),atom(B),atom(C).
bool([A,and,B]) :- bool(A),bool(B).

% this predicate is from https://stackoverflow.com/a/8312742/975097
replace(ToReplace, ToInsert, List, Result) :-
    once(append([Left, ToReplace, Right], List)),
    append([Left, ToInsert, Right], Result).

rewrite_system(Input,Output) :-
    rewritten(Input),Input=Output;
    rewrite_rule(A,B),
    replace(A,B,Input,Input1),
    writeln(Input1),
    rewrite_system(Input1,Output).

Unter Verwendung desselben Algorithmus habe ich auch eine adaptiver Parser die aus ihrer Eingabe neue Umschreibregeln "lernt".