[WikiDyd] [TitleIndex] [WordIndex

Materiały zostały opracowane w ramach realizacji Programu Rozwojowego Politechniki Warszawskiej.

http://prpw.iem.pw.edu.pl/images/KAPITAL_LUDZKI.gif http://prpw.iem.pw.edu.pl/images/EU+EFS_P-kolor.gif

http://www.pr.pw.edu.pl/ jest projektem współfinansowanym przez Unię Europejską w ramach Europejskiego Funduszu społecznego (działanie 4.1.1 Programu Operacyjnego Kapitał Ludzki) i ma na celu poprawę jakości kształcenia oraz dostosowanie oferty dydaktycznej Politechniki Warszawskiej do potrzeb rynku pracy. Będzie on realizowany przez Uczelnię w latach 2008-2015.


Laboratorium metodyki programowania

Ćwiczenie 8: Modularna budowa programu

Scenariusz

Ćwiczenie wykonywane w parach.

  1. Studenci logują się do systemu LOP (Laboratorium Otwartego Programowania).
  2. Studenci przechodzą do katalogu roboczego dla zajęć LMP.
  3. Studenci pobierają z repozytorium kod programów.
  4. Po wyjaśnieniach prowadzącego przystępują do analizy problemu i podziału zadań.
  5. Studenci programują według wskazówek prowadzącego (patrz opis szczegółowy).

Opis szczegółowy

W trakcie zajęć nauczymy się metod radzenia sobie ze złożonością większych programów oraz zapoznamy się z problemami występującymi przy współpracy nad tworzeniem programu.

Rozpoczęcie pracy

Zajęcia będą prowadzone na komputerze stud.iem.pw.edu.pl. W celu rozpoczęcia pracy należy zalogować się na tym komputerze za pomocą usługi ssh. Można w tym celu wykorzystać albo dostępny w każdym praktycznie systemie Unix/Linux program ssh albo klienta SSH dla systemu Windows - PuTTY. Na maszynach studenckich w IETiSIP PW można podnieść różne dystrybucje Uniksa/Linuksa lub system Windows, ale w każdej z nich jest zainstalowane oprogramowanie ssh.

Do logowania na maszynie stud.iem.pw.edu.pl należy użyć takiego samego loginu i hasła jakie wykorzystywane sa do dostępu do usług wydziałowych (poczta, e-dziekanat, itd.).

Po zalogowaniu się należy przejść do utworzonego na pierwszych zajęciach katalogu lmp:

 cd lmp

Kod so zajęć

lmp8.tgz

Zadanie

Proszę zaprojektować i wykonać program wypisujący drzewo wywołań funkcji na podstawie analizy programu w języku C.

Program ma być wywoływany z listą argumentów - nazw plików zawierających kod w jęz. C. Program ma czytać te pliki i na ich podstawie budować strukturę danych określającą z jakich funkcji składa się analizowany kod i jak te funkcje są powiązane wywołaniami. Na zakończenie program powinien wypisywać drzewo wywołań funkcji.

Na przykład wyobraźmy sobie kod zawarty w dwóch plikach o postaci:

Plik fa.c

   1 int fa( int x ) {
   2   return 2*x;
   3 }

Plik p.c

   1 int fa( int );
   2 int fb( int );
   3 
   4 int main( ) {
   5   int i= 5;
   6   printf( "funkcjaa(%i)=%i", i, fa(i) );
   7   printf( "funkcjab(%i)=%i", i, fb(i) );
   8   printf( "funkcjac(%i)=%i", i, fc(i) );
   9   printf( "jeszcze raz funkcjab(%i)=%i", i, fb(i) );
  10   return 0;
  11 }
  12 
  13 int fb( int x ) {
  14   x= fc(x);
  15   return 2*fa(x);
  16 }

Po przeczytaniu tych plików "nasz" program powinien wypisywać coś w rodzaju:

   Funkcja fa: 
      Prototyp:
        plik p.c od linia 1 do linia 1
      Definicja:
        plik fa.c od linia 1 do linia 3
      Użycie:
        plik p.c od linia 6 do linia 6
      Wywołuje:
        brak


   Funkcja fb:
      Prototyp:
        plik p.c od linia 2 do linia 2
      Definicja:
        plik p.c od linia 13 do linia 16
      Użycie:
        plik p.c od linia 7 do linia 7
        plik p.c od linia 9 do linia 9
      Wywołuje:
        fc
        fa

   Funkcja main:
      Prototyp:
        brak
      Definicja:
        plik p.c od linia 4 do linia 11
      Użycie:
        brak
      Wywołuje:
        printf (4 razy)
        fa
        fb (2 razy)
        fc 
  1. Program powinien umożliwiać:
    • przetwarzanie dowolnie wielu plików w jednym przebiegu
    • ignorowanie pewnych funkcji (zgodnie z lista domyślną, lub listą dostarczoną przez użytkownika)
    • wypisywanie numerów linii, gdzie rozpoczyna i kończy się funkcja oraz gdzie są wywoływane poszczególne funkcje
  2. Program powinien poprawnie reagować na niezbilansowanie nawiasów klamrowych w plikach źródłowych.
  3. Program powinien poprawnie obsługiwać komentarze

  4. Program ma być zbudowany modularnie. Podział na pliki źródłowe ma być odzwierciedleniem funkcjonalnej struktury programu. Przykładowa lista modułów:
    • analizator leksykalny - zamiana ciągu znaków, jakim jest plik, na ciąg symboli leksykalnych; pomija symbole nieistotne z p. widzenia zadania
    • analizator składni - wykrywanie prototypów, definicji, wywołań funkcji
    • kontener danych - przechowywania w pamięci drzewa wywołań
    • lista funkcji pomijanych - wykorzystywana przez analizator składni do określenia, czy zapisywać dane o funkcji, czy nie
    • formater wydruku - wypisuje zawartość kontenera w odpowiedniej formie
    • sterowanie - funkcja main: analizuje argv, inicjuje kontener, wywołuje analizator składni
  5. Opcje:
    • obsługiwanie zagnieżdżonych plików włączanych przez include
    • ignorowania makrodefinicji: Jeżeli w pliku źródłowym występuje np. makrodefinicja

   #define max(A,B) ((A)>(B)?(A):(B))

   int fx( double a ) {
      ....
      cos_tam= max( cos, cos_innego );
      ...
   }

Wskazówki

Najtrudniejszym i jednocześnie najciekawszym zadaniem jest stworzenie analizatora składni. Można zaproponować następującą jego postać:

   1 #include <stdio.h>              
   2 #include <stdlib.h> // exit - ale exit trzeba kiedyś usunąć i nie będzie to potrzebne
   3 #include "alex.h"       // analizator leksykalny                                     
   4 #include "fun_stack.h"  // stos funkcji                                              
   5 
   6 #define MAXINDENTLENGHT 256     // maks długość identyfikatora
   7 
   8 void
   9 analizatorSkladni (char *inpname)
  10 {                               // przetwarza plik inpname
  11 
  12   FILE *in = fopen (inpname, "r");
  13 
  14   int nbra = 0;   // bilans nawiasów klamrowych {}
  15   int npar = 0;   // bilans nawiasów zwykłych ()
  16 
  17   alex_init4file (in);          // ustaw analizator leksykalny, aby czytał in
  18 
  19   lexem_t lex;
  20 
  21   lex = alex_nextLexem ();      // pobierz następny leksem
  22   while (lex != EOFILE) {
  23     switch (lex) {
  24     case IDENT:{
  25         char *iname = alex_ident ();   // zapamiętaj identyfikator i patrz co dalej
  26         lexem_t nlex = alex_nextLexem ();
  27         if (nlex == OPEPAR) {   // nawias otwierający - to zapewne funkcja
  28           npar++;
  29           put_on_fun_stack (npar, iname);       // odłóż na stos funkcji
  30                                                 // stos f. jest niezbędny, aby poprawnie obsłużyć sytuacje typu
  31                                                 // f1( 5, f2( a ), f3( b ) )
  32         }
  33         else {                  // nie nawias, czyli nie funkcja
  34           lex = nlex;
  35           continue;
  36         }
  37       }
  38       break;
  39     case OPEPAR:
  40       npar++;
  41       break;
  42     case CLOPAR:{              // zamykający nawias - to może być koniec prototypu, nagłówka albo wywołania
  43         if (top_of_funstack () == npar) {       // sprawdzamy, czy liczba nawiasów bilansuje się z wierzchołkiem stosu funkcji
  44                                                 // jeśli tak, to właśnie wczytany nawias jest domknięciem nawiasu otwartego
  45                                                 // za identyfikatorem znajdującym się na wierzchołku stosu
  46           lexem_t nlex = alex_nextLexem ();     // bierzemy nast leksem
  47           if (nlex == OPEBRA)   // nast. leksem to klamra a więc mamy do czynienia z def. funkcji
  48             store_add_def (get_from_fun_stack (), alex_getLN (), inpname);
  49           else if (nbra == 0)   // nast. leksem to nie { i jesteśmy poza blokami - to musi być prototyp
  50             store_add_proto (get_from_fun_stack (), alex_getLN (), inpname);
  51           else                  // nast. leksem to nie { i jesteśmy wewnątrz bloku - to zapewne wywołanie
  52             store_add_call (get_from_fun_stack (), alex_getLN (), inpname);
  53         }
  54         npar--;
  55       }
  56       break;
  57     case OPEBRA:
  58       nbra++;
  59       break;
  60     case CLOBRA:
  61       nbra--;
  62       break;
  63     case ERROR:{
  64         fprintf (stderr, "\nBUUUUUUUUUUUUUUUUUUUUUU!\n"
  65                  "W pliku %s (linia %d) są błędy składni.\n"
  66                  "Kończę!\n\n", inpname, alex_getNL ());
  67         exit (1);               // to nie jest najlepsze, ale jest proste ;-)
  68       }
  69       break;
  70     default:
  71       break;
  72     }
  73     lex = alex_nextLexem ();
  74   }
  75 }

Popatrzmy jeszcze na szkic analizatora leksykalnego:

   1 #ifndef _ALEX_H_IS_INCLUDED_
   2 #define _ALEX_H_IS_INCLUDED_
   3 
   4 #include <stdio.h>
   5 
   6 // interesujące leksemy: błąd, inny symbol, koniec pliku, otwierająca klamra {,
   7 //                       zamykająca klamra }, identyfikator, otwierający nawias,
   8 //                       zamykający nawias
   9 typedef enum { ERROR, OTHER, EOFILE, OPEBRA, CLOBRA, IDENT, OPEPAR, CLOPAR } lexem_t;
  10 
  11 void    alex_init4file( FILE * );  // zacznij czytać nowy plik
  12 lexem_t alex_nextLexem( void );    // daj kolejny leksem w czytanym pliku
  13 char *  alex_ident( void );        // daj ostatni identyfikator
  14 int     alex_getLN();              // daj aktualny nr linii
  15 
  16 #endif
  17 

   1 #include "alex.h"
   2 
   3 #include <ctype.h>
   4 
   5 static int  ln= 0;
   6 static char ident[256];
   7 static FILE *ci= NULL;
   8 
   9 void    alex_init4file( FILE *in ) {
  10    ln= 0;
  11    ci= in;
  12 }
  13 
  14 lexem_t alex_nextLexem( void ) {
  15   int c;
  16   while( (c= fgetc(ci)) != EOF ) {
  17     if( isspace( c ) )
  18                         continue;
  19                 else if( c == '\n' )
  20                         ln++;
  21     else if( c == '(' )
  22                         return OPEPAR;
  23     else if( c == ')' )
  24       return CLOPAR;
  25     else if( c == '{' )
  26                         return OPEBRA;
  27     else if( c == '}' )
  28                         return CLOBRA;
  29     else if( isalpha( c ) ) {
  30       int i= 1;
  31       ident[0] = c;
  32       while( isalnum( c= fgetc(ci) ) )
  33                                 ident[i++] = c;
  34                         ident[i] = '\0';
  35       return isKeyword(ident) ? OTHER : IDENT;
  36                 } else if( c == '"' ) {
  37       /* Uwaga: tu trzeba jeszcze poprawic obsluge nowej linii w trakcie napisu
  38          i \\ w napisie
  39       */
  40       int cp = c;
  41                         while( (c= fgetc(ci)) != EOF && c != '"' && cp == '\\' ) {
  42                                 cp = c;
  43       }
  44       return c==EOF ? EOFILE : OTHER;
  45     } else if( c == '/' ) {
  46       /* moze byc komentarz */
  47                 } if( isdigit( c ) || c == '.' ) {
  48       /* liczba */
  49                 } else {
  50       return OTHER;
  51                 }
  52         }
  53   return EOFILE;
  54 }
  55 
  56 char *  alex_ident( void ) {
  57    return ident;
  58 }
  59 
  60 int     alex_getLN() {
  61         return ln;
  62 }

Stos funkcji (który może być częścią analizatora leksykalnego) powinien posiadać następujący interfejs (który nie musi być osobnym plikiem, gdyż będzie wykorzystywany tylko wewnątrz parsera):

   1 #ifndef _FUN_STACK_H_IS_INCLUDED_
   2 #define _FUN_STACK_H_IS_INCLUDED_
   3 
   4 int top_of_funstack( void );  // zwraca par_level - "zagłębienie nawiasowe" przechowywane na szczycie
   5 void put_on_fun_stack( int par_level, char *funame ); // odkłada na stos parę (funame,par_level)
   6 char *get_from_fun_stack( void ); // usuwa z wierzchołka parę (funame,par_level), zwraca zdjętą funame
   7 
   8 #endif
   9 

Program na zaliczenie

Do wyboru przez prowadzącego: wykonanie działających wybranych modułów i programów testujących te moduły. Każdy student wykonuje inny moduł.


To już prawie wszystko, ale nie wolno nam zapomnieć, że

materiały zostały opracowane w ramach realizacji Programu Rozwojowego Politechniki Warszawskiej.

http://prpw.iem.pw.edu.pl/images/KAPITAL_LUDZKI.gif http://prpw.iem.pw.edu.pl/images/EU+EFS_P-kolor.gif

http://www.pr.pw.edu.pl/ jest projektem współfinansowanym przez Unię Europejską w ramach Europejskiego Funduszu społecznego (działanie 4.1.1 Programu Operacyjnego Kapitał Ludzki) i ma na celu poprawę jakości kształcenia oraz dostosowanie oferty dydaktycznej Politechniki Warszawskiej do potrzeb rynku pracy. Będzie on realizowany przez Uczelnię w latach 2008-2015.


2015-09-23 06:44