- Boost - lists.boost.org

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

28 Dec '04

Hartmut Kaiser wrote: >I'd be willing to write the interfacing stub to plug your library into >Wave. Thanks - I think this should be relatively easy because we currently use a forward iterator across the tokens in order to generate suitable output for Spirit. Clearly one of the requirements for the Boost community to accept this library in general will probably be meeting the Standard requirements for forward iterators - and I note that this is one of your key requirements in Wave. >The two different lexers I was using in the Wave library were a re2c based >lexer (static switch based lexer, extremly fast and compact) and a SLEX >based lexer (runtime generated DFA). I haven't done serious speed >measurements, but the numbers I've got so far showed similar timings for >both with a slight advantage for re2c (as expected). I'd expect your >library >to be very similar in speed as well. But just out of curiousity I'm very >interested in seeing the static DFA generation version :-) Can these lexers be effectively used with any Spirit grammar? I'll download Wave over the next few days and have a look at how much overlap there is between our library and the lexers within Wave. My plan for the static DFA version (which we haven't fully discussed in our internal design discussions yet so may change significantly), is to use the memento pattern to reflect the internal state of the DFA, along with the production rules. These could then be saved or loaded, or serialised to a C++ file, in a rather similar way to flex. This would mean that the lextl classes would be both an inline and an offline tool. In principle this gives some very desirable advantages: 1) The API remains the same in both compile-time and run-time versions. 2) You can very easily swap between run-time and compile-time versions - for example during development you may use run-time creation to speed up the process of developing a complex grammar, then switch to compile-time for your production release. 3) You have a number of options for compile-time versions. The grammar can be in a configuration file, or compiled into the program directly. >at least you could have used the symbol parser ... <snip> I've changed the Spirit grammar to use the symbol parser, and dropped the time from 40-50 seconds to about 6-7 seconds. Thanks for the tip. >Is there any documentation available? No, I'm sorry, we don't have any documentation at present, because we are still only a little beyond a prototyping stage. We still have to refine the API a little, and complete some optimisation work before we publish an early Alpha. As I said in my original post, I'm trying to gauge interest at the moment, and I'm pleased to see that we are generating a little interest. As a flavour, the current API would result in some code looking like: syntax<> mySyntax; mySyntax.add_rule( rule<token<1> >( "Group" ) ); mySyntax.add_rule( rule<token<2> >( "Separator" ) ); mySyntax.add_rule( rule<token<3> >( "Switch" ) ); // Lots more symbols for the rest of VRML... mySyntax.add_rule( rule<token_float<69> >( "([-+]?((([0-9]+[.]?)|([0-9]*[.][0-9]+))([eE][-+]?[0-9]+)?))" ) ); mySyntax.add_rule( rule<token_string<70> >( "#[^\\n\\r]*[\\n\\r]" ) ); mySyntax.add_rule( rule<token_string<71> >( "\"[^\"\\n\\r]*[\"\\n\\r]" ) ); mySyntax.add_rule( rule<token_string<72> >( "[a-zA-Z_][a-zA-Z0-9_]*" ) ); mySyntax.add_rule( rule<token<73> >( "[ \\t\\n\\r]+" ) ); lexer<> myLexer( mySyntax ); std::ifstream fsp( "test.vrml" ); myLexer.set_source( fsp ); // Also it will have a char iterator interface lexer<>::token_iterator iter = myLexer.begin(); for ( ; iter != myLexer.end(); ++iter ) // Do something with the tokens... ; Essentially you create a syntax to which you add rules. These rules explain the token that will be created by the rule, and a regular expression to be matched. Special versions of tokens exist that will automatically generate a float, int or string from the matched expression. You then construct a lexer off the syntax, set a suitable source input, and then iterate over the tokens. The tokens are polymorphic so you can easily access the type and data, they are statically typed so you can use types to match the tokens, or you can dispatch tokens to functions through a visitor framework. You can also use dynamically typed tokens as well if you want - although you lose much of the benefit of strong typing. I especially like the idea of using visitors to distinguish between tokens. This means that in my example of a VRML file, the long float lists can be handled with a visitor that contains visit functions for a float token, a comma token (note that in vector lists in VRML the elements in a 3D vector are separated by whitespace, and the 3D vectors themselves separated by commas) and a list termination token (eg a "]"). The visitor would then automatically store the floats in a suitable data structure - like a list of 3D vectors. Dave

3 2

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

28 Dec '04

Dick Hadsell wrote: <snip> >disappointed, because I was hoping to use Spirit or something like it, >to give me some independence from Lex/Yacc's dictatorial control of the >input source. >Your project sounds like it would solve the worst of the problems I have >in trying to move to Spirit. The current API we are working with templatises the input so that in theory it will work with any character like input, in much the same way as std::basic_string<>. We are still working on getting the DFA to work generically, rather than just explicitly with char and wchar_t, but I think we should have some success. At present the lexer is strongly typed from this character type in the same way as std::basic_string<> but I don't necessarily see that as a problem. >I broke up the problem into 3 steps. In the first phase the program >uses a Spirit grammar to generate a list of tokens with info similar to <snip> Depending on the type of grammar I think you should easily achieve a 6x or greater performance boost. If the input has long repetitive sections, you could probably further optimise the stage so that the lexer does most of the work - for example if you have long lists of numbers or similar. I'm not sure how well this would work with Spirit until I try it, but it should be possible to switch control part way through a parse to a very quick and efficient parser that just throws the tokens at a visitor until a particular section is finished. I'm sure this could probably be done by writing a new parser type in Spirit. The idea would be to process long lists of numbers or strings or similar, where those lists have a clearly defined end token. 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: >Would you please post the grammar productions you used for Spirit? Would >you >consider testing the yard parser as well, http://yard-parser.sf.net ? Are >there other advantages of your tool over Flex, other than providing a nice >interface to Spirit? The grammar for Spirit was (in a slightly cut down form): keyword = str_p( "Group" ) | str_p( "Separator" ) | //etc.; comment = lexeme_d[ ch_p( '#' ) >> * ( ~chset_p( "\n\r" ) ) >> chset_p( "\n\r" ) ]; stringLiteral = lexeme_d[ ch_p( '\"' ) >> * ( ~chset_p( "\"\n\r" ) ) >> chset_p( "\"\n\r" ) ]; word = lexeme_d[ ( alpha_p | ch_p( '_' ) ) >> * ( alnum_p | ch_p( '_' ) ) ]; floatNum = real_p; vrml = *( keyword | comment | stringLiteral | word | floatNum ); I've cut down the keywords because there are over 60 of them. I would be interested to know if there was any obvious ways to optimise the Spirit parser. Regarding writing a comparitive test for YARD, I will certainly consider it, although I have no experience of using YARD. I've written quite a lot of flex/bison parsers, written a number of Spirit based parsers, and hand coded a number in my time, but I would need to spend a little time learning the YARD framework first. There are a number of advantages over Flex (including a nice interface to Spirit). The key ones are: 1) An extensible object oriented approach to writing the entire system. This can be very useful if you want to handle something like say the parsing of a filename in the lexer. You can simply write a new token type that will split the incoming filename into path, extension, name, etc. This can massively simplify the production of a final parser - allowing you to deal with grammar issues at that stage. 2) DFAs can be created at run-time, or eventually compile-time. 3) The code is considerably less obfuscated than the code produced by flex. Don't get me wrong, I like flex a lot, but the pre-processor directives, and look-up tables in the generated code are pretty unreadable IMHO. Dave Handley

4 3

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