Was ist ein "semantisches Prädikat" in ANTLR?

103

Was ist ein semantisches Prädikat in ANTLR?

Bart Kiers
quelle
3
Da ich für jemanden, der wissen wollte, was ein semantisches Prädikat ist, keine anständige Online-Ressource zum Posten finden konnte , habe ich beschlossen, die Frage hier selbst zu posten (die ich in Kürze auch selbst beantworten werde).
Bart Kiers
1
Danke dafür; Ich mag es immer, wenn Leute ihre eigenen Fragen beantworten, besonders wenn sie die Frage speziell stellen, um sie auf diese Weise zu beantworten.
Daniel H
1
Lies das Buch. Kapitel 11 der endgültigen ANTLR 4-Referenz befasst sich mit semantischen Prädikaten. Hast du das Buch nicht? Kapiert! Jeden Dollar wert.
James.garriss

Antworten:

169

ANTLR 4

Für Prädikate in ANTLR 4, Check - out diesen Stapelüberlauf Q & A:


ANTLR 3

Ein semantisches Prädikat ist eine Möglichkeit, zusätzliche (semantische) Regeln für Grammatikaktionen mithilfe von einfachem Code durchzusetzen.

Es gibt 3 Arten von semantischen Prädikaten:

  • Validierung semantischer Prädikate;
  • gated semantische Prädikate;
  • eindeutige semantische Prädikate.

Beispielgrammatik

Angenommen, Sie haben einen Textblock, der nur aus durch Kommas getrennten Zahlen besteht und Leerzeichen ignoriert. Sie möchten diese Eingabe analysieren und sicherstellen, dass die Zahlen höchstens 3 Ziffern "lang" sind (höchstens 999). Die folgende Grammatik ( Numbers.g) würde so etwas tun:

grammar Numbers;

// entry point of this parser: it parses an input string consisting of at least 
// one number, optionally followed by zero or more comma's and numbers
parse
  :  number (',' number)* EOF
  ;

// matches a number that is between 1 and 3 digits long
number
  :  Digit Digit Digit
  |  Digit Digit
  |  Digit
  ;

// matches a single digit
Digit
  :  '0'..'9'
  ;

// ignore spaces
WhiteSpace
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

Testen

Die Grammatik kann mit folgender Klasse getestet werden:

import org.antlr.runtime.*;

public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("123, 456, 7   , 89");
        NumbersLexer lexer = new NumbersLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        NumbersParser parser = new NumbersParser(tokens);
        parser.parse();
    }
}

Testen Sie es, indem Sie den Lexer und den Parser generieren, alle .javaDateien kompilieren und die MainKlasse ausführen :

java -cp antlr-3.2.jar org.antlr.Tool Numbers.g
javac -cp antlr-3.2.jar * .java
java -cp .: antlr-3.2.jar Main

Dabei wird nichts auf die Konsole gedruckt, was darauf hinweist, dass nichts schief gelaufen ist. Versuchen Sie zu ändern:

ANTLRStringStream in = new ANTLRStringStream("123, 456, 7   , 89");

in:

ANTLRStringStream in = new ANTLRStringStream("123, 456, 7777   , 89");

und führen Sie den Test erneut durch: Unmittelbar nach der Zeichenfolge wird auf der Konsole ein Fehler angezeigt 777.


Semantische Prädikate

Dies bringt uns zu den semantischen Prädikaten. Angenommen, Sie möchten Zahlen mit einer Länge zwischen 1 und 10 Stellen analysieren. Eine Regel wie:

number
  :  Digit Digit Digit Digit Digit Digit Digit Digit Digit Digit
  |  Digit Digit Digit Digit Digit Digit Digit Digit Digit
     /* ... */
  |  Digit Digit Digit
  |  Digit Digit
  |  Digit
  ;

würde umständlich werden. Semantische Prädikate können helfen, diese Art von Regel zu vereinfachen.


1. Validierung semantischer Prädikate

Ein validierendes semantisches Prädikat ist nichts anderes als ein Codeblock, gefolgt von einem Fragezeichen:

RULE { /* a boolean expression in here */ }?

Um das obige Problem mithilfe eines validierenden semantischen Prädikats zu lösen , ändern Sie die numberRegel in der Grammatik in:

number
@init { int N = 0; }
  :  (Digit { N++; } )+ { N <= 10 }?
  ;

Die Teile { int N = 0; }und { N++; }sind einfache Java-Anweisungen, deren erste initialisiert wird, wenn der Parser die numberRegel "eingibt" . Das eigentliche Prädikat lautet : { N <= 10 }?, wodurch der Parser FailedPredicateException immer dann a auslöst, wenn eine Zahl länger als 10 Stellen ist.

Testen Sie es mit den folgenden Methoden ANTLRStringStream:

// all equal or less than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,1234567890"); 

Dies erzeugt keine Ausnahme, während das Folgende eine Ausnahme auslöst:

// '12345678901' is more than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,12345678901");

2. Gated Semantic Prädikate

Ein gated semantisches Prädikat ähnelt einem validierenden semantischen Prädikat , nur die gated Version erzeugt einen Syntaxfehler anstelle von a FailedPredicateException.

Die Syntax eines gated semantischen Prädikats lautet:

{ /* a boolean expression in here */ }?=> RULE

Um stattdessen das obige Problem mit gated Prädikaten zu lösen , um Zahlen mit einer Länge von bis zu 10 Stellen abzugleichen, würden Sie schreiben:

number
@init { int N = 1; }
  :  ( { N <= 10 }?=> Digit { N++; } )+
  ;

Testen Sie es erneut mit beiden:

// all equal or less than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,1234567890"); 

und:

// '12345678901' is more than 10 digits
ANTLRStringStream in = new ANTLRStringStream("1,23,12345678901");

und Sie werden sehen, dass der letzte einen Fehler auslöst.


3. Disambiguierung semantischer Prädikate

Der letzte Prädikattyp ist ein eindeutiges semantisches Prädikat , das ein bisschen wie ein validierendes Prädikat ( {boolean-expression}?) aussieht , sich jedoch eher wie ein gated semantisches Prädikat verhält (es wird keine Ausnahme ausgelöst, wenn der boolesche Ausdruck ausgewertet wird false). Sie können es zu Beginn einer Regel verwenden, um eine Eigenschaft einer Regel zu überprüfen und den Parser mit dieser Regel übereinstimmen zu lassen oder nicht.

Angenommen, die Beispielgrammatik erstellt NumberToken (eine Lexer-Regel anstelle einer Parser-Regel), die mit Zahlen im Bereich von 0..999 übereinstimmen. Jetzt im Parser möchten Sie zwischen niedrigen und hohen Zahlen unterscheiden (niedrig: 0..500, hoch: 501..999). Dies kann mithilfe eines eindeutigen semantischen Prädikats erfolgen, bei dem Sie das nächste Token im Stream ( input.LT(1)) überprüfen, um festzustellen, ob es entweder niedrig oder hoch ist.

Eine Demo:

grammar Numbers;

parse
  :  atom (',' atom)* EOF
  ;

atom
  :  low  {System.out.println("low  = " + $low.text);}
  |  high {System.out.println("high = " + $high.text);}
  ;

low
  :  {Integer.valueOf(input.LT(1).getText()) <= 500}? Number
  ;

high
  :  Number
  ;

Number
  :  Digit Digit Digit
  |  Digit Digit
  |  Digit
  ;

fragment Digit
  :  '0'..'9'
  ;

WhiteSpace
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

Wenn Sie jetzt die Zeichenfolge analysieren "123, 999, 456, 700, 89, 0", wird die folgende Ausgabe angezeigt:

low  = 123
high = 999
low  = 456
high = 700
low  = 89
low  = 0
Bart Kiers
quelle
12
Mann, Sie sollten wirklich in Betracht ziehen, einen Leitfaden für Anfänger zu ANTLR zu schreiben: P
Yuri Ghensev
5
@ Bart Kiers: Bitte schreiben Sie ein Buch über ANTLR
Santosh Singh
2
Für ANTLR v4 input.LT(1)ist getCurrentToken()jetzt :-)
Xiao Jia
Fantastisch ... Dies ist die Art von erschöpfender Erklärung und Beispiele, die in den Dokumenten enthalten sein sollten!
Hesekiel Victor
+1. Diese Antwort ist weitaus besser als das Nachschlagewerk The Definitive ANTLR 4. Diese Antwort ist genau das Richtige mit schönen Beispielen.
Asyncwait
11

Ich habe immer den knappen Verweis auf ANTLR-Prädikate auf wincent.com als Leitfaden verwendet.

Kaleb Pederson
quelle
6
Ja, ein ausgezeichneter Link! Aber wie Sie bereits erwähnt haben, könnte es für jemanden (relativ) neu bei ANTLR etwas schwierig sein. Ich hoffe nur, dass meine Antwort (etwas) freundlicher für den ANTLR-Grass-Hopper ist. :)
Bart Kiers