Home -> Usenet -> comp.databases.theory -> Hierarchical query

Hierarchical query

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: Wed, 13 Jun 2007 09:11:40 -0700
Message-ID: <1181751100.046067.275750_at_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 - 18:11:40 CEST












Original text of this message