0

通常 DFA 用于检查给定的字符串是否以某种语言存在。例如 _ab1c 存在于 C 中的变量语言中。

我在做什么？ 但正如这个问题中所述，我正在使用 DFA 来跟踪所有评论、字符串等。

我过得怎么样？ 考虑一个在给定字符串/程序中跟踪 //comments 的示例。

static int makeTransition[][] = {
        /*     Transition Table        */
              /*{other,\n, \, /, *, ', "}  */  
            /*q0*/ { 0, 0, 0, 1, 0, 0, 0},
            /*q1*/ { 0, 0,-1, 2, 0, 0, 0},
            /*q2*/ { 2, 0, 2, 2, 2, 2, 2},
        };

为此，如果我有，

void assignPointerValuesInPairs(int index) 
    {
/*comments is an ArrayList
before marking start hotpointer = -1
after marking start hotpointer = 0
after marking end hotpointer is resetted to -1*/
        switch(currentState)
            {   
            case 2:     /*q2*/
                      comments.add(/*mark start*/);
                      hotPointer = 0;
                      break;
            case 0:    /*On initial state q0*/
                switch(hotPointer)
                {
                case 0: //If I am in end of comment.
                    comments.add(/*mark end*/);                            
                     hotPointer = -1; //Resetting the hotPointer.
                             break;

                case -1: /*Already in q1 only*/
                    /*Do nothing*/
                }
        }
     }

 public static void traceOut(String s) //entire program is accepted as string.
    {
            int index = 0;
        while (index < s.length() ) {                
                      char c = s.charAt(index);
                      try{
             currentState = makeTransition[currentState][symbolToInteger(c)];
              if(currentState == -1)
              throw new InvalidSyntaxException();
                  }
              catch(InvalidSyntaxException e){
              currentState = 0;
              invalidSyntax.add(index);                      
              }
                assignPointerValuesInPairs(index);
                index++;    
            }
                
                
                
                currentState = 0;
                assignPointerValuesInPairs(index);  //These 2 statements help to color while typing.. (i.e) It forces the current state to get finished abruptly.   
      }

}

我的问题是...

我可以使用 DFA，以这种方式标记 //comment 的结束和开始，或者我必须遵循 CFG 等其他方式。

IE

我的声明：我可以使用 DFA，不仅可以检查特定语言，还可以跟踪给定字符串中属于某些语言的某些字符串。（证明：通过上述方法）。

我的上述说法正确吗？

4

2 回答 2

1

我的声明：我可以使用 DFA，不仅可以检查特定语言，还可以跟踪给定字符串中属于某些语言的某些字符串。

我的上述说法正确吗？

你的说法是非常正确的。 可以使用 DFA 检查某些语言。（证明是存在的。如果存在任何这样的语言，那么您的陈述是正确的。并且语言

        <program> ::= 'A'

是一个满足存在性证明的简单例子。）

但这并不是一个特别有用的陈述，因为它没有说明可以使用 DFA 检查哪种语言。

例如，如果您的评论语言支持评论块的嵌套（正如一些历史编程语言所做的那样），那么 DFA 将不起作用。

您的陈述忽略的第二点是，对于给定语言，使用 DFA 是否可行。对于在语法中具有所有形式的嵌套/递归等界限的语言，理论上您可以将语法转换为单个有限 DFA。然而，DFA 太大以至于无法实现。

（除此之外 - 没有现代编程语言在语法层面上有这样的界限......并不是说这个问题完全是关于编程语言的。）

于 2011-10-06T02:25:28.790 回答
0

你需要更多的状态。您的 DFA 在多行注释上中断。我很确定您没有识别*/.

是的，DFA 可以识别这些类型的评论。容易地。

大多数常见的编程语言都不是常规语言，并且无法被 DFA 识别。但是，有些是并且可以是。

于 2011-10-06T02:24:26.363 回答