kazuk は null に触れてしまった

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

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#始めました(2) ソース位置情報をトラッキングするパーサー」への1件のフィードバック

  1. toshihiro nakamura (@nakamura_to) 2011/09/15 12:22

    位置情報追加したくなりますよね。

    > 十分単純ですが、ちょっと長ったらしくなるのは仕方ないと言えば仕方ない話ですが微妙に残念感が漂います。

    fsyに記述する量をちょっとでも少なくしようとして、自分はヘルパー的な関数を呼び出して処理するようにしたことがあります。
    http://soma.codeplex.com/SourceControl/changeset/view/92cd01182a50#Soma.Core%2fExpressionParser.fsy

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中

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