On 13 jun, 18:11, Vadim Tropashko <vadimtro_inva...@yahoo.com> 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
> 1.4.1.1  identifier
> 1.4.1.2  ':='
> 1.4.1.3  number
> 1.4.1.4  ';'
> 1.4.2  statements (matches empty token)
>  1.5  'end';
>
> Now, given a derivation tree and the leaf node identifier 1.4.1.1
> 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
follows:

(1)  $dvar/(
(2)    ../../statements//assignment/var[string() = $dvar/string()]
(3)        minus
(4)    ../../statements//stat_bl[decl_item_list/var/string() = $dvar/
string()]/statements//var
(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/
string()]
(3)      minus
(4)     ancestor::stat_bl[decl_item_list/var/string() = $uvar/
string()]/ancestor::stat_bl/decl_item/var
(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
problem.

-- Jan Hidders