Как найти первый сет?

Question

Я пытаюсь перечислить первый набор данной грамматики с помощью этой функции:

Примечание:
char c - символ для поиска первого набора;
first_set - хранить элементы соответствующего первого набора;
q1, q2 - предыдущая позиция;
rule - хранить все правила грамматики построчно, перечисленные ниже;
в первый раз параметры ('S', 0, 0).

void findfirst(char c, int q1, int q2){
    if(!(isupper(c)) || c=='$'){
         first_set[n++] = c;
    }
    for(int j=0;j<rule_number;j++){
        if(rule[j][0]==c){
            if(rule[j][2]==';'){
                if(rule[q1][q2]=='\0')
                    first_set[n++] = ';';
                else if(rule[q1][q2]!='\0' &&(q1!=0||q2!=0))
                    findfirst(rule[q1][q2], q1, (q2+1));
                else
                    first_set[n++] = ';';
            }
            else if(!isupper(rule[j][2]) || rule[j][2]=='$')
                first_set[n++] = rule[j][2];
            else
                findfirst(rule[j][2],j,3);
        }
    }
}

Но обнаружил, что если данная грамматика выглядит так:

S AC$
C c
C ;
A aBCd
A BQ
B bB
B ;
Q q
Q ;

(которые с левой стороны или любые заглавные буквы с правой стороны не являются терминальными, а любые строчные буквы - терминальными) функция не смогла правильно вывести первый набор для S, поскольку она остановится при поиске первого набора Q и сохранит ';' в первом наборе и не будет продолжать поиск C Первый сет.

У кого-нибудь есть подсказка? Заранее спасибо.

Answer 1

Вы можете сделать следующее: code:

used[i] означает, что rule[i] используется или нет

Метод Depth-first search, см. https://en.wikipedia.org/wiki/Depth-first_search

#include <iostream>

#define MAX_SIZE 1024

char rule[][10] = {
  "S AC$",
  "C c",
  "C ;",
  "A aBCd",
  "A BQ",
  "B bB",
  "B ;",
  "Q q",
  "Q ;"
};

constexpr int rule_number = sizeof(rule) / sizeof(rule[0]);

char first_set[MAX_SIZE];

bool findfirst(int row, int col, int *n, bool* used) {
  for (;;) {
    char ch = rule[row][col];
    if (ch == '$' || ch == ';' || ch == '\0') {
      first_set[*n] = '\0';
      break;
    }
    if (islower(ch)) {
      first_set[(*n)++] = ch;
      ++col;
      continue;
    }
    int i;
    for (i = 0; i != rule_number; ++i) {
      if (used[i] == true || rule[i][0] != ch)
        continue;
      used[i] = true;
      int k = *n;
      if (findfirst(i, 2, n, used) == true)
        break;
      used[i] = false;
      *n = k;
    }
    if (i == rule_number)
      return false;
    ++col;
  }
  return true;
}

int main() {
  bool used[rule_number];
  int n = 0;
  for (int i = 2; rule[0][i] != '$' && rule[0][i] != '\0'; ++i) {
    for (int j = 0; j != rule_number; ++j)
      used[j] = false;
    used[0] = true;
    findfirst(0, i, &n, used);
  }
  std::cout << first_set << std::endl;
  return 0;
}

Answer 2

Крайне неэффективно вычислять ПЕРВЫЕ наборы по одному, поскольку они взаимозависимы. Например, чтобы вычислить ПЕРВЫЙ набор из A, вам также необходимо вычислить ПЕРВЫЙ набор из B, а затем, поскольку B может получить строку emoty, вам необходим ПЕРВЫЙ набор из Q.

Большинство алгоритмов вычисляют их все параллельно, используя некоторые варианты алгоритма транзитивного замыкания. Вы можете сделать это с помощью поиска в глубину, который, кажется, является тем, что вы пытаетесь, но может быть проще реализовать алгоритм наименьшей фиксированной точки, описанный в книге Дракона (и Википедия .

В любом случае, вам, вероятно, будет проще сначала вычислить NULLABLE (то есть, какие нетерминалы получают пустое множество). Для этого существует простой алгоритм линейного времени (линейный по размеру грамматики), который, опять же, легко найти.

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