Instituto Politcnico e Nacional

Escuela Superior de Cmputo o

Proyecto Final Grmatica del lenguaje de a programacin C o

Flores Moscoso Nstor Daniel e

Resumen En este proyecto nal, se tratara de explicar que es una grmatica libre a de contexto y su uso en la construccin del analizador sintctico. o a Tambin se presenta la grmatica del lenguaje de programacin C y los e a o pasos a seguir para evitar ambigedades a la hora de contruir un analiu zador sintctico funcional sin el uso de herramientas tales como YACC, a Bison, etc.

 Indice
1. Introduccin o 1.1. Objetivos . . . . . . . . . . . 1.2. Grmatica libre de contexto a 1.3. Analizador sintctico . . . . . a 1.4. Lenguaje de programacin C o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 4 4 5 5 5 5 6 6 6 7 7 7 7 7 7 8 8 14 15

2. Grmatica libre de contexto a 2.1. Denicin formal . . . . . . . . . . . . . . . . . . . . . . . . . o 2.2. Ejemplo de una GLC . . . . . . . . . . . . . . . . . . . . . . . 2.3. Uso de la GLC en la construcc de un analizador sintctico on a 2.3.1. Derivaciones y rboles sintcticos . . . . . . . . . . . . a a 2.3.2. Derivaciones ms a la izquierda y ms a la derechas . a a 2.3.3. Gramticas ambiguas . . . . . . . . . . . . . . . . . . a 2.3.4. Conversin de gramticas ambiguas en no ambiguas . o a 3. Gramtica para el lenguaje C a 3.1. Componentes lxicos (tokens) . . . e 3.1.1. Identicadores . . . . . . . 3.1.2. Palabras reservadas . . . . 3.1.3. Constantes . . . . . . . . . 3.1.4. Cadenas literales . . . . . . 3.2. Gramtica completa de lenguaje C a 4. Conclusiones 5. Bibliograa

. . . . . . .

. . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

1.

Introduccin o

A lo largo de este cap tulo se describe los objetivos del proyecto, una explicacin breve de las grmaticas libres de contexto, su uso en la conrstrucin de o a o un analizador sintctico y la grmatica que rige al lenguaje de programacin C. a a o

1.1.

Objetivos

El objetivo principal del proyecto es mostrar como se evita la ambigedad en u el lenguaje de programacin C y mostrar la utilidad que tienen las grmaticas o a libres de contexto en la construccin de un compilador. o

1.2.

Grmatica libre de contexto a

Una grmatica libre de contexto (GLC) es un conjunto nito de variables, a cada una de las cuales representan un lenguaje. Los lenguajes representados por las variables se describen recursivamente en trminos de otros lenguajes o de e s mbolos primitivos llamados terminales. Las reglas que describen el lenguaje asociado con cada variable se llaman producciones.[1]

1.3.

Analizador sintctico a

Un analizador sintctico (en ingls parser) es una de las partes de un coma e pilador que transforma su entrada en un rbol de derivacin. a o El anlisis sintctico convierte el texto de entrada en otras estructuras (comnmena a u te rboles), que son ms utiles para el posterior anlisis y capturan la jerarqu a a a a impl cita de la entrada. Un analizador lxico crea tokens de una secuencia de e caracteres de entrada y son estos tokens los que son procesados por el analizador sintctico para construir la estructura de datos, por ejemplo un rbol de anlisis a a a o rboles de sintaxis abstracta.[2] a

1.4.

Lenguaje de programacin C o

C es un lenguaje de programacin de propsito general que ha sido estrechao o mente asociado con el sistema UNIX en donde fue desarrollado puesto que tanto el sistema como los programas que corren en l estan escritos en lenguaje C. Sin e embargo, este lenguaje nos est ligado a ningn sistema operativo ni a ninguna a u mquina, y aunque se le llama lenguaje de programacin de sistemasdebido a a o su utilidad para escribir compiladores y sistemas operativos, se utiliza con igual ecacia para escribir importante programas en diversas disciplinas.[3]

2.
2.1.

Grmatica libre de contexto a

As como cualquier gramtica formal, una gramtica libre de contexto puede a a ser denida mediante la 4-tupla: G = (Vt , Vn , P, S) donde Vt en un conjunto nito de terminales. V n es un conjunto nito de no terminales. P es un conjunto nito de producciones. S Vn el denominado S mbolo inicial. Los elementos de P son de la forma: Vn (Vt Vn )

2.2.

Ejemplo de una GLC

Suponga que queremos describir todas las expresiones aritmeticas legales usando suma, resta, multiplicacin y dvisin. Aqu se muestra un ejemplo de o o una posible GLC[2]: E E int E E Op E E (E) Op + Op Op * Op / E Op E E Op (E) E Op (E Op E) E (E Op E) int (E Op E) int (int Op E) int (int Op int) int (int + int)

2.3.

Uso de la GLC en la construcc on de un analizador sintctico a

Habitualmente la estructura sintctica de los lenguajes de programacin se a o especica mediante Gramticas Libres de Contexto (GLC). a

2.3.1.

Derivaciones y rboles sintcticos a a

Analizar sintcticamente una cadena de tokens es encontrar para ella un a a rbol sintctico o derivacin, que tenga como ra el s a o z mbolo inicial de la gramtia ca libre de contexto y mediante la aplicacin sucesiva de sus reglas de derivacin o o se pueda alcanzar dicha cadena como hojas del rbol sintctico. En caso de xito a a e la sentencia pertenece al lenguaje generado por la gramtica, y puede proseguira se el proceso de compilacin. En caso contrario, es decir cuando no se encuentra o el rbol que genera dicha cadena, se dice entonces que la sentencia no pertenea ce al lenguaje, y el compilador emite un mensaje de error, pero el proceso de compilacin trata de continuar [4]. o 2.3.2. Derivaciones ms a la izquierda y ms a la derechas a a

Las reglas de derivacin que se aplican desde el s o mbolo inicial hasta alcanzar la sentencia a reconocer, pueden reemplazar los s mbolos no terminales tomando el de ms a la izquierda (derivaciones ms a la izquierda) o tomando el no a a terminal de ms a la derecha (derivaciones ms a la derecha). A estos dos tipos a a de derivaciones se les llama derivaciones cannicas[4]. o

Figura 1: Ejemplo de rbol de derivacin de la expresin x + y x a o o

2.3.3.

Gramticas ambiguas a

Una sentencia generada por una gramtica es ambigua si existe ms de un a a a rbol sintctico para ella. Una gramtica es ambigua si genera al menos una a a sentencia ambigua, en caso contrario es no ambigua. El grado de ambigedad de una sentencia se caracteriza por el nmero de u u a rboles sintcticos distintos que la generan. a La ambigedad de una gramtica es una propiedad indecidible, lo que signiu a

ca que no existe ningn algoritmo que acepte una gramtica y determine con u a certeza y en un tiempo nito si la gramtica es ambigua o no[4]. a 2.3.4. Conversin de gramticas ambiguas en no ambiguas o a

Se ha indicado anteriormente que la propiedad de ambigedad es indecidible, u es decir, no existe ni puede construirse un algoritmo que, tomando una gramtia ca, determine con certeza, y en plazo nito de tiempo, si es ambigua o no. Sin embargo, se han desarrollado las condiciones que, de cumplirse, garantizan la no ambigedad, aunque en caso de que no se cumplan no puede armarse nada. u Son condiciones sucientes pero no necesarias[4]. Una gramtica ambigua produce problemas al analizador sintctico, por lo a a que interesa construir gramticas no ambiguas. a

3.
3.1.

Gramtica para el lenguaje C a

Existen seis clases de componentes lxicos: identicadores, palabras resere vadas, constantes, cadenas literales, operadores, y otros separadores. Los espacios en blanco, tabuladores horizontales y verticales, nueva linea, etc, son ignorados[3]. 3.1.1. Identicadores

Un identicador es una secuencia de letras y digitos. El primer carcter debe a ser una letra. Las letras minscula y mayscula son diferentes. u u 3.1.2. Palabras reservadas

Los siguientes identicadores son palabras reservadas y no se pueden utilizar de otro manera: auto break case char 3.1.3. Constantes double else enum extern int long register return struct switch typedef union

Hay varios tipos de constantes. Cade una tiene un tipo de dato. constant: integer-constant character-constant oating-constant

enumeration-constant

3.1.4.

Cadenas literales

Una cadena literal, tambin llamada cadena es una secuencias de caracteres e delimitados por comillas, como en Hola Mundo[3].

3.2.

Gramtica completa de lenguaje C a

Los s mbolos terminales estan representados por el formato de letra italica y negrita. translation-unit: external-declaration translation-unit external-declaration external-declaration: function-denition declaration function-denition: declaration-speciersopt declarator declaration-listopt compound-statement declaration: declaration-speciers init-declarator-lisopt ; declaration-list: declaration declaration-list declaration declaration-speciers: storage-class-specier declaration-speciersopt type-specier declaration-speciersopt type-qualier declaration-speciersopt storage-class specier: one of auto register static extern typedef type specier: one of void char short int long oat double signed unsigned struct-or-union-specier enum-specier typedef-name type-qualier: one of const volatile

struct-or-union-specier: struct-or-union identieropt struct-declaration-list struct-or-union identier struct-or-union: one of struct union struct-declaration-list: struct declaration struct-declaration-list struct declaration init-declarator-list: init-declarator init-declarator-list, init-declarator init-declarator: declarator declarator = initializer struct-declaration: specier-qualier-list struct-declarator-list; specier-qualier-list: type-specier specier-qualier-listopt type-qualier specier-qualier-listopt struct-declarator-list: struct-declarator struct-declarator-list , struct-declarator struct-declarator: declarator declaratoropt : constant-expression enum-specier: enum identieropt enumerator-list enum identier enumerator-list: enumerator enumerator-list , enumerator enumerator: identier identier = constant-expression

declarator: pointeropt direct-declarator direct-declarator: identier (declarator) direct-declarator [ constant-expressionopt ] direct-declarator ( parameter-type-list ) direct-declarator ( identier-listopt ) pointer: * type-qualier-listopt * type-qualier-listopt pointer type-qualier-list: type-qualier type-qualier-list type-qualier parameter-type-list: parameter-list parameter-list , ... parameter-list: parameter-declaration parameter-list , parameter-declaration parameter-declaration: declaration-speciers declarator declaration-speciers abstract-declaratoropt identier-list: identier identier-list , identier initializer: assignment-expression initializer-list initializer-list , initializer-list: initializer initializer-list , initializer type-name: specier-qualier-list abstract-declaratoropt

10

abstract-declarator: pointer pointeropt direct-abstract-declarator direct-abstract-declarator: ( abstract-declarator ) direct-abstract-declaratoropt [constant-expressionopt ] direct-abstract-declaratoropt (parameter-type-listopt ) typedef-name: identier statement: labeled-statement expression-statement compound-statement selection-statement iteration-statement jump-statement labeled-statement: identier : statement case constant-expression : statement default : statement expression-statement: expressionopt ; compound-statement: declaration-listopt statement-listopt statement-list: statement statement-list statement selection-statement: if (expression) statement if (expression) statement else statement switch (expression) statement iteration-statement: while (expression) statement do statement while (expression); for (expressionopt ; expressionopt ; expressionopt ) statement jump-statement: 11

goto identier; continue; break ; return expressionopt ; expression: assignment-expression expression , assignment-expression assignment-expression: conditional-expression unary-expression assignment-operator assignment-expression assignment-operator: one of = *= /= %= += -= <<= >>= &= = |= conditional-expression: logical-OR-expression logical-OR-expression ? expression : conditional-expression constant-expression: conditional-expression logical-OR-expression: logical-AND-expression logical-OR-expression logical-AND-expression logical-AND-expression: inclusive-OR-expression logical-AND-expression && inclusive-OR-expression inclusive-OR-expression: exclusive-OR-expression inclusive-OR-expression | exclusive-OR-expression exclusive-OR-expression: AND-expression exclusive-OR-expression AND-expression AND-expression: equality-expression AND-expression & equality-expression equality-expression: relational-expression equality-expression == relational-expression 12

equality-expression != relational-expression relational-expression: shift-expression relational-expression relational-expression relational-expression relational-expression

< shift-expression > shift-expression <= shift-expression >= shift-expression

shift-expression: additive-expression shift-expression << additive-expression shift-expression >> additive-expression additive-expression: multiplicative-expression additive-expression + multiplicative-expression additive-expression - multiplicative-expression multiplicative-expression: multiplicative-expression * cast-expression multiplicative-expression / cast-expression multiplicative-expression % cast-expression cast-expression: unary expression (type-name) cast-expression unary-expression: postx expression ++unary expression - -unary expression unary-operator cast-expression sizeof unary-expression sizeof (type-name) unary operator: one of & * + - ! postx-expression: primary-expression postx-expression[expression] postx-expression(argument-expression-listopt ) postx-expression.identier postx-expression > +identier postx-expression++ 13

postx-expression primary-expression: identier constant string (expression) argument-expression-list: assignment-expression assignment-expression-list , assignment-expression constant: integer-constant character-constant oating-constant enumeration-constant En la gramtica del lenguaje al parecer solo hay una posible ambigedad a u con respecto al uso del if-else, la cual puede ser evitada con el uso de llaves.

4.

Conclusiones

La gramtica del lenguaje C esta construida con el n de evitar cualquier a posible ambigedad, por lo cual C es uno de los lenguajes mas estables y podeu rosos, ya que todos los componentes que conforman el compilador (Analizador Lxico, Sintactico, Smantico, etc) son sumamento ables a la hora de realizar e e su correspondiente tarea.

14

5.

Bibliograa

Referencias
[1] Curso Cinvestav: http://acme.math.cinvestav.mx/~basico/cuatro. html [2] Alex Aiken Compilers: http://www.stanford.edu/class/cs143/ lectures/02/Slides02.pdf [3] Kernighan, Brian W.; Dennis M. Ritchie (February 1978). The C Programming Language (1st ed.). Englewood Clis, NJ: Prentice Hall. ISBN 0-13-110163-3. Regarded by many to be the authoritative reference on C. [4] M. Cndida Luengo D Juan Manuel Cueva Lovelle, Francisco Ort Soa ez, n ler, Ral Izquierdo Castanedo, Aquilino A. Juan Fuente, Jose Emilio Labra u Gayo (Enero 2005) ANALISIS SINTACTICO EN PROCESADORES DE LENGUAJE

15