Compiladores

NOTACIÓN DE CHOMSKY

Según Chomsky, una gramática formal es una estructura matemática, consistente en un conjunto de reglas que definen la forma de construir  todas y cada una de las cadenas de caracteres que componen un determinado lenguaje, denominadas sentencias, y donde el conjunto de todas las sentencias constituye el lenguaje. Como no se describe el significado de dichas sentencias, sino únicamente su forma, de ahí procede el calificativo de formal. Además de las reglas, la descripción de una gramática formal se completa con dos conjuntos de símbolos, denominados alfabetos, uno, denominado terminal,  de los caracteres que conforman las sentencias propias del lenguaje, y otro, el no terminal, constituido por una serie de símbolos auxiliares usados durante el proceso de cómputo y que no aparecen en las sentencias válidas del lenguaje, sino únicamente durante los pasos intermedios. Para finalizar, también se añade un símbolo no terminal especial, denominado inicial, usualmente denotado por la letra S, que sirve para dar comienzo a la construcción de cualquier sentencia.

Explicacion notacion de chomsky