The treexpr library is a Free Software library that applies regular expression concepts to tree structures. It it written in C and has a JNI binding to Java.
SourceForge summary page-- Syntax -- Expr ::= Term | Expr "|" Term Term ::= Factor | Term Factor Factor ::= Symbol | Symbol "*" | "~" | "(" Expr ")" | "(" Expr ")" "*" | Symbol "->" Expr | Symbol ":" String | Symbol Attrs | Symbol Attrs "->" Expr Attrs ::= "<" Attr* ">" Attr ::= Symbol | Symbol "=" String Symbol ::= any alphanumeric string with '_' and '-' String ::= quoted string (skips over \") -- Semantics -- A tree can be thought of as a hierarchical list, each element of the list can have a list of children. Consider the following tree: html / \ head body / / \ title h1 p root list: html list of html's children: head body list of head's children: title list of body's children: h1 p list of h1's chlidren: ~ (where ~ denotes the empty list) list of p's children: ~ By the same token, a tree expression can be thought of as a hierarchical regular expression, each symbol in the expression can have a child expression. The "->" operator binds a child expression to a symbol in the parent expression. If a symbol has no child expression it is equivalent to having a child expression that matches everything. In other words the children of a symbol are ignored if there is no child expression. It can also be said that "->" adds a restriction to the symbol on it's left-hand side: the symbol will only be matched if the symbol's children match the child expression. Other restriction operators are discussed later to improve matching of HTML. Consider the following expressions: These match the tree above: html - matches the root list and ignores html's children html -> head body - also matches html's children and ignores head and body's children html -> (head -> title) body - also matches head's children and ignores title's children html -> (head -> title -> ~) body - also matches title's children html -> (head -> title -> ~) (body -> h1 p) - also matches body's children html -> (head -> title -> ~) (body -> (h1 -> ~) (p -> ~)) - matches the tree exactly These do not match the tree above: body - does not match root list html -> body - matches root list but does not match html's children (must match all) html -> body head - matches root list but html's children are out of order Note the grouping around "->". In the second expression "->" binds the symbol "html" to the expression "head body". In the third expression we want the symbol "head" to be bound to the expression "title" and not "title body" so we must group them together using parenthesis. Tree expressions use the alternation "|" and closure "*" operators from reqular expressions. Consider the following expressions: html* - matches the root list because it consists of zero or more "html" symbols html | xml - matches the root list because it consists of "html" or "xml" html -> (head -> title | title meta) body - matches In addition to the "~" special symbol there is "." which matches any symbol: html -> .* - matches the root list and html's children because html has zero or more html -> .* (body -> .* p .*) .* - matches a tree that has "html" at the root, html has atleast one child named "body", and body has atleast one child named "p". -- Extra restriction operators for HTML matching -- The ":" operator binds a regular expression to a symbol, the symbol matches only if it's contents matches the regular expression. In HTML the only tags that have contents are "text" and "comment". So most of the time it will be used like: p -> text:"ab*c" - matches the HTML '<p>abbbbbc</p>' The "<", "=", and ">" operators are used together to bind a symbol to an attribute list, the symbol matches only if every attribute matches an attribute of the HTML tag. An attribute restriction is a list of name and value pairs. A name without a value is matched only if it appears in the HTML without a value. Consider the following: table <bgcolor="blue"> - matches the HTML '<table bgcolor="blue">' and also the HTML '<table bgcolor="blue" border="1">' foo <bar> - matches the HTML '<foo bar>' but not '<foo bar="">' or '<foo bar="baz">' foo <bar> | foo <bar=".*"> - matches all three It is possible to combine the attribute restriction operators with the "->" operator (for example option <selected> -> text:"blue"), but it is not possible to combine the content restriction operator with the "->" operator (for example text:"blue" -> br) because "text" and "comment" symbols never have children. -- Extracting values from an HTML page -- This section has been up for debate because it can be very confusing. The way we extract strings from the tree expressions is from the contents and attribute rescrictions. These restrictions contain regular expressions that match against some of the data contained in an HTML page. Most regular expression libraries allow you to use something called back references where each parenthasized sub-expression is given a number and the string matching that sub-expression can be referenced later. For example the expression "foo" has no sub-expressions, the expression "fo(o*)" has one sub-expression, namely "o*". When "fo(o*)" is matched against "fooo", the fist sub-expression references the string "oo". The sub-expressions are numbered by the position of their open parenthesis. For example "(b(a)(r))" has three sub-expressions, 1. "b(a)(r)" 2. "a" 3. "r". If a sub-expression matches multiple strings then the last match is what is referenced. For example "(ab|ac)*" matches "ababac" and the string referenced will be "ac". A tree expression can have several regular expressions embedded in it. In order to find a specific sub-expression they are numbered in the order they appear in the tree expression. For example: form -> input<value="([0-9]+)"> text:"." input<value="([0-9]+)"> text:"." input<value="([0-9]+)"> text:"." input<value="([0-9]+)"> input has four sub-expressions. This tree expression would match against an HTML form that might be used for changing an IP address: <form method="POST" action="/cgi-bin/setip"> <input type="text" name="first" value="192"> . <input type="text" name="second" value="168"> . <input type="text" name="third" value="1"> . <input type="text" name="fourth" value="42"> <input type="submit" value="Set IP"> </form> In this case the extracted values will be: 1: "192" 2: "168" 3: "1" 4: "42" It's simple to specify a method for combining the strings together to form a usefull output. For example something like "\1.\2.\3.\4" would produce "192.168.1.42".
/* Example program to output all 1st headings in an HTML document */ /* NB: please tell me if this works, I haven't tested it */ #include <stdio.h> #include <treexpr.h> #include <libxml/HTMLtree.h> #include <libxml/HTMLparser.h> int main( int argc, char **argv ) { const char *expr = "h1 -> text:\"(.*)\""; /* Expression to match */ struct machine *m; /* Pointer to compiled expression */ htmlDocPtr doc; /* Pointer to HTML document */ const char *end; /* end of expression parsed */ int error = 0; /* return code of main */ struct match *z; /* matches returned by document_process */ /* Check command line options */ if( argc != 2 ) { printf( "USAGE: %s <url>\n", argv[0] ); return -1; } /* Parse expression, a pointer to the compiled expression is stored at m */ end = parse_treexpr( expr, &m ); if( end == NULL ) { printf( "Error parsing expression near: %s\n", m->buf ); printf( "Details: %s\n", m->error ); error = -1; goto free_m; } /* Load HTML document from a URL */ doc = htmlReadFile( arg[1], NULL, PARSER_OPTIONS ); if( doc == NULL ) { printf( "Error reading document: %s\n", arg[1] ); error = -1; goto free_m; } /* Search for any matches of the expression */ z = document_process( m, doc ); /* Loop through linked list of matches */ while( z != NULL ) { struct regex_match *re = z->re; /* First subexpression */ int i; puts( "Heading: " ); for( i = re->match.rm_so; i < re->match.rm_eo; i++ ) putchar( re->str[i] ); putchar( '\n' ); z = z->next; /* Consider next match in list */ } /* Free memory allocated by document_process */ free_matches( z ); /* Free memory and return */ xmlFreeDoc( doc ); free_m: free_machine( m ); return error; }