kazuk は null に触れてしまった

C# / .NET 系技術ネタ縛りでお送りしております

fsyacc/fslex でF#始めました(1) リストのパースとそのAST


という訳で、fsyacc/fslexでF#始めました的にこの辺のツールに絡んでF#の基礎からやって行こうかと。

という訳で 整数のカンマ区切りのリストをパースしてみます。

AST は以下の通り。

namespace Ast
open System

type IntegerList =
    val innerList : int list
    new ( value:int ) =
        { innerList = [ value ] }
    new ( original:IntegerList, value:int ) =
        { innerList = original.innerList @ [ value ] }
    override this.ToString() =
        this.innerList.ToString()

型一個だけの簡単な AST です、2つコンストラクタを用意していて、それぞれ int 値一個、もしくはすでに構築済みの IntegerList を受けます。

F# での list の構築は値を [ ] で括るだけです。複数の値の場合にはセミコロンで区切って与える必要があります。

また F# では list @ list で二つのリストの結合が出来ます、これを組み合わせて既存リストの末尾に新しいリストを結合する事で値を追加しています。

これをパースしている fsy 定義は以下

%{
open Ast
%}

%token <System.Int32> INT32
%token COMMA
%token EOF

%start start 
%type < Ast.IntegerList > start %% start: Prog { $1 } Prog: | IntegerList EOF { $1 } IntegerList: | IntegerList COMMA INT32 { IntegerList( $1,$3 ) } | INT32 { IntegerList( $1 ) }

トークンとして INT32 と COMMA , EOFを定義します。 start から解析開始する事の、Ast.IntegerList を返すパーサーです。

単独の INT32 はまず IntegerList に還元されます。続いてカンマと INT32値が現れると、再度 IntegerList に還元されこの還元の繰り返しにより、IntegerList に整数値が蓄積されます。

標準の Calcuratorサンプルでは値のリストが一個も扱われていないのでとりあえずのサンプルとしてリストの扱いまで。

List の要素を class / interface / struct / enum / delegate の定義の判別共用体にすれば定義リストを扱う事ができるようになりますね。

使った fsl は以下の通り。

{
module Lexer
open System
open Parser
open Microsoft.FSharp.Text.Lexing

let lexeme lexbuf =
    LexBuffer<char>.LexemeString lexbuf
}

// These are some regular expression definitions
let digit = ['0'-'9']
let whitespace = [' ' '\t' ]
let newline = ('\n' | '\r' '\n')

rule tokenize = parse
| whitespace    { tokenize lexbuf }
| newline       { tokenize lexbuf }
| ","            { COMMA }
// Operators
| ['-']?digit+    { INT32 (Int32.Parse(lexeme lexbuf)) }
// EOF
| eof            { EOF }

標準の fsl を削って COMMA の定義を足しただけです。ドライバは以下の通り、同様にサンプルを削ってパース結果の ToString を呼ぶ様にしただけです。

open System
open Microsoft.FSharp.Text.Lexing

open Ast
open Lexer
open Parser

printfn "IntegerList"

let rec readAndProcess() =
    printf ":"
    match Console.ReadLine() with
    | "quit" -> ()
    | expr ->
        try
            printfn "Lexing [%s]" expr
            let lexbuff = LexBuffer<char>.FromString(expr)
            
            printfn "Parsing..."
            let list = Parser.start Lexer.tokenize lexbuff
            
            printfn "Result: %s" (list.ToString())
            
        with ex ->
            printfn "Unhandled Exception: %s" ex.Message

        readAndProcess()

readAndProcess()

結果は以下の通り、ちゃんとパースできてますね。

IntegerList

:100,200,300

Lexing [100,200,300]

Parsing…

Result: [100; 200; 300]

:

ASTとParserの部品みたいな物なので、本来的にはなんか include メカニズムとかで何とかしたい気もしないでも無いですね。 %type ディレクティブを使って int list に結合すれば IntegerList クラス自体が無くてもいけそうなんですが、それをすると AST 内にソース位置情報とか持とうとすると破たんすると思われますので今回はせず。

ソース位置情報とかも AST内にもって意味フェーズ以降まで位置情報を引き継ぐ例は今度書こうと思います。

F#の諸先輩方、もっとスマートになるよとか、突っ込みプリーズ。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。