C#中的递归字符串替换

Question

塞纳里奥

我有一个对象关键字 - >它有一个名称和一个值(字符串)

关键字不能包含itsSelf ...但可以包含其他关键字示例

K1 = "%K2% %K3% %K4%"

其中K2,K3,K4是关键词......

只是用他们的价值观重新实现它们,但这里有一个我正面临的问题

考试:

K3= "%K2%"

K2= "%K4%"

K4="%K2%"

现在,如果我开始更换,将会有一个无限循环,因为K2给了K4和副Versa ......

我希望避免这样的问题

但是要求我允许uesr嵌套其他关键字...我怎么能检查"添加如果DeadLock发生"我将显示无效...我应该使用HashTable或什么... Some Code Direction would be nice...

Answer 1

来自你的评论:

我希望能够采用Context Free Grammar并在其上运行一个分析器来确定是否存在任何 "无限循环".

这很容易做到.首先,让我们清楚地定义一个"无上下文语法".CFG是具有"终端"和"非终端"符号的替代系统.终端是"完成"的东西; 非终端用一系列终端和非终端符号代替.

在我的例子中,非终端将是大写的,终端将是小写的.替换规则将被写为"NONTERMINAL:替换符号".所以CFG的一个例子是:

SENTENCE : SUBJECT VERB OBJECT
SUBJECT  : ARTICLE NOUN
ARTICLE  : a
ARTICLE  : the
NOUN     : can
NOUN     : man
VERB     : saw
VERB     : kicked
OBJECT   : ARTICLE NOUN

因此,如果我们从SENTENCE开始,那么我们可以进行替换:

SENTENCE
SUBJECT VERB OBJECT
ARTICLE NOUN VERB OBJECT
the NOUN VERB OBJECT
the man VERB OBJECT
the man kicked OBJECT
the man kicked ARTICLE NOUN
the man kicked the NOUN
the man kicked the can

而且我们没有更多的非终端,所以我们已经完成了.

CFG可以有周期:

EQUATION : TERM = TERM
TERM     : 1
TERM     : ADDITION
ADDITION : TERM + TERM

现在我们做制作:

EQUATION
TERM = TERM
1 = TERM
1 = ADDITION
1 = TERM + TERM
1 = 1 + TERM
1 = 1 + 1

这个人最终可以停止,但也可以永远停止.当然,你可以定义必须永远存在的CFG ; 如果没有生产"TERM:1"那么这个将永远不会找到只有终端的有效序列.

那么你如何确定是否有任何可以永远运行的作品？

你所做的是制作有向图数据结构.将所有非终端设置为图中的节点.然后为右侧具有非终端的每个生产规则添加边.所以对于我们的第一个例子,我们有图表:

SENTENCE ----->  SUBJECT
  |   |          |     |
  |   |          |     |
  v   |          |     |
 VERB |          |     |   
      v          v     |
     OBJECT--->ARTICLE |
         \             v  
          ---------->NOUN

在第二个例子中,我们有图表:

EQUATION --> TERM ---> ADDITION
                 <-----/

如果图形包含可从开始符号到达的循环,则语法包含可以永久扩展的产品.如果没有,那就不行了.

所以现在你所要做的就是构建一个循环检测器,这在图形分析中是一个简单的问题.如果没有循环,或者如果从开始符号无法到达唯一的循环,则语法是好的.