Regular expression to detect semi-colon terminated C for while loops

Question

In my Python application  I need to write a regular expression that matches a C   for or while loop that has been terminated with a semi-colon      For example  it should match this   for  int i   0  i  lt  10  i           but not this   for  int i   0  i  lt  10  i      This looks trivial at first glance  until you realise that the text between the opening and closing parenthesis may contain other parenthesis  for example   for  int i   funcA    i  lt  funcB    i       I m using the python re module  Right now my regular expression looks like this  I ve left my comments in so you can understand it easier      match any line that begins with a  for  or  while  statement    s  for while  s        match the initial opening parenthesis       Now make a named group  balanced  which matches a balanced substring        P lt balanced gt            A balanced substring is either something that is not a parenthesis                               or a parenthesised string               A parenthesised string begins with an opening parenthesis               P balanced        followed by a sequence of balanced substrings                 and ends with a closing parenthesis           Look for a sequence of balanced substrings       Finally  the outer closing parenthesis    must end with a semi-colon to match   s   s    This works perfectly for all the above cases  but it breaks as soon as you try and make the third part of the for loop contain a function  like so   for  int i   0  i  lt  10  doSomethingTo i      I think it breaks because as soon as you put some text between the opening and closing parenthesis  the  balanced  group matches that contained text  and thus the   P balanced  part doesn t work any more since it won t match  due to the fact that the text inside the parenthesis is different    In my Python code I m using the VERBOSE and MULTILINE flags  and creating the regular expression like so   REGEX STR   r     match any line that begins with a  for  or  while  statement    s  for while  s        match the initial opening parenthesis       Now make a named group  balanced  which matches       a balanced substring        P lt balanced gt            A balanced substring is either something that is not a parenthesis                               or a parenthesised string               A parenthesised string begins with an opening parenthesis               P balanced        followed by a sequence of balanced substrings                 and ends with a closing parenthesis           Look for a sequence of balanced substrings       Finally  the outer closing parenthesis    must end with a semi-colon to match   s   s      REGEX OBJ   re compile REGEX STR  re MULTILINE  re VERBOSE    Can anyone suggest an improvement to this regular expression  It s getting too complicated for me to get my head around

User · Accepted Answer

You could write a little  very simple routine that does it  without using a regular expression    Set a position counter pos so that is points to just before the opening bracket after your for or while   Set an open brackets counter openBr to 0  Now keep incrementing pos  reading the characters at the respective positions  and increment openBr when you see an opening bracket  and decrement it when you see a closing bracket  That will increment it once at the beginning  for the first opening bracket in  for     increment and decrement some more for some brackets in between  and set it back to 0 when your for bracket closes   So  stop when openBr is 0 again    The stopping positon is your closing bracket of for       Now you can check if there is a semicolon following or not

User · Answer

This is a great example of using the wrong tool for the job  Regular expressions do not handle arbitrarily nested sub-matches very well  What you should do instead is use a real lexer and parser  a grammar for C   should be easy to find  and look for unexpectedly empty loop bodies

User · Answer

Greg is absolutely correct   This kind of parsing cannot be done with regular expressions    I suppose it is possible to build some horrendous monstrosity that would work for many cases  but then you ll just run across something that does   You really need to use more traditional parsing techniques    For example  its pretty simple to write a recursive decent parser to do what you need

User · Answer

This is the kind of thing you really shouldn t do with a regular expression  Just parse the string one character at a time  keeping track of opening closing parentheses   If this is all you re looking for  you definitely don t need a full-blown C   grammar lexer parser  If you want practice  you can write a little recursive-decent parser  but even that s a bit much for just matching parentheses

User · Answer

I don t know that regex would handle something like that very well  Try something like this  line   line Trim    if line StartsWith  for    amp  amp  line EndsWith              your code here

User · Answer

Try this regexp    s  for while  s       P lt balanced gt             P balanced      s   s   I removed the wrapping       around   P balanced  and moved the   to behind the any not paren sequence   I have had this work with boost xpressive  and rechecked that website  Xpressive  to refresh my memory

User · Answer

As Frank suggested  this is best without regex  Here s  an ugly  one-liner   match string   orig string orig string index      len orig string -orig string   -1  index         Matching the troll line est mentioned in his comment   orig string    for  int i   0  i  lt  10  doSomethingTo           match string   orig string orig string index      len orig string -orig string   -1  index         returns  int i   0  i  lt  10  doSomethingTo        This works by running through the string forward until it reaches the first open paren  and then backward until it reaches the first closing paren  It then uses these two indices to slice the string

User · Answer

I wouldn t even pay attention to the contents of the parens   Just match any line that starts with for and ends with semi-colon     t for       Unless you ve got for statements split over multiple lines  that will work fine

User · Answer

Another thought that ignores parentheses and treats the for as a construct holding three semicolon-delimited values   for s                       s     This option works even when split over multiple lines  once MULTILINE enabled   but assumes that for                     is the only valid construct  so wouldn t work with a for   x in y   construct  or other deviations   Also assumes that there are no functions containing semi-colons as arguments  such as   for   var i   0  i  lt  ListLen  a b c         i        Whether this is a likely case depends on what you re actually doing this for

User · Answer

A little late to the party  but I think regular expressions are not the right tool for the job   The problem is that you ll come across edge cases which would add extranous complexity to the regular expression   est mentioned an example line   for  int i   0  i  lt  10  doSomethingTo          This string literal contains an  unbalanced   parenthesis  which breaks the logic  Apparently  you must ignore contents of string literals  In order to do this  you must take the double quotes into account  But string literals itself can contain double quotes  For instance  try this   for  int i   0  i  lt  10  doSomethingTo              If you address this using regular expressions  it ll add even more complexity to your pattern   I think you are better off parsing the language  You could  for instance  use a language recognition tool like ANTLR  ANTLR is a parser generator tool  which can also generate a parser in Python  You must provide a grammar defining the target language  in your case C    There are already numerous grammars for many languages out there  so you can just grab the C   grammar   Then you can easily walk the parser tree  searching for empty statements as while or for loop body

[c++] Regular expression to detect semi-colon terminated C++ for & while loops

Examples related to c++

Examples related to python

Examples related to regex

Examples related to parsing

Examples related to recursion