Flattening hierarchical structure

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Flattening hierarchical structure

Bugzilla from rdmisc@dahlsys.com
Folks,

I'm having a hard time picking up Spirit. If someone could help me with
a very simple parser, it would be much appreciated.

I'm trying to parse grammar like the following:

X = {
    Y = {
        A = "B"
    }
}

This is a group X that contains a group Y. Group Y contains a tag/value
pair. Groups can contain an arbitrary number of groups mixed with
tag/value pairs.

I would like to convert the above to:

Y_A = "B"

So I want to "flatten" the hierarchical structure and display all
tag/value pairs, with just the name of the group that it's in prepended
to the tag name.

As far as I've understood, this is a task for closures. I would use a
closure to bring the name of the group from the group rule to the
tag/value rule. But then, in the tag/value rule, I need to somehow call
my own function with the name of the group (from the closure) and the
tag/value strings, and this is the part I can't find a way to do.
Semantic actions only send the matching string to the function, while I
need to include the group name from the closure.

Later, I will also need to count instances of groups and number the
tags. For instance, if there are two Y groups, both containing an A tag,
the first one might be Y_A01 = "B" and the second Y_A02 = "C". This is
just to say that I will eventually need to do more complex stuff in the
semantic action than just concatenating strings. But for now, if someone
could outline for me how to bring all the required information together
for processing by my code, I would very grateful.

Roger



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Flattening hierarchical structure

Joel de Guzman-2
Roger Dahl wrote:

> Folks,
>
> I'm having a hard time picking up Spirit. If someone could help me with
> a very simple parser, it would be much appreciated.
>
> I'm trying to parse grammar like the following:
>
> X = {
>    Y = {
>        A = "B"
>    }
> }
>
> This is a group X that contains a group Y. Group Y contains a tag/value
> pair. Groups can contain an arbitrary number of groups mixed with
> tag/value pairs.
>
> I would like to convert the above to:
>
> Y_A = "B"
>
> So I want to "flatten" the hierarchical structure and display all
> tag/value pairs, with just the name of the group that it's in prepended
> to the tag name.
>
> As far as I've understood, this is a task for closures. I would use a
> closure to bring the name of the group from the group rule to the
> tag/value rule. But then, in the tag/value rule, I need to somehow call
> my own function with the name of the group (from the closure) and the
> tag/value strings, and this is the part I can't find a way to do.
> Semantic actions only send the matching string to the function, while I
> need to include the group name from the closure.
>
> Later, I will also need to count instances of groups and number the
> tags. For instance, if there are two Y groups, both containing an A tag,
> the first one might be Y_A01 = "B" and the second Y_A02 = "C". This is
> just to say that I will eventually need to do more complex stuff in the
> semantic action than just concatenating strings. But for now, if someone
> could outline for me how to bring all the required information together
> for processing by my code, I would very grateful.

It's good to start with your EBNF grammar. Then later, let's
work on the semantic actions. Please post your grammar.

Cheers,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

bill barry
I'd imagine the (quasi-spiritized) ebnf to be like this:

expr
    =   identifier >> '=' >> ( group | str )
    ;

identifier
    =   lexeme_d
        [
            alpha_p >> *( alphanum_p | '_' )
        ]
    ;

group
    =   '{' >> +expr >> '}'
    ;

str
    =   lexeme_d
        [
            '"' >> ( lex_escape_char_p - '"' ) >> '"'
        ]
    ;

you will probably want this to be inside a grammar.
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Bugzilla from rdmisc@dahlsys.com
In reply to this post by Joel de Guzman-2

>
> It's good to start with your EBNF grammar. Then later, let's
> work on the semantic actions. Please post your grammar.
>
> Cheers,

Hello Joel,

Thank you for Spirit. It looks awesome.

Here's the grammar I have so far:

            top_p = *(group_p | value_p);

            group_p =
                (!(lexeme_d[(+alnum_p)] >> ch_p('=')) >>
                ch_p('{') >> *(group_p | value_p) >> ch_p('}'))
                [&group_action];

            value_p =
                lexeme_d[(+alnum_p)][&valuename_action] >> ch_p('=') >>
                ((lexeme_d[ch_p('"') >> *(anychar_p - ch_p('"')) >>
ch_p('"')])
                [&value_action]);

This does not use closures. At first, I figured that I would need only
semantic actions and a global variable. In the group action, I would
store the name of the group in a global variable and then, in the
key/value action, I would read that variable. But I found that the
action for the group gets called -after- the action for the key/value.
That's when I started looking into closures. But how would I bring the
value from a closure into my own action?

Thanks again for any help.

Roger



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Bugzilla from rdmisc@dahlsys.com
In reply to this post by bill barry
bill barry wrote:

> I'd imagine the (quasi-spiritized) ebnf to be like this:
>
<snip>

Thanks! I hadn't considered having both group and key/value share the
identifier part. That looks more elegant than what I had set up.

Roger


-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Bugzilla from rdmisc@dahlsys.com
In reply to this post by bill barry
bill barry wrote:

> I'd imagine the (quasi-spiritized) ebnf to be like this:
>
<snip>

I changed my grammar to what you suggested and it turns out that it had
the pleasant side effect of enabling my initial approach because now,
the action for the group identifier gets called before the action for
the value. So by pushing identifiers onto a global stack, I now have
access to the "context" required for generating the output I need. I'm
still looking into using closures though, since that would provide for a
solution that would scale better to more complex parsing tasks.

Thanks again,

Roger


-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Flattening hierarchical structure

Joel de Guzman-2
Roger Dahl wrote:

> bill barry wrote:
>
>> I'd imagine the (quasi-spiritized) ebnf to be like this:
>>
> <snip>
>
> I changed my grammar to what you suggested and it turns out that it had
> the pleasant side effect of enabling my initial approach because now,
> the action for the group identifier gets called before the action for
> the value. So by pushing identifiers onto a global stack, I now have
> access to the "context" required for generating the output I need. I'm
> still looking into using closures though, since that would provide for a
> solution that would scale better to more complex parsing tasks.

Well, not really. As always, you can use a stack. I think what
you are doing is fine and has the same effect.

Cheers,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Chadderack
In reply to this post by Bugzilla from rdmisc@dahlsys.com

> This does not use closures. At first, I figured that I would need only
> semantic actions and a global variable. In the group action, I would
> store the name of the group in a global variable and then, in the
> key/value action, I would read that variable. But I found that the
> action for the group gets called -after- the action for the key/value.
> That's when I started looking into closures. But how would I bring the
> value from a closure into my own action?

When you're using closures, the return value from the parser is the FIRST
member (member1) of the closure.

outerrule = innerrule[outerrule.val = phoenix::arg1]  >> (and so on with
your parser, here....)

Then, for any rules enclosing the outerrule, you keep passing phoenix::arg1
back to the outermost rule. Eventually, you just assign that to a variable,
and you have the end value of your parser:

entire_parser[phoenix::var(your_variable) = phoenix::arg1];

Cheers,

Chad



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

bill barry
In reply to this post by Bugzilla from rdmisc@dahlsys.com

On 9/21/05, Roger Dahl <[hidden email]> wrote:
bill barry wrote:

> I'd imagine the (quasi-spiritized) ebnf to be like this:
>
<snip>

Thanks! I hadn't considered having both group and key/value share the
identifier part. That looks more elegant than what I had set up.

Roger

The problem I see with it is that it is ultimately recursive and henceforth cannot be as optimized as something that is not recursive (unless I am wrong and you actually can optimize it like you can a non-recursive grammar).

I would, however, be willing to bet that it could be redesigned with the help of spirit symbol tables and functor parsers so that it is not written recursively (and therefore optimizeable). Unfortunately I'm just not that good yet.

Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Bugzilla from rdmisc@dahlsys.com
In reply to this post by Chadderack
Chadderack wrote:

>When you're using closures, the return value from the parser is the FIRST
>member (member1) of the closure.
>
>outerrule = innerrule[outerrule.val = phoenix::arg1]  >> (and so on with
>your parser, here....)
>
>Then, for any rules enclosing the outerrule, you keep passing phoenix::arg1
>back to the outermost rule. Eventually, you just assign that to a variable,
>and you have the end value of your parser:
>
>entire_parser[phoenix::var(your_variable) = phoenix::arg1];
>
>Cheers,
>
>Chad
>
>  
>
Thank you, Chad. I appreciate the information. If I understand this
correctly, closures are for use only when the entire result of the parse
operation comes down to one single value?

Roger



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Roger Dahl-3
In reply to this post by Joel de Guzman-2
Joel de Guzman wrote:

>> I changed my grammar to what you suggested and it turns out that it
>> had the pleasant side effect of enabling my initial approach because
>> now, the action for the group identifier gets called before the
>> action for the value. So by pushing identifiers onto a global stack,
>> I now have access to the "context" required for generating the output
>> I need. I'm still looking into using closures though, since that
>> would provide for a solution that would scale better to more complex
>> parsing tasks.
>
>
> Well, not really. As always, you can use a stack. I think what
> you are doing is fine and has the same effect.
>
> Cheers,

Thanks again, Joel.

One thing that I hadn't really realized before is that you can put a
semantic action anywhere in the grammar, making pretty much anything
possible even for complex parsing tasks.

I do have one more question in that regard. In my grammar, I needed to
get called when a group is entered. That part of the grammar is simply

ch_p('{')

But I couldn't attach an action to that alone. I got it working by
creating a composite parser by adding this bogus part that will never
match in my grammar like so:

(ch_p('{') >> !ch_p('~'))

Why this limitation?

Roger



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Flattening hierarchical structure

Joel de Guzman-2
In reply to this post by Bugzilla from rdmisc@dahlsys.com
Roger Dahl wrote:

> Chadderack wrote:
>
>> When you're using closures, the return value from the parser is the FIRST
>> member (member1) of the closure.
>>
>> outerrule = innerrule[outerrule.val = phoenix::arg1]  >> (and so on with
>> your parser, here....)
>>
>> Then, for any rules enclosing the outerrule, you keep passing
>> phoenix::arg1
>> back to the outermost rule. Eventually, you just assign that to a
>> variable,
>> and you have the end value of your parser:
>>
>> entire_parser[phoenix::var(your_variable) = phoenix::arg1];
>>
>> Cheers,
>>
>> Chad
>>
>>  
>>
> Thank you, Chad. I appreciate the information. If I understand this
> correctly, closures are for use only when the entire result of the parse
> operation comes down to one single value?

Well, not really. You can return a whole structure or a tuple,
for example. Or, if that's too expensice, you can return a
boost::shared_ptr<structure>.

Cheers,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Flattening hierarchical structure

Joel de Guzman-2
In reply to this post by Roger Dahl-3
Roger Dahl wrote:

> Joel de Guzman wrote:
>
>>> I changed my grammar to what you suggested and it turns out that it
>>> had the pleasant side effect of enabling my initial approach because
>>> now, the action for the group identifier gets called before the
>>> action for the value. So by pushing identifiers onto a global stack,
>>> I now have access to the "context" required for generating the output
>>> I need. I'm still looking into using closures though, since that
>>> would provide for a solution that would scale better to more complex
>>> parsing tasks.
>>
>>
>>
>> Well, not really. As always, you can use a stack. I think what
>> you are doing is fine and has the same effect.
>>
>> Cheers,
>
>
> Thanks again, Joel.
>
> One thing that I hadn't really realized before is that you can put a
> semantic action anywhere in the grammar, making pretty much anything
> possible even for complex parsing tasks.
>
> I do have one more question in that regard. In my grammar, I needed to
> get called when a group is entered. That part of the grammar is simply
>
> ch_p('{')
>
> But I couldn't attach an action to that alone. I got it working by
> creating a composite parser by adding this bogus part that will never
> match in my grammar like so:
>
> (ch_p('{') >> !ch_p('~'))
>
> Why this limitation?

There's no limitation. Remember that the sig for ch_p('{')
is:

     void func(CharT ch);

See "Specialized Actions" in http://tinyurl.com/a2aez

Cheers,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Flattening hierarchical structure

Bugzilla from rdmisc@dahlsys.com
Joel de Guzman wrote:

> There's no limitation. Remember that the sig for ch_p('{')
> is:
>
>     void func(CharT ch);
>
> See "Specialized Actions" in http://tinyurl.com/a2aez
>
> Cheers,

I had missed that part. Man -- this is awesome :)

Roger


-------------------------------------------------------
SF.Net email is sponsored by:
Tame your development challenges with Apache's Geronimo App Server. Download
it for free - -and be entered to win a 42" plasma tv or your very own
Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general