Qu'est-ce qu'un «prédicat sémantique» dans ANTLR?

103

Qu'est-ce qu'un prédicat sémantique dans ANTLR?

Bart Kiers
la source
3
Notez que comme je ne pouvais pas trouver une ressource en ligne décente à publier pour quelqu'un qui voulait savoir ce qu'est un prédicat sémantique , j'ai décidé de poster moi-même la question ici (à laquelle je vais bientôt répondre moi-même).
Bart Kiers
1
Merci d'avoir fait cela; J'aime toujours que les gens répondent à leurs propres questions, surtout s'ils posent la question spécifiquement pour y répondre de cette manière.
Daniel H
1
Lis le livre. Ch 11 de The Definitive ANTLR 4 Reference est sur les prédicats sémantiques. Vous n'avez pas le livre? Tu piges! Vaut chaque dollar.
james.garriss

Réponses:

169

ANTLR 4

Pour les prédicats dans ANTLR 4, consultez ces questions et réponses sur le débordement de pile :


ANTLR 3

Un prédicat sémantique est un moyen d'imposer des règles (sémantiques) supplémentaires aux actions de grammaire en utilisant du code brut.

Il existe 3 types de prédicats sémantiques:

  • valider les prédicats sémantiques;
  • prédicats sémantiques fermés ;
  • disambiguating prédicats sémantiques.

Exemple de grammaire

Disons que vous avez un bloc de texte composé uniquement de chiffres séparés par des virgules, en ignorant les espaces blancs. Vous souhaitez analyser cette entrée en vous assurant que les nombres sont au plus 3 chiffres "longs" (au plus 999). La grammaire suivante ( Numbers.g) ferait une telle chose:

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();}
  ;

Essai

La grammaire peut être testée avec la classe suivante:

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();
    }
}

Testez-le en générant le lexer et l'analyseur, en compilant tous les .javafichiers et en exécutant la Mainclasse:

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

Ce faisant, rien n'est imprimé sur la console, ce qui indique que rien ne s'est mal passé. Essayez de changer:

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

dans:

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

et refaites le test: vous verrez une erreur apparaître sur la console juste après la chaîne 777.


Prédicats sémantiques

Cela nous amène aux prédicats sémantiques. Supposons que vous souhaitiez analyser des nombres entre 1 et 10 chiffres. Une règle comme:

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
  ;

deviendrait encombrant. Les prédicats sémantiques peuvent aider à simplifier ce type de règle.


1. Validation des prédicats sémantiques

Un prédicat sémantique de validation n'est rien d'autre qu'un bloc de code suivi d'un point d'interrogation:

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

Pour résoudre le problème ci-dessus en utilisant un prédicat sémantique de validation , changez la numberrègle de la grammaire en:

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

Les parties { int N = 0; }et { N++; }sont des instructions Java simples dont la première est initialisée lorsque l'analyseur "entre" la numberrègle. Le prédicat réel est:, { N <= 10 }?ce qui oblige l'analyseur à lancer un FailedPredicateException chaque fois qu'un nombre comporte plus de 10 chiffres.

Testez-le en utilisant ce qui suit ANTLRStringStream:

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

qui ne produit aucune exception, alors que ce qui suit fait une exception:

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

2. Prédicats sémantiques fermés

Un prédicat sémantique gated est similaire à un prédicat sémantique de validation , seule la version gated produit une erreur de syntaxe au lieu d'un FailedPredicateException.

La syntaxe d'un prédicat sémantique gated est:

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

Pour résoudre à la place le problème ci-dessus en utilisant des prédicats fermés pour faire correspondre des nombres jusqu'à 10 chiffres, vous écririez:

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

Testez à nouveau avec les deux:

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

et:

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

et vous verrez le dernier sur lancera une erreur.


3. Élimination de l'ambiguïté des prédicats sémantiques

Le dernier type de prédicat est un prédicat sémantique sans ambiguïté , qui ressemble un peu à un prédicat de validation ( {boolean-expression}?), mais agit plus comme un prédicat sémantique fermé (aucune exception n'est levée lorsque l'expression booléenne évalue à false). Vous pouvez l'utiliser au début d'une règle pour vérifier certaines propriétés d'une règle et laisser l'analyseur faire correspondre cette règle ou non.

Disons que l'exemple de grammaire crée des Numberjetons (une règle de lexer au lieu d'une règle d'analyseur) qui correspondent à des nombres compris entre 0 et 999. Maintenant, dans l'analyseur, vous aimeriez faire une distinction entre les nombres faibles et élevés (bas: 0..500, haut: 501..999). Cela pourrait être fait en utilisant un prédicat sémantique sans ambiguïté dans lequel vous inspectez le jeton suivant dans le flux ( input.LT(1)) pour vérifier s'il est bas ou élevé.

Une démo:

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();}
  ;

Si vous analysez maintenant la chaîne "123, 999, 456, 700, 89, 0", vous verrez la sortie suivante:

low  = 123
high = 999
low  = 456
high = 700
low  = 89
low  = 0
Bart Kiers
la source
12
Homme, vous devriez vraiment envisager d'écrire un guide du débutant sur ANTLR: P
Yuri Ghensev
5
@Bart Kiers: Veuillez écrire un livre sur ANTLR
santosh singh
2
Pour ANTLR v4, input.LT(1)c'est getCurrentToken()maintenant :-)
Xiao Jia
Fantastique ... C'est le genre d'explications et d'exemples exhaustifs qui devraient figurer dans la documentation!
Ezekiel Victor
+1. Cette réponse est bien meilleure que le livre de référence The Definitive ANTLR 4. Cette réponse correspond parfaitement au concept avec de beaux exemples.
asyncwait
11

J'ai toujours utilisé la référence laconique aux prédicats ANTLR sur wincent.com comme guide.

Kaleb Pederson
la source
6
Oui, un excellent lien! Mais, comme vous l'avez mentionné, cela pourrait être un peu difficile pour quelqu'un (relativement) nouveau dans ANTLR. J'espère juste que ma réponse est (un peu) plus amicale pour l'ANTLR-grass-hopper. :)
Bart Kiers