Jerarquia de Chomsky y Fases de un compilador DOCX

Title	Jerarquia de Chomsky y Fases de un compilador
Author	Marisol Lucio
Pages	6
File Size	109.8 KB
File Type	DOCX
Total Downloads	142
Total Views	464

Summary

Description

Jerarquía de Chomsky En 1956, Noam Chomsky clasificó las gramáticas en cuatro tipos de lenguajes y esta clasificación es conocida como la jerarquía de Chomsky, en la cual cada lenguaje es descrito por el tipo de gramática generado. Estos lenguajes sirven como base para la clasificación de lenguajes de programación. Los cuatro tipos son: lenguajes recursivamente enumerables, lenguajes sensibles al contexto, lenguajes libres de contexto y lenguajes regulares. Dichos lenguajes también se identifican como lenguajes de tipo 0, 1, 2 y 3. Sea un lenguaje L definido por al menos una gramática G que cumple: Si todas las producciones de G tienen la forma A xB o donde A y B son símbolos no terminales y x es un terminal; entonces G se dice que es una gramática regular y L es un lenguaje regular o de tipo 3. Si todas las producciones de G tienen la forma donde x es una combinación de símbolos terminales y no terminales, entonces G se dice que es una gramática libre de contexto y L es un lenguaje libre de contexto o de tipo 2. De ser las producciones de G de la forma donde A es un símbolo no terminal cualquiera, x, y, y z son combinaciones de terminales y no terminales, tales que x e y pueden ser cadenas vacías; entonces se dice que G es una gramática dependiente del contexto y L es un lenguaje dependiente del contexto o lenguaje de tipo 1. Si ninguna de las gramáticas de L cumple las propiedades anteriores entonces se dice que es un lenguaje sin restricciones, recursivamente enumerable o de tipo 0. Desde el punto de vista conjuntival la jerarquía de Chomsky funciona como se ve en al gráfico: . De manera que todos los lenguajes de tipo 3 (LR) son también de tipo 2 (LLC) y los LLC son de tipo 1 (LDC) son de tipo 0 (LSR o LRE). Existe una exacta correspondencia entre cada uno de estos tipos de lenguajes y particulares arquitecturas de máquinas en el sentido que por cada lenguaje de tipo T hay una arquitectura de máquina A que reconoce el lenguaje de tipo T y por cada arquitectura...