Teoría de Compiladores (1era Parte) - ¿Qué es un compilador?

Cuando se habla de compiladores (bajo el marco lógico de la teoría de compiladores y sobre el contexto de la ingeniería en informática) nos referimos a un tipo de programa de sistema conocido como procesador de lenguaje. Los procesadores de lenguaje mas conocidos son los compiladores y los interpretes (mas no son todos), y la diferencia entre estos radica en la forma como procesan en lenguaje y la salida que se obtiene.


En lineas generales, un compilador (como procesador de lenguaje) es un programa que recibe como entrada un programa escrito en un lenguaje fuente y que da como salida la traducción de ese programa a un lenguaje destino. Normalmente la mayoría de los compiladores usan como lenguaje destino el código maquina, que no es otra sino el lenguaje que entienden las computadoras.


ENTRADA -> [COMPILADOR] -> SALIDA


Un compilador no es un programa aislado sino que para lograr el objetivo de traducir un programa al lenguaje maquina necesita la ayuda de otros programas. La tarea de recolectar los archivos que conforman el programa de origen es llevado a cabo por el pre-procesador. Este a su vez se encarga de expandir fragmentos de código conocidos como macros. La salida del pre-procesador es la entrada del compilador, que dará como salida el programa en lenguaje ensamblador. Esta salida del compilador pasara a un programa conocido como Ensamblador y este producirá codigo maquina a partir del código ensamblador y por ultimo si el programa ha sido compilado en partes el Enlazador es el ultimo programa en realizar su labor al unir las distintas partes del programa en código maquina.


Por tanto el proceso de compilación en general esta representado de la siguiente forma:


Codigo Fuente -> [Pre-procesador] -> [Compilador] -> [Ensamblador] -> [Enlazador] -> Programa.




Ahora bien, el compilador mas que ser un programa que realiza un trabajo mágico como si de una caja negra se tratara, consta en realidad de dos grandes sub-procesos: El Análisis y la Síntesis.


En el famoso libro del dragon ("Compiladores. Principios, Tecnicas y Herramientas" de Alfred. Aho, Monica Lam, Ravi Sethi y Jeffrey Ullman, 2da Edición 2008) se nos explica bajo el apartado 1.2 Estructura de un compilador lo siguiente:

La parte de análisis divide el programa fuente en componentes e impone una estructura gramatical sobre ellas. Después utiliza esta estructura para crear una representación intermedia del programa fuente [...]. La parte del análisis tambien recolecta información sobre el programa fuente y la almacena en una estructura de datos llamada tabla de símbolos, la cual se pasa junto con la representación intermedia a la parte de síntesis.

María del Mar Aguilera Sierra y Sergio Gálvez Rojas en su obra "Traductores, Compiladores e Intérpretes" en el tema "Tabla de Símbolos" explican en que consiste esta particular estructura de datos:

La tabla almacena la información que en cada momento se necesita sobre las variables del programa, información tal como: nombre, tipo, dirección de localización, tamaño, etc. La gestión de la tabla de símbolos es muy importante, ya que consume gran parte del tiempo de compilación. De ahí que su eficiencia sea crítica. Aunque también sirve para guardar información referente a los tipos creados por el usuario, tipos enumerados y, en general, a cualquier identificador creado por el usuario.

Permanece sólo en tiempo de compilación, no de ejecución, excepto en aquellos casos en que se compila con opciones de depuración.

En el libro del dragón (citado anteriormente) se nos da información adicional:

La tabla de símbolos es una estructura de datos que contiene un registro para cada nombre de variable, con campos para los atributos del nombre. La estructura de datos debe estar diseñada de tal forma que permita al compilador buscar el registro para cada nombre o almacenar u obtener los datos de ese registro con rapidez.

De forma que, tenemos como salidas del proceso de análisis dos estructuras de datos: La tabla de símbolos y representación intermedia del programa fuente. El árbol sintáctico es normalmente la estructura de datos usada para representar de forma intermedia el código fuente. Ambas estructuras pasan al proceso de síntesis que según los autores Aho, Lam, Sethi y Ullman consiste en:

contru[ir] el programa destino deseado a partir de la representación intermedia y de la información de la tabla de símbolos. A la parte de análisis se le llama comúnmente el front-end del compilador; la parte de síntesis (propiamente la traducción es el back-end.

Observando con más detalle el proceso de compilación podemos notar que esta compuesto de fases teóricamente definidas pero que en la practica pueden solaparse y agruparse. Estas fases transforman una representación del programa fuente en otro. La tabla de símbolos es usada es todas las fases de compilación.


En otra vertiente podemos preguntarnos: ¿Cuales son cada una de estas fases?, ¿Como realizan su trabajo? ¿Cuales son sus entradas y salidas? y ¿En que consiste el agrupamiento de fases en pasadas?.


Todas interrogantes serán respondidas en la segunda parte de esta serie sobre teoría de compiladores:  Teoría de Compiladores (2da Parte) - Fases de un compilador

MouseMover... Aprendiendo a Mover El cursor del Mouse en C.

1. #include <windows.h>
2. /*Este programa ha sido desarrollado por Kellerman Rivero krsloco@gmail.com
3. con propositos educativos, y no me hago responsable por el uso que se le pueda
4. dar*/
6. /*Este programa obtiene la resolucion de la pantalla en windows y
7. mueve el puntero cerca de la diagonal principal de la pantalla.*/
9. /*Kellerman Rivero Suarez
10. krsloco@gmail.com*/
12. /*Dedicado a mi novia bella.. Johana Romero Ten
13. Agradecimientos a enrique zambrano y otros colaboradores*/
15. int WINAPI WinMain (HINSTANCE hThisInstance,
16.                     HINSTANCE hPrevInstance,
17.                     LPSTR lpszArgument,
18.                     int nFunsterStil)
19. {
20.    char XW[10];                        
21.    char YW[10];
22.    RECT area;
23.    long lret;                
24.    int x,y;
25.    long x_max;
26.    long y_max;
27.    
28.    lret=SystemParametersInfo(SPI_GETWORKAREA,0,&area,0);
29.    x_max =  area.right - area.left;
30.    y_max =  area.bottom - area.top;
32.    for(;;){
33.    for(x=0;x<x_max;){
34.                       for(y=0;((x<x_max)&&(y<y_max));(y+=10),(x+=10)){
35.                                          
36.                                          SetCursorPos(x,y);
37.                                          Sleep(100);
38.                                          }                  
39.    }
40.    }
41. }

Juego el Brujo en ASM.

1. [ORG 7C00h]        
2.          
3. ; Codigo desarrollado por Kellerman Rivero, krsloco@gmail.com
5.          xor ax,ax
6.          mov ax,cs ; Mueve al registro AX (Acumulador) el contenido del Registro CS (Code Segment)
7.          mov ds,ax ; Mueve al registro DS (Data Segment) el contenido del registro AX (Acumulador)
8.          ;Por tanto hemos colocado el DS en la misma direccion apuntada por CS.
9.          mov es,ax ; Mueve al registro ES (Extra Segment) el contenido del registro AX(Acumulador)
10.          mov ax,00 ; Peticion para limpiar pantalla
11.          mov al,03
12.          int 0x10;
13.          mov cx,longmas
14.          ;mov si, mascara
15.          ;mov di, respuesta
16.          lea di, [respuesta]
17.          lea si, [mascara]
18.          jmp cargar_respuesta
20. mascara db 'El Brujo:',0
21. longmas equ $-mascara
22. norep db 'No puedo responder tu pregunta',13,0
23. longnorep equ $-norep
24. respuesta resb longmas  
26. cargar_respuesta:
27.          xor ax,ax
28.          int 16h       
29.          mov dl,al
30.          mov al,[si]
31.          mov ah,0x0E            
32.          mov bx,0x0007          
33.          int 0x10
34.          mov [di],dl
35.          inc di;
36.          inc si;
37.          loop cargar_respuesta
38.          mov cx,longmas
39.          lea si, [respuesta]
40.          jmp cargar_pregunta
42. mostrar_respuesta:
43.          xor ax,ax
44.          int 16h
45.          cmp ah,1Ch
46.          jne mostrar_respuesta
47.          mov ax,00 ; Peticion para limpiar pantalla
48.          mov al,03
49.          int 0x10;       
50.          ciclo:
51.          mov al,[si]
52.          cmp al,2Eh
53.          je hang
54.          mov ah,0x0E            
55.          mov bx,0x0007          
56.          int 0x10
57.          inc si
58.          loop ciclo
59.          jmp hang
61. cargar_pregunta:
62.         xor ax,ax
63.         int 16h
64.         mov dh,ah
65.         mov ah,0x0E            
66.         mov bx,0x0007          
67.         int 0x10
68.         cmp dh,35h
69.         je mostrar_respuesta   
70.         jmp cargar_pregunta            
72. hang:   jmp hang                ; Hang
73.        
74. times 512-($-$$)-2 db 0
75.         dw 0AA55h
    
    Esta es la version en emsablador de mi juego realizado en C, el brujo responde. Interesante para pasar ratos.
    
    
    
    

Proyecto Keejoo, un cliente para twitter escrito en C. (Introducción a OAuth)

Introducción

El protocolo OAuth provee un método para que clientes accedan a recursos en un servidor sin ser el dueño del mismo. Provee un proceso para que los usuarios finales den permiso a aplicaciones de terceros para acceder a los recursos en el servidor sin hacer necesaria el intercambio del par/dato usuario/contraseña.

He empezado el desarrollo de un minicliente Twitter en Lenguaje C y usando las librerias GTK3 para Gnome 3. Es necesario conocer las bases sobre las que se sustenta el desarrollo de este Cliente para Twitter y es por eso que he escrito el articulo.


Nombre: Keejoo
Descripción: Cliente para Twitter.
Lenguaje: C
Librerias (Dependencias): libpng libxml2 gtk+-3.0 libcurl liboauth
IDE: Anjuta
URL: http://code.google.com/p/keejoo/
Plataforma: Fedora 15


Detalles

El protocolo OAuth fue originalmente creado por una pequeña comunidad de desarrolladores web de una variedad de sitios web y servicios de Internet para resolver el problema comun de permitir acceso delegado a recursos protegidos.

El protocolo OAuth resultante fue estabilizado a la versión en octubre de y revisado en Junio de 2009.

En el modelo de autenticación tradicional, el cliente usa credenciales (usuario/contraseña) para acceder a recursos hospedados por un servidor. Con el aumento de los servicios web distribuidos y la computación en la nube, aplicaciones de terceros requieren acceso a esos recursos hospedados en los servidores.

OAuth introduce un tercer rol en el modelo de autenticación tradicional Cliente/Servidor: El dueño del recurso. En el modelo OAuth, el cliente (que no es el dueño del recurso pero tiene relación con el) requiere acceso a los recursos controlados por el dueño del recurso, pero hospedados en el servidor. Ademas, OAuth permite al servidor verificar no solo la autorización del dueño del recurso, sino también la identidad del cliente que esta haciendo la petición.


Twitter

La API de autenticación de Twitter esta basada en OAuth. Esto quiere decir que hace falta una implementación del protocolo OAuth para poder acceder a los recursos alojados en el servidor Twitter.

Proceso de autenticación de Twitter

Antes de comenzar a hablar sobre el proceso de autenticación con twitter, necesitamos definir algunos conceptos utiles.

Token: Identificador unico usado por el servidor y usado por cliente para asociar peticiones de autenticación con el dueño del recurso cuando es requerida autorización o es obtenida por el cliente. Los Token tienen un par correspondencia Shared/Secret (Compartido/Secreto) utilizado por el cliente para establecer su propiedad sobre el token y para representar al dueño del recurso.

• Consumer: Cliente

• Service Provider: Servidor

• User: Dueño del recurso.

• Consumer Key and Secret: Credenciales del Cliente.

• Request Token and Secret: Credenciales Temporales (se usan para la comunicación pre-autenticación con el servidor)

• Access Token and Secret: Credenciales de Acceso (lo concede el servidor al cliente autorizado previamente por el dueño del recurso para que pueda acceder a los recursos alojados en el servidor)

El ciclo de autenticación es sencillo:

1. Se recupera/obtiene el Request Token and Secret.

1. Se solicita la autorización redireccionando al User a la pagina de acceso (login) Twitter.com. (Metodo PIN)

1. Se cambia el Request Token and Secret por un Access Token and Secret

Cabecera de Keejoo para autenticación con Twitter

El archivo api_twitter.h contiene las funciones necesarias para la autenticación mediante el protocolo OAuth con Twitter.

char* get_token (char *resource, char **key, char **secret, char *oauth_key, char *oauth_secret, char **username):

Funcion para la recuperacion/obtencion del Request Token and Secret y el intercambio del Request Token and Secret recuperado por el Access Token and Secret

void get_authorize_url(char *oauth_token, char **authorize_url):

Devuelve la URL de acceso (login) Twitter de redirección para obtener autorizaciòn.

void create_file_with_access_token (char username[MAX_USERNAME_LENGTH],char *access_token_key, char *access_token_secret):

Crea un archivo binario que contiene una copia de las credenciales Access Token and Secret para su posterior uso. Evita la solicitud constante al Service Provider del Access Token and Secret usando una copia local de las ultimas credenciales.

int load_file_with_access_token(char username[MAX_FILENAME_LENGTH], char **access_token_key, char **access_token_secret):

Permite cargar la copia local de las credenciales Access Token and Secret creadas con la función anterior.

char* get_resource (char *resource, char *access_token_key, char *access_token_secret):

Solicita un recurso al Service Provider.

void get_token_in_parameters(char *reply, char **key, char **secret, char **username):

Obtiene los Token devueltos por el Service Provider en la URL de respuesta.

Arboles en C [Parte I. Definición De Arbol y Estructura del Nodo]

Deseo reanudar la escritura de mi blog con un interesante articulo sobre arboles. Ya he escrito sobre otros temas como inteligencia artificial, o algoritmos genéticos sin haberme verme visto en la necesidad de implementar directamente los conceptos explicados, pero en esta ocasión deseo explicar un sub-area de la informática: Los arboles (que derivan de la teoría de los grafos) aplicando una metodología totalmente distinta.

Para muchos el concepto de árbol es difícil de comprender, al fin y al cabo cuando se nos introduce en la programación se nos enseña a pensar linealmente, esto es una perspectiva un tanto irreal del mundo que nos rodea,¿Como representar entonces modelos de datos no secuenciales?, como por ejemplo: la información de mapas. He aquí donde la teoría de grafos hizo su aparición. Y no quiero adentrarme mucho en ella puesto que me desviaría del tema que estoy tratando, pero para fines prácticos y sencillos, un grafo es un tipo de estructura de datos no lineal.

Y un árbol, es un tipo de grafo jerarquizado,una estructura de datos dinamica.
El Árbol este compuesto por Nodos. Un nodo es la unidad sobre la que se construye un árbol, (similar a los nodos con lo que se construye una pila, cola o lista dinámica).

Veamos algunas propiedades de los nodos.

• Un nodo puede tener o no hijos.
• Un nodo sin hijos se conoce como nodo hoja.
• Cada nodo de un árbol es un sub-árbol en si mismo.

 El hecho de que un nodo sea un sub-arbol en si mismo denota las propiedades recursivas de los arboles, y sera de ahora en adelante el elemento clave para tu trabajo.

Definición de un nodo en C.

#define MAX_HIJOS 2

struct nodo_tree {
     <tipo_de_dato> info;
     struct nodo_tree *hijos[MAX_HIJOS];
} nodo;

Como podemos observar la forma mas simple de construir un nodo en C es usando una estructura (struct) ... Podemos observar las caracteristicas esenciales de un nodo.

• Posee una parte de información que puede ser un tipo de dato simple o una estructura mas compleja.
• Posee un conjunto de punteros del tipo de la propia estructura.

Podemos mejorar nuestra estructura incluyendo una definición de tipos, creando un nuevo tipo de dato llamado nodo.

#define MAX_HIJOS 2

typedef struct _tree {
     int info;
     struct _tree *hijos[MAX_HIJOS];
} tnodo;

Ahora tenemos un nuevo tipo de dato llamado tnodo, y podemos crear variables del tipo tnodo (Esto nos simplificara mucho el trabajo de ahora en adelante). La estructura interna de tnodo es muy similar a la anterior, el campo de información para fines didácticos es de tipo entero (int) y el tipo tnodo contiene 2 punteros. Esto hace que el arbol que podamos construir usando este nodo sea un arbol binario (binario por que usa una pareja de apuntadores).

En la próxima entrega veremos nuestros primeros algoritmos relacionados a los arboles.

[Metaprogramación] QuineK... Mi primer Quine.

Leyendo sobre metaprogramacion, decidí hacer mi primer Quine.. o para los que no conocen el termino, un programa capaz de generar como salida su código fuente...acepto sugerencias o correcciones.

#include <stdio.h>
char fuente[] = {
  'i',
  'n',
  't',
  ' ',
  'm',
  'a',
  'i',
  'n',
  '(',
  ')',
  '{',
  '\n',
  '\t',
  'i',
  'n',
  't',
  ' ',
  'i',
  ';',
  '\n',
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '#',
  'i',
  'n',
  'c',
  'l',
  'u',
  'd',
  'e',
  '<',
  's',
  't',
  'd',
  'i',
  'o',
  '.',
  'h',
  '>',
  '\\',
  'n',
  'c',
  'h',
  'a',
  'r',
  ' ',
  'f',
  'u',
  'e',
  'n',
  't',
  'e',
  '[',
  ']',
  ' ',
  '=',
  ' ',
  '{',
  '\\',
  'n',
  '"',
  ')',
  ';',
  '\n',
  '\t',
  'f',
  'o',
  'r',
  '(',
  'i',
  '=',
  '0',
  ';',
  'f',
  'u',
  'e',
  'n',
  't',
  'e',
  '[',
  'i',
  ']',
  ';',
  'i',
  '+',
  '+',
  ')',
  '{',
  '\n',
  '\t',
  '\t',
  's',
  'w',
  'i',
  't',
  'c',
  'h',
  '(',
  'f',
  'u',
  'e',
  'n',
  't',
  'e',
  '[',
  'i',
  ']',
  ')',
  '{',
  '\n',
  '\t',
  '\t',
  '\t',
  'c',
  'a',
  's',
  'e',
  ' ',
  '\'',
  '\\',
  'n',
  '\'',
  ':',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '\\',
  't',
  '\'',
  '\\',
  '\\',
  'n',
  '\'',
  ',',
  '\\',
  'n',
  '"',
  ')',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'b',
  'r',
  'e',
  'a',
  'k',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  'c',
  'a',
  's',
  'e',
  ' ',
  '\'',
  '\\',
  't',
  '\'',
  ':',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '\\',
  't',
  '\'',
  '\\',
  '\\',
  't',
  '\'',
  ',',
  '\\',
  'n',
  '"',
  ')',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'b',
  'r',
  'e',
  'a',
  'k',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  'c',
  'a',
  's',
  'e',
  ' ',
  '\'',
  '\\',
  '\\',
  '\'',
  ':',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '\\',
  't',
  '\'',
  '\\',
  '\\',
  '\\',
  '\\',
  '\'',
  ',',
  '\\',
  'n',
  '"',
  ')',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'b',
  'r',
  'e',
  'a',
  'k',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  'c',
  'a',
  's',
  'e',
  ' ',
  '\'',
  '\\',
  '\'',
  '\'',
  ':',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '\\',
  't',
  '\'',
  '\\',
  '\\',
  '\\',
  '\'',
  '\'',
  '\\',
  'n',
  '"',
  ')',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'b',
  'r',
  'e',
  'a',
  'k',
  ';',
  '\n',
  '\t',
  '\t',
  '\t',
  'd',
  'e',
  'f',
  'a',
  'u',
  'l',
  't',
  ':',
  '\n',
  '\t',
  '\t',
  '\t',
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '\\',
  't',
  '\'',
  '%',
  'c',
  '\'',
  ',',
  '\\',
  'n',
  '"',
  ',',
  'f',
  'u',
  'e',
  'n',
  't',
  'e',
  '[',
  'i',
  ']',
  ')',
  ';',
  '\n',
  '\t',
  '\t',
  '}',
  '\n',
  '\t',
  '}',
  '\n', 
  '\t',
  'p',
  'r',
  'i',
  'n',
  't',
  'f',
  '(',
  '"',
  '\\',
  't',
  '0',
  '\\',
  'n',
  '}',
  ';',
  '\\',
  'n',
  '\\',
  'n',
  '%',
  's',
  '\\',
  'n',
  '"',
  ',',
  'f',
  'u',
  'e',
  'n',
  't',
  'e',
  ')',
  ';',
  '\n',
  '\t',
  'r',
  'e',
  't',
  'u',
  'r',
  'n',
  ' ',
  '0',
  ';',
  '\n',
  '}',
  0
};

int main(){
  int i;
  printf("#include <stdio.h>\nchar fuente[] = {\n");
  for(i=0;fuente[i];i++){
    switch(fuente[i]){
      case '\n':
           printf("\t'\\n',\n");
           break;
      case '\t':
           printf("\t'\\t',\n");
           break; 
      case '\\':
           printf("\t'\\\\',\n");
           break; 
      case '\'':
           printf("\t'\\\'',\n");
           break; 
      default:
           printf("\t'%c',\n",fuente[i]);
    }
    
  }
  printf("\t0\n};\n\n%s\n",fuente);
  return 0;
}

Listas con Recursividad e Indirección Multiple.

Indirección Multiple, Listas, y estructuras...

/* header para el manejo de listas, realizando algoritmos 
de indireccion multiple y algoritmos recursivos....

desarrollado por kellerman rivero krsloco@gmail.com
bajo licencia creative commons, 

Muestra la manera de utilizar punteros a punteros de estructuras..
y algunos detalles adicionales... 

Aunque se puede simplificar cada una de las funciones
haciendo que no devuelvan valor, he decidido dejarlas
implementadas de esa forma, con la finalidad de poder hacer
hacer asignaciones del tipo:

puntero_lista = funcion_ex(&puntero_principal,parametros...);

de forma tal, que se puede pasar el puntero principal de la 
lista sin miedo a perderlo, a la vez que la funcion retorna
una copia del puntero principal que puede ser almacenada en otra 
parte.

Puede tener errores, asi que acepto sugerencias.


CULTCA (UNELTCA) 2010... 
Kellerman Rivero

*/

#include  <stdio.h>
#include  <stdlib.h>
#include  <time.h>


/*funcion de inserción por el inicio
mejorada con indireccion multiple */
lista *insertar_inicio_ex (lista **inicio, int valor){
    lista *q;
    if((q = solicitar_nodo())!=NULL){
      q -> info = valor;
      q -> sig = *inicio;
      *inicio = q;
    } else printf("Memoria no Disponible \n");
    return *inicio;
}

/*funcion de eliminacion por el inicio
mejorada con indireccion multiple */
lista *eliminar_inicio_ex (lista **inicio){ 
    if (inicio != NULL){
      lista *q;
      q = *inicio;
      *inicio = (*inicio)->sig;
      free(q);
      return *inicio;
    } else return NULL;
}

/*funcion de insercion al final de la lista usando
indireccion multiple */
lista *insertar_final_ex (lista **inicio, int valor){
   if (*inicio != NULL){
     lista *q,*w; w = *inicio;
     while ( w->sig != NULL)
       w = w->sig;
     if((q = solicitar_nodo())!=NULL){
      q -> info = valor;
      q -> sig = NULL;
      w -> sig = q;
     } else printf("Memoria no Disponible \n");
     return *inicio;
   } else {
     insertar_inicio_ex(inicio,valor);
     return *inicio;
   }
}

/*Funcion de eliminacion al final de la lista 
mejorada con indireccion multiple */
lista *eliminar_final_ex (lista **inicio){
  lista *q,*w;
  if (*inicio != NULL){
    if((*inicio)->sig == NULL) eliminar_inicio_ex(inicio);
    else {
      w = *inicio; 
      while (w->sig != NULL){
  q = w;
  w = w -> sig;
      }
      q -> sig = NULL;
      free(w); 
    }
    return *inicio;
  } else return NULL;
}

/*funcion de eliminacion al final de la lista
usando recursividad (mas recursos) e indireccion multiple*/
lista *eliminar_final_rex (lista **inicio){ 
  if(*inicio != NULL){
    if((*inicio)->sig==NULL) eliminar_inicio_ex(inicio);
    else{
     if  ((*inicio)->sig->sig != NULL) {
       lista *q;
       q = (*inicio)->sig;
       eliminar_final_rex(&q);
     } else if((*inicio)->sig!=NULL) {
       free((*inicio)->sig);
       (*inicio)->sig = NULL;
     }
    }
  } else return NULL;
}

/*funcion de insercion al final de la lista
usando recursividad (mas recursos) e indireccion multiple*/
lista *insertar_final_rex(lista **inicio, int valor){ 
  if(*inicio != NULL){
    lista *q,*a;
     if((*inicio)->sig == NULL){
       if((q = solicitar_nodo())!=NULL){
            q -> info = valor;
     q -> sig = NULL;
     (*inicio)->sig =q;  
       } else {
        printf("Memoria no Disponible \n");
        return NULL;
       }
     } else {
 q= (*inicio)->sig;
       insertar_final_rex(&q,valor);
     }
  } else {
     return insertar_inicio_ex(inicio,valor);
  }
}

/*Funcion de inicializacion simple*/
lista *inicializar_ex(lista **inicio){
  *inicio = NULL;
  return *inicio;
}

lista *liberar_ex(lista **inicio){
  if (*inicio != NULL){
  while((*inicio)->sig != NULL)
    eliminar_inicio_ex(inicio);
    
    inicializar_ex(inicio);
  }
  return *inicio;
}

/*funcion de inicializacion de la lista
con n-nodos con informacion aleatoria */
lista *inicializar_random_ex(lista **inicio,int num_nodos){
  lista *q;
  if(*inicio != NULL) {liberar_ex(inicio);}
  inicializar_ex(inicio);
  srand(time(NULL));
  while(num_nodos--){
    insertar_inicio_ex(inicio,1+rand()%20);
  }
  return *inicio;
}


/*Combina dos valores, y los introduce en la lista_destino.. */
lista *combinar_valores_ex (lista** lista_destino, int valor1, int valor2){
  insertar_final_ex(lista_destino,(valor1 + valor2));
  return *lista_destino;
}

lista *fusion_nodos_regla01 (lista **lista_p, lista **lista_w){
    lista *P = *lista_p;
    liberar_ex(lista_w);
    while(P->sig != NULL){
    combinar_valores_ex(lista_w,P->info,P->sig->info);
    if (P->sig->sig != NULL){ /*si podemos desplazarnos 2 posiciones lo hacemos*/
      P = P->sig->sig;
    } else { 
      break; 
    }
  }
  if ((P->sig==NULL)) combinar_valores_ex(lista_w,P->info,0);
  return *lista_w;
}

lista *fusion_nodos_regla02 (lista** lista_p, lista** lista_w){
    lista *i,*j;
    i = j =  *lista_p;
    liberar_ex(lista_w);
    while((i->sig!=NULL)&&(j->sig!=NULL)){
      /*Si nodo->info apuntado por i es impar*/
      if(i->info%2){ 
 /*Si el siguiente del nodo apuntado por j es distinto
 de NULL, y j es impar nos seguimos desplazando hasta 
 conseguir un nodo->info apuntado por j par, o se acabe 
 la lista */
 while((j->sig!=NULL)&&(j->info%2))   
     j=j->sig;
 
 /*Al salir del ciclo mientras, preguntamos si 
 el ultimo nodo->info apuntado por j es par..
 en caso afirmativo, realizamos la fusion de nodos */
 if (j->info%2==0) //
    combinar_valores_ex(lista_w,i->info,j->info);
      }
      
      i=i->sig; /*nos seguimos desplazando con el apuntador i.*/
      if(j->sig!=NULL)j=j->sig;
    } 
    printf("Resultado: ");
    //imprimir_lista(*lista_w,0);
  return *lista_w;
}
      

void menu_ex(lista **P, lista **W){
     int r, n_nodos=0;
     do {
         system("cls");
         printf("************************************************\n");
         printf("* USANDO INDIRECCION MULTIPLE (lista **inicio) *\n");         
         printf("************************************************\n");
         printf("************************************************\n");
         printf("*1)  Inicializar Lista                         *\n");
         printf("*2)  Imprimir    Lista                         *\n");
         printf("*3)  Insertar Inicio                           *\n");         
         printf("*4)  Insertar Final                            *\n");
         printf("*5)  Insertar Final Recursivo                  *\n");                  
         printf("*6)  Eliminar Inicio                           *\n");
         printf("*7)  Eliminar Final                            *\n");         
         printf("*8)  Eliminar Final Recursivo                  *\n");         
         printf("*9)  Liberar Lista                             *\n");         
         printf("*10) Crear Fusion (SubLista) (Ejer. 01)        *\n");         
         printf("*11) Crear Fusion (SubLista) (Ejer. 02)        *\n");
         printf("*12) Menu Disponible (Ejer. XX)                *\n");   
         printf("************************************************\n");
         printf("************************************************\n");         
         printf("*    PRESIONE CERO PARA SALIR DEL PROGRAMA     *\n");
         printf("************************************************\n");
         scanf("%d",&r);
         switch(r){
                   case 1: 
                         system("cls");
                         printf("Introduzca el numero de nodos: ");
                         scanf("%d",&n_nodos);
                         inicializar_random_ex(P,n_nodos);
                         break;
                   case 2: 
                         system("cls");
                         imprimir_lista(*P,0);
                         break;
                   case 3:
                         insertar_inicio_ex(P,1+rand()%20);
                         break;
                   case 4:
                         insertar_final_ex(P,1+rand()%20);
                         break;
                   case 5:
                         insertar_final_rex(P,1+rand()%20);
                         break;
                   case 6:
                         eliminar_inicio_ex(P);
                         break;
                   case 7:
                         eliminar_final_ex(P);
                         break;
                   case 8:
                         eliminar_final_rex(P);
                         break;
                   case 9:
                         liberar_ex(P);
                         break;
                   case 10:
                         fusion_nodos_regla01(P,W);
                         break;
                   case 11:
                         fusion_nodos_regla02(P,W);
                         break;
                   default: 
                         printf("Opcion invalida \n");
         }
         
         if (r != 2) {system("cls"); imprimir_lista(*P,0);}
         if ((r > 9) && (r<12))imprimir_lista(*W,0);
         n_nodos = getch();
     } while (r =! 0);
}

Ahora el programa principal...

#include  <stdio.h>
#include  <stdlib.h>
#include  "lista.h"
//#include  "listas_normales.h"
#include  "listas_indireccion.h"
#define MODO_HORIZONTAL 0
#define MODO_VERTICAL 1

int main(){
  int n_nodos;
  lista *P,*W;
  inicializar_ex(&P);
  inicializar_ex(&W);
  menu_ex(&P,&W);
  return 0;
}

Listas en C con recursividad

listas.h:

/* header para el manejo de listas....
desarrollado por kellerman rivero krsloco@gmail.com
bajo licencia creative commons, 

el manejo de listas, realizando algoritmos convencionales
y algoritmos recursivos

UNELTCA 2010 Prog II

*/

#include  <stdio.h>
#include  <stdlib.h>

typedef struct lista_simple {
      int info;    
      struct lista_simple *sig;
} lista;

lista *inicializar_lista(){
  return NULL;
}

lista *solicitar_nodo (){
  return ((lista *)malloc(sizeof(lista)));
}

lista *insertar_inicio (lista *inicio, int valor){
    lista *q;
    if((q = solicitar_nodo())!=NULL){
      q -> info = valor;
      q -> sig = inicio;
      inicio = q;
    } else printf("Memoria no Disponible \n");
    return inicio;
}

lista *eliminar_inicio (lista *inicio){
    if (inicio != NULL){
      lista *q;
      q = inicio;
      inicio = inicio->sig;
      free(q);
      return inicio;
    } else return NULL;
}

lista *insertar_final (lista *inicio, int valor){
   if (inicio != NULL){
     lista *q,*w; w = inicio;
     while ( w->sig != NULL)
       w = w->sig;
     if((q = solicitar_nodo())!=NULL){
      q -> info = valor;
      q -> sig = NULL;
      w -> sig = q;
     } else printf("Memoria no Disponible \n");
     return inicio;
   } else {
    inicio = insertar_inicio(inicio,valor);
    return inicio;
   }
}

lista *eliminar_final (lista *inicio){
  if (inicio != NULL){
    lista *q, *w; q = inicio, w = inicio;
    while (w->sig != NULL){
      q = w;
      w = w -> sig;
    }
    q -> sig = NULL;
    free(w);
    return inicio;
  } else return NULL;
}

void imprimir_lista (lista *inicio){
  if (inicio != NULL){
    int n=1;
    printf("Nodo[%d] - Valor: %d\n",n,inicio->info);
    while (inicio->sig != NULL){
      n++;
      inicio = inicio -> sig;
      printf("Nodo[%d] - Valor: %d\n",n,inicio->info);
    }
  } else {
    printf("Lista Vacia \n");
  }
}

lista *eliminar_final_r (lista *inicio){ 
  if(inicio != NULL){
    if  (inicio->sig != NULL) {
    lista *q;
    q = eliminar_final_r(inicio->sig);
    inicio->sig = q;
    } else {
      free(inicio);
      return NULL;
    }
  } else return NULL;
}

lista *insertar_final_r(lista *inicio, int valor){ 
  if(inicio != NULL){
    lista *q;
     if(inicio -> sig == NULL){
       if((q = solicitar_nodo())!=NULL){
  q -> info = valor;
  q -> sig = NULL;
  inicio->sig = q;
       } else {
  printf("Memoria no Disponible \n");
  return NULL;
       }
     } else {
       q = insertar_final_r(inicio->sig,valor);
       inicio->sig = q;
     }
  } else {
     return insertar_inicio(inicio,valor);
  }
}

main.c:

/* Programa para el manejo de listas....
desarrollado por kellerman rivero krsloco@gmail.com
bajo licencia creative commons, 

el manejo de listas, realizando algoritmos convencionales
y algoritmos recursivos

UNELTCA 2010 Prog II

*/

#include  <stdio.h>
#include  <stdlib.h>
#include  "listas.h"
#define for_x for(x=0; x<N; x++)

int main(){
  lista *P;
  int N,valor,x;
  P = inicializar_lista();
  printf("Introduzca la cantidad de nodos: ");
  scanf("%d",&N);
  for_x{
   system("cls");
   printf("Introduzca el valor para el nodo[%d]: ",x+1);
   scanf("%d",&valor);
   P = insertar_inicio(P,valor);
  }
  imprimir_lista(P);
  P = eliminar_inicio(P);
  P = eliminar_final_r(P);
  getch();
  system("cls");
  imprimir_lista(P);
  
  return 0;
}

Recursividad en C... [Desglose de timbres fiscales]

/* Demuestre que, con sellos de 4 y 5 céntimos, se puede franquear cualquier carta
que requiera sellos por valor de 12 o más céntimos.

Usando recursividad, realizado por Kellerman Rivero krsloco@gmail.com
bajo licencia creative commons, UNELTCA Catedra: Prog II

*/


#include <stdlib.h>
#include <stdio.h>

#define FACTORI 5
#define FACTORP 4
#define desc_num_impar(x) x-= FACTORI
#define desc_num_par(x) x-= FACTORP

void descomponer (int num, int *c_par, int *c_impar);

int main() {
	int c_par = 0, c_impar = 0;
	int n;

	do {
		system("cls");
		printf("Valor de los Timbres Fiscales? ");
		scanf("%d",&n);
	} while (n < 12);
	printf("Sellos Equivalentes: \n");
	descomponer(n,&c_par,&c_impar);
	(c_par > 0) ? printf("%d timbres de %d centimos\n",c_par,FACTORP): 1;
	(c_impar > 0) ? printf("%d timbres de %d centimos\n",c_impar,FACTORI):1 ;	
}

void descomponer (int num, int *c_par, int *c_impar){
	if (num > 0) {
		if(num%FACTORI==0) {
			desc_num_impar(num);
			*c_impar = *c_impar+1;
		} else {
		        desc_num_par(num);
			*c_par= *c_par+1;
		}
		descomponer(num,c_par,c_impar);
	}
}