Малое соответствие регулярному выражению nfa, в то время как возможно более крупные совпадения - PullRequest
Новая
       12

Малое соответствие регулярному выражению nfa, в то время как возможно более крупные совпадения

2 голосов
/ 06 мая 2019

Я создаю свой собственный генератор лексического анализатора, похожий на (f) lex. Мой план состоял в том, чтобы сделать инструмент наподобие grep и перейти оттуда. Прямо сейчас я следил за статьями Расса Кокса о создании анализатора в качестве виртуальной машины: https://swtch.com/~rsc/regexp/regexp2.html

Проблема, с которой я столкнулся, заключается в отслеживании небольших совпадений во время выполнения более крупного совпадения. Примером, где это может произойти, является ". * D | ab" во входной строке "abcabcabcabcabcabcd".

В настоящее время у меня работает NFA, которая практически такая же, как у Кокса. Он использует алгоритм Томпсона для вычисления наборов dfa на лету из nfa. Потоки хранятся в разреженном наборе. (Престон Бриггс и Линда Торцзон, статья 1993 г. «Эффективное представление разреженных множеств»)

Потоки, которые появляются ранее в этом списке, имеют большее значение и исключают более поздние потоки при принятии.

Моя текущая реализация может найти слово, соответствующее регулярному выражению, но не может непрерывно продолжать сопоставление. Чтобы показать, что происходит в данный момент, давайте рассмотрим приведенный выше пример регулярного выражения и строки.

Первый шаг состоит из трех нитей. Два для левой стороны союза, один для правой стороны. Только потоки, использующие символы подстановки и 'a', переходят в следующий список.

Шаг второй, снова выдвигаются подстановочный знак, и поток на этот раз принимает 'b'. Он также добавляет новый поток, чтобы попытаться сопоставить этот символ в качестве отправной точки.

Шаг третий продвигает подстановочный знак и переводит поток, выполняющий «ab», в состояние принятия. Теперь более новые (менее приоритетные) потоки удаляются и добавляются новые потоки, чтобы начать сопоставление с этим символом.

Вот здесь и начинается проблема: nfa пока не может вывести совпадение на "ab". Следует подождать, пока ". * D" закончится. Это означает, что для большого входного файла большое количество совпадений должно буферизоваться до тех пор, пока не завершится «. * D» (то есть последний символ, чтобы получить наибольшее возможное совпадение)

Таким образом, фактический вопрос заключается в следующем: каков эффективный способ хранения этих совпадений или есть другой способ не выполнять потенциальную буферизацию всего входного файла?

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

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

По запросу фрагменты кода:

Операционные коды VM, представляющие ". * D | ab": 

0 SPLIT 2, 5
1 ANY
2 SPLIT 1, 3
3 CHAR 'd'
4 JMP 7
5 CHAR 'a'
6 CHAR 'b'
7 ACCEPT

CHAR устанавливает вводимый символ для соответствия первому операнду.

SPLIT создает два новых потока, начиная с первого и второго операнда.

ЛЮБОЙ соответствует любому вводимому символу.

JMP устанавливает счетчик программы на первый операнд.

ACCEPT переводит текущий поток в состояние принятия.

Функция добавления для рекурсивного прохождения кодов операций до достижения кода операции CHAR или ACCEPT и последующего добавления их в следующий список потоков. 

static void recursive_add(struct NFA *nfa, struct Thread *thread)
{
    switch(nfa->code[thread->pc])
    {
        case OPCODE_JMP:
            printf("    |   jmp\n");
            thread->pc = nfa->code[thread->pc + 1];
            recursive_add(nfa, thread);
            break;

        case OPCODE_SPLIT:
        {
            uint16_t pc = thread->pc;
            printf("    |   split: %d op1: %d op2: %d\n", thread->pc, nfa->code[thread->pc + 1], nfa->code[thread->pc + 2]);
            thread->pc = nfa->code[thread->pc + 1];
            recursive_add(nfa, thread);
            thread->pc = nfa->code[pc + 2];
            recursive_add(nfa, thread);
            break;
        }

        case OPCODE_CHAR:   case OPCODE_ACCEPT:
            printf("    |   char/accept %d\n", thread->pc);
            add_sparseset(nfa->nthreads, thread);
            return;

        default:
            fprintf(stderr, "Unexpected opcode %x at program counter %d\n", nfa->code[thread->pc],  thread->pc);
            exit(1);
    }
}

И основной цикл, в настоящее время немного запутанный, но это должно дать лучшее представление о том, что делает код. 

void execute_nfa(struct NFA *nfa)
{
    struct Thread thread;
    struct SparseSet *swap;
    char c;
    for(;;)
    {
        c = getchar();
        printf("Input char %c\n", c);

        //add new starting thread for every character
        thread.pc = 0;
        recursive_add(nfa, &thread);

        clear_sparseset(nfa->cthreads);
        swap = nfa->cthreads;
        nfa->cthreads = nfa->nthreads;
        nfa->nthreads = swap;

        for(unsigned int i = 0; i < nfa->cthreads->size; i++)
        {
            thread = *(((struct Thread *)nfa->cthreads->dense) + i);
            printf("    thread pc: %d\n", thread.pc);
            switch(nfa->code[thread.pc])
            {
                case OPCODE_CHAR:
                    if(nfa->code[thread.pc + 1] == c)
                    {
                        printf("    Add to next\n");
                        thread.pc += 2;
                        recursive_add(nfa, &thread);
                    }
                    break;

                case OPCODE_ACCEPT:
                    printf("    accept (still need to do shit)\n");
                    break;

                default:
                    fprintf(stderr, "Unexpected opcode %x at program counter %d\n", nfa->code[thread.pc],  thread.pc);
                    exit(1);
            }
        }
    }
}
...