Metalenguaje BNF

BNF

                                               Teoria de la computacion

DEFINICION DE METALENGUAJES BNF

Sintaxis de los Lenguajes de Programación • Metalenguaje B.N.F. – Notación para especificar una gramática generativa: define el conjunto de cadenas que son programas del LP sujeto, junto con su estructura sintáctica – Permite describir lenguajes con una sintaxis “independiente del contexto” • Gramáticas de atributos – Extensión de B.N.F. mediante atributos y reglas de evaluación de dichos atributos. – Permite describir lenguajes con hechos sintácticos
“dependientes del contexto”

Metalenguaje B.N.F. (Forma de Backus-Naur) símbolos no-terminales (uno de ellos distinguido) • para describir los constructores sintácticos del LP sujeto símbolos terminales • para describir los símbolos (texto) del LP sujeto reglas de producción • una regla con (alternativas) para cada símb. no-terminal • cada alternativa: cadena de terminales y/o no-terminales Ejemplos: ::= if then fi | if then else fi ::=

Se permite recursión en las reglas de producción – a izquierdas: ::= | ; – a derechas: ::= | ; • Estructura sintáctica => árbol sintáctico Ejemplo (parte de un árbol): if then fi ; FLP 2009/10 - Marisa Navarro 4 • Gramática ambigua: – Para una cadena terminal hay más de un árbol sintáctico Ejemplo: ::= x | y | z | () | + | * (recursión a izquierda y derecha para un mismo símbolo no-term.) Dos árboles sintácticos para la cadena x + y * z : + * x * + z y z x y 

La idea de transcribir la estructura del lenguaje con reglas de reescritura se remontan cuando menos al trabajo del gramático indio Panini (hacia el 460 a. C.), que la utilizó en su descripción de la estructura de palabras del idioma sánscrito (algunos incluso han sugerido renombrar BNF a Forma Panini-Backus). Lingüïstas estadounidenses como Leonard Bloomfield y Zellig Harris llevaron esta idea un paso más adelante al tratar de formalizar el lenguaje y su estudio en términos de definiciones formales y procedimientos (1920-1960).

Noam Chomsky, maestro de lingüística de alumnos de teoría de la información del MIT, combinó la lingüística y las matemáticas, tomando esencialmente el formalismo de Axel Thue como la base de su descripción de la sintaxis del lenguaje natural. También introdujo una clara distinción entre reglas generativas (de la gramática libre de contexto) y reglas transformativas (1956).

John Backus, un diseñador de lenguajes de programación de IBM, adoptó las reglas generativas de Chomsky para describir la sintaxis del nuevo lenguaje de programación IAL, conocido en la actualidad como ALGOL 58 (1959), presentando en el primer Congreso de Computación Mundial (World Computer Congress) el artículo "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference".

Peter Naur, en su reporte sobre ALGOL 60 de 1963, identificó la notación de Backus como la Forma Normal de Backus (Backus Normal Form), y la simplificó para usar un conjunto de símbolos menor, pero a sugerencia de Donald Knuth, su apellido fue agregado en reconocimiento a su contribución, reemplazando la palabra "Normal" por Naur, dado que no se trata de una forma normal en ningún sentido, a diferencia, por ejemplo de la Forma Normal de Chomsky

Fuentes:

http://www.exa.unicen.edu.ar/catedras/ccomp1/ClaseGLC.pdf