Co to jest „predykat semantyczny” w ANTLR?


103

Co to jest predykat semantyczny w ANTLR?


3
Zauważ, że ponieważ nie mogłem znaleźć przyzwoitego zasobu internetowego do opublikowania dla kogoś, kto chciałby wiedzieć, czym jest predykat semantyczny , zdecydowałem się opublikować tutaj to pytanie (na które również wkrótce odpowiem).
Bart Kiers

1
Dzięki za zrobienie tego; Zawsze lubię, gdy ludzie odpowiadają na własne pytania, zwłaszcza jeśli zadają pytanie konkretnie, aby odpowiedzieć w ten sposób.
Daniel H

1
Czytać książkę. Rozdział 11 książki The Definitive ANTLR 4 Reference dotyczy predykatów semantycznych. Nie masz książki? Zdobyć! Wart każdego dolara.
james.garriss

Odpowiedzi:


169

ANTLR 4

W przypadku predykatów w ANTLR 4 sprawdź te pytania i odpowiedzi dotyczące przepełnienia stosu :


ANTLR 3

Semantyczny orzecznikiem jest sposobem wymuszenia Extra (semantyczne) zasady upon działań gramatyki przy użyciu zwykłego kodu.

Istnieją 3 typy predykatów semantycznych:

  • walidacja predykatów semantycznych;
  • bramkowane predykaty semantyczne;
  • ujednoznaczniające semantyczne predykaty.

Przykład gramatyki

Powiedzmy, że masz blok tekstu składający się tylko z liczb oddzielonych przecinkami, ignorując wszelkie spacje. Chciałbyś przeanalizować te dane wejściowe, upewniając się, że liczby mają co najwyżej 3 cyfry „długie” (najwyżej 999). Następująca gramatyka ( Numbers.g) zrobiłaby coś takiego:

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

Testowanie

Gramatykę można przetestować z następującą klasą:

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

Przetestuj, generując lekser i parser, kompilując wszystkie .javapliki i uruchamiając Mainklasę:

java -cp antlr-3.2.jar org.antlr. Numery narzędzi. g
javac -cp antlr-3.2.jar * .java
java -cp.: antlr-3.2.jar Main

W takim przypadku nic nie jest drukowane na konsoli, co oznacza, że ​​nic nie poszło nie tak. Spróbuj zmienić:

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

w:

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

i powtórz test: zaraz po napisie na konsoli pojawi się błąd 777.


Predykaty semantyczne

To prowadzi nas do semantycznych predykatów. Powiedzmy, że chcesz przeanalizować liczby zawierające od 1 do 10 cyfr. Zasada taka:

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
  ;

stałoby się uciążliwe. Predykaty semantyczne mogą pomóc w uproszczeniu tego typu reguły.


1. Walidacja predykatów semantycznych

Walidacji semantyczny orzeczenie nie jest niczym więcej niż bloku kodu, a następnie znak zapytania:

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

Aby rozwiązać powyższy problem za pomocą walidacyjnego predykatu semantycznego, zmień numberregułę w gramatyce na:

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

Części { int N = 0; }i { N++; }są prostymi instrukcjami Java, z których pierwsza jest inicjowana, gdy parser „wchodzi” do numberreguły. Rzeczywistym predykatem jest:, { N <= 10 }?co powoduje, że parser rzuca a, FailedPredicateException gdy liczba ma więcej niż 10 cyfr.

Przetestuj, korzystając z ANTLRStringStream:

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

co nie tworzy wyjątku, podczas gdy następujące zgłasza wyjątek:

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

2. Bramkowe predykaty semantyczne

Ogrodzony semantyczny orzecznikiem jest podobny do zatwierdzającego semantycznej orzecznik , tylko brama wersja produkuje błąd składni zamiast FailedPredicateException.

Składnia bramkowanego predykatu semantycznego jest następująca:

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

Aby zamiast tego rozwiązać powyższy problem, używając predykatów bramkowanych do dopasowania liczb do 10 cyfr, napiszesz:

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

Przetestuj ponownie, używając obu:

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

i:

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

a zobaczysz, że ostatni z nich wyrzuci błąd.


3. Ujednoznaczniające predykaty semantyczne

Ostatnim typem predykatu jest ujednoznaczniający predykat semantyczny , który wygląda trochę jak predykat walidacyjny ( {boolean-expression}?), ale działa bardziej jak bramkowany predykat semantyczny (żaden wyjątek nie jest zgłaszany, gdy wartość wyrażenia logicznego wynosi false). Możesz go użyć na początku reguły, aby sprawdzić jakąś właściwość reguły i pozwolić parserowi dopasować tę regułę lub nie.

Powiedzmy, że przykładowa gramatyka tworzy Numbertokeny (reguła leksera zamiast reguły analizatora składni), które będą dopasowywać liczby z zakresu 0..999. Teraz w parserze chciałbyś rozróżnić między małymi i wysokimi liczbami (niski: 0..500, wysoki: 501..999). Można to zrobić za pomocą ujednoznaczniającego predykatu semantycznego, w którym następnie sprawdzasz token w stream ( input.LT(1)), aby sprawdzić, czy jest niski lub wysoki.

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

Jeśli teraz przeanalizujesz ciąg "123, 999, 456, 700, 89, 0", zobaczysz następujące dane wyjściowe:

low  = 123
high = 999
low  = 456
high = 700
low  = 89
low  = 0

12
Człowieku, naprawdę powinieneś rozważyć napisanie przewodnika dla początkujących do ANTLR: P
Yuri Ghensev

5
@Bart Kiers: Proszę napisać książkę o ANTLR
santosh singh

2
Dla ANTLR v4 input.LT(1)jest getCurrentToken()teraz :-)
Xiao Jia

Fantastycznie ... To rodzaj wyczerpujących wyjaśnień i przykładów, które powinny znajdować się w dokumentacji!
Ezekiel Victor

+1. Ta odpowiedź jest znacznie lepsza niż w książce The Definitive ANTLR 4 Reference. Ta odpowiedź jest trafna w koncepcję z ładnymi przykładami.
asyncwait

11

Zawsze używałem zwięzłego odniesienia do predykatów ANTLR na wincent.com jako mojego przewodnika.


6
Tak, doskonały link! Ale, jak wspomniałeś, może to być trochę trudne dla kogoś (stosunkowo) nowego w ANTLR. Mam tylko nadzieję, że moja odpowiedź jest (trochę) bardziej przyjazna dla kosza na trawę ANTLR. :)
Bart Kiers
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.