Descripción
Elaboración de la gramática, su representación de en BNF y desarrollo del
programa para validar cadenas de acuerdo a esta, para el siguiente lenguaje:
Gramática p/ EAS
Gramática
G= (V , T , P , S )
Donde :
V ={E }
T ={ + ,∗, ( , ) , a , b }
P={ E → E+ E , E∗E , ( E ) , a , b }
S={E }
Gramática en BNF (Backus Naur Form)
<expresion> ::= <expresion> + <expresion>
| <expresion> * <expresion>
| ( <expresion> )
|a
|b
Diagramas de sintaxis
Diagrama de árbol de derivación por la izquierda y por la derecha
El diagrama de ambas derivaciones es exactamente el mismo.
Pseudocódigo
Inicio
Definir Clase ExpressionValidator
Atributos:
Scanner scanner
char currentCharacter
Método Constructor ExpressionValidator(String input)
Inicializar scanner con input
Llamar a readNextCharacter()
Método boolean validate()
Asignar a isValid el resultado de parseExpression()
Retornar isValid y currentCharacter es igual a fin de cadena ('\0')
Método boolean parseExpression()
Si currentCharacter es 'a' o currentCharacter es 'b' Entonces
Llamar a readNextCharacter()
Retornar Verdadero
Sino Si currentCharacter es '(' Entonces
Llamar a readNextCharacter()
Si parseExpression() es Verdadero Entonces
Si currentCharacter es ')' Entonces
Llamar a readNextCharacter()
Retornar Verdadero
Fin Si
Fin Si
Retornar Falso
Sino
Si parseExpression() es Verdadero Entonces
Si currentCharacter es '+' o currentCharacter es '*' Entonces
Guardar currentCharacter en operator
Llamar a readNextCharacter()
Si parseExpression() es Verdadero Entonces
Retornar Verdadero
Fin Si
Fin Si
Fin Si
Fin Si
Retornar Falso
Método void readNextCharacter()
Si scanner tiene siguiente Entonces
currentCharacter = [Link] carácter
Sino
currentCharacter = '\0'
Método boolean hasValidCharacters(String expression)
Para cada carácter c en expression Hacer
Si c no es 'a', 'b', '+', '*', '(', ')' Entonces
Retornar Falso
Fin Si
Fin Para
Para i desde 0 hasta longitud de expression - 2 Hacer
Si (expression[i] es '+' o '*' Y expression[i + 1] es '+' o '*') Entonces
Retornar Falso
Fin Si
Fin Para
Retornar Verdadero
Método principal
Definir Scanner userInputScanner
Mostrar "Cadenas Validadoras - Análisis Sintáctico"
Mostrar "Cátedra: Lenguajes y Autómatas II"
Mostrar "Estudiantes: Brandon Pérez Meneses y Angel Emanuel Pérez
Romero"
Mostrar "Números de Control: 21200623 y 21200624"
Mostrar "Este programa valida si una cadena es correcta de acuerdo a la
siguiente gramática:"
Mostrar "P = { E → E + E, E → E * E, E → (E), E → a, E → b }"
Mostrar "Introduce una cadena (sin espacios): "
Leer input de userInputScanner
Crear una instancia de ExpressionValidator llamada validator con input
Si  Entonces
Mostrar "Error: La cadena tiene caracteres no válidos o presenta operadores
consecutivos."
Sino Si [Link]() Entonces
Mostrar "La cadena es válida según la gramática."
Sino
Mostrar "La cadena NO es válida según la gramática."
Fin Si
Cerrar userInputScanner
Fin
Código Fuente
/*
LENGUAJES Y AUTOMATAS II
Programa en base a la gramática de un número entero
Integrantes del equipo:
Calzada Islas Zyanya Camila 21200586
Navarro Ordonez Daniela 21200622
*/
package lengyautom2;
import [Link];
public class ExpressionValidator {
private Scanner scanner;
private char currentCharacter;
// Constructor que inicializa el escáner con la cadena de entrada
public ExpressionValidator(String input) {
[Link] = new Scanner(input);
readNextCharacter(); // Leer el primer carácter
}
// Método principal que valida si la cadena es una expresión válida
public boolean validate() {
boolean isValid = parseExpression(); // Comenzamos con la producción inicial E
return isValid && currentCharacter == '\0'; // La cadena es válida si consumimos todo
el input
}
// Función para resolver las producciones de "E"
private boolean parseExpression() {
if (currentCharacter == 'a' || currentCharacter == 'b') {
readNextCharacter(); // Consumimos el terminal 'a' o 'b'
return true; // E → a | b
} else if (currentCharacter == '(') {
readNextCharacter(); // Consumimos '('
if (parseExpression()) {
if (currentCharacter == ')') {
readNextCharacter(); // Consumimos ')'
return true; // E → (E)
}
}
return false; // No cerró el paréntesis
} else {
// Intentamos reconocer las producciones E → E + E o E → E * E
if (parseExpression()) {
if (currentCharacter == '+' || currentCharacter == '*') {
char operator = currentCharacter; // Guardamos el operador
readNextCharacter(); // Consumimos el operador
if (parseExpression()) {
return true; // E → E + E | E → E * E
}
}
}
}
return false; // No fue una expresión válida
}
// Función para avanzar al siguiente carácter
private void readNextCharacter() {
if ([Link]()) {
currentCharacter = [Link]().charAt(0);
} else {
currentCharacter = '\0'; // Fin de la cadena
}
}
// Método para verificar si la cadena es válida
private boolean hasValidCharacters(String expression) {
// Comprobamos si hay caracteres no válidos
for (char c : [Link]()) {
if (c != 'a' && c != 'b' && c != '+' && c != '*' && c != '(' && c != ')') {
return false;
}
}
// Comprobamos si hay operadores consecutivos
for (int i = 0; i < [Link]() - 1; i++) {
if (([Link](i) == '+' || [Link](i) == '*') &&
([Link](i + 1) == '+' || [Link](i + 1) == '*')) {
return false; // Operadores consecutivos
}
}
return true; // La expresión es válida
}
// Método principal para ejecutar el analizador sintáctico
public static void main(String[] args) {
Scanner userInputScanner = new Scanner([Link]);
[Link]("Introduce una cadena (sin espacios): ");
String input = [Link]().replace(" ", ""); // Eliminamos espacios en
blanco
ExpressionValidator validator = new ExpressionValidator(input);
if () {
[Link]("Error: La cadena tiene caracteres no válidos o presenta
operadores consecutivos.");
} else if ([Link]()) {
[Link]("La cadena es válida según la gramática.");
} else {
[Link]("La cadena NO es válida según la gramática.");
}
[Link]();
}
}
Resultados
Al ingresar una cadena válida.
Al ingresar una cadena inválida.
