Problema – Implementar un reconocedor de identificadores pascales basado en un DFA que acepte strings pertenecientes a la definición del lenguaje del mismo.
Aquí hay una definición regular para el conjunto de identificadores de Pascal que se definen como el conjunto de strings de letras y dígitos que comienzan con una letra.
letter : A | B | . . . | Z | a | b | . . . | z digit : 0 | 1 | 2 | . . . | 9 ID : letter (letter | digit)*
El ID de expresión regular es el patrón para el identificador de Pascal y define una letra y un dígito donde una letra es una expresión regular para el conjunto de todas las letras mayúsculas y minúsculas del alfabeto y el dígito es regular para el conjunto de todos los dígitos decimales.
Diagrama de estado del DFA
Código de trabajo para el reconocedor:
C++
// C++ program to implement DFA based regonizer that accepts // all strings which follow the language // L = { letter (letter | digit)* } #include <bits/stdc++.h> #include <iostream> using namespace std; // dfa tells the number associated // with the present state int dfa; // This function is for // the starting state (zeroth) of DFA void start(char c) { if (isalpha(c)) dfa = 1; else // -1 is used to check for any invalid symbol dfa = -1; } // This function is for the first state of DFA void state1(char c) { if (isalnum(c)) dfa = 1; else dfa = -1; } bool DFA_for_ID(string token) { dfa = 0; int i, len = token.length(); for (i = 0; i < len; i++) { if (dfa == 0) start(token[i]); else if (dfa == 1) state1(token[i]); else return 0; } if (dfa == 1) return 1; else return 0; } // driver code int main() { string input = "Geeks for Geeks is 9ice platfo$m for every1 "; // to separate all the tokens by space in the string // and checking for each token stringstream ss(input); string token; while (ss >> token) { bool isValid = DFA_for_ID(token); if (isValid) cout << token << " : " << "Valid" << endl; else cout << token << " : " << "Invalid" << endl; } return 0; }
Producción:
Geeks : Valid for : Valid Geeks : Valid is : Valid 9ice : Invalid platfo$m : Invalid for : Valid every1 : Valid
Publicación traducida automáticamente
Artículo escrito por Archana choudhary y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA