curso

CENTRO AMERICANO DE ESTUDIOS SUPERIORES
INGENIERÍA EN SISTEMAS COMPUTACIONALES
LENGUAJES Y AUTÓMATAS

Unidad II
Gramáticas.
Objetivo General. Al término de la unidad, el alumno conocerá las estructuras de las gramáticas
utilizadas para la generación de compiladores.
2.1. Introducción a las Gramáticas.
Una gramática es una herramienta o notación que nos permite definir un lenguaje pormedio de una
serie de reglas que nos dicen cómo construir cadenas válidas (oraciones) para el lenguaje.
Las gramáticas son capaces de describir la mayoría, pero no todas las sintaxis de los lenguajes de
programación. Un analizador léxico efectúa una cantidad limitada de análisis sintáctico conforme
produce la secuencia de componentes léxicos a partir de caracteres de entrada. Ciertas limitacionesde
la entrada, como el requisito de que los identificadores se declaren antes de ser utilizados no pueden
describirse mediante una gramática independiente de contexto.
Una gramática da una especificación sintáctica precisa y fácil de entender de un lenguaje de
programación.
A partir de algunas clases de gramáticas se puede construir automáticamente un analizador sintáctico
eficiente quedetermine si un programa fuente está sintácticamente bien formado. Otra ventaja es que el
proceso de construcción del analizador sintáctico puede revelar ambigüedades sintácticas y otras
construcciones difíciles de analizar que de otro modo podrían pasar sin detectar en la fase inicial de
diseño de un lenguaje y de su compilador.
Una gramática diseñada adecuadamente imparte una estructura a unlenguaje de programación útil
para la traducción de programas fuentes a código objeto correcto y para la detección de errores. Existen
herramientas para convertir descripciones de traducciones basadas en gramáticas de programas
operativos.
Los lenguajes van evolucionando con el tiempo y adquiriendo nuevas construcciones, además de que
adicionan nuevas tareas. Estas nuevas construcciones sepueden añadir a un lenguaje cuando existe
una aplicación basada en una descripción gramatical de lenguaje.
La gramática de un lenguaje es el conjunto de reglas capaces de generar todas las posibilidades
combinatorias de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural.
La expresión “gramática formal” tiene dos sentidos:
(a) Gramática de un lenguaje formal.
(b) Descripciónformal de la gramática de un lenguaje natural.
En cuanto a (b), la descripción formal de la gramática de una lengua es la que explicita las reglas
combinatorias mentales a partir de fórmulas lógico-matemáticas. Estas reglas combinatorias que utiliza
el lenguaje natural reciben el nombre de sintaxis, y son inconscientes.

L.I. DARÍO DE LOS ÁNGELES L ARA CASTILLO

1

CENTRO AMERICANO DEESTUDIOS SUPERIORES
INGENIERÍA EN SISTEMAS COMPUTACIONALES
LENGUAJES Y AUTÓMATAS
En cuanto a (a), ‘gramática formal’ se utiliza en analogía con el concepto de gramática, usado
tradicionalmente para los lenguajes naturales. Por tanto, una gramática formal es el conjunto de reglas
combinatorias de un lenguaje formal. Hay distintos tipos de gramáticas formales que generan lenguajes
formales.
TipoLenguaje

Normas de producción de gramáticas

0

recursivamente enumerable (LRE)

Sin restricciones

1

dependiente del contexto (LSC)

αAβ → αγβ

2

independiente del contexto (LLC)

A→γ

3

regular (RL)

A → aB
A→a

Imaginemos una gramática con estas dos reglas:
1. A → bAc 2. A → de
La idea es substituir el símbolo inicial de la izquierda por otros símbolosaplicando las reglas. El lenguaje
al cual representa esta gramática es el conjunto de cadenas de símbolos que pueden ser generados de
esta manera: en este caso, por ejemplo:
A → bAc → bbAcc → bbbAccc -→ bbbdeccc.
El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son símbolos terminales.
Las cadenas de la lengua son aquellas que solo contienen elementos terminales, como...