Apa yang dimaksud dengan 'predikat semantik' di ANTLR?

103

Apa yang dimaksud dengan predikat semantik di ANTLR?

Bart Kiers
sumber
3
Perhatikan bahwa karena saya tidak dapat menemukan sumber daya online yang layak untuk diposkan untuk seseorang yang ingin tahu apa itu predikat semantik , saya memutuskan untuk mengirim pertanyaan di sini sendiri (yang akan segera saya jawab juga).
Bart Kiers
1
Terima kasih telah melakukan ini; Saya selalu suka ketika orang menjawab pertanyaan mereka sendiri, terutama jika mereka menanyakan pertanyaan secara khusus untuk menjawabnya dengan cara ini.
Daniel H
1
Membaca buku. Ch 11 dari The Definitive ANTLR 4 Reference berada pada predikat semantik. Tidak punya bukunya? Mengerti! Layak setiap dolar.
james.garriss

Jawaban:

169

ANTLR 4

Untuk predikat di ANTLR 4, periksa T&J stack overflow ini:


ANTLR 3

Sebuah predikat semantik adalah cara untuk menegakkan tambahan (semantik) aturan pada tindakan tata bahasa menggunakan kode polos.

Ada 3 jenis predikat semantik:

  • memvalidasi predikat semantik;
  • predikat semantik berpagar ;
  • merusak predikat semantik.

Contoh tata bahasa

Misalkan Anda memiliki blok teks yang hanya terdiri dari angka yang dipisahkan oleh koma, mengabaikan spasi putih apa pun. Anda ingin mengurai masukan ini untuk memastikan bahwa nomornya paling banyak 3 digit "panjang" (paling banyak 999). Grammar ( Numbers.g) berikut akan melakukan hal seperti itu:

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

Menguji

Tata bahasa dapat diuji dengan kelas berikut:

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

Ujilah dengan membuat lexer dan parser, mengompilasi semua .javafile dan menjalankan Mainkelas:

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

Saat melakukannya, tidak ada yang dicetak ke konsol, yang menunjukkan bahwa tidak ada yang salah. Coba ubah:

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

ke:

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

dan lakukan tes lagi: Anda akan melihat kesalahan muncul di konsol tepat setelah string 777.


Predikat Semantik

Ini membawa kita ke predikat semantik. Misalkan Anda ingin mengurai angka antara 1 dan 10 digit. Aturan seperti:

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
  ;

akan menjadi tidak praktis. Predikat semantik dapat membantu menyederhanakan jenis aturan ini.


1. Memvalidasi Predikat Semantik

Sebuah memvalidasi predikat semantik adalah tidak lebih dari sebuah blok kode diikuti dengan tanda tanya:

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

Untuk mengatasi masalah di atas menggunakan predikat semantik yang memvalidasi , ubah numberaturan dalam tata bahasa menjadi:

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

Bagian { int N = 0; }dan { N++; }pernyataan Java biasa yang pertama diinisialisasi ketika parser "memasukkan" numberaturan. Predikat sebenarnya adalah:, { N <= 10 }?yang menyebabkan parser melempar FailedPredicateException setiap kali bilangan lebih dari 10 digit.

Uji dengan menggunakan berikut ini ANTLRStringStream:

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

yang tidak menghasilkan pengecualian, sementara yang berikut ini menampilkan pengecualian:

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

2. Predikat Semantik Gerbang

Sebuah predikat semantik terjaga keamanannya mirip dengan predikat semantik memvalidasi , hanya terjaga keamanannya versi menghasilkan kesalahan sintaks bukannya FailedPredicateException.

Sintaks dari predikat semantik yang terjaga keamanannya adalah:

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

Untuk mengatasi masalah di atas menggunakan predikat berpagar untuk mencocokkan angka hingga 10 digit, Anda akan menulis:

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

Uji lagi dengan keduanya:

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

dan:

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

dan Anda akan melihat yang terakhir akan melempar kesalahan.


3. Menghilangkan Predikat Semantik

Jenis terakhir dari predikat adalah predikat semantik yang membingungkan , yang terlihat seperti predikat validasi ( {boolean-expression}?), tetapi bertindak lebih seperti predikat semantik yang terjaga keamanannya (tidak terkecuali dilemparkan saat ekspresi boolean mengevaluasi ke false). Anda dapat menggunakannya di awal aturan untuk memeriksa beberapa properti aturan dan membiarkan parser cocok dengan aturan tersebut atau tidak.

Misalkan, contoh tata bahasa membuat Numbertoken (aturan lexer dan bukan aturan parser) yang akan cocok dengan angka dalam rentang 0..999. Sekarang di parser, Anda ingin membuat perbedaan antara angka rendah dan tinggi (rendah: 0..500, tinggi: 501..999). Ini bisa dilakukan dengan menggunakan predikat semantik disambiguasi di mana Anda memeriksa token berikutnya di stream ( input.LT(1)) untuk memeriksa apakah nilainya rendah atau tinggi.

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

Jika sekarang Anda mengurai string "123, 999, 456, 700, 89, 0", Anda akan melihat output berikut:

low  = 123
high = 999
low  = 456
high = 700
low  = 89
low  = 0
Bart Kiers
sumber
12
Sobat, Anda benar-benar harus mempertimbangkan untuk menulis panduan pemula untuk ANTLR: P
Yuri Ghensev
5
@Bart Kiers: Silakan tulis buku tentang ANTLR
santosh singh
2
Untuk ANTLR v4, input.LT(1)adalah getCurrentToken()sekarang :-)
Xiao Jia
Fantastis ... Ini adalah jenis penjelasan dan contoh lengkap yang harus ada di dokumen!
Ezekiel Victor
+1. Jawaban ini jauh lebih baik dari buku Referensi Definitive ANTLR 4. Jawaban ini tepat pada konsep dengan contoh yang bagus.
asyncwait
11

Saya selalu menggunakan referensi singkat untuk predikat ANTLR di wincent.com sebagai panduan saya.

Kaleb Pederson
sumber
6
Ya, tautan yang sangat bagus! Tapi, seperti yang Anda sebutkan, mungkin agak sulit bagi seseorang (yang relatif) baru mengenal ANTLR. Saya hanya berharap jawaban saya (sedikit) lebih ramah untuk ANTLR-wereng rumput. :)
Bart Kiers