I think Mathematica with its symbolic and pattern-matching capabilites is well suited to tackle parser and tree searching. It's better to check, though. Here are two quick proof-of-concept of the toy engine. One ad-hoc, the other using functional parsers.
It' s readily apparent that every simple selector can be mapped to some form of XMLElement pattern:
"div.aClass[attr='val']" => XMElement["div", {___,"class"->"aClass",___,"attr"->"val", ___},_]
Let's build over this.
Custom solution:
Some patterns and auxiliary functions used throughout the program:
NMSTART = "_" | LetterCharacter;
NMCHAR = "_" | WordCharacter | "-";
IDENT = "-" | NMSTART ~~ NMCHAR ...;
selectorPats = {
"." ~~ val : IDENT :> (Sow["class" -> c_String /; inAttrQ[c, val]];""),
"#" ~~ val : NMCHAR .. :> (Sow["id" -> val]; ""),
"[" ~~ key : IDENT ~~ "=" ~~ "\"" ~~ val : Except["\""] .. ~~ "\"" ~~ "]" :> (Sow[key -> val]; ""),
"[" ~~ key : IDENT ~~ "=" ~~ "'" ~~ val : Except["'"] .. ~~ "'" ~~ "]" :> (Sow[key -> val]; ""),
"[" ~~ key : IDENT ~~ "=" ~~ val : IDENT ~~ "]" :> (Sow[key -> val]; ""),
"[" ~~ key : IDENT ~~ "]" :> (Sow[key -> _]; "")
};
inAttrQ = #1 === #2 || StringMatchQ[#1,
{StartOfString, Whitespace, __ ~~ Whitespace} ~~ #2 ~~ {Whitespace, Whitespace ~~ __, EndOfString}
] &;
hasAttrsQ[attrs_List, r_List] := MemberQ[attrs, #] & /@ r /. {b__} :> And[b];
cleanAttr[str_String] :=
StringReplace[StringTrim@str,
{StartOfString ~~ Shortest[key__] ~~ "=" ~~ val__ ~~ EndOfString :> StringTrim@key <> "=" <> StringTrim@val}]
toXMLElement translates simpleSelector strings into XMLElement[...] patterns:
toXMLElement[str_String] :=
Module{attrs = _, tag = _, sel = StringTrim@str},
StringLength@sel === 0 && Return[$Failed];
sel = StringReplace[sel, "*" ~~ val : Except["*"] .. :> val];
sel = StringReplace[sel, StartOfString ~~ type : IDENT :> (tag = type; "")];
attrs = Rest@Reap[sel = StringReplace[sel, selectorPats]] // Flatten;
(sel =!= "" && sel =!= "*" && attrs === {}) && Return[$Failed];
XMLElement[
tag,
Switch[attrs,
{}, _,
{_}, {___, attrs[[1]], ___},
_, Condition @@ {a : {__}, hasAttrsQ[a, attrs]}],
_]
]
parseSelector is an ad-hoc lexer/parser to translate the selector into a list of patterns: {pat1, {combinator2, pat2}, {combinator3, pat3}, ...}
parseSelector[str_String] :=
Module[{f, n = 0},
Replace[
GatherBy[
StringSplit[str, {
"[" ~~ attr :Except["]"] ... ~~ "]" :> "[" ~~ cleanAttr[attr] ~~ "]",
WhitespaceCharacter ... ~~ comb : ">" | "~" | "+" ~~ WhitespaceCharacter ... :> f[comb],
Whitespace -> f[" "]}],
(Head@# === f && ++n; n) &],
{{f[a_], b__} :> {a, toXMLElement@StringJoin@b}, {b__} :> toXMLElement@StringJoin@b}, 1]]
Actual interpreter:
positionSelector[ctx_, sel_String] :=
Fold[positionSelector[ctx, #1, #2] &,
Position[ctx, First@#],
Rest@#
] &@parseSelector[sel]
Auxiliary function to delete descendants of nodes in a list. The list is the result of Position, and thus is ordered depth-first, post-order:
deleteDescendants[col_List] := (Reverse@col //. {lft___, aa : {a__}, b : {__}, rght___} /; (MatchQ[b, {a, __}]) :> {lft, aa, rght}) // Reverse
positionSelector[ctx_, curr_List, {" ", sel_XMLElement}] :=
(With[{ref = Append[#, 3]},
Join[ref, #] & /@ Position[Extract[ctx, ref], sel]
] & /@ deleteDescendants@curr)~Flatten~1
positionSelector[ctx_, curr_List, {">", sel_XMLElement}] :=
(With[{ref = Append[#, 3]},
Join[ref, #] & /@ Position[Extract[ctx, ref], sel, {1}]
] & /@ curr)~Flatten~1
positionSelector[ctx_, curr_List, {"+", sel_XMLElement}] :=
(With[{pos = #[[-1]], container = Drop[#, -1]},
Extract[ctx, container] //
Cases[
Position[#, sel, {1}] /. {n_Integer} /; n <= pos :> Sequence[],
{a_} /; MatchQ[#[[pos + 1 ;; a - 1]], {___String}] :> Append[container, a]
] &
] & /@ curr)~Flatten~1
positionSelector[ctx_, curr_List, {"~", sel_XMLElement}] :=
(With[{pos = #[[-1]], container = Drop[#, -1]},
Join[container, #] & /@
Position[ctx[[Sequence @@ container]], sel, {1}] /. {n_} /; n <= pos :> Sequence[]
] & /@ curr)~Flatten~1
Test:
xml = ImportString["<!doctype html><html><h1>Animals</h1>", "XMLObject"];
positionSelector[xml, "body"]
positionSelector[xml, "*"]
Extract[xml, positionSelector[xml, "h1"]]
(* ==> {{2, 3, 1}} *)
(* ==> {{2, 3, 1, 3, 1}, {2, 3, 1}, {2}} *)
(* ==> {XMLElement["h1", {}, {"Animals"}]} *)
xml = ImportString["<body><div id='abc' class='aClass'>Eh... <b id='b1'><div><span>What's </span>up, <span id='def'>doc?</span>up, <span id='def'>doc?</span></div></b></div><div class='bClass' attr1='val1' attr2='val2'>Legen<div class='cClass'>--<div class='dClass'>Wait for it</div>--</div>Dary!</div><div id='abc'>No. <div attr1='val3'>I <b id='b2'><span>am</span></b> your</div><div> father.</div></div></body>", "XML", "NormalizeWhitespace" -> False];
result = positionSelector[xml, "div>span"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 1, 3, 2, 3, 1, 3, 1}, {2, 3, 1, 3, 2, 3, 1, 3, 3}, {2, 3, 1, 3, 2, 3, 1, 3, 5}} *)
(* ==> ColumnForm[{
XMLElement["span", {}, {"What's "}],
XMLElement["span", {"id" -> "def"}, {"doc?"}],
XMLElement["span", {"id" -> "def"}, {"doc?"}]}] *)
result = positionSelector[xml, "[class]>div"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 2, 3, 2, 3, 2}, {2, 3, 2, 3, 2}} *)
(* ==> ColumnForm[{
XMLElement["div", {"class" -> "dClass"}, {"Wait for it"}],
XMLElement["div", {"class" -> "cClass"}, {"--",
XMLElement["div", {"class" -> "dClass"}, {"Wait for it"}], "--"}]}] *)
xml = ImportString["<!doctype html><html>
<h1>Animals</h1>
<h2 class='animal dog border-collie' id='lillith'><span class='christian Name'>Lillith></span></h2>
<h2 class='animal dog mutt' id='maggie'><span class='christian Name'>Maggie</span><span class='nick Name'>Fatty</span></h2></html>", "XMLObject"];
result = positionSelector[xml, "h2+.dog"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 1, 3, 5}} *)
(* ==> ColumnForm[{
XMLElement["h2", {"class" -> "animal dog mutt", "id" -> "maggie"}, {
XMLElement["span", {"class" -> "christian Name"}, {"Maggie"}],
XMLElement["span", {"class" -> "nick Name"}, {"Fatty"}]}]}] *)
result = positionSelector[xml, "h2+#maggie"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 1, 3, 5}} *)
(* ==> ColumnForm[{
XMLElement["h2", {"class" -> "animal dog mutt", "id" -> "maggie"}, {
XMLElement["span", {"class" -> "christian Name"}, {"Maggie"}],
XMLElement["span", {"class" -> "nick Name"}, {"Fatty"}]}]}] *)
positionSelector[xml, "h1~.dog"]
positionSelector[xml, "h1~b"]
(* ==> {{2, 3, 1, 3, 3}, {2, 3, 1, 3, 5}} *)
(* ==> {} *)
Functional parsers
A more standard approach would be using functional parsers. Here is the lexer/parser using the FunctionalParser library from Anton Antonov, so you don't have to reinvent the wheel.
First, we generate the parsers using a BNF grammar:
Needs["FunctionalParsers`"]
Options[tokenize] = {QuotedStrings -> True, Quotes -> {"'", "\""}, CollapseWhitespace -> True};
tokenize[str_String, terminals : _List : {}, opts : OptionsPattern[]] :=
Module[{
terminalRules = If[TrueQ@OptionValue[CollapseWhitespace], Append[terminals, Whitespace -> " "], terminals],
quoteRules = # ~~ s : Except[#] ... ~~ # :> QuotedString[s, #] & /@ OptionValue[Quotes]},
Replace[
If[TrueQ@OptionValue[QuotedStrings], StringSplit[str, quoteRules], {str}],
s_String :> (StringSplit[s, terminalRules] /. "" -> Sequence[]),
1
] /. {QuotedString[qs_String, q_: "\""] :> Sequence@{q, qs, q}} // Flatten
]
terminalRules = {
"*" -> "*",
"." -> ".",
"#" -> "#",
WhitespaceCharacter ... ~~ ">" ~~ WhitespaceCharacter ... -> ">",
WhitespaceCharacter ... ~~ "~" ~~ WhitespaceCharacter ... -> "~",
WhitespaceCharacter ... ~~ "+" ~~ WhitespaceCharacter ... -> "+",
WhitespaceCharacter ... ~~ "=" ~~ WhitespaceCharacter ... -> "=",
"[" ~~ WhitespaceCharacter ... -> "[",
WhitespaceCharacter ... ~~ "]" -> "]"
};
ClearAll[IAttr, ISimple];
IAttr[{key_String, val_String: ""}] := key -> If[val === "", _, val];
ISimple[{tag_String: "", attrs___Rule}] := XMLElement[
If[tag === "*" || tag === "", _, tag],
Switch[{attrs}, {}, _, {_}, {___, attrs, ___}, _, Condition @@ {a : {__}, hasAttrsQ[a, {attrs}]}],
_];
selectorGrammar = "
<selector> = <simple_selector> , { <comb_selector> } ;
<comb_selector> = <combinator> , <simple_selector> <@ {#[[1]],#[[2]]}& ;
<simple_selector> = [ <type_selector> | '*' ] , { <hash> | <class> | <attrib> } <@ ISimple[Flatten@#]& ;
<combinator> = '+' | '>' | '~' | '?' ;
<type_selector> = '_IdentifierString' ;
<class> = '.' \[RightTriangle] '_WordString' <@ \"class\"\[Rule](a_String/;inAttrQ[a,#])& ;
<hash> = '#' \[RightTriangle] '_IdentifierString' <@ \"id\"\[Rule]#& ;
<attrib> = '[' \[RightTriangle] [ <s> ] \[RightTriangle] '_IdentifierString' , [ '=' \[RightTriangle] ( '_WordString' | <string> ) ] \[LeftTriangle] ']' <@ IAttr[Flatten[#]]& ;
<string1> = '\"' \[RightTriangle] '_String' \[LeftTriangle] '\"' ;
<string2> = \"'\" \[RightTriangle] '_String' \[LeftTriangle] \"'\" ;
<string> = <string1> | <string2> ;
<s> = { '?' } ;
";
code = ToTokens@selectorGrammar /. "'?'" -> "' '";
GenerateParsersFromEBNF[code];
With that in place, we simply need to change the parser in the positionSelector definition:
positionSelectorFP[ctx_, sel_String] :=
Fold[positionSelector[ctx, #1, #2] &,
Position[ctx, First@#]
, Rest@#
] &@(pSELECTOR[Tokenize[sel, terminalRules]]~Flatten~3)
Test:
xml = ImportString["<!doctype html><html><h1>Animals</h1>", "XMLObject"];
positionSelectorFP[xml, "body"]
positionSelectorFP[xml, "*"]
Extract[xml, positionSelectorFP[xml, "h1"]]
(* ==> {{2, 3, 1}} *)
(* ==> {{2, 3, 1, 3, 1}, {2, 3, 1}, {2}} *)
(* ==> {XMLElement["h1", {}, {"Animals"}]} *)
xml = ImportString["<body><div id='abc' class='aClass'>Eh... <b id='b1'><div><span>What's </span>up, <span id='def'>doc?</span>up, <span id='def'>doc?</span></div></b></div><div class='bClass' attr1='val1' attr2='val2'>Legen<div class='cClass'>--<div class='dClass'>Wait for it</div>--</div>Dary!</div><div id='abc'>No. <div attr1='val3'>I <b id='b2'><span>am</span></b> your</div><div> father.</div></div></body>", "XML", "NormalizeWhitespace" -> False];
result = positionSelectorFP[xml, "div>span"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 1, 3, 2, 3, 1, 3, 1}, {2, 3, 1, 3, 2, 3, 1, 3, 3}, {2, 3, 1, 3, 2, 3, 1, 3, 5}} *)
(* ==> ColumnForm[{
XMLElement["span", {}, {"What's "}],
XMLElement["span", {"id" -> "def"}, {"doc?"}],
XMLElement["span", {"id" -> "def"}, {"doc?"}]}] *)
result = positionSelectorFP[xml, "[class]>div"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 2, 3, 2, 3, 2}, {2, 3, 2, 3, 2}} *)
(* ==> ColumnForm[{
XMLElement["div", {"class" -> "dClass"}, {"Wait for it"}],
XMLElement["div", {"class" -> "cClass"}, {"--",
XMLElement["div", {"class" -> "dClass"}, {"Wait for it"}], "--"}]}] *)
xml = ImportString["<!doctype html><html>
<h1>Animals</h1>
<h2 class='animal dog border-collie' id='lillith'><span class='christian Name'>Lillith></span></h2>
<h2 class='animal dog mutt' id='maggie'><span class='christian Name'>Maggie</span><span class='nick Name'>Fatty</span></h2>
</html>", "XMLObject"];
result = positionSelectorFP[xml, "h2+.dog"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 1, 3, 5}} *)
(* ==> ColumnForm[{
XMLElement["h2", {"class" -> "animal dog mutt", "id" -> "maggie"}, {
XMLElement["span", {"class" -> "christian Name"}, {"Maggie"}],
XMLElement["span", {"class" -> "nick Name"}, {"Fatty"}]}]}] *)
result = positionSelectorFP[xml, "h2+#maggie"]
Extract[xml, result] // ColumnForm
(* ==> {{2, 3, 1, 3, 5}} *)
(* ==> ColumnForm[{
XMLElement["h2", {"class" -> "animal dog mutt", "id" -> "maggie"}, {
XMLElement["span", {"class" -> "christian Name"}, {"Maggie"}],
XMLElement["span", {"class" -> "nick Name"}, {"Fatty"}]}]}] *)
positionSelectorFP[xml, "h1~.dog"]
positionSelectorFP[xml, "h1~b"]
(* ==> {{2, 3, 1, 3, 3}, {2, 3, 1, 3, 5}} *)
(* ==> {} *)