Hierarchical query

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: Wed, 13 Jun 2007 09:11:40 -0700
Message-ID: <1181751100.046067.275750@z28g2000prd.googlegroups.com>

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? Received on Wed Jun 13 2007 - 11:11:40 CDT