gl5_progのメモ

自分のためのメモとかまとめとか

3種類のsemantic predicate

ANTLRのsemantic predicateの説明でStackOverflowに良い説明があったので訳してみる。
antlr - What is a 'semantic predicate' in ANTLR3? - Stack Overflow

A semantic predicate is a way to enforce extra (semantic) rules upon grammar actions using plain code.
semantic predicateは平素なコードを使ったアクションで特別なルールを強制する方法です。

There are 3 types of semantic predicates:

  • validating semantic predicates;
  • gated semantic predicates;
  • disambiguating semantic predicates.

3種類のsemantic predicatesがあります。

  • 検証意味述語
  • 制御意味述語
  • 決定意味述語

Example grammar

Let's say you have a block of text consisting of only numbers separated by comma's, ignoring any white spaces. You would like to parse this input making sure that the numbers are at most 3 digits "long" (at most 999). The following grammar (Numbers.g) would do such a thing:
カンマで分割された数字だけで構成された文字列があるとしよう。少なくとも数字が3桁であることを明確にするためパースしたい。下に示す文法は、そのようなことを行う。

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

Testing

The grammar can be tested with the following class:
この文法は以下のクラスでテストができる。

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

Test it by generating the lexer and parser, compiling all .java files and running the Main class:
生成されたレキサーとパーサーでテストします。すべてのjavaファイルをコンパイルし、Mainクラスを実行します。

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

When doing so, nothing is printed to the console, which indicates that nothing went wrong. Try changing:
実行すると何もコンソールに出力されません。これは何も間違っていないことを示します。 変えてみましょう。

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

into:

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

and do the test again: you will see an error appearing on the console right after the string 777.
そして再びテストします。777という文字列の後にエラーがコンソールに表示されます。

Semantic Predicates

This brings us to the semantic predicates. Let's say you want to parse numbers between 1 and 10 digits long. A rule like:
これは意味的述語をもたらします? 1桁から10桁をパースしたいとします。

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
  ;

would become cumbersome. Semantic predicates can help simplify this type of rule.
複雑になってしまいました。semantic predicatesはこのような場合にシンプルにしてくれます。

1. 検証意味的述語 Validating Semantic Predicates

A validating semantic predicate is nothing more than a block of code followed by a question mark:
検証意味的述語は?マークをつけるだけです。

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

To solve the problem above using a validating semantic predicate, change the number rule in the grammar into:
検証意味的述語を使って問題を解決するために、numberルールを変更します。

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

The parts { int N = 0; } and { N++; } are plain Java statements of which the first is initialized when the parser "enters" the number rule. The actual predicate is: { N <= 10 }?, which causes the parser to throw a FailedPredicateException whenever a number is more than 10 digits long.
{ int N = 0; } と { N++; }はJavaの文です。1つ目はnumberルールに入ったときの初期化です。実際の述語は{ N <= 10 }?です。これにより数字が10桁より多い場合FailedPredicateException例外を投げます。

Test it by using the following ANTLRStringStream:
テストしましょう。

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

which produces no exception, while the following does thow an exception:
これは例外を出しません。一方、以下のものは例外を出します。

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

2. 制御意味的述語 Gated Semantic Predicates

A gated semantic predicate is similar to a validating semantic predicate, only the gated version produces a syntax error instead of a FailedPredicateException.
制御意味的述語は検証意味的述語と似ています。制御意味的述語だけはFailedPredicateException例外のかわりに構文エラーになります。

The syntax of a gated semantic predicate is:
制御意味的述語の構文は以下のとおりです。

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

To instead solve the above problem using gated predicates to match numbers up to 10 digits long you would write:
制御意味的述語を使って問題を解決するには以下のように書きます。

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

Test it again with both:
再びテストします。

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

and:

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

and you will see the last on will throw an error.
最後のやつはエラーを出します。

3. 決定意味的述語 Disambiguating Semantic Predicates

The final type of predicate is a disambiguating semantic predicate, which looks a bit like a validating predicate ({boolean-expression}?), but acts more like a gated semantic predicate (no exception is thrown when the boolean expression evaluates to false). You can use it at the start of a rule to check some property of a rule and let the parser match said rule or not.
最後の述語の種類は決定意味的述語です。検証述語に似ている。ルールの始めにいくつかのプロパティをチェックできます。

Let's say the example grammar creates Number tokens (a lexer rule instead of a parser rule) that will match numbers in the range of 0..999. Now in the parser, you'd like to make a distinction between low- and hight numbers (low: 0..500, high: 501..999). This could be done using a disambiguating semantic predicate where you inspect the token next in the stream (input.LT(1)) to check if it's either low or high.
サンプル文法は0..999の数字のNumberトークン(パーサールールではなくレキサールール)を作るとします。パーサーでは、独自のlowとheightの範囲を作りたいとします(low:0..500, high:501..999)。これは決定意味的述語を使うことで実行できます。

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

If you now parse the string "123, 999, 456, 700, 89, 0", you'd see the following output:
もし "123, 999, 456, 700, 89, 0"を貼付けた場合、以下の出力が得られます。

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