Перестановка основной строки в стиле BNF

Question

Я хочу найти все перестановки для очень простых строк в стиле BNF.

Единственные операторы ()[]|

поэтому () для "должен иметь" [] для "необязательный" и | для "или"

Так дана строка (foo | bar) [zop] [flip | flop]

Это даст мне следующий результат:

• foo flip
• фу зоп флип
• фу зоп флоп
• фу флоп
• бар флип
• бар zop flip
• бар Зоп флоп
• бар флоп
• foo zop
• бар зоп
• Foo
• бар

Есть ли алгоритмы, которые я могу использовать для этого? Я могу написать простой парсер + токенизатор, но мое внутреннее чувство, вероятно, есть более простое решение. Я пишу это в ISO C.

Answer 1

Что вы можете сделать, это использовать рекурсию с парсингом строки. Итак, для каждого персонажа:

1. Если он начинается с '[', дескриптор обязательно установить
2. Если он начинается с '(' опционально установить дескриптор
3. В противном случае просто перейдите к следующей закрывающей скобке ')' или ']'

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1024

void printPermutation(char* result[], int size) {
        for (int i = 0; i < size; ++i) {
                printf("%s ", result[i]);
        }
        printf("\n");
}

void parseDeep(char* s, char* result[], int currIdx) {
    char* mandatory[1024];
    char* optional[1024];
    char *start = 0, *end = 0;
    char* delim = "|";
    int mandatorySize = 0;
    int optionalSize = 0;

    while (*s != 0) {
            //Mandatory
            if ('(' == *s) {
                ++s;
                end = start = s;
                while (*end != ')') {
                        ++end;
                }
                char* mandatorySet = malloc(end - start + 1);
                strncpy(mandatorySet, start, end - start);
                mandatorySet[end - start] = 0;

                char* token = strtok(mandatorySet, delim);
                while (token != 0) {
                        mandatory[mandatorySize] = malloc(strlen(token) + 1);
                        strcpy(mandatory[mandatorySize++], token);
                        token = strtok(0, delim);
                }
                for (int m = 0; m < mandatorySize; ++m) {
                        result[currIdx] = mandatory[m];
                        parseDeep(end, result, currIdx + 1);
                }
                for (int i=0; i < mandatorySize; ++i) {
                    free(mandatory[i]);
                }
                free(mandatorySet);
                s = end;
                return;
            //Optional
            } else if ('[' == *s) {
                ++s;
                end = start = s;
                while (*end != ']') {
                        ++end;
                }
                char* optionalSet = malloc(end - start + 1);
                strncpy(optionalSet, start, end - start);
                optionalSet[end - start] = 0;

                char* token = strtok(optionalSet, delim);
                while (token != 0) {
                        optional[optionalSize] = malloc(strlen(token) + 1);
                        strcpy(optional[optionalSize++], token);
                        token = strtok(0, delim);
                }
                for (int m = -1; m < optionalSize; ++m) {
                        //Optional when it is not added
                        if (m == -1) {
                            continue;
                        } else {
                            result[currIdx] = optional[m];
                            parseDeep(end, result, currIdx + 1);
                        }

                }
                for (int i=0; i < optionalSize; ++i) {
                    free(optional[i]);
                }
                free(optionalSet);
                s = end;
            }
            mandatorySize = optionalSize = 0;
            ++s;
        }
    printPermutation(result, currIdx);
}

void parse(char* s) {
        char* result[MAX_SIZE];
        parseDeep(s, result, 0);
}


int main() {
    char *s = "(foo | bar) [zop] [flip | flop]";
    parse(s);
}

Это не проверяет правильность строки.