Re: Hierarchical query

On Jun 13, 2:44 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
> On 13 jun, 22:58, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
>
>
>
>
>
> > On Jun 13, 9:11 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com>
> > wrote:
>
> > > 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';
>
> > 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_item_list
> > statement_block.declaration_item_list.identifier"i"
> > statement_block.declaration_item_list.'integer'
> > ... 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 oversimplification, of course. Received on Wed Jun 13 2007 - 23:56:47 CEST