Jump to content
  • Advertisement
Sign in to follow this  
andrew111

Reading a context free grammar in c++?

This topic is 3023 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, In c++, I'm reading language like data from text files, and I've decided to use a context free grammar to interpret the data to avoid doing a lot of ifs/elseifs code. I've implemented context free grammars before, using Scala, where the functional and pattern matching aspects made it really easy to do. But I'm at a loss at how to go about it in an imperative language like c++. Has anyone any experience in this? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Sure! ANTLR is a good solution. I'd advise steering clear of boost.spirit, which is too clever by half and too wordy by about 20x.

Share this post


Link to post
Share on other sites
Generally, you use a lexer and parser generator to create C or C++ code that you call from your own code. Use your favorite search engine with the terms "C++ parser generator" and "C++ lexer" to find tools.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Generally, you use a lexer and parser generator to create C or C++ code that you call from your own code. Use your favorite search engine with the terms "C++ parser generator" and "C++ lexer" to find tools.


Oh okay, so it's not as simple as getting a library to do the lexical and syntactical analysis on it and then build a kind of 'source program tree' for me.

Quote:
Original post by Sneftel
Sure! ANTLR is a good solution. I'd advise steering clear of boost.spirit, which is too clever by half and too wordy by about 20x.


So this seems to be an example of what SiCrane was talking about.

I keep away from boost for now.

Thanks!

Share this post


Link to post
Share on other sites
Actually, it would be really useful to have a library to which you give a grammar and a piece of text and it returns a tree. Of course, not knowing the grammar at compile time probably means that it won't be as fast as more traditional solutions, but I am sure there are many applications for which the speed would still be acceptable.

I wonder how hard it would be to implement... Does anyone want to work with me in writing one?

Share this post


Link to post
Share on other sites
If your grammar isn't too large, boost::spirit is an option. I mean it's an option if your grammar is large as well, but in that case I don't recommend it.

Share this post


Link to post
Share on other sites
There's also boost::xpressive which lets you define grammars using recursive regular (but not) expressions.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Actually, it would be really useful to have a library to which you give a grammar and a piece of text and it returns a tree. Of course, not knowing the grammar at compile time probably means that it won't be as fast as more traditional solutions, but I am sure there are many applications for which the speed would still be acceptable.

I wonder how hard it would be to implement... Does anyone want to work with me in writing one?


I wish this existed, would be useful for small things.

It would be hard to do on top of spirit: easy to define a grammar for the grammar specification but then to dynamically generate spirit objects for the target parser from the AST would be hard to do. Spirit.classic used to have "dynamic parsers" which might be the right thing but I think they've been deprecated and I'm not sure it would fit this use case anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Actually, it would be really useful to have a library to which you give a grammar and a piece of text and it returns a tree.
I'm not sure what that would be useful for. With no semantic backend, you wouldn't be able to go any further than the tree. Nevertheless, you can certainly do it.. just pass the output of yacc to tcc.

Share this post


Link to post
Share on other sites
Quote:
Original post by jwezorek
Quote:
Original post by alvaro
Actually, it would be really useful to have a library to which you give a grammar and a piece of text and it returns a tree. Of course, not knowing the grammar at compile time ...<snip>
I wish this existed, would be useful for small things.
Assuming I'm reading you correctly, then this is exactly what boost::xpressive does [smile]. Expressions can be mostly just regex-style strings, so grammars can be combined at run-time; then the result of a match can be returned as an iterable hierarchy of match groups. Don't think that you're limited to regular grammars though, expressions are allowed to be recursive so it's pretty simple to construct context-free grammars too.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!