JavaScript で XPath の構文木を考えてみる。
またまた
パーサーブームの続編です。
昨日は数式のパーサーを作って、帰り道にいろいろ考えたんですけど、普通の言語で考えると構文木って結構複雑になるんじゃないかなあって思いました。
で、横断歩道で明日 XPath の構文木を考えてみようと思ったわけです。
では、仕様と見比べながら XPath の構文木の構造を考えてみましょう。
仕様読むの大嫌いなんですけど、がんばります。
仕様のリンク
まず、冒頭に
The primary syntactic construct in XPath is the expression. An expression matches the production Expr.
http://www.w3.org/TR/xpath#section-Introduction
とあるので、 XPath 全体は Expr であることが分かります。
では、 Expr を見てみましょう。
Expr
[14] Expr ::= OrExpr
[21] OrExpr ::= AndExpr
| OrExpr 'or' AndExpr
[22] AndExpr ::= EqualityExpr
| AndExpr 'and' EqualityExpr
[23] EqualityExpr ::= RelationalExpr
| EqualityExpr '=' RelationalExpr
| EqualityExpr '!=' RelationalExpr
[24] RelationalExpr ::= AdditiveExpr
| RelationalExpr '<' AdditiveExpr
| RelationalExpr '>' AdditiveExpr
| RelationalExpr '<=' AdditiveExpr
| RelationalExpr '>=' AdditiveExpr
[25] AdditiveExpr ::= MultiplicativeExpr
| AdditiveExpr '+' MultiplicativeExpr
| AdditiveExpr '-' MultiplicativeExpr
[26] MultiplicativeExpr ::= UnaryExpr
| MultiplicativeExpr MultiplyOperator UnaryExpr
| MultiplicativeExpr 'div' UnaryExpr
| MultiplicativeExpr 'mod' UnaryExpr
http://www.w3.org/TR/xpath#NT-Expr
となっています。
なんだか、難しそうですが、よくよく見るとただの二項演算の数式にしかすぎません。
なので、構文木はJavaScript で数式パーサを書いてみた。 - IT戦記で書いたような演算子を分岐点とした UnaryExpr の木になることが分かります。
で、部分木を↓こんな感じのクラスで表現してみた。(JavaScript ではクラスを関数で表現します。)
var BinaryExpr = function(operator, left, right) { this.op = op; this.left = left; this.right = right; };
op を分岐点とした left right の枝を持つ部分木を表現しています。
じゃあ、次は UnaryExpr を見てましょう。
UnaryExpr
[27] UnaryExpr ::= UnionExpr | '-' UnaryExprhttp://www.w3.org/TR/xpath#NT-UnaryExpr
となっています。
これは簡単ですね。- (マイナス)が分岐点で UnaryExpr が枝です。 XPath には + (プラス)の単項演算子がないんですね。
というわけで、この部分木を↓こういうクラスで表現します。
var UnaryExpr = function(op, expr) { this.op = op; this.expr = expr; };
op は - (マイナス)演算子しかありえないんですが、一応データとして持つことにしました。
では、次に UnionExpr を見てみましょう。
UnionExpr
[18] UnionExpr ::= PathExpr | UnionExpr '|' PathExprhttp://www.w3.org/TR/xpath#NT-UnionExpr
| （パイプ）演算子で区切られた PathExpr を表しています。| (パイプ)演算子はその性質から結合順は左右どちらでもいいと思われます（書いてない？）。
UnionExpr では一つの演算子しかないため、複雑な数式のパースを行わず可変数の PathExpr (枝)を持つ部分木として扱います。
で、↓このようなクラスにしてみました。
var UnionExpr = function() { this.paths = []; }; UnionExpr.prototype.path = function(path) { this.paths.push(path); };
次は PathExpr です。
PathExpr
[19] PathExpr ::= LocationPath
| FilterExpr
| FilterExpr '/' RelativeLocationPath
| FilterExpr '//' RelativeLocationPath
[1] LocationPath ::= RelativeLocationPath
| AbsoluteLocationPath
[2] AbsoluteLocationPath ::= '/' RelativeLocationPath?
| AbbreviatedAbsoluteLocationPath
[3] RelativeLocationPath ::= Step
| RelativeLocationPath '/' Step
| AbbreviatedRelativeLocationPath
[10] AbbreviatedAbsoluteLocationPath ::= '//' RelativeLocationPath
[11] AbbreviatedRelativeLocationPath ::= RelativeLocationPath '//' Step
http://www.w3.org/TR/xpath#NT-PathExpr
これも、いろいろややこしく書いてありますが、実はとても簡単です。
要は Step が // か / によって区切られていて、最初に FilterExpr を持っている場合があったり、先頭に // や / を持つものがあるというだけです。
これを↓のようなクラスで表します。
var PathExpr = function(filter) { this.filter = filter; this.steps = []; }; PathExpr.prototype.step = function(op, step) { this.steps.push([op, step]); };
op は (// か / を表します。)と step は基本的にセットで考えて、先頭 step の例外は内部的に特殊な FilterExpr を生成して対応します。
ちなみに、 // は /descendant-or-self::node()/ の省略系だと定義してありますが、別々として扱った方が処理系を書くときに楽な気がした（getElementsByTagName とかあるから）ので別ものとして扱っています。
次は、 FilterExpr です。
FilterExpr
[20] FilterExpr ::= PrimaryExpr | FilterExpr Predicate
[15] PrimaryExpr ::= VariableReference
| '(' Expr ')'
| Literal
| <a class="okeyword" href="g:javascript:keyword:Number">Number</a>
| FunctionCall
http://www.w3.org/TR/xpath#NT-FilterExpr
これは、 FilterExpr は PrimaryExpr のあとに Predicate がいくつも続くという意味です。
PrimaryExpr は VariableReference か Expr か Literal か Number か FunctionCall になります。
ですので、↓のようなクラスで表します。
var FilterExpr = function(primary) { this.primary = primary; this.predicates = []; }; FilterExpr.prototype.predicate = function(predicate) { this.predicates.push(predicate); };
次は、 Step です。
Step
[4] Step ::= AxisSpecifier NodeTest Predicate*
| AbbreviatedStep
[5] AxisSpecifier ::= AxisName '::'
| AbbreviatedAxisSpecifier
[6] AxisName ::= 'ancestor'
| 'ancestor-or-self'
| 'attribute'
| 'child'
| 'descendant'
| 'descendant-or-self'
| 'following'
| 'following-sibling'
| 'namespace'
| 'parent'
| 'preceding'
| 'preceding-sibling'
| 'self'
[7] NodeTest ::= NameTest
| NodeType '(' ')'
| 'processing-instruction' '(' Literal ')'
[12] AbbreviatedStep ::= '.' | '..'
[13] AbbreviatedAxisSpecifier ::= '@'?
http://www.w3.org/TR/xpath#NT-Step
これもかなり複雑に見えますが、 AxisSpecifier と NodeTest を一つ持っていて Predicate を複数持っているにすぎません。
AxisSpecifier は特定の AxisName と AbbreviatedAxisSpecifier しかないので、この部分木に含めてしまいます。
NodeTest は processing-instruction が NodeType だとすると、 NodeType と NameTest の二種類に分けられます。これらのうちのどちらかをこの部分木に持つことになります。
そして、 Predicate は FilterExpr と同様に複数持っています。
これをクラスで書くと↓こうなります。
var Step = function(axis, test) { this.axis = axis; this.test = test; this.predicates = []; }; Step.prototype.predicate = function(predicate) { this.predicates.push(predicate); };
次は Predicate です。
Predicate
[8] Predicate ::= '[' PredicateExpr ']' [9] PredicateExpr ::= Exprhttp://www.w3.org/TR/xpath#NT-Predicate
Predicate は Expr しか持たない部分木なので Predicate は BinaryExpr クラスを用いて表すことにします。
次は、 NodeType です。
NodeType
[38] NodeType ::= 'comment' | 'text' | 'processing-instruction' | 'node'http://www.w3.org/TR/xpath#NT-NodeType
NodeType は Step の項で言ったように名前付きの processing-instruction も含めて考えているので、木には NodeType の名前と processing-instruction だった場合の Literal が含まれます。
クラスは↓こんな感じ
var NodeType = function(type, literal) { this.type = type; this.literal = literal; };
次は NameTest です。
NameTest
[37] NameTest ::= '*' | NCName ':' '*' | QNamehttp://www.w3.org/TR/xpath#NT-NameTest
ここでは、 NameTest の名前だけを保存しています。 QName は Prefix と NCName に分けられるのですが、悩んだ末、木にはそのまま QName で保存することにしました。
↓こんな感じ。
var NameTest = function(name) { this.name = name; };
次は VariableReference
VariableReference
[36] VariableReference ::= '$' QNamehttp://www.w3.org/TR/xpath#NT-VariableReference
これも変数名 QName は Prefix と NCName に分けずにそのまま保存します。
↓こんな感じ
var VariableRefernce = function(name) { this.name = name; };
次は、 Literal です。
Literal
[29] Literal ::= '"' [^"]* '"' | "'" [^']* "'"http://www.w3.org/TR/xpath#NT-Literal
Literal は文字列を表現しているので、そのデータを木に保存します。
↓こんな感じ
var Literal = function(text) { this.text = text; };
次は、 Number です。
Number
[30] Number ::= Digits ('.' Digits?)? | '.' Digits
[31] Digits ::= [0-9]+
http://www.w3.org/TR/xpath#NT-Number
Number は数値を表現しているので、そのデータを木に保存します。
↓こんな感じ
var _Number = function(digit) { this.digit = +digit; };
次は、 FunctionCall です。
FunctionCall
[16] FunctionCall ::= FunctionName '(' ( Argument ( ',' Argument )* )? ')'
[17] Argument ::= Expr
[35] FunctionName ::= QName - NodeType
http://www.w3.org/TR/xpath#NT-FunctionCall
Function は関数名と複数の Argument で出来てると分かります。 Argument は Expr なので BinaryExpr クラスを使います。
↓こんな感じ
var FunctionCall = function(name) { this.name = name; this.arguments = []; }; FunctionCall.prototype.argument = function(argument) { this.arguments.push(argument); };
全部終了！
ふー疲れた＞＜
これで、全部の構文の部分木の構造を定義したかなあ＞＜
まとめ
こうやって全部の構文を見てみて、 XPath って実装の簡単さを考えて作られてるんだなあと分かりました！スバラシス
っていうか、処理系作る時ってこんなやり方でいいのかなあ＞＜
もう、やってみないと分かりません＞＜
がんばります＞＜
