OS X用GigE Visionカメラドライバ - その35

GigE VisionカメラのOS Xドライバを仕上げないといけない。大したことない仕事に時間を取られて、ちょっと時間的に厳しくなってきた。

今日と次回でGEN<i>CAM規格のなかでは異色の存在であるSwissKnife系の実装について考える。こういう数式の解析は、知ってる人には簡単だけど、知らない人には妙に敷居が高い。僕は会社に入ってすぐのころ、たまたまUCSD pascalコンパイラのソースとその解説ドキュメントを見せてもらったことがあって、その構文解析の部分を理解することができたとき、実にうまくできてるなあ、と感心した。懐かしい。これまでその経験が役に立つことはほとんどなかったけど、今でもほいほいと書けることがわかってちょっとうれしい。

いや、それは僕の記憶力が高いからではなくて、スタックの効果さえ理解すれば中身は簡単。ほんとは動作原理を説明してその面白さを伝えたいけど、僕には初心者向けに解説する力も時間もない。残念だけど、雰囲気を見てもらって興味がある人は専門のサイトを参照してもらいたい。

8.2  SwissKnife、Converterの実装

先に実装上の問題としてあげたけどSwissKnifeとConverterの<Formula>エレメントの中にはCスタイルの数式を記述できる。実装上はこれが一番めんどくさくて、しかも規格には「Cスタイル」とあるだけでちゃんと書かれていない（例えばCにはないベキが定義されているのに優先順位の記述がない）ので、あってるかどうかは実際に動作させてGenApiの標準実装と比較しないとわからない。

たとえば僕が最初に使いたいと考えているカメラのXMLファイルには

<IntSwissKnife Name="CalcBytesPerPixel" NameSpace="Custom">
  <pVariable Name="PIXELFORMAT">PixelFormatRegister</pVariable>
  <Formula>((PIXELFORMAT >> 16) & 0xFF) / 8</Formula>
</IntSwissKnife>
<IntSwissKnife Name="CalcPayloadSize" NameSpace="Custom">
  <pVariable Name="WIDTH">Width</pVariable>
  <pVariable Name="HEIGHT">Height</pVariable>
  <pVariable Name="BYPP">CalcBytesPerPixel</pVariable>
  <Formula>WIDTH * HEIGHT * BYPP</Formula>
</IntSwissKnife> 

などとなっている（実体参照は解いた）。

このFormulaエレメントの中身はXMLの形式ではないので、この部分だけのために字句解析と構文解析が独立に必要になる。ここに書ける式は単一の式（評価結果がスカラになる）で、許されている演算子と関数をもう一度書くと

(,)	括弧
+,−,*,/	四則
%	剰余
**	ベキ
&,|,＾,〜	ビット間演算
< > ,=, > , < , <=, >=	論理演算
&&,||	論理積と論理和
<< , >>	左シフト右シフト

条件操作

    <condition> ? <true expr.> : <false expr.>

関数

    SGN,NEG

SwissKnifeの中だけで使える関数（IntSwissKnifeではダメ）

    ATAN,COS,SIN,TAN,ABS,EXP,LN,LG,SQRT,
    TRUNC,FLOOR,CEIL,ROUND(x,presision),
    ASIN,ACOS,SGN,NEG,E,PI

しかない。Cに使われている3項演算子が出てくるが、これはif文の代わりに使え、ということだろう。代入の演算子がないので、最終的な式の値（あるいは型）はノードがどう解釈するかで決まる、ということだろう。

ということで構文要素としては演算子と関数呼び出し（新しい関数の定義ができないので決まった関数を呼ぶだけ）だけで、if文さえないので式の解析としてはぜんぜん難しくなくて、lex/yaccを使うほどではない（もちろん使ってもいいよ、使いたければ）。SwissKnifeの中でプログラミングするわけではないので当然だけど、それだったらやっぱり式の表現もXMLにすればよかったのに、と思ってしまう。なんのためにC式に似せたのか僕には理解できない。

まあ、最初に書いたように僕はコンパイラの構造を勉強したこともあり、またどうせ「なんちゃってMathematica」でlex/yaccを使わずに構文解析を手で書こうと思っていたのでついでにできてしまうだろう、と考えてこの部分だけ先回りして実装してしまうことにする。字句解析と構文解析を別々に考える。

8.2.1  字句解析

字句解析はそれほど難しくない。一番の問題は数値ぐらいで

• 0xで始まる16進数
• 数字で始まる10進整数
• ピリオドと10のベキ（E、あるいはe）を含む浮動小数点数

がちゃんと区別して読み込めればいいのでたいしたことはない。

ひとつずつ文字をスキャンして「 < 」と「 << 」や「 > 」と「 >> 」、「*」と「**」なんかを別のtoken（トークン、単語）として切り出すのは、先に2文字のtokenとして調べて、それがヒットしなければ1文字のtokenとしてチェックするようにすればいい。

もちろんそのためには少なくとも2文字の先読みが必要になるが、文字列バッファの中をたどればいいだけなので、それほどオーバーヘッドは大きくない。

8.2.2  構文解析 - Backus-Naur Form

演算子順位も、ベキ（演算子「**」）が一番高くてこれだけ右側結合（普通、数式ではA^BCはA^(BC)と解釈する）で、あとはCで定義されているのと同じだとすれば難しくない。

演算子順位を考慮してBNFで構文を書き下してみた。こんなぐあいになった。

    <factor>            ::=  <symbol>
                            |<number>
                            | <functionName> "(" <arguments> ")"
                            |"(" <conditionalCheck> ")"
 
    <powerFactor>       ::=  <factor>
                            |<factor> "**" <powerFactor>
 
    <term>              ::=  <powerFactor>
                            |<powerFactor> {<termRest>}*
    
    <termRest>          ::=  "*" <powerFactor>
                            |"/" <powerFactor>
 
    <expression>        ::=  <term>
                            |<term> {<expressionRest>}*

    <expressionRest>    ::=  "+" <term>
                            |"-" <term>
 
    <shiftExpression>   ::=  <expression>
                            |<expression> "<<" <expression>
                            |<expression> ">>" <expression>
 
    <bitExpression>     ::=  <shiftExpression>
                            |<shiftExpression> "&" <shiftExpression>
                            |<shiftExpression> "|" <shiftExpression>
                            |<shiftExpression> "^" <shiftExpression>

    <compareExpression> ::=  <bitExpression>
                            |<bitExpression> "<" <bitExpression>
                            |<bitExpression> "<=" <bitExpression>
                            |<bitExpression> ">" <bitExpression>
                            |<bitExpression> ">=" <bitExpression>
                            |<bitExpression> "<>" <bitExpression>
                            |<bitExpression> "=" <bitExpression>
 
    <logicalExpression> ::=  <compareExpression>
                            |<compareExpression> "&&" <compareExpression>
                            |<compareExpression> "||" <compareExpression>
 
    <conditionalCheck>  ::=  <logicalExpression>
                            |<logicalExpression> "?" <shiftExpression> ":" <shiftExpression>
 
    <aruments>          ::=  <shiftExpression>
                            |<shiftExpression> "," <shiftExpression>

構文規則を使って演算子の優先順位を実装してしまうpascalのコンパイラで使われたスタイルである。非終端記号の名前は適当に書いた。また、終端記号は省略している。

これだとtokenをひとつ先読みして、非終端記号に対応するメソッドをこのまま再帰呼び出しすればいいだけになる。再帰呼び出しを使うとスタックの消費が高いけど、GEN<i>CAMのXMLファイルでそれほど複雑な式が使われるとは思えないので、ぜんぜん問題にはならないだろう。再帰呼び出しはBNFに書いたままコードを書けばいいのでめちゃ簡単になる。

次回はこれをもとに実装コードを書く。