DSL/Alternative Tokenization - Java EE勉強会

Alternative Tokenization †

一言要約 †

パーサから文脈を伝えてレキサのふるまいを変更する

要約 †

I. 仕組み †

パーサとレキサの役割の原則
- レキサがパーサにトークンを渡し、パーサが構文木に変換する。
- 原則はパーサからレキサへの一方通行
- しかし、トークン化の方法をパーサから伝える必要があるケースもある。
```
 catalog  : item*;
 item  : 'item' ID* ';
```
  - ここで、"item small white item;"のように、'item'というキーワードを含むものが現れた場合にはどうすればよいか？

引用符を使う

 item camera
 item small power plant;
 item "small white item";

文法

 catalog  : item*;
 item  : 'item' item_name  ';';

 item_name     :  (ID | QUOTED_STRING)* ;
 QUOTED_STRING : '"' (options{greedy = false;} : .)* '"';

引用された文字列内に引用符が含まれている場合の対応
- エスケープ
```
 QUOTED_STRING : '"' ('""' |  ~('"'))* '"';
```

普通では使われそうもない引用符を使う（例えば"{:"など）
引用符として使えるものを複数準備する。（"と'を両方使えるようにする）

{}のようにペアになる時だけ使えるやり方（プッシュダウンのみ）

 catalog  : item*;
 item  : 'item' item_name  CONDITION?';';
 CONDITION : NESTED_CONDITION;
 fragment NESTED_CONDITION  : '{' (CONDITION_CHAR | NESTED_CONDITION)* '}';    
 fragment CONDITION_CHAR    : ~('{'|'}') ;

Lexical State

itemの名前を読んでいる間は全く別のレキサに切り替える。
- 例としてFlexを使う。（これはレキサを別のモードにするだけだが、例としては充分）
- 文法としてはJava CUPを用いる

 <YYINITIAL> "item"        {return symbol(K_ITEM);}
 <YYINITIAL> {Word}      {return symbol(WORD);}#br
 <gettingName> {Word} {return symbol(WORD);}#br
 ";"         {return symbol(SEMI);}
 {WS}        {/* ignore */}
 {Comment}   { /* ignore */}

BNF

 catalog  ::= item | catalog item ;

 item_name ::=
   WORD:w {: RESULT = w; :}
   | item_name:n WORD:w {: RESULT = n + " " + w; :}
   ;

 item  ::= K_ITEM
   {: parser.helper.startingItemName(); :}
   item_name:n
   {: parser.helper.recognizedItem(n); :}
   SEMI
   ;

 class ParsingHelper...
     void recognizedItem(String name) {
         items.add(name);
         setLexicalState(Lexer.YYINITIAL);
     }
     public void startingItemName() {
         setLexicalState(Lexer.gettingName);
     }
     private void setLexicalState(int newState) {
         getLexer().yybegin(newState);
     }

先読み問題（CUPは1トークンだけ先読みする）
```
 item item the troublesome
```

SEPの前にecognizedItemを呼び出している

Token Type Mutation

パーサに必要なのはトークンの中身ではなく「型」
この手法は先読みが必須（Antlr記法に戻る）

 catalog  : item*;
 item  : 
   'item' {helper.adjustItemNameTokens();} 
   ID* 
   SEP
   ;
 SEP : ';';

   void adjustItemNameTokens() {
         for (int i = 1; !isEndOfItemName(parser.getTokenStream().LA(i)); i++) {
             assert i < 100 : "This many tokens must mean something's wrong";
             parser.getTokenStream().LT(i).setType(parser.ID);
         }
     }
     private boolean isEndOfItemName(int arg) {
         return (arg == parser.SEP);

しかしこの手法はレキサがパーサに渡したものしか保持されない
HibernateのHQLパーサがこの方式を用いている

Ignoring Token Types

型を無視して、番兵まで全てを読む

 catalog  : item*;
 item : 'item' item_name SEP;
 item_name : ~SEP* ;
 SEP : ';';

Antlrには否定演算子があるが、ない場合は面倒
```
 item   : (ID | 'item')* SEP;
```

II. 使いどころ †

ファウラーへのフィードバック †

担当者のつぶやき †

この辺りは完全に外部DSL処理系の実装パターンですね。どこまでしっかり理解しないといけないのかは、ひとそれぞれかもしれません。
レキサとパーサの関係を押さえた上で、解析方法を一度まとめるとよさそうです。
- と言ってしまうと、自分でやることになるのが最近の傾向ですが。。。

DSL / Alternative Tokenization

Menu

最新の20件

Alternative Tokenization †

一言要約 †

要約 †

I. 仕組み †

II. 使いどころ †

ファウラーへのフィードバック †

担当者のつぶやき †

みんなの突っ込み †

Menu

最新の20件