Kann antlr Typ-abhängiges Parsing tun?

Question

Lassen Sie mich fragen, ob Antlr3 die folgende Beispielgrammatik akzeptiert.

for an input , x + y * z , 
it is parsed as x+(y*z) if each in {x,y,z} is a number; 
it is parsed as (x+y)*z if each in {x,y,z} is an object of a particular type T; 

Und lassen Sie mich fragen, ob eine solche Grammatiken manchmal verwendet werden, oder nur sehr selten für Computersprachen.

Vielen Dank.

Answer 1

Im Allgemeinen überprüfen Parser (die von Parsergeneratoren erzeugt werden) nur Syntax.

Ein Parser (mit allen Mitteln erzeugt), der mehrere Parsen untersuchen kann (ich glaube, ANTLR tut dies durch Backtracking; andere Parsing-Engines [GLR, Earley] tun dies durch parallele Erkundung möglicher Parser), wenn semantische Prüfinformationen hinzugefügt werden , könnte Parsen ablehnen, die semantischen Beschränkungen nicht entsprachen.

Leute neigen dazu, solche Parser nach meiner Erfahrung nicht zu bauen, teilweise weil es den Benutzern schwer zu erklären ist. Wenn sie es nicht verstehen, ist Ihr Parser nicht erfolgreich; Ihr Beispiel ist in Bezug auf die Erklärbarkeit besonders schlecht. Sie neigen auch dazu, dies nicht zu tun, weil sie diese Art von Informationen benötigen, und das ist nicht immer bequem zu sammeln, während Sie analysieren. Die GCC-Parser tun bekanntlich nur das diese Aussagen zu analysieren, wie

X*T; 

und der Parser ist ein bisschen ein Durcheinander wegen der Notwendigkeit, diese Art Informationen zu analysieren und zu sammeln, wie es geht.

Ich vermute, ANTLR kann semantische Prädikate überprüfen. Wie leicht es ist, Typinformationen von der Art zu bekommen, die Sie mit diesen semantischen Prüfungen besprechen, ist eine andere Frage; Ich habe hier keine Erfahrung.

Die GLR-Parsing-Engine, die von unserem DMS Software Reengineering Toolkit verwendet wird, hat "semantische" Prädikate. Es ist nicht besonders einfach, diesen Prädikaten durch das architektonische Design echte semantische Information zu geben; Wir wollten solche Prädikate von der "Syntax" abbringen. Aber dann wird alles (einschließlich Typinferenz) von der Syntax abgetrieben. Wir halten also Informationen rein lokal an die vorgeschlagene Reduktion. Dies ist besonders praktisch, in (nicht) als getrennte Arten von parst erkennen, wird die folgende eigentümlichen FORTRAN vs. Shared-do-termination für verschachtelte-do-termination konstruieren:

 DO 10 I=1,10,1 
     DO 10 J=1,10,1 
      A(I,J)=0 
10 CONTINUE 
20 CONTINUE 

vs.

 DO 20 I=1,10,1 
     DO 10 J=1,10,1 
      A(I,J)=0 
    10 CONTINUE 
    20 CONTINUE 

um den Parser, bei der reinen Syntax-Ebene, die beide diese wie folgt aussehen:

DO <INT> <VAR>=... 
     DO <INT> <VAR>=... 
      <STMTS> 
    <INT> CONTINUE 
    <INT> CONTINUE 

Wie eine, die Aussage zu WEITER bestimmen kann, gehört, die mit diesen Informationen nur DO consrtuct? Du kannst nicht.

Der DMS-FORTRAN-Parser macht genau dies, indem er zwei Regelsätze für DO-Schleifen hat, einen für nicht freigegebene, einen für gemeinsame Weiterleitungen. Sie unterscheiden unter Verwendung von semantischen Prädikaten, die überprüfen, ob die CONTINUE-Anweisungsbezeichnung mit der mit DO-Schleife bezeichneten Bezeichnung übereinstimmt. Und so erhält der DMS-FORTRAN-Parser die Schleifenverschachtelung beim Analysieren richtig. AFAIK, alle anderen FORTRAN-Compiler analysieren die Anweisungen einzeln und stechen anschließend die DO-Loop-Nester in einem Post-Pass zusammen.

Und ja, während FORTRAN dieses (verwirrende) Konstrukt hat, hat keine andere moderne Sprache, die ich kenne, es kopiert.