1

I am writing a perl script to generate .cpp files out of .h files using regular expressions to find functions, then using regex again to break the reults into two peices, the return type and the function.

I created a regular expression to find the return type which almost works.

^(\s*&?\w*\s*(\<{1}.*\>{1})*\s)

Edit: I updated the regex string to one that works better, but still no change as far as this question is concerned.

This works on most cpp prototypes such as

int funky();
int funky(int something);
&int funky(int something);
&int <vector *> funky();

in these cases the regex matches

int
int
&int
&int <vector *>

Which is perfect, however in cases where there is a string that matches inside the function arguments, such as:

int <vector> funky(int <vector> i);
int <vector> funky(int <vector *> i);
int <vector> funky(const int <vector> i);

The regex matches

int <vector> funky(int <vector>
int <vector> funky(int <vector *>
int <vector> funky(const int <vector>

When I want it to return

int <vector>
int <vector>
int <vector>

And I can't figure out whey its continuing past the end of the first closing bracket '>'. I am new to regular expressions and simply can't figure this out.

Sorry of there is an answer out there for this, I searched and haven't been able to find one, probably cause i don't even know what terms to look for :(.

Edit2: If this question is more complicated than I anticipated, could someone explain why it continues on past the first <.*>? I don't see why this doesn't work.

3 Answers 3

3

Regular expressions are great - for regular languages. However, most programming languages are not regular. Everything that has some sort of braces and recursion is a context free language, or even context dependend. (If these CS terms confuse you, look them up on Wikipedia. They are useful).

Especially C has a very complex grammar.

However, Perl's Regexes are not restricted to Regular Expressions. We can express context free grammars, i.e define a set of rules that the string must match. In each rule, we can reference other rules. Because of this, we can do recursion, and things like matching nested parens:

m{
   ^ (?&NESTED_PAREN) $
   (?(DEFINE)
     (?<NESTED_PAREN> [(] (?: [^()]+ | (?&NESTED_PAREN) )* [)] )
   )
}x;

This regex defines a top rule: The whole string from beginning to end has to be a nested paren. Then follows a DEFINE block. We define one rule NESTED_PAREN, that starts with a ( and can contain any number of non-paren characters and nested parens. It is followed by a ). It has to be taken into account that it is easy to write an infinitely recursing grammar, but luckily each recursion will consume characters or fail in this example.

For a nicer interface to write grammars in Perl, I highly recommend Regexp::Grammars from CPAN.

Now we know how to write grammars in Perl and can create one for your function declarations. Here is a symbolic notation without whitespaces:

FUNCTION ::= TYPE VECTOR? NAME '(' ARGUMENTS ')'
VECTOR   ::= '<' vector '*'? '>'
ARGUMENTS::= ( ARGUMENT (',' ARGUMENT)* )?
ARGUMENT ::= TYPE VECTOR? NAME

You may have noticed that we can re-use some of the rules for the function inside the argument list. Now you just have to map this grammar to a set of (DEFINE) rules, write the top-level rule and you are ready to go. Again, using Regexp::Grammars will make this job much more easy, but it provides another language you will have to learn.

See perldoc perlre for the ultimate reference of built-in featurs in Perl regexes.

Please note that, (because of the preprocessor, among other things), the C (and C++) syntax is neither regular nor context-free. Everything short of executing the preprocessor will end up being a nice try…

4
  • Wow, thanks for the in depth answer, but that seems like a lot of new information and learning to get something that seems like it should be relatively simple done, is there no way to limit the regex to just the first case that matches? There is no regex magic i'm missed somewhere that can help me out here? Sep 22, 2012 at 22:05
  • @EricWooley you simply cannot match nested structures like level0 ( level1 (level2)) with a simple regex, but you have to use a grammar like LEVEL ::= 'level' \d (\s '(' LEVEL ')')?. Either your regex recurses, or you recurse manually. If you really want to subject yourself to the horror, the regex /[&]?\w+\s+([<]vector(\s+[*])?[>]\s+)?[a-zA-Z]\w*\s*[(]\s*\w+\s+([<]vector(\s+[*])?[>]\s+)?[a-zA-Z]\w*\s*([,]\s*\w+\s+([<]vector(\s+[*])?[>]\s+)?[a-zA-Z]\w*\s*)*[)]/ will have a better chance of passing your cases, but I dare you to maintain that.
    – amon
    Sep 22, 2012 at 22:22
  • Edit: I can't debug the regex to get it working. I am not suprised, considering that it goes on for three lines.
    – amon
    Sep 22, 2012 at 22:28
  • Yea, but im really not looking for anything with recursiveness. I really just want to match the return type, which for my purposes, is only 1 word and potentially a second string that is covered in brackets may only have 1 level of brackets <.> so simplified its basically "word" or "word <word>" That would suffice. I don't know why it's continuing past that into the function with the brackets. I apologize if i am being particularly dense here. But I'm just not seeing why I can't match such a seemingly simple string without a ton of recursive things. Sep 22, 2012 at 22:29
2

Regular expressions are greedy. Use a ? following your .* to make it non-greedy and it will stop at the first match, rather than the last one.

^(\s*&?\w*\s*(\<{1}.*?\>{1})*\s)

More info at http://perldoc.perl.org/perlre.html#Regular-Expressions:

2
  • My god! you are amazing. I've been trying to figure this out for like 3 hours! Thank you so much. I would give you the up vote if i could! Sep 22, 2012 at 22:42
  • No worries, I would also look into the /x modifier which allows you to add whitespace/comments so you will be better able to understand what's going on when you look at it later. perldoc.perl.org/perlre.html#Extended-Patterns
    – RobEarl
    Sep 22, 2012 at 22:47
1

Here's another way to do it:

/^\s*&?\w*(\s+\<[^\>]+\>)?/

The part in parentheses (\s+\<[^\>]+\>)? is any text starting with spaces, then a "<" followed by any characters that are NOT a ">" (negation character class [^\>]+) and then a ">".

The negation character class with ">" makes sure that the matching will end as soon as the <> part ends. Also the parentheses are followed by a "?" making it an optional part of the expression.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.