DFA (Reconocedor) para identificadores Pascal válidos

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *