如何找到第一个集合？

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]=='[=10=]')
                    first_set[n++] = ';';
                else if(rule[q1][q2]!='[=10=]' &&(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

一次计算一个 FIRST 集是非常低效的，因为它们是相互依赖的。例如，为了计算 A 的第一个集合，您还需要计算 B 的第一个集合，然后因为 B 可以导出 emoty 字符串，您需要 FIRST一组 Q.

大多数算法使用传递闭包算法的某些变体并行计算所有这些。你可以用深度优先搜索来做到这一点，这似乎是你正在尝试的，但它可能更容易实现龙书中描述的最小不动点算法（和 Wikipedia.

无论哪种方式，您可能会发现首先计算 NULLABLE（即，哪些非终端派生空集）更容易。有一个简单的线性时间算法（与语法大小成线性关系），也很容易找到。

如果您将这项工作作为 class 的一部分进行，您可能会在课程材料中找到相关算法。或者，您可以查找 Dragon book 或其他类似教科书的副本。

Answer 2

你可以像下面这样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 == '[=10=]') {
      first_set[*n] = '[=10=]';
      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] != '[=10=]'; ++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;
}

如何找到第一个集合？

How to find first set?

c++

compiler-construction