スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#で入門 コンパイラ、インタプリタ編 トークン化(1)

 今回からは、難解プログラミング言語ではなく、一般のプログラミング言語について考えてみます。 
例えばc言語の次のプログラムは 
 
int main(void) 
  puts("Hello, World!"); 
  return 0; 
 
int,main,(,void,),putsなどという語句、が決められたパターンによって並べられています。 
プログラミング言語を考える(作る)場合はまずは、トークン(ソースを構成する語彙(lexicon))とそれの並び方の規則である構文規則について考える必要があります。 
今回はトークンを定義して、ソースをトークン列にわける方法を考えます。 
(処理時間はかかるが、簡単にできる方法でやります。) 
 
まずはトークンを表すクラスを定義します。 
kindは整数とか文字列とか等号とかの、トークンの種別を表す文字列 
imgはソース上での文字列としての表現 
row,colはソース上でのそのトークンの位置を表す行と列です。 
 
> type Token(kind:string,img:string,row:int,col:int) = 
    member this.Kind = kind 
    member this.Img = img 
    member this.Row = row 
    member this.Col = col 
;; 
 
type Token = 
  class 
    new : kind:string * img:string * row:int * col:int -> Token 
    member Col : int 
    member Img : string 
    member Kind : string 
    member Row : int 
  end 
 
どのようなcharctorの並びが、どのトークン種別に属するかを定義するのには、トークン種別名(文字列)と正規表現のタプルで与えることにします。(これをトークンルールタプルと呼ぶことにします。) 
 
例えば数字の並びがトークン種別INTNUMであると定義するには ("INTNUM","\d+")を与えるものとします。 
ではまずは、この形のタプルのリストをプログラムで使う正規表現に変換する関数を定義します。 
 
> open System.Text.RegularExpressions;; 
> let makeTokenizeRules (inDefLst:list<string*string>) = 
    inDefLst 
        |> List.map(fun (name,rgText) ->(name,(new Regex ( @"^(?<sPart>\s*)(?<parts>" + rgText + @")"))));; 
 
val makeTokenizeRules : (string * string) list -> (string * Regex) list 
 
(実行例) 
> makeTokenizeRules [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")]  ;; 
val it : (string * Regex) list = 
  [("INTNUM", ^(?<sPart>\s*)(?<parts>\d+) {Options = None; 
                                           RightToLeft = false;}); 
   ("STR", ^(?<sPart>\s*)(?<parts>"[^"]*") {Options = None; 
                                            RightToLeft = false;}); 
   ("TLE", ^(?<sPart>\s*)(?<parts><=) {Options = None; 
                                       RightToLeft = false;})] 
                                       
                                       
次に部分文字列とトークンルールタプルリストとその部分文字列の全体のソース中での位置(行、列)を与えて、どんどん正規表現にマッチするか調べてゆき、マッチした場合はトークンオブジェクトを返す関数を定義します。 
 
> let tokenizeTopPart (textPart:string) (trl:list<string*Regex>) (row:int) (col:int) = 
    trl 
      |>List.fold (fun (curToken:Token,curLongestLength:int) (name,rg) -> 
                        let wholeMatch = rg.Match(textPart) 
                        let partMatch = wholeMatch.Groups.["parts"]  //必要な部分 
                        let sPartMatch = wholeMatch.Groups.["sPart"] //先頭の空白部分 
                        if wholeMatch.Value.Length > curLongestLength then //最長マッチ 
                            (new Token(name,partMatch.Value,row, col + sPartMatch.Value.Length),wholeMatch.Value.Length ) 
                        else 
                            (curToken,curLongestLength) 
                  ) 
                  (new Token("","",0,0),0);; 
 
val tokenizeTopPart : 
  string -> (string * Regex) list -> int -> int -> Token * int 
 
(実行例) 
> tokenizeTopPart " 23 56 <=" (makeTokenizeRules [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")]) 10 20;; 
val it : Token * int = (FSI_0002+Token {Col = 21; 
                                        Img = "23"; 
                                        Kind = "INTNUM"; 
                                        Row = 10;}, 3) 
 
なおマッチしない場合は     
(FSI_0013+Token {Col = 0; Img = ""  ;Kind = "";      Row = 0;}, 0)という値が返ります。                                     
ここまでは、文字列の先頭だけを取り出していたので、次に一行全部をトークン化していきます。 
まずは 一行をトークン化したときの結果用の型を定義します。 
 
> type TokenizeOneLineResult = 
    |TOLSuccess of list<Token> 
    |TOLFail of int*int //トークン化失敗したときの行と列 
 
    member this.IsSuccess () = 
        match this with 
        |TOLSuccess(_) -> true 
        | _ -> false;; 
 
type TokenizeOneLineResult = 
  | TOLSuccess of Token list 
  | TOLFail of int * int 
  with 
    member IsSuccess : unit -> bool 
  end 
 
次に一行全部をトークン化する関数の定義です。 
 
> let tokenizeOneLine (inDefLst:list<string*string>) (inRow:int) (inOneLineStr:string) = 
    let trs = makeTokenizeRules inDefLst 
    let rec tokenizeOneLineSub (curCol:int) (remainStr:string) res = 
        if remainStr.Trim().Length = 0 then 
            TOLSuccess(List.rev res) 
        else 
           let (slicedToken,length) = tokenizeTopPart remainStr trs inRow curCol 
           if length = 0 then 
                let topBlankNum = remainStr.Length - remainStr.TrimStart().Length 
                TOLFail(inRow,curCol+topBlankNum) 
           else 
              tokenizeOneLineSub (curCol + length) (remainStr.Substring(length)) (slicedToken::res)        
    tokenizeOneLineSub 1 inOneLineStr [];; 
 
val tokenizeOneLine : 
  (string * string) list -> int -> string -> TokenizeOneLineResult 
 
(実行例(成功する場合)) 
> tokenizeOneLine  [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] 5 " 23 \"abc\" <= ";; 
val it : TokenizeOneLineResult =TOLSuccess 
 [FSI_0002+Token {Col = 2;Img = "23";Kind = "INTNUM";Row = 5;};  
FSI_0002+Token {Col = 5; Img = ""abc"";Kind = "STR";Row = 5;}; 
FSI_0002+Token {Col = 11;Img = "<=";Kind = "TLE"; Row = 5;}] 
 
(実行例(失敗する場合))                  
> tokenizeOneLine  [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] 100 " 23 fail  <= ";; 
val it : TokenizeOneLineResult = TOLFail (100,5) 
 
最後にソース全体をトークン化する関数を定義します。 
> let tokenizer (inDefLst:list<string*string>) (source:list<string>) = 
    let oneLineTokenizer = tokenizeOneLine inDefLst 
    let isTOLSuccess (x:TokenizeOneLineResult) = 
        match x with 
        |TOLSuccess(_) -> true 
        |_             -> false 
    let sucLst,failLst = 
        source 
        |>List.map (fun str -> str.TrimEnd()) 
        |>List.mapi (fun i str -> oneLineTokenizer (i+1) str ) 
        |>List.partition (fun tr -> tr.IsSuccess () ) 
    if failLst.Length > 0 then  
        failwith (sprintf "%A" failLst) 
    else  
        sucLst 
          |>List.map (fun tolr -> match tolr with 
                                     |TOLSuccess(tol) -> tol 
                                     | _ -> failwith "error" //これは起こらない 
                     ) 
          |>List.fold (fun s lst -> s @ lst) [];; 
 
val tokenizer : (string * string) list -> string list -> Token list 
 
(実行例(成功する場合) 
tokenizer [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] [" 23 <= ";"\"abc\"  89"];; 
結果 Token list = [FSI_0002+Token {Col = 2;Img = "23";Kind = "INTNUM"; Row = 1;};FSI_0002+Token {Col = 5;Img = "<=";Kind = "TLE"; Row = 1;}; 
                   FSI_0002+Token {Col = 1;Img = ""abc"";Kind = "STR";Row = 2;}; FSI_0002+Token {Col = 8;Img = "89"; Kind = "INTNUM";Row = 2;}] 
 
(実行例(失敗する場合)) 
tokenizer [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] [" <<< <= ";" 23 fail  <= "];; 
結果 System.Exception: [TOLFail (1,2); TOLFail (2,5)] 
 
ではこれをクラス化しておいて今回はおしまいにします。 
 
> open System.Text.RegularExpressions 
 
type Token(kind:string,img:string,row:int,col:int) = 
    member this.Kind = kind 
    member this.Img = img 
    member this.Row = row 
    member this.Col = col 
 
//一行をトークン化したときの結果用の型 
type TokenizeOneLineResult = 
    |TOLSuccess of list<Token> 
    |TOLFail of int*int //トークン化失敗したときの行と列 
 
    member this.IsSuccess () = 
        match this with 
        |TOLSuccess(_) -> true 
        | _ -> false 
 
type TokenizerFactory (defLst:list<string*string>) = 
    //makeTokenizeRules [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")]    
    //結果val it : (string * Regex) list = [("INTNUM", ^(?<sPart>\s*)(?<parts>\d+)以下略 (sPartは先頭の空白用)  
    let makeTokenizeRules (inDefLst:list<string*string>) = 
        inDefLst 
            |> List.map(fun (name,rgText) ->(name,(new Regex ( @"^(?<sPart>\s*)(?<parts>" + rgText + @")")))) 
     
    //tokenizeTopPart " 23 56 <=" (makeTokenizeRules [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")]) 10 20 
    //結果(どれかにマッチする場合)   Token * int = (FSI_0013+Token {Col = 21;Img = "23";Kind = "INTNUM";Row = 10;},3) 
    //結果(どれにもマッチしない場合)Token * int = (FSI_0013+Token {Col = 0; Img = ""  ;Kind = "";      Row = 0;}, 0) 
    let tokenizeTopPart (textPart:string) (trl:list<string*Regex>) (row:int) (col:int) = 
        trl 
          |>List.fold (fun (curToken:Token,curLongestLength:int) (name,rg) -> 
                            let wholeMatch = rg.Match(textPart) 
                            let partMatch = wholeMatch.Groups.["parts"]  //必要な部分 
                            let sPartMatch = wholeMatch.Groups.["sPart"] //先頭の空白部分 
                            if wholeMatch.Value.Length > curLongestLength then //最長マッチ 
                                (new Token(name,partMatch.Value,row, col + sPartMatch.Value.Length),wholeMatch.Value.Length ) 
                            else 
                                (curToken,curLongestLength) 
                      ) 
                      (new Token("","",0,0),0) 
 
 
 
    //tokenizeOneLine  [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] 5 " 23 \"abc\" <= " 
    //結果TOLSuccess [FSI_0002+Token {Col = 2;Img = "23";Kind = "INTNUM";Row = 5;};  
    //////////////////FSI_0002+Token {Col = 5; Img = ""abc"";Kind = "STR";Row = 5;}; 
    //////////////////FSI_0002+Token {Col = 11;Img = "<=";Kind = "TLE"; Row = 5;}] 
    //tokenizeOneLine  [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] 100 " 23 fail  <= ";; 
    //結果TOLFail (100,5) 
    let tokenizeOneLine (inDefLst:list<string*string>) (inRow:int) (inOneLineStr:string) = 
        let trs = makeTokenizeRules inDefLst 
        let rec tokenizeOneLineSub (curCol:int) (remainStr:string) res = 
            if remainStr.Trim().Length = 0 then 
                TOLSuccess(List.rev res) 
            else 
               let (slicedToken,length) = tokenizeTopPart remainStr trs inRow curCol 
               if length = 0 then 
                    let topBlankNum = remainStr.Length - remainStr.TrimStart().Length 
                    TOLFail(inRow,curCol+topBlankNum) 
               else 
                  tokenizeOneLineSub (curCol + length) (remainStr.Substring(length)) (slicedToken::res)        
        tokenizeOneLineSub 1 inOneLineStr [] 
 
    //tokenizer [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] [" 23 <= ";"\"abc\"  89"];; 
    //結果 Token list = [FSI_0002+Token {Col = 2;Img = "23";Kind = "INTNUM"; Row = 1;};FSI_0002+Token {Col = 5;Img = "<=";Kind = "TLE"; Row = 1;}; 
    //                   FSI_0002+Token {Col = 1;Img = ""abc"";Kind = "STR";Row = 2;}; FSI_0002+Token {Col = 8;Img = "89"; Kind = "INTNUM";Row = 2;}] 
    //tokenizer [("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")] [" <<< <= ";" 23 fail  <= "];; 
    //結果 System.Exception: [TOLFail (1,2); TOLFail (2,5)] 
    let tokenizer (inDefLst:list<string*string>) (source:list<string>) = 
        let oneLineTokenizer = tokenizeOneLine inDefLst 
        let isTOLSuccess (x:TokenizeOneLineResult) = 
            match x with 
            |TOLSuccess(_) -> true 
            |_             -> false 
        let sucLst,failLst = 
            source 
            |>List.map (fun str -> str.TrimEnd()) 
            |>List.mapi (fun i str -> oneLineTokenizer (i+1) str ) 
            |>List.partition (fun tr -> tr.IsSuccess () ) 
        if failLst.Length > 0 then  
            failwith (sprintf "%A" failLst) 
        else  
            sucLst 
              |>List.map (fun tolr -> match tolr with 
                                         |TOLSuccess(tol) -> tol 
                                         | _ -> failwith "error" //これは起こらない 
                         ) 
              |>List.fold (fun s lst -> s @ lst) [] 
 
 
    member this.GetTokenizer() = 
        tokenizer defLst;; 
 
//クラス定義ここまで 
 
type Token = 
  class 
    new : kind:string * img:string * row:int * col:int -> Token 
    member Col : int 
    member Img : string 
    member Kind : string 
    member Row : int 
  end 
type TokenizeOneLineResult = 
  | TOLSuccess of Token list 
  | TOLFail of int * int 
  with 
    member IsSuccess : unit -> bool 
  end 
type TokenizerFactory = 
  class 
    new : defLst:(string * string) list -> TokenizerFactory 
    member GetTokenizer : unit -> (string list -> Token list) 
  end 
 
(実行例) 
> let tknz = (new TokenizerFactory ([("INTNUM","\d+");("STR","\"[^\"]*\"");("TLE" , @"<=")])).GetTokenizer();; 
 
val tknz : (string list -> Token list) 
 
> tknz [" 23 <= ";"\"abc\"  89"];; 
val it : Token list = 
  [FSI_0014+Token {Col = 2; 
                   Img = "23"; 
                   Kind = "INTNUM"; 
                   Row = 1;}; FSI_0014+Token {Col = 5; 
                                              Img = "<="; 
                                              Kind = "TLE"; 
                                              Row = 1;}; 
   FSI_0014+Token {Col = 1; 
                   Img = ""abc""; 
                   Kind = "STR"; 
                   Row = 2;}; FSI_0014+Token {Col = 8; 
                                              Img = "89"; 
                                              Kind = "INTNUM"; 
                                              Row = 2;}
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。