CODEWITHSUNDEEP
javadfa
Muthu Ganapathy Nathan
Muthu Ganapathy Nathan

Reputation: 3307

Could I use the DFA to trace strings of a certain Languages?

Generally DFA's are used to check, whether given string is present in a certain language. e.g _ab1c is present in the Language of variables in C.

What I am doing? But as stated in this question,I am using DFA to trace all comments,strings etc.

How I am doing? Consider an example of tracing a //comments in a given string/program.

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},
        };

For this, If I have,

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.   
      }

}

My Question is...

can I use the DFA, to mark the end and start of the //comment in this way, or I have to follow some other way like CFG etc..

i.e

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?

Upvotes: 0

Views: 516

Answers (2)

Stephen C
Stephen C

Reputation: 719336

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?

Your statement is trivially correct. Certain languages can be checked using DFAs. (The proof is by existence. If any such language exists, then your statement is true. And the language

        <program> ::= 'A'

is a trivial example to satisfy the existence proof.)

But this is not a particularly useful statement, because it says nothing about what kind of languages can be checked using a DFA.

For example, if your comment language supported nesting of comment blocks (as some historical programming languages have done), then a DFA won't work.

A second point that your statement ignores is whether use of a DFA is practical for a given language. For a language with bounds on all forms of nesting / recursion in the grammar, etc you could in theory translate the grammar into a single finite DFA. However the DFA would be so large that it would be unimplementable.

(Aside - no modern programming language has such bounds at the grammatical level ... not that this question is exclusively about programming languages.)

Upvotes: 1

user684934
user684934

Reputation:

You need more states. Your DFA breaks on multiline comments. I'm pretty sure sure that you're not recognizing the "end of comment" sequence of */.

And yes, a DFA can recognize these types of comments. Easily.

Most common programming languages are not regular languages, and cannot be recognized by DFAs. However, some are, and can be.

Upvotes: 0

Related Questions