Re: Hierarchical query

On Jun 14, 9:41 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> On Jun 14, 2:47 am, Jan Hidders <hidd..._at_gmail.com> wrote:
>
> > Are you saying that anything for
> > which one would typically use XPath can be done just as well with
> > regular expressions assuming that the tree is somehow encoded in a
> > string?
>
> A set of strings
>
> > This is clearly not the case for the encoding you gave. Or are
> > you going to extend that? Perhaps also extend the regular expressions
> > a little?
>
> I was going to define tree query in pure language settings, be it
> regular languges, context free grammars, or else.
>
> > Or did you just have a particular query in mind?
>
> Let's start from scratch again with simpler example. Given a grammar
>
> expr :
> expr '+' expr
> | '(' expr ')'
> | '1'
>
> and derivation tree find all the '1's that are nested within a pair of
> brackets. In the example
>
> 1 expr
> 1.1 expr
> 1.1.1 (
> 1.1.2 expr
> 1.1.2.1 expr
> 1.1.2.1.1 1
> 1.1.2.2 +
> 1.1.2.3 expr
> 1.1.2.3.1 1
> 1.1.3 )
> 1.2 +
> 1.2 expr
> 1.2.1 1
>
> the query should return nodes 1.1.2.1.1 and 1.1.2.3.1

Actually, this query is easy in the relational world. For an open parenthesis node, find a parent, and then all the descendants such that ... One may use nested sets encoding, or nested intervals in matrix encoding (where finding parent is much more transparent).

Alternatively, one can build transitively closed relationship of all the token precedences, then finding all the tokens nested inside some pair of parenthesis is expressed via 2 joins query.

So, I have hard time to define a concept of query in pure language settings... Received on Thu Jun 14 2007 - 19:13:27 CEST