java - 我可以使用 DFA 来跟踪特定语言的字符串吗？

Question

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

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

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

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 来以这种方式标记//注释的结束和开始吗？ 或者我必须遵循其他方式，例如 CFG 等..

即

My Statement: I can use DFA, not only to check for a particular language also to trace out certain strings belong to certain languages in a given string. (proof : by above method).

Does my above statement correct?

Answer 1

My Statement: I can use DFA, not only to check for a particular language also to trace out certain strings belong to certain languages in a given string.

Does my above statement correct?

你的说法完全正确。 某些语言可以使用DFA进行检查。 (证明是存在的。如果任何这样的语言存在，那么你的陈述就是正确的。并且该语言

        <program> ::= 'A'

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

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

例如，如果您的评论语言支持评论 block 嵌套(正如某些历史编程语言所做的那样)，则 DFA 将不起作用。

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

(顺便说一句 - 没有现代编程语言在语法层面上有这样的界限......并不是说这个问题只与编程语言有关。)