kazuk は null に触れてしまった

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

月別アーカイブ: 9月 2011

fsyacc/fslex でF#始めました(2) ソース位置情報をトラッキングするパーサー


という訳で連日 F# でfsyacc/fslexです。

今日は位置情報のトラッキングについてです。位置情報は還元アクションにおいて parseState から IParseState で示されるインターフェースによって取得する事が出来ます。

これを ASTのノードに保持する事で、意味フェーズ以降でもソースの位置情報を利用する事ができ、たとえば C# コードを出力するのであれば #line プラグマによって出力ソース上にオリジナルファイルの位置情報をマップしたり、pdb を出力するなら pdb 上のソース位置、はたまた意味フェーズでしか捉えられないエラーをハンドルする為に使用する事が出来ます。

意味フェーズでのエラー、簡単に言えば、以下の変数から変数の代入文

x = y;

これは構文解析フェーズでは、何の型もない事が普通で、型が解決されて初めてエラーが検出できるようになります。(Cのような1パスコンパイラでフォワード宣言を強制すれば、宣言されていない事自体がエラーなので構文解析中に意味情報を利用できる)

この意味フェーズは構文解析は終わった段階で呼び出される為、還元動作で parseState から位置情報は取り出しておき、意味フェーズ以降で利用できるようにしなければなりません。

実際に実用になる言語を作ろうとするとこれは非常に重要な事でエラーがありますで単に停止してしまう処理系はおおよそ役に立ちません。(F#コンパイラは interactive モードをもってるせいかおかげか、この辺若干エラーの報告精度が甘い気がしますけど)

という訳で AST から、基本的には Starter Kit をベースに位置情報の追加をしています。位置情報と若干の色づけを考えて居る為、型名としては AstNode と付けています。

namespace Ast
open System
open Microsoft.FSharp.Text.Lexing
open Microsoft.FSharp.Text.Parsing

type NodeKind =
    | Factor =0
    | Term =1
    | Expr =2
    | Equation =3

type AstNode =
    val nodeKind : NodeKind
    val startPos : Position
    val endPos : Position
    new ( nodeKind:NodeKind, 
          parseState:IParseState, 
          startIndex:int, 
          endIndex:int ) =
        let startPos = parseState.InputStartPosition(startIndex)
        let endPos = parseState.InputEndPosition(endIndex)
        { 
            nodeKind=nodeKind; 
            startPos=startPos; 
            endPos=endPos 
        }

type Factor =
    | Float   of Double * AstNode
    | Integer of Int32 * AstNode
    | ParenEx of Expr * AstNode

and Term =
    | Times  of Term * Factor * AstNode
    | Divide of Term * Factor * AstNode
    | Factor of Factor * AstNode

and Expr =
    | Plus  of Expr * Term * AstNode
    | Minus of Expr * Term * AstNode
    | Term  of Term * AstNode
    
and Equation =
    | Equation of Expr * AstNode

やっている事は単純ですね Position 値を InputStartPosition, InputEndPosition で取ってそれを保存するコンストラクタを定義し、判別共用体の全要素に持たせています。

この AST を得るパーサーは以下の様になります。

%{

open Ast

%}

// The start token becomes a parser function in the compiled code:

%start start

// These are the terminal tokens of the grammar along with the types of

// the data carried by each token:

%token <System.Int32> INT32

%token <System.Double> FLOAT

%token PLUS MINUS ASTER    SLASH

%token LPAREN RPAREN

%token EOF

// This is the type of the data produced by a successful reduction of the ‘start’

// symbol:

%type < Ast.Equation > start

%%

// These are the rules of the grammar along with the F# code of the

// actions executed as rules are reduced.  In this case the actions

// produce data using F# data construction terms.

start: Prog { $1 }

Prog:

    | Expr EOF                   
        { Equation($1, AstNode(NodeKind.Equation,parseState,1,1) ) }

Expr:

    | Expr PLUS  Term           
        { Plus($1, $3, AstNode(NodeKind.Expr,parseState,1,3)) }

    | Expr MINUS Term           
        { Minus($1, $3, AstNode(NodeKind.Expr,parseState,1,3)) }

    | Term                       
        { Term($1, AstNode(NodeKind.Expr,parseState,1,1))      }

Term:

    | Term ASTER Factor           
        { Times($1, $3, AstNode(NodeKind.Term,parseState,1,3))  }

    | Term SLASH Factor           
        { Divide($1, $3, AstNode(NodeKind.Term,parseState,1,3)) }

    | Factor                   
        { Factor($1, AstNode(NodeKind.Term,parseState,1,1))     }

   
Factor:

    | FLOAT                       
        { Float($1, AstNode(NodeKind.Factor,parseState,1,1))  }

    | INT32                       
        { Integer($1, AstNode(NodeKind.Factor,parseState,1,1)) }

    | LPAREN Expr RPAREN       
        { ParenEx($2, AstNode(NodeKind.Factor,parseState,1,3)) }

それぞれの還元アクションで AstNode の要素を生成してタプルに収めているだけですね。十分単純ですが、ちょっと長ったらしくなるのは仕方ないと言えば仕方ない話ですが微妙に残念感が漂います。

ドライブする Program.fs はこんな感じ。 eval では位置情報要らないので捨ててます、そしてツリーの位置情報を表示する為の printHoge メソッドを用意しています。

open System
open Microsoft.FSharp.Text.Lexing
open Microsoft.FSharp.Text.Parsing

open Ast
open Lexer
open Parser

/// Evaluate a factor
let rec evalFactor factor =
    match factor with
    | Float (x, _)   -> x
    | Integer (x, _) -> float x
    | ParenEx (x, _) -> evalExpr x

/// Evaluate a term
and evalTerm term =
    match term with
    | Times (term, fact, _)  -> (evalTerm term) * (evalFactor fact)
    | Divide (term, fact, _) -> (evalTerm term) / (evalFactor fact)
    | Factor (fact, _)       -> evalFactor fact

/// Evaluate an expression
and evalExpr expr =
    match expr with
    | Plus (expr, term, _)  -> (evalExpr expr) + (evalTerm term)
    | Minus (expr, term, _) -> (evalExpr expr) - (evalTerm term)
    | Term (term, _)        -> evalTerm term

/// Evaluate an equation
and evalEquation eq =
    match eq with
    | Equation (expr, _) -> evalExpr expr


let printNode( node:AstNode, indent:int) =
    let s = node.startPos.pos_cnum
    let e = node.endPos.pos_cnum
    let k = Enum.GetName( typeof<Ast.NodeKind>, node.nodeKind )
    let ind = System.String(' ',indent)
    printfn "%s(%s %d %d)" ind k s e

let rec printFactor( factor, indent )=
    match factor with
    | Float ( _, node) -> 
        printNode( node, indent ) 
    | Integer (_, node) -> 
        printNode( node,indent )
    | ParenEx (ex, node) -> 
        printNode( node,indent)
        printExpr( ex,indent+1 )
and printTerm (term,indent) =
    match term with
    | Times (term, fact, node ) -> 
        printNode( node,indent)
        printTerm( term,indent+1)
        printFactor( fact,indent+1)
    | Divide (term, fact, node ) -> 
        printNode( node,indent)
        printTerm( term,indent+1)
        printFactor( fact,indent+1)
    | Factor (fact, node) -> 
        printNode( node,indent)
        printFactor( fact,indent+1)
and printExpr( expr,indent ) =
    match expr with
    | Plus (e,t,node) -> 
        printNode( node,indent)
        printExpr( e,indent+1)
        printTerm( t,indent+1)
    | Minus (e,t,node) -> 
        printNode( node,indent)
        printExpr( e,indent+1)
        printTerm( t,indent+1)
    | Term (t,node) -> 
        printNode( node,indent)
        printTerm( t,indent+1)
and printEqu( equ,indent) =
    match equ with
    | Equation (e,node) -> 
        printNode( node,indent)
        printExpr( e,indent+1);

printfn "Calculator"

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

        readAndProcess()

readAndProcess()

実行結果はこんな感じ。

Calculator

:(20+30)*50

Lexing [(20+30)*50]

Parsing…

(Equation 0 10)

(Expr 0 10)

  (Term 0 10)

   (Term 0 7)

    (Factor 0 7)

     (Expr 1 6)

      (Expr 1 3)

       (Term 1 3)

        (Factor 1 3)

      (Term 4 6)

       (Factor 4 6)

   (Factor 8 10)

Evaluating Equation…

Result: 2500

:

ちゃんと位置情報が取れている事が解ります。 Equation が 0..10 で(20+30)*50 全体、(Factor 0 7) では (20+30) の部分が取り出されている事が解りますね。

これで、このASTの中で意味的におかしいところを見つけたらちゃんと位置を付けて、必要ならばそのソース断片とともに報告する事もできるし、最終的な生成物にシンボル情報を埋め込む事もできそうですね。

fsl ファイルについては Starter からいじってないので割愛!

textual DSL を作るにしてもちゃんとしたコンパイラを作るにしても、「どこがおかしいか解らないエラーが出る」とか使い物になるならないの重要な分岐点なんで、ソース位置情報重要って事でサンプルであんまり書いてない事について書いてみました。

言語書いてる人はこの位置情報と AST上のトークン種別とかの色をマークアップ織り込み処理してVSの中でソースのカラーリングする為の EditorTextClassfier に応用すればVS上でソースがカラー表示できる様になるわけですね。(そこでの選択肢を提供できるようになれば夢のインテリセンス!ですね)

広告

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#の諸先輩方、もっとスマートになるよとか、突っ込みプリーズ。