Регулярное выражение для обнаружения замкнутых циклов С++ для циклов while и while

В моем приложении Python мне нужно написать регулярное выражение, которое соответствует циклу С++ for или while, который был прерван точкой с запятой (;). Например, он должен соответствовать этому:

for (int i = 0; i < 10; i++);

... но не это:

for (int i = 0; i < 10; i++)

Это выглядит тривиально с первого взгляда, пока вы не поймете, что текст между открывающей и закрывающей скобками может содержать другую скобку, например:

for (int i = funcA(); i < funcB(); i++);

Я использую модуль python.re. Прямо сейчас мое регулярное выражение выглядит так (я оставил свои комментарии, чтобы вы могли понять это проще):

# 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<balanced>
        # 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*

Это отлично работает для всех вышеперечисленных случаев, но он ломается, как только вы пытаетесь сделать третью часть цикла for, содержать функцию, например:

for (int i = 0; i < 10; doSomethingTo(i));

Я думаю, что это ломается, потому что, как только вы помещаете какой-либо текст между открывающей и закрывающей скобками, "сбалансированная" группа соответствует тому, что содержит текст, и, следовательно, часть (?P=balanced) больше не работает, поскольку она не будет (из-за того, что текст внутри скобки отличается).

В моем коде Python я использую флаги VERBOSE и MULTILINE и создаю регулярное выражение следующим образом:

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<balanced>
        # 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)

Может ли кто-нибудь предложить улучшение этого регулярного выражения? Мне становится слишком сложно, чтобы я опустил голову.

Ответы

Ответ 1

Вы можете написать небольшую, очень простую процедуру, которая делает это, не используя регулярное выражение:

Установите счетчик позиций pos, чтобы он указывал непосредственно перед открывающей скобкой после for или while.
Установите счетчик открытых скобок openBr в 0.
Теперь продолжайте увеличивать pos, читая символы в соответствующих положениях и увеличивая openBr, когда вы видите открывающий кронштейн, и уменьшаете его, когда вы видите закрывающую скобку. Это будет увеличивать его один раз в начале, для первой открытой скобки в "for (", увеличивать и уменьшать некоторые значения для некоторых скобок между ними и возвращать ее к 0, когда скобка for закрывается.
Итак, остановитесь, когда openBr снова 0.

Позицией остановки является ваш замыкающий кронштейн for(...). Теперь вы можете проверить, есть ли точка с запятой или нет.

Ответ 2

Это то, что вам действительно не нужно делать с регулярным выражением. Просто проанализируйте строку по одному символу за раз, отслеживая открывающие/закрывающие круглые скобки.

Если это все, что вы ищете, вам определенно не нужен полноценный лексер/парсер грамматики С++. Если вы хотите практиковать, вы можете написать небольшой рекурсивный-достойный парсер, но даже это немного для соответствия круглых скобок.

Ответ 3

Это отличный пример использования неправильного инструмента для работы. Регулярные выражения не очень хорошо обрабатывают произвольно вложенные подвыборки. Вместо этого вы должны использовать реальный лексер и парсер (грамматику для С++ следует легко найти) и искать неожиданно пустые тела цикла.

Ответ 4

Я бы даже не обратил внимание на содержимое парнеров.

Просто сопоставьте любую строку, начинающуюся с for и заканчивающуюся запятой:

^\t*for.+;$

Если у вас нет операторов for, разделенных на несколько строк, это будет нормально работать?

Ответ 5

Попробуйте это регулярное выражение

^\s*(for|while)\s*
\(
(?P<balanced>
[^()]*
|
(?P=balanced)
\)
\s*;\s

Я удалил обертку \( \) вокруг (?P=balanced) и переместил * за любую последовательность без парнов. У меня была эта работа с boost xpressive и перепровела этот веб-сайт (Xpressive), чтобы обновить мою память.

Ответ 6

Грег абсолютно прав. Такой разбор не может выполняться с помощью регулярных выражений. Я полагаю, что можно создать ужасающее чудовище, которое будет работать во многих случаях, но тогда вы просто столкнетесь с чем-то, что делает.

Вам действительно нужно использовать более традиционные методы парсинга. Например, довольно просто написать рекурсивный достойный парсер, чтобы делать то, что вам нужно.

Ответ 7

Я не знаю, что регулярное выражение будет обрабатывать что-то подобное очень хорошо. Попробуйте что-то вроде этого

line = line.Trim();
if(line.StartsWith("for") && line.EndsWith(";")){
    //your code here
}

Ответ 8

Другая мысль, которая игнорирует круглые скобки и рассматривает for как конструкцию, содержащую три значения с разделителями с запятой:

for\s*\([^;]+;[^;]+;[^;]+\)\s*;

Эта опция работает даже при разбиении на несколько строк (один раз MULTILINE включен), но предполагает, что for ( ... ; ... ; ... ) является единственной допустимой конструкцией, поэтому не будет работать с конструкцией for ( x in y ) или другими отклонениями.

Также предполагается, что в качестве аргументов нет функций, содержащих полуколоны, такие как:

for ( var i = 0; i < ListLen('a;b;c',';') ; i++ );

Является ли это вероятным случаем, зависит от того, что вы на самом деле делаете для этого.

Ответ 9

Не решение Python (возможно, вы могли бы написать обертку...)

Сначала загрузите lexertl (http:/www.benhanson.net/lexertl.html), затем:

#include <algorithm>
#include "lexertl/generator.hpp"
#include <iostream>
#include "lexertl/lookup.hpp"

int main()
{
    lexertl::rules rules_;
    lexertl::state_machine sm_;

    rules_.add_state("FW");
    rules_.add_state("SEMI");
    rules_.add_state("NESTED");

    rules_.add("*", "[/][/].*|[/][*](.|\n)*?[*][/]|[\"](.|\\\")*[\"]",
        rules_.skip(), ".");
    rules_.add("INITIAL", "for\\s*\\([^;]*;[^;]*;|while\\s*\\(",
        rules_.skip(), "FW");
    rules_.add("FW", "\\)", rules_.skip(), "SEMI");
    rules_.add("FW,NESTED", "\\(", ">NESTED");
    rules_.add("NESTED", "\\)", rules_.skip(), "<");
    rules_.add("SEMI", "\\s*;", 1, "INITIAL");
    rules_.add("SEMI", ".|\n", rules_.skip(), "INITIAL");
    lexertl::generator::build (rules_, sm_);

    lexertl::memory_file buff_("main.cpp");
    const char *start_ = buff_.data ();
    const char *end_ = start_ + buff_.size ();
    lexertl::crmatch results_(start_, end_);

    do
    {
        lexertl::lookup(sm_, results_);

        if (results_.id == 1)
        {
            std::cout << "found on line " <<
                std::count(start_, results_.end, '\n') + 1 << '\n';
        }
    } while (results_.id != sm_.eoi());

    return 0;
}

Ответ 10

Как сказал Фрэнк, это лучше всего без регулярного выражения. Здесь (уродливый) однострочный:

match_string = orig_string[orig_string.index("("):len(orig_string)-orig_string[::-1].index(")")]

Соответствие линии тролля, упомянутое в его комментарии:

orig_string = "for (int i = 0; i < 10; doSomethingTo(\"(\"));"
match_string = orig_string[orig_string.index("("):len(orig_string)-orig_string[::-1].index(")")]

возвращает (int i = 0; i < 10; doSomethingTo("("))

Это работает, пропустив строку вперед до тех пор, пока не достигнет первого открытого парота, а затем назад, пока не достигнет первого закрывающего пара. Затем он использует эти два индекса для среза строки.

Ответ 11

Немного опоздал на вечеринку, но я думаю, что регулярные выражения не являются подходящим инструментом для работы.

Проблема в том, что вы столкнетесь с крайними случаями, которые добавят постороннюю сложность к регулярному выражению. @est упомянул пример строки:

for (int i = 0; i < 10; doSomethingTo("("));

Этот строковый литерал содержит (несбалансированную!) Скобку, которая нарушает логику. По-видимому, вы должны игнорировать содержимое строковых литералов. Для этого необходимо учитывать двойные кавычки. Но сами строковые литералы могут содержать двойные кавычки. Например, попробуйте это:

for (int i = 0; i < 10; doSomethingTo("\"(\\"));

Если вы решите это с помощью регулярных выражений, это еще больше усложнит ваш шаблон.

Я думаю, что вам лучше разбирать язык. Например, вы можете использовать инструмент распознавания языков, такой как ANTLR. ANTLR - это инструмент генератора парсеров, который также может генерировать парсер в Python. Вы должны предоставить грамматику, определяющую целевой язык, в вашем случае C++. Уже существует множество грамматик для многих языков, так что вы можете просто взять грамматику C++.

Тогда вы можете легко ходить по дереву синтаксического анализа, поиск пустых заявлений, как в while или for тела цикла.