Introduccion Alos Lenguajes

INTRODUCCION A LOS LENGUAJES FORMALES.

Es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados. Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmulabien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.

Laidea básica es considerar a un lenguaje como un conjunto compuesto por cadenas de longitud finita formadas por símbolos tomados de un alfabeto. Es decir, dado un alfabeto[pic], decimos que[pic], (para un [pic]dado, que llamamos longitud de[pic]) es una cadena construida con símbolos de[pic]. Si [pic]tenemos la cadena llamada vacía, y denotada por[pic]. Al conjunto formado por de todas las cadenasque se pueden construir con las letras de dicho alfabeto se le llama lenguaje universal y se le denota por [pic]*. Es evidente que el número de elementos de [pic]* es infinito numerable. Entre las cadenas, como elementos de [pic]*, se define una operación, llamada concatenación, mediante la cual a dos cadenas dadas [pic]* se le asocia otra cadena [pic]obtenida por yuxtaposición de[pic]; es decir, si[pic]*, e [pic]*, entonces la cadena[pic], sería: [pic]

















ESTRUCTURAS DE LAS GRAMATICAS
Una gramática consiste de 4 componentes, y es denotada por G = (VT, VN, S, ()
donde :
VT Es el conjunto de símbolos terminales a partir de los cuales las cadenas son
formadas. Si la gramática es usada para denotar un lenguaje de programación , entonces
los tokens sonlos símbolos terminales.
VN Es el conjunto de símbolos no terminales , también llamados variables  es

.

Las variables sintácticas denotan un conjunto de cadenas. Los símbolos no terminales
definen conjuntos de cadenas que ayudan a definir el lenguaje generado por la
gramática.
S Es un símbolo no terminal de la gramática que es distinguido como símbolo de
inicio. El conjunto de cadenasque este símbolo de inicio denota, es el lenguaje definido
por la gramática G.
((Es el conjunto de producciones o reglas gramaticales. Las producciones de una
gramática especifican la manera en que los tokens ( terminales ) y las variables
Sintácticas ( no terminales ) pueden ser combinados para formar cadenas.
Ejemplo Dada la siguiente gramática:
R read
R readln
R read (P)
R readln (P)P P, id
P id
Encuentra sus componentes VT, VN,, S y (.
Usemos la siguiente convención de notación :
(Las letras mayúsculas servirán para denotar variables sintácticas (Símbolos no
terminales).
(El lado izquierdo de la primera producción es el símbolo de inicio.
(Si A (1 , A (2, . . . A (K son producciones teniendo a la no
terminal A en el lado izquierdo, podemos escribir A (1 (((2 ((. . .(((K ((donde
(1, (2, . . . ,(K se les llama las alternativas para A.
38 Ing. Fco. Ríos Acosta friosam@prodigy.net.mx Gramáticas
38
Encontremos el conjunto de símbolos terminales VT.
VT = { read, readln, ( , ) , , , id }
ya que read y readln son palabras reservadas, ( , ) y la coma son separadores, e id es un
identificador.
VN = { R, P } únicamente dos símbolos no terminales.
El símbolo deinicio es R, aplicando la 2da. convención de notación, y el conjunto ((de
producciones es condensado, aplicando la 3a. convención :
((= { R read ((readln ((read (P) ((readln (P)
P P, id ((id }
La gramática es :
G = ( { read, readln, ( , ) , , , id }, {R,P},R,(()
Ejemplo Supongamos la gramática que especifica a la instrucción de asignación
en Pascal, con expresiones aritméticas +, -, * y...