Altova Mailing List Archives

Re: Hierarchical query

From: Jan Hidders <hidders@-----.--->
Date: 6/13/2007 10:19:00 AM

On 13 jun, 18:11, Vadim Tropashko <> wrote:
> Reposting with more clarification (as Jan asked).
> Suppose I have a BNFgrammar and a source text parsed into a tree. How
> would I query an
> identifier declaration?
> All the XQuery tutorials (where I went to gather some ideas) start
> with simpleminded examples like browsing all the descendants of /
> bookstore/book (and the bookstore XML design is such wrong idea to
> boot).
> Perhaps some example is needed. A simplified grammar:
> statement_block:
>   'declare'
>   declaration_item_list
>   'begin'
>   statements
>   'end'
> ;
> statements:
>   (statement_block | assignment) statements |
> ;
> assignment:
>   identifier ':=' (identifier | number) ';'
> ;
> declaration_item_list:
>   identifier 'integer' ';'
> ;
> Suppose we parse the following text
> declare      -- token #1
>   i integer;  -- tokens 2,3,4
> begin
>   i := 1;     -- tokens 6,7,8,9
> end;
> So that we get the derivation tree like this:
> 1    statement_block
> 1.1 'declare'   (matches token #1)
> 1.2   declaration_item_list
> 1.2.1  identifier (matches token #2)
> 1.2.2  'integer'  (matches token #3)
> 1.2.3  ';'   (matches token #4)
> 1.3  'begin'  (matches token #5)
> 1.4  statements
> 1.4.1  assignment
>  identifier
>  ':='
>  number
>  ';'
> 1.4.2  statements (matches empty token)
>  1.5  'end';
> Now, given a derivation tree and the leaf node identifier
> corresponding to the token #6 which is variable i, how do we find the
> node 1.2.1 that declares it?

Ok. I'm going to assume the following DTD (in a notation of my own
making to make it a bit more readable) for the syntax tree. (It uses
no attributes to keep things simple):

<stat_bl> --> <decl_kw> <decl_item_list> <begin_kw> <statements>
<semicol_kw> <end-kw>
<decl_kw> --> EMPTY
<begin_kw> --> EMPTY
<end_kw> --> EMPTY
<semicol_kw> --> EMPTY
<statements> --> ( <stat_bl> | <assignment> )+
<assignment> --> <var> <assign_kw> ( <var> | <number> ) <semicol_kw>
<var> --> PCDATA
<assign_kw> --> EMPTY
<number> --> PCDATA
<decl_item_list> --> ( <var> <type> <semicol_kw> )+
<type> --> PCDATA

For starters I'll first do the reverse query, so I will assume there
is a variable $dvar that contains a <var> element that describes a
variable in a declaration. The XPath expression that walks to all the
<var> nodes in an assignment that are in the scope of $dvar is as

(1)  $dvar/(
(2)    ../../statements//assignment/var[string() = $dvar/string()]
(3)        minus
(4)    ../../statements//stat_bl[decl_item_list/var/string() = $dvar/
(5)  )

The idea is quite simple: the path expression in line (2) walks to all
variables that are nested within the statement block of the
declaration $dvar, and the path expression in line (4) subtracts those
for which there is another intermediate declaration that supersedes
the one of $dvar.

Now the query that you asked for, which in some sense simply the
reverse. We assume now that $uvar contains the <var> element that is
used in an assignment and the path expression walks to the <var>
elements in a declaration that binds the <var> element in $uvar:

(1)  $uvar/(
(2)     ancestor::stat_bl/decl_item_list/var[string() = $uvar/
(3)      minus
(4)     ancestor::stat_bl[decl_item_list/var/string() = $uvar/
(5)  )

Of course there are many many different ways of expressing these
queries, but these are the most compact ones I could think of. Note
that I actually didn't have to take into account the order of the
declarations, just how they are nested. But this is because of the way
you defined the syntax and scoping rules. However, if you would extend
the syntax and the scoping rules such that order also maters then
extending the queries to take that into account should not be a big

-- Jan Hidders


These Archives are provided for informational purposes only and have been generated directly from the Altova mailing list archive system and are comprised of the lists set forth on Therefore, Altova does not warrant or guarantee the accuracy, reliability, completeness, usefulness, non-infringement of intellectual property rights, or quality of any content on the Altova Mailing List Archive(s), regardless of who originates that content. You expressly understand and agree that you bear all risks associated with using or relying on that content. Altova will not be liable or responsible in any way for any content posted including, but not limited to, any errors or omissions in content, or for any losses or damage of any kind incurred as a result of the use of or reliance on any content. This disclaimer and limitation on liability is in addition to the disclaimers and limitations contained in the Website Terms of Use and elsewhere on the site.