Hierarchical query

[Vadim Tropashko]

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_ite m_list
'begin'
statements
'end'
;

statements:
(statement_bloc k | assignment) statements |
;

assignment:
identifier ':=' (identifier | number) ';'
;

declaration_ite m_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_ite m_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?

[Jan Hidders]

On 13 jun, 18:11, Vadim Tropashko <vadimtro_inva. [e-mail] te:

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_ite m_list
'begin'
statements
'end'
;

statements:
(statement_bloc k | assignment) statements |
;

assignment:
identifier ':=' (identifier | number) ';'
;

declaration_ite m_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_ite m_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_i tem_list<begin_ kw<statements>
<semicol_kw<e nd-kw>
<decl_kw--EMPTY
<begin_kw--EMPTY
<end_kw--EMPTY
<semicol_kw--EMPTY
<statements--( <stat_bl| <assignment)+
<assignment--<var<assign_k w( <var| <number) <semicol_kw>
<var--PCDATA
<assign_kw--EMPTY
<number--PCDATA
<decl_item_li st--( <var<type<semic ol_kw)+
<type--PCDATA

For starters I'll first do the reverse query, so I will assume there
is a variable $dvar that contains a <varelement that describes a
variable in a declaration. The XPath expression that walks to all the
<varnodes 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 <varelement that is
used in an assignment and the path expression walks to the <var>
elements in a declaration that binds the <varelement 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

[Aloha Kakuikanu]

On Jun 13, 9:19 am, Jan Hidders <hidd...@gmail. comwrote:

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_i tem_list<begin_ kw<statements>
<semicol_kw<e nd-kw>
<decl_kw--EMPTY
<begin_kw--EMPTY
<end_kw--EMPTY
<semicol_kw--EMPTY
<statements--( <stat_bl| <assignment)+
<assignment--<var<assign_k w( <var| <number) <semicol_kw>
<var--PCDATA
<assign_kw--EMPTY
<number--PCDATA
<decl_item_li st--( <var<type<semic ol_kw)+
<type--PCDATA

All right, the DTD is a bastardized [context free?] grammar describing
a language that XML document is an element of. Although the adjectives
"cumbersome " and "ugly" still apply, I grudgingly admit that the idea
that a grammar fits into DTD effortlessly is quite powerful (so I'm
removing the "XML sucks" image from my homepage:-)

For starters I'll first do the reverse query,
so I will assume there
is a variable $dvar that contains a <varelement that describes a
variable in a declaration. The XPath expression that walks to all the
<varnodes 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, ...

I have trouble comprehending this line

(2) ../../statements//assignment/var[string() = $dvar/string()]

should I read it left to right? Then the ".." selects the parent of
the current node, and what is the current node? Or do we start from
some node that mathes "statements ", then go two levels up? The
statement block <stat_blis only one level up!

[Vadim Tropashko]

On Jun 13, 9:19 am, Jan Hidders <hidd...@gmail. comwrote:

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_i tem_list<begin_ kw<statements>
<semicol_kw<e nd-kw>
<decl_kw--EMPTY
<begin_kw--EMPTY
<end_kw--EMPTY
<semicol_kw--EMPTY
<statements--( <stat_bl| <assignment)+
<assignment--<var<assign_k w( <var| <number) <semicol_kw>
<var--PCDATA
<assign_kw--EMPTY
<number--PCDATA
<decl_item_li st--( <var<type<semic ol_kw)+
<type--PCDATA

All right, the DTD is a bastardized [context free?] grammar describing
a language that XML document is an element of. Although the adjectives
"cumbersome " and "ugly" still apply, I grudgingly admit that the idea
that a grammar fits into DTD effortlessly is quite powerful (so I'm
removing the "XML sucks" image from my homepage:-)

For starters I'll first do the reverse query,
so I will assume there
is a variable $dvar that contains a <varelement that describes a
variable in a declaration. The XPath expression that walks to all the
<varnodes 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, ...

I have trouble comprehending this line

(2) ../../statements//assignment/var[string() = $dvar/string()]

should I read it left to right? Then the ".." selects the parent of
the current node, and what is the current node? Or do we start from
some node that mathes "statements ", then go two levels up? The
statement block <stat_blis only one level up!

[Joe Kesselman]

Vadim Tropashko wrote:

I have trouble comprehending this line

(2) ../../statements//assignment/var[string() = $dvar/string()]

should I read it left to right?

Find a good tutorial on XPath. Yes, it evaluates left to right. From the
context node, find its parent; find the parent of that; find its
<statementschil dren; find their <assignmentdesc endants (at any
depth), find their <varchildren whose string value is the same as ...
hmmm. actually I'm not sure what $dvar/string() was intended to mean,
and I don't have time right now to check that.
--
() ASCII Ribbon Campaign | Joe Kesselman
/\ Stamp out HTML e-mail! | System architexture and kinetic poetry

[Vadim Tropashko]

On Jun 13, 9:11 am, Vadim Tropashko <vadimtro_inva. [e-mail]>
wrote:

1 statement_block
1.1 'declare' (matches token #1)
1.2 declaration_ite m_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';

Actually, here is quite simple method. Write down the parse tree as a
set of paths, using grammar varibles and constants (terminals and
nonterminals) as path elements. In the example above we get:

statement_block
statement_block .'declare'
statement_block .declaration_it em_list
statement_block .declaration_it em_list.identif ier"i"
statement_block .declaration_it em_list.'intege r'
.... and so on ...

Query this set with regular expressions.

XML, good bye!

[Jan Hidders]

On 13 jun, 21:10, Vadim Tropashko <vadimtro_inva. [e-mail] te:

On Jun 13, 9:19 am, Jan Hidders <hidd...@gmail. comwrote:

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_i tem_list<begin_ kw<statements>
<semicol_kw<e nd-kw>
<decl_kw--EMPTY
<begin_kw--EMPTY
<end_kw--EMPTY
<semicol_kw--EMPTY
<statements--( <stat_bl| <assignment)+
<assignment--<var<assign_k w( <var| <number) <semicol_kw>
<var--PCDATA
<assign_kw--EMPTY
<number--PCDATA
<decl_item_li st--( <var<type<semic ol_kw)+
<type--PCDATA

All right, the DTD is a bastardized [context free?] grammar describing
a language that XML document is an element of. Although the adjectives
"cumbersome " and "ugly" still apply, I grudgingly admit that the idea
that a grammar fits into DTD effortlessly is quite powerful (so I'm
removing the "XML sucks" image from my homepage:-)

Of course, it combines ugliness with great power. Welcome to the Dark
Side. :-)

For starters I'll first do the reverse query,
so I will assume there
is a variable $dvar that contains a <varelement that describes a
variable in a declaration. The XPath expression that walks to all the
<varnodes 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, ...

I have trouble comprehending this line

(2) ../../statements//assignment/var[string() = $dvar/string()]

should I read it left to right? Then the ".." selects the parent of
the current node, and what is the current node?

First a small correction, the 'minus' I used should actualy be
'except', which has the semantics of the set minus.

What is the current node? Note that the global structure is p_1/(p_2
except p_3) where (p_2 except p_3) means that from the context node
you evaluate p_2 which gives you a set (or rather sequence) of nodes
and from that you subtract the set of nodes that you get when you
evaluate p_3 starting from the context node. So in this case the
"current node" that you ask about is for both subexpressions the same,
namely the node in $dvar.

Btw., if you forget about sequence order, document order and value
comparisons for a moment, the core of XPath is actually a relatively
neat calculus of binary relations:
- p_1/p_2 is the concatenation of binary relations
- p_1[p_2] is the selection of pairs in p_2 whose right-hand side
matches a left-hand side in p_2 (semijoin anyone?)
- p_1 union p_2 is the set union of two binary relations
- p_1 intersect p_2 is the set intersection of two binary relations
- p_1 except p_2 is the set difference between binary relations

Did I mention Tarski already? :-) Of course we had to wait until
XPath2.0 until the three set operations were all allowed everywhere,
but we have them now.

-- Jan Hidders

[Jan Hidders]

On 13 jun, 21:37, Joe Kesselman <keshlam-nos...@comcast. netwrote:

Vadim Tropashko wrote:

I have trouble comprehending this line

(2) ../../statements//assignment/var[string() = $dvar/string()]

should I read it left to right?

Find a good tutorial on XPath. Yes, it evaluates left to right. From the
context node, find its parent; find the parent of that; find its
<statementschil dren; find their <assignmentdesc endants (at any
depth), find their <varchildren whose string value is the same as ...
hmmm. actually I'm not sure what $dvar/string() was intended to mean,
and I don't have time right now to check that.

It retrieves the text node children of the nodes in $dvar. Actually it
is unnecessary, in this case I might just have well have written the
predicate as [. = $dvar].

-- Jan Hidders

[Jan Hidders]

On 13 jun, 22:58, Vadim Tropashko <vadimtro_inva. [e-mail] te:

On Jun 13, 9:11 am, Vadim Tropashko <vadimtro_inva. [e-mail]>
wrote:

1 statement_block
1.1 'declare' (matches token #1)
1.2 declaration_ite m_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';

Actually, here is quite simple method. Write down the parse tree as a
set of paths, using grammar varibles and constants (terminals and
nonterminals) as path elements. In the example above we get:

statement_block
statement_block .'declare'
statement_block .declaration_it em_list
statement_block .declaration_it em_list.identif ier"i"
statement_block .declaration_it em_list.'intege r'
... and so on ...

Query this set with regular expressions.

XML, good bye!

Not so fast. An enumeration of the paths in a tree does not always
give you enough information to reconstruct the tree, so you would be
losing expressive power. Never mind that you ignore the order, which
may be a factor for the scope of declarations.

-- Jan Hidders

[Vadim Tropashko]

On Jun 13, 2:44 pm, Jan Hidders <hidd...@gmail. comwrote:

On 13 jun, 22:58, Vadim Tropashko <vadimtro_inva. [e-mail] te:

On Jun 13, 9:11 am, Vadim Tropashko <vadimtro_inva. [e-mail]>
wrote:

1 statement_block
1.1 'declare' (matches token #1)
1.2 declaration_ite m_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';

Actually, here is quite simple method. Write down the parse tree as a
set of paths, using grammar varibles and constants (terminals and
nonterminals) as path elements. In the example above we get:

statement_block
statement_block .'declare'
statement_block .declaration_it em_list
statement_block .declaration_it em_list.identif ier"i"
statement_block .declaration_it em_list.'intege r'
... and so on ...

Query this set with regular expressions.

XML, good bye!

Not so fast. An enumeration of the paths in a tree does not always
give you enough information to reconstruct the tree, so you would be
losing expressive power. Never mind that you ignore the order, which
may be a factor for the scope of declarations.

Derivation tree was the confusing part. When we query nodes on a tree
what exactly are we doing? Then, your reply was a critical for me
understanding that the tree structure is unnecessary, the derivation
is essentially a language -- a set of words (which includes both
terminals and nonterminals) and this set of words can be quieried
solely with the language theory means. Formally, a query is a language
intersection.

The order on the tree comes from the order in the Kleene algebra, and
of course the information about the order is still there in the
grammar rules (or should I say inequalities?).

The "reqular expression" exclamation in my previous is
oversimplificat ion, of course.