- Boost - lists.boost.org

Interest in a fast lexical analyser compatible with Spirit
by Dave Handley 28 Dec '04

28 Dec '04

A colleague and I are working on a fast lexical analyser designed to work alongside Spirit. We currently have some working prototypes, and as such I thought that I would gauge interest in this library. We plan to produce a DFA based lexical analyser that provides output as a set of iterable polymorphic flyweighted tokens. These could then be provided as input to Spirit instead of character iterators (albeit with the addition of a token_p parser in Spirit). The objectives of our project are as follows: 1) As fast as lex/flex. 2) Simple to use 3) Rules to generate tokens can be provided both statically and dynamically. Static definition would be through an offline pre-process stage much like lex. 4) Easy to interface with Spirit. I understand from Joel's posts below (both on this group and on codeproject) that he is already planning some work to this end. My understanding of expression template based lexers is that they can outperform DFAs under some circumstances, but with other situations DFAs can provide the best performance. I am therefore recommending this in addition to Joel and Eric's work rather than instead of it. Finally, as a taster of the work we are doing, I have performed some rather unscientific and arbitrary performance tests on a 20Mb VRML 1.0 file. The performance of flex, Spirit, and our new library are as follows: flex: < 1 second new library: about 1 second Spirit: 40-50 seconds. These results were produced with no semantic actions to slow down any of the 3 solutions. They are also not conclusive, since we are almost an order of magnitude slower on an Athlon 64 bit machine at present. Dave Handley Relevant posts: Joel de Guzman wrote: >> I guess if you use string literals you'll have this >> problem no matter what, though I'm not sure the use of string literals >> should be a foregone conclusion. If you consider parser generators like >> YACC, they cleanly separate lexical analysis from parsing and the parser >> itself is never working with string literals. > >Again, true. However, one of the original intent of Spirit is to >be usable in micro parsing tasks. When parsing small grammars >like, say, a complex number, you do not want to write a separate >front end lexer. > >Anyway, I do plan to write an optional but separate lexer >sometime. Joel de Guzman wrote: > As for the lexer, I am working with Eric Niebler, author of Greta and >xpressive (google regular expression c++) with the hopes of developing >a powerful expresion template based lexer front end.

6 5

RE: [boost] Interest in a fast lexical analyser compatible
by Dave Handley 28 Dec '04

28 Dec '04

Hartmut Kaiser wrote: >I'm definitely interested to have a look at your library. Besides my >general >interest in Spirit I'd like to try it out as an alternative lexing >component >for Wave. I'm pretty sure this should is interesting for you as well, >because there are implemented already two different lexers, which gives a >good opportunity to compare them in a real environment. I have to confess to not knowing much about Wave, but I would be willing to look in more detail at using this library for Wave. Once we have our first stable version of the software we will be happy to let you have a look at it in more detail. I expect this to happen within the next month or so. >As for a dynamic DFA based lexer Wave already uses the Spirit based SLEX, >but a static DFA based solution is very interesting to look at. Is the DFA >generated at compile time? By static and dynamic, I am meaning compile-time and run-time. The system is designed to generate the DFA at run-time. But we are discussing a method at the moment whereby the same code base could be used to generate code-stubs for compile-time DFA creation. I am keen to support both. >We definitely should try the new upcoming Spirit-2 code base as well, since >it should be a lot faster then the current version. Is it possible to have >a >look at your test code as well? This way we could try to make a comparision >as soon as the Spirit-2 codebase evolves. I would be quite keen to see how Spirit-2 performs on similar tests. If the interest is there, then we will quite happily post the code into the boost yahoo group once we have completed a bit of tidying up in the New Year. We need to put some effort into writing more detailed test cases. At present, we are only directly comparing lexical analysis, and have not looked at the performance of the interface in real detail. We have a desire to properly test the system with a complete parse. To do this I think there are a number of useful test cases: 1) Flex and bison/lex and yacc. 2) Spirit - without any assistance from any lexer. 3) Spirit 2 once available. 4) Our library (called lextl at present) with yacc/bison. 5) Lextl with Spirit. 6) Lextl with Spirit 2. Case 1 would be the control - and the target performance for other cases to achieve. I am confident that case 4 should achieve the same speed, also I think there is a good likelihood of cases 5 and 6 achieving the same speed. The key question is whether 5 outperforms 2 and 6 outperforms 3. If this is the case, then I think we have a viable library. My current test file which is a 20Mb VRML1.0 file reduces to about 2e6 tokens when whitespace is stripped and the file is lexed. By using flyweighted tokens, we are hoping to reduce the overhead for Spirit to parse tokens instead of characters to a minimum, so the reduction from 2e7 to 2e6 input entities should give an order of magnitude speed increase to Spirit. At least that is my hope :-) Dave Handley

3 2

Interest in a fast lexical analyser compatible with Spirit
by Dave Handley 28 Dec '04

28 Dec '04

Christopher Diggins wrote: >Hi David, I will write the grammar for you. I am just finishing up version >2.0 of YARD, and then I will post the equivalent YARD grammar. Thanks. Hi Christopher - that would be excellent. I've had a quick look at YARD now, and consider it perfectly feasible to get our library to work with YARD as well. Essentially, all we require is a generic (ie templatised) interface that expects any form of forward iterator. It seems on first inspection that this is exactly what your library requires. Dave Handley

1 0

Re: [jamboost] Re: [boost] Re: #include <...> not in list of dependants
by Roland Schwarz 27 Dec '04

27 Dec '04

Rene Rivera wrote: > > Looking into this.. I don't see a problem on my setup. Specifically > Oops the thread got totally messed up. It is my fault I think, because I did not manage to subscribe to the correct list at the beginning. I crossposted to boost and jamboost. Sorry for this. This is the _last_ crosspost! Please every follow up to go to jamboost only! Back to the original problem: Steps to repduce the described behaviour: 1) Update boost tree from CVS 2) issuing SET TOOLS=vc-7_1 bjam --prefix=C: install 2) Editing the file boost/boost/thread/detail/config.hpp 3) issuing SET TOOLS=vc-7_1 bjam --prefix=C: install does not rebuild the threading library, altough I expected it to. Am I wrong with this expectation? Roland

1 0

[MPL] zip_view documentation bug?
by David Greene 27 Dec '04

27 Dec '04

I think I've found either a bug in zip_view with gcc or a bug in the zip_view docs. If I try to use a zip_view<> in which the sequences are not all of the same length, the compiler goes into "infinite" recursion instantiating at<> templates until it hits the instantiation limit. According to the MPL reference manual, the size<> of the sequence should be the minimum of the size<>es of all the participating sequences. At first I thought this was only a problem when one of the sequences is empty but I was able to reproduce it with populated sequences of varying length. Just two is enough to expose it. This is a problem with gcc 3.2, 3.3 and 3.4. I can work around the problem by using iterator_range<> and copy<> to truncate the sequences before feeding them to zip_view<>. What's supposed to happen in this case? -Dave

2 1

RE: [boost][regex] Bug in regex 1.32 ?
by Jan Hermelink 27 Dec '04

27 Dec '04

>> boost::regex re("x", boost::regex_constants::icase); > That should be: > boost::regex re("x", boost::regex::perl|boost::regex_constants::icase); Or boost::regex re("x", boost::regex::normal | boost::regex::icase) Ok, I have overlooked this statement in the documentation: "A valid value of type syntax_option_type will always have exactly one of the elements normal, basic, extended, awk, grep, egrep, sed or perl set". My fault - Thank you! Jan

1 0

Properties and boost::any / boost::program_options
by Dirk Gregorius 27 Dec '04

27 Dec '04

Dear group, I have a text file which defines several properties. For example: // Properties.txt "Position" "1.0 2.0 3.0" "Color" "1.0 0.0 0.0" "Intensity" "500" I wonder if it is possible to use the Property structure like defined in the boost::any example: // Property from boost::any help file struct Property { Property(); Property( const char* ) // Convinence c'tor for easy use with std::find Property( const std::string&, const boost::any& ); std::string Key; boost::any Value; } typedef std::vector<Property> Properties_t; // Operators for sorting and finding bool operator==( const Property& lhs, const Property& rhs ) { return lhs. Key == rhs.Key; } bool operator<( const Property& lhs, const Property& rhs ) { return lhs. Key < rhs.Key; } I want to do two things. First I like to parse through my text file and simply push_back() the parsed properties as pairs of strings: // The parse function - basically void ParseProperties( std::ifstream& is, Properties_t& properties ) { std::string key, value; while( is ) { is >> key >> value; properties.push_back( Property( key, value ) ); } std::sort( properties.begin(), properties.end() ); } Then later I would like to be able to process the properties like this: // Process the parsed properties... void ProcessProperties( const Properties_t& properties ) { typedef Properties_t::iterator PIter; PIter pos = find( properties.begin(), properties.end(), "Position" ); // Here we need the const char* c'tor if ( pos != properties.end() ) Vector3 position = any_cast<Vector3>( pos->Value ); } 1. Is it possible to use boost::any in this way? If yes - where and how do I have to implement the conversions? 2. If this is not possible could I use boost::programm_options instead for the value type? How and where do I have to implement the conversion here. 3. Would you suggest to define a simple Value class like this when I can not use any boost classes: class Value { public: Value(); Value( const std::string& ) template<typename T> T As(void ) const; private: std::string m_Value; } Are there any rules how to implement such a class? I have very, very few experience with template code. So do I need a traits class to look up the conversions in the As() function or how should a simple class like this be implemented in order to be nicely extendable by a client? I wish you all a nice christmas and a happy new year! Regards, -Dirk

2 1

[boost][regex] Bug in regex 1.32 ?
by Jan Hermelink 27 Dec '04

27 Dec '04

Hello, I think there is a bug in Boost.Regex 1.32.0 with regex_constants::icase. std::string s("xx"); boost::regex re("x", boost::regex_constants::icase); boost::regex_replace(s, re, "a"); The replace yields "axa"; should be "aa" I think. Without the icase flag the replace yields "aa". Thank you Jan

2 1

Re: [boost] Re: thoughts on a GUI component library
by brangdon＠cix.compulink.co.uk 27 Dec '04

27 Dec '04

In-Reply-To: <cqcjii$hs0$1(a)sea.gmane.org> dave(a)boost-consulting.com (David Abrahams) wrote (abridged): > That's okay for simple things, but for any serious printing work you > need to know you're talking to a printer. For example, you may need to > embed postscript in your output stream. Not all printers support postscript, so you'd need to know not just that you were printing, but what kind of printer it was. Although there probably needs to be some kind of abstraction-busting pass-through mechanism, I see it as the exception rather than the rule. Another issue is transparency. My employer's drawing framework supports semi-transparency in the form of an alpha channel. This is used by us for things like anti-aliasing, and by users for subtle colour blends. Some printers can support transparency directly and some cannot. We found we needed a relatively elaborate architecture to hide that detail from application drawing code. I'm a bit concerned about the scope of this boost project. Our drawing framework is pretty huge. -- Dave Harris, Nottingham, UK

13 44

automatic garbage collecting algorithm and its implementation in c++
by yilin yang 27 Dec '04

27 Dec '04

hi, everybody i've just designed and coded a garbage collecting infrastructure named u_canforget. it was uploaded onto the news group at boost.yahoo. the main idea is that we count the reference to track the life-cycle of the given object. as the new operator was overloaded to statisfy this requirement. the other important concept was the reference object. with the syntax represented by the redefined macros, the codes may be written in a very simple way with relationships automatically constructed, objects are freed without delete operater can be realized as well. i would keep tracking this thread, if there are any thought about this algorithm. thx for your advices. your's yilin. --------------------------------- Do You Yahoo!? 150万曲MP3疯狂搜，带您闯入音乐殿堂美女明星应有尽有，搜遍美图、艳图和酷图 1G就是1000兆，雅虎电邮自助扩容！

1 0