O que é um 'predicado semântico' em ANTLR?

103

O que é um predicado semântico em ANTLR?

Bart Kiers
fonte
3
Observe que, como não consegui encontrar um recurso online decente para postar para alguém que queria saber o que é um predicado semântico , decidi postar a pergunta aqui (a qual responderei em breve).
Bart Kiers
1
Obrigado por fazer isso; Eu sempre gosto quando as pessoas respondem às suas próprias perguntas, especialmente se fazem a pergunta especificamente para respondê-la dessa forma.
Daniel H
1
Leia o livro. O Capítulo 11 da Referência ANTLR 4 Definitiva é sobre predicados semânticos. Não tem o livro? Pegue! Valeu cada dólar.
james.garriss

Respostas:

169

ANTLR 4

Para predicados em ANTLR 4, verifique estas perguntas e respostas sobre estouro de pilha :


ANTLR 3

Um predicado semântico é uma maneira de impor regras extras (semânticas) em ações gramaticais usando código simples.

Existem 3 tipos de predicados semânticos:

  • validar predicados semânticos;
  • predicados semânticos bloqueados ;
  • desambiguação de predicados semânticos.

Gramática de exemplo

Digamos que você tenha um bloco de texto consistindo apenas de números separados por vírgulas, ignorando todos os espaços em branco. Você gostaria de analisar esta entrada certificando-se de que os números tenham no máximo 3 dígitos "longos" (no máximo 999). A seguinte gramática ( Numbers.g) faria isso:

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

Testando

A gramática pode ser testada com a seguinte classe:

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

Teste-o gerando o lexer e o analisador, compilando todos os .javaarquivos e executando a 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

Ao fazer isso, nada é impresso no console, o que indica que nada deu errado. Tente mudar:

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

para dentro:

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

e faça o teste novamente: você verá um erro aparecendo no console logo após a string 777.


Predicados Semânticos

Isso nos leva aos predicados semânticos. Digamos que você queira analisar números entre 1 e 10 dígitos. Uma regra como:

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
  ;

se tornaria complicado. Os predicados semânticos podem ajudar a simplificar esse tipo de regra.


1. Validando Predicados Semânticos

Um predicado semântico de validação nada mais é do que um bloco de código seguido por um ponto de interrogação:

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

Para resolver o problema acima usando um predicado semântico de validação , altere a numberregra na gramática para:

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

As partes { int N = 0; }e { N++; }são instruções Java simples, das quais a primeira é inicializada quando o analisador "insere" a numberregra. O predicado real é:, { N <= 10 }?que faz com que o analisador lance um FailedPredicateException sempre que um número tiver mais de 10 dígitos.

Teste-o usando o seguinte ANTLRStringStream:

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

que não produz exceção, enquanto o seguinte faz uma exceção:

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

2. Predicados semânticos bloqueados

Um predicado semântico com portas é semelhante a um predicado semântico de validação , apenas a versão com portas produz um erro de sintaxe em vez de um FailedPredicateException.

A sintaxe de um predicado semântico fechado é:

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

Em vez disso, para resolver o problema acima usando predicados bloqueados para combinar números de até 10 dígitos, você escreveria:

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

Teste novamente com ambos:

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

e:

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

e você verá que o último em gerará um erro.


3. Desambiguação de Predicados Semânticos

O tipo final de predicado é um predicado semântico sem ambiguidade , que se parece um pouco com um predicado de validação ( {boolean-expression}?), mas age mais como um predicado semântico com portas (nenhuma exceção é lançada quando a expressão booleana é avaliada como false). Você pode usá-lo no início de uma regra para verificar alguma propriedade de uma regra e permitir que o analisador corresponda a essa regra ou não.

Digamos que a gramática de exemplo crie Numbertokens (uma regra de lexer em vez de uma regra de analisador) que corresponderão a números no intervalo de 0..999. Agora, no analisador, você gostaria de fazer uma distinção entre os números baixos e altos (baixo: 0..500, alto: 501..999). Isso pode ser feito usando um predicado semântico de eliminação de ambigüidade, em que você inspeciona o token a seguir no fluxo ( input.LT(1)) para verificar se está baixo ou alto.

Uma demonstração:

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

Se você agora analisar a string "123, 999, 456, 700, 89, 0", verá a seguinte saída:

low  = 123
high = 999
low  = 456
high = 700
low  = 89
low  = 0
Bart Kiers
fonte
12
Cara, você realmente deveria considerar escrever um guia para iniciantes para ANTLR: P
Yuri Ghensev
5
@ Bart Kiers: Por favor, escreva um livro sobre ANTLR
santosh singh
2
Para ANTLR v4, agora input.LT(1)é getCurrentToken():-)
Xiao Jia
Fantástico ... Este é o tipo de explicação exaustiva e exemplos que deveriam estar na documentação!
Ezekiel Victor
+1. Essa resposta é muito melhor do que o livro The Definitive ANTLR 4 Reference book. Esta resposta é exata no conceito com bons exemplos.
asyncwait
11

Sempre usei a referência concisa aos predicados ANTLR em wincent.com como meu guia.

Kaleb Pederson
fonte
6
Sim, um excelente link! Mas, como você mencionou, pode ser um pouco difícil para alguém (relativamente) novo no ANTLR. Só espero que minha resposta seja (um pouco) mais amigável para o funil de grama ANTLR. :)
Bart Kiers