你没有提供很多细节,一个简单的实现(即使是伪代码)可以帮助我们给出提示。
来自维基百科:
让输入为由n个字符组成的字符串S:a1 ... an。让
对于此问题,您可以使用一个简单的字符串或char向量。
语法包含r个非终结符R1 ... Rr。
我会将非终结符存储在bool数组中std::array nonterminal{};然后,由于您有字符,您可以使用true初始化对应于该字符的位置。
nonterminal[static_cast('C')] = true;
您可以对终止符做同样的操作,从而具有非常快的查找机制。
这个语法包含了子集Rs,它是起始符号的集合。让P[n,n,r]成为一个布尔数组。将P的所有元素初始化为false。对于每个i = 1到n,对于每个单元产生式Rj -> ai,设置P[i,1,j] = true。对于每个i = 2到n - 跨度的长度,对于每个j = 1到n-i + 1 - 跨度的开始,对于每个k = 1到i-1 - 跨度的分区,对于每个RA -> RB RC的产生式,如果P[j,k,B]和P[j + k,i-k,C]则设置P[j,i,A] = true。如果任何P[1,n,x]为true(其中x迭代整个Rs集合的索引),则S是语言的成员,否则S不是语言的成员。之后,该算法似乎非常简单明了。只需确保不在紧密循环内初始化临时值即可。