Zajęcia P2. Analizator składniowy (Flex + Bison, Linux)
1. Cel ćwiczeń
Celem ćwiczeń jest stworzenie analizatora składniowego dla języka będącego podzbiorem języka
wysokiego poziomu (C lub Turbo Pascal). Przy tworzeniu analizatora należy skorzystać ze
stworzonego analizatora leksykalnego. Sprawdzenie działania analizatora należy przeprowadzić dla
zadanego programu testowego (Test.c lub Test.pas).
2. Środowisko Linux, Flex + Bison
A) po włączeniu komputera wybieramy system operacyjny Linux (użytkownik student)
B) uruchomienie edytora tekstu i konsoli roboczej
C) utworzenie w oknie konsoli własnego katalogu (mkdir nazwisko)
D) przejście do własnego katalogu (cd nazwisko)
E) UWAGA! Po zakończeniu zajęć należy skopiować własne projekty, a następnie skasować je
z twardego dysku.
3. Informacja o programach Lex/Flex oraz Yacc/Bison
A) Do utworzenia programu zaleca się skorzystać z pliku Makefile, który można ściągnąć (nie
kopiować z edytora) ze strony przedmiotu! Kompilacji i łączenia dokonuje się za pomocą
polecenia make. Wykonywalny plik programu nosi nazwę parser.tab. Alternatywnie można
wykonać poniższe polecenia:
B) Generacja kodu parsera (pliki y.tab.c oraz y.tab.h): bison –d parser.y
C) Generacja kodu skanera (plik lex.yy.c): flex lexer.l
D) Kompilacja kodu parsera (plik zad): gcc parser.tab.c lexer.c –o parser.tab
E) Przekierowanie standardowych strumieni: ./Scaner <plik_we >plik_wy
F) wartość wykrytego tokena należy ustawić w zmiennej yylval (w kodzie dla Flex’a)
G) postać reguł składniowych: A: B C D {akcja semantyczna} ;
H) wartość zmiennej po lewej stronie reguły składniowej: $$ (left value)
I) wartość tokenów i zmiennych po prawej stronie reguły składniowej: $1, $2, $3
J) predefiniowany token błędu: yyerror
K) predefiniowane makra dla akcji semantycznych w Yacc’u:
YYABORT – zakończenie działania parsera z sygnalizacją błędu
YYACCEPT – zakończenie działania parsera z sygnalizacją akceptacji
YYERROR – generuje błąd składniowy jednak bez wywoływania procedury yyerror
4. Analizator składniowy (realizowany stopniowo zgodnie z instrukcjami zapisanymi w pliku *.y).
UWAGA 1! Zadanie należy realizować krok po kroku sprawdzając efekty działania kolejnych
implementowanych reguł składniowych. Po rozpoznaniu konstrukcji składniowej należy wypisać
stosowny komunikat.
UWAGA 2! Do wypisywania informacji o znalezionych strukturach składniowych należy używać
funkcji found() z pliku parser.y.
A) Czynności wstępne
a) Wgranie własnego pliku lexer.l
b) Ściągnięcie ze strony przedmiotu pliku parser.y i test.c
c) Zapisanie informacji o autorze w pliku parser.y.
d) Wypisywanie własnego imienia i nazwiska na początku programu (funkcja main() w
parser.y).
e) Kompilacja programu z wykorzystaniem pliku Makefile lub za pomocą poleceń (pkt 3).
f) Uruchomienie programu
B) Rozpoznawane konstrukcje języka
a) ogólna struktura programu
b) deklaracje danych
c) definicja pustej funkcji bez parametrów
d) definicja pustej funkcji z parametrami
e) wywołania funkcji bez parametrów
f) wywołania funkcji z parametrami
g) instrukcje podstawienia
h) wyrażenia arytmetyczne
i) pętla for
j) instrukcja warunkowa if
k) pętle while .. do i do .. while
UWAGA 3! Składnia języka C (Pascal) jest o wiele bardziej skomplikowana niż może to wynikać
z realizowanego projektu. Na laboratorium upraszczamy tę składnię tak, by można było
przeanalizować program testowy.
Pliki testowe:
Przykładowy plik testowy dla języka C
Przykładowy plik testowy dla Turbo Pascala
//
int
a;
Program testowy C
float
a1, _b, _00;
double
I
.1415926;
P = 3
unsigned
char c;
int
fromASCII = 128
ASCII = 255;
, to
void
FunkcjaPusta( void )
{
}
int
FunkcjaPustaZParametrami( int a, double d )
{
}
float
FunkcjaZDeklaracjamiZmiennych( double d )
{
int a;
double
half = .5;
}
int
x1 = fromASCII + 2 * ( 20 + toASCII );
double
realTest = 12.34 + .56 + 78.;
void
main( void )
{
int a = 1, b, c, m;
FunkcjaPusta();
safsafd();
FunkcjaPustaZParametrami( "x", 123, 12.34 );
printf( "\n\n\nRozszerzone kody ASCII\n\n" );
for ( uc = fromASCII; uc <= toASCII; uc1++ )
{
int a;
printf( "%3d:%2c", uc, uc );
}
if ( a > 10 )
b = a;
if ( a > 1 )
b = a;
else
b = 1;
if ( a > b )
if ( a > c )
m = a;
else
m = c;
else
if ( b > c )
m = b;
else
m = c;
}
Program
Testowy;
Const
minASCII = 30;
maxASCII = 255;
t
Var
ekst = 'napis testowy';
c : Char;
r : Real;
i, i1, _i, _00 : Integer;
Procedure
Pusta_Bez_Parametrow()
Begin
End
Function
Pusta_Z_Parametrami( a : Integer, c : Char, r
: Real ) : Integer
Begin
End
Procedure
Z_Deklaracjami()
Var
s
:
String
;
Const
r1 = 12.34;
r2 = .56;
Begin
r3 = 78.;
End
Begin
ClrScr;
Writeln( 'Kody ASCII (30-255):' );
For i := minASCII To maxASCII Do
Write( Chr( i ), ' ' );
ReadKey; (* czekaj na nacisnięcie klawisza *)
i := ( i1 + 3 ) * _00;
if ( a > 10 )
then b := a;
if ( a > 1 )
then b := a
else b := 1;
if
a > b )
(
then
if
a > c )
(
then m := a
else m := c
else
if ( b > c )
then m := b
else m := c;
End.
Przykładowy efekt działania analizatora składniowego
Język C
Turbo Pascal
Imie i Nazwisko
yytext Typ tokena Wartosc tokena zn.
int KW_INT
a IDENT a
Imie i Nazwisko
yytext Typ tokena Wartosc tokena zn.
Program KW_PROGRAM
Testowy IDENT Testowy
; 59
===== FOUND: deklaracja zmiennych =====
float KW_FLOAT
a1 IDENT a1
, 44
_b IDENT _b
, 44
_00 IDENT _00
; 59
===== FOUND: deklaracja zmiennych =====
double KW_DOUBLE
PI IDENT PI
= 61
3.1415926 FLOAT_NUMBER 3.1415926
; 59
===== FOUND: deklaracja zmiennych =====
unsigned KW_UNSIGNED
char KW_CHAR
c IDENT c
; 59
===== FOUND: deklaracja zmiennych =====
int KW_INT
fromASCII IDENT fromASCII
= 61
128 INT_NUMBER 128
, 44
toASCII IDENT toASCII
= 61
255 INT_NUMBER 255
; 59
===== FOUND: deklaracja zmiennych =====
void KW_VOID
FunkcjaPusta IDENT FunkcjaPusta
( 40
void KW_VOID
) 41
{ 123
} 125
===== FOUND: definicja funkcji =====
int KW_INT
FunkcjaPustaZParame IDENT FunkcjaPustaZPa
( 40
int KW_INT
a IDENT a
, 44
double KW_DOUBLE
d IDENT d
) 41
{ 123
} 125
===== FOUND: definicja funkcji =====
float KW_FLOAT
FunkcjaZDeklaracjam IDENT FunkcjaZDeklara
( 40
double KW_DOUBLE
d IDENT d
) 41
{ 123
int KW_INT
a IDENT a
; 59
double KW_DOUBLE
half IDENT half
= 61
.5 FLOAT_NUMBER .5
; 59
} 125
===== FOUND: definicja funkcji =====
int KW_INT
x1 IDENT x1
= 61
fromASCII IDENT fromASCII
+ 43
2 INT_NUMBER 2
* 42
( 40
20 INT_NUMBER 20
+ 43
toASCII IDENT toASCII
) 41
; 59
===== FOUND: deklaracja zmiennych =====
double KW_DOUBLE
; 59
===== FOUND: nazwa programu =====
Const KW_CONST
minASCII IDENT minASCII
= 61
30 INT_NUMBER 30
; 59
maxASCII IDENT maxASCII
= 61
255 INT_NUMBER 255
; 59
tekst IDENT tekst
= 61
'napis testowy TEXT_CONST napis testowy
; 59
Var KW_VAR
===== FOUND: deklaracja stałych =====
c IDENT c
: 58
Char KW_CHAR
; 59
r IDENT r
: 58
real KW_REAL
; 59
i IDENT i
, 44
i1 IDENT i1
, 44
_i IDENT _i
, 44
_00 IDENT _00
: 58
Integer KW_INTEGER
; 59
Procedure KW_PROCEDURE
===== FOUND: deklaracja zmiennych =====
Pusta_Bez_Parametro IDENT Pusta_Bez_Para
( 40
) 41
Begin KW_BEGIN
End KW_END
===== FOUND: blok =====
===== FOUND: definicja procedury
'Pusta_Bez_Parametrow'=====
===== FOUND: procedura =====
Function KW_FUNCTION
Pusta_Z_Parametrami IDENT Pusta_Z_Parametr
( 40
a IDENT a
: 58
Integer KW_INTEGER
, 44
c IDENT c
: 58
Char KW_CHAR
, 44
r IDENT r
: 58
Real KW_REAL
) 41
: 58
Integer KW_INTEGER
Begin KW_BEGIN
End KW_END
===== FOUND: blok =====
===== FOUND: definicja funkcji =====
===== FOUND: funkcja =====
Procedure KW_PROCEDURE
Z_Deklaracjami IDENT Z_Deklaracjami
( 40
) 41
Var KW_VAR
s IDENT s
: 58
String KW_STRING
; 59
Const KW_CONST
===== FOUND: deklaracja zmiennych =====
r1 IDENT r1
= 61
12.34 FLOAT_NUMBER 12.34
; 59
realTest IDENT realTest
= 61
12.34 FLOAT_NUMBER 12.34
+ 43
.56 FLOAT_NUMBER .56
+ 43
78. FLOAT_NUMBER 78.
; 59
===== FOUND: deklaracja zmiennych =====
void KW_VOID
main IDENT main
( 40
void KW_VOID
) 41
{ 123
int KW_INT
a IDENT a
= 61
1 INT_NUMBER 1
, 44
b IDENT b
, 44
c IDENT c
, 44
m IDENT m
; 59
FunkcjaPusta IDENT FunkcjaPusta
( 40
) 41
; 59
===== FOUND: wywołanie funkcji FunkcjaPusta=====
safsafd IDENT safsafd
( 40
) 41
; 59
===== FOUND: wywołanie funkcji safsafd=====
FunkcjaPustaZParame IDENT FunkcjaPustaZPa
( 40
"x TEXT_CONST x
, 44
123 INT_NUMBER 123
, 44
12.34 FLOAT_NUMBER 12.34
) 41
; 59
===== FOUND: wywołanie funkcji
FunkcjaPustaZParametrami=====
printf IDENT printf
( 40
"\n\n\nRozszerzone TEXT_CONST \n\n\nRozszerzone
, 44
uc IDENT uc
, 44
uc IDENT uc
) 41
; 59
===== FOUND: wywołanie funkcji printf=====
for KW_FOR
( 40
uc IDENT uc
= 61
fromASCII IDENT fromASCII
; 59
uc IDENT uc
<= 273
toASCII IDENT toASCII
; 59
uc1 IDENT uc1
++ 272
) 41
{ 123
int KW_INT
a IDENT a
; 59
printf IDENT printf
( 40
"%3d:%2c" TEXT_CONST %3d:%2c
, 44
uc IDENT uc
, 44
uc IDENT uc
) 41
; 59
r2 IDENT r2
= 61
.56 FLOAT_NUMBER .56
; 59
r3 IDENT r3
= 61
78. FLOAT_NUMBER 78.
; 59
Begin KW_BEGIN
===== FOUND: deklaracja stałych =====
End KW_END
===== FOUND: blok =====
===== FOUND: definicja procedury ===
===== FOUND: procedura =====
Begin KW_BEGIN
Pusta_Bez_Parametro IDENT Pusta_Bez_Parame
; 59
===== FOUND: wywołanie funkcji =====
Pusta_Z_Parametrami IDENT Pusta_Z_Parametr
( 40
123 INT_NUMBER 123
, 44
'c' CHAR_CONST c
, 44
12.34 FLOAT_NUMBER 12.34
) 41
===== FOUND: wywołanie funkcji =====
; 59
ClrScr IDENT ClrScr
; 59
===== FOUND: wywołanie funkcji =====
Writeln IDENT Writeln
( 40
'Kody ASCII (30-255 TEXT_CONST Kody ASCII (30-255):
) 41
===== FOUND: wywołanie funkcji =====
; 59
For KW_FOR
i IDENT i
:= OP_ASSIGNMENT
minASCII IDENT minASCII
To KW_TO
maxASCII IDENT maxASCII
Do KW_DO
Write IDENT Write
( 40
Chr IDENT Chr
( 40
i IDENT i
) 41
, 44
' ' CHAR_CONST ' '
) 41
===== FOUND: wywołanie funkcji =====
===== FOUND: pętla for =====
; 59
ReadKey IDENT ReadKey
; 59
===== FOUND: wywołanie funkcji =====
i IDENT i
:= ASSIGN
( 40
i1 IDENT i1
+ 43
3 INT_NUMBER 3
) 41
* 42
_00 IDENT _00
; 59
===== FOUND: przypisanie =====
if KW_IF
( 40
a IDENT a
> 62
10 INT_NUMBER 10
) 41
then KW_THEN
b IDENT b
:= ASSIGN
a IDENT a
; 59
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
===== FOUND: wywołanie funkcji printf=====
} 125
===== FOUND: pętla for =====
if KW_IF
( 40
a IDENT a
> 62
10 INT_NUMBER 10
) 41
b IDENT b
= 61
a IDENT a
; 59
===== FOUND: przypisanie =====
if KW_IF
===== FOUND: instrukcja warunkowa if =====
( 40
a IDENT a
> 62
1 INT_NUMBER 1
) 41
b IDENT b
= 61
a IDENT a
; 59
===== FOUND: przypisanie =====
else KW_ELSE
b IDENT b
= 61
1 INT_NUMBER 1
; 59
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
if KW_IF
( 40
a IDENT a
> 62
b IDENT b
) 41
if KW_IF
( 40
a IDENT a
> 62
c IDENT c
) 41
m IDENT m
= 61
a IDENT a
; 59
===== FOUND: przypisanie =====
else KW_ELSE
m IDENT m
= 61
c IDENT c
; 59
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
else KW_ELSE
if KW_IF
( 40
b IDENT b
> 62
c IDENT c
) 41
m IDENT m
= 61
b IDENT b
; 59
===== FOUND: przypisanie =====
else KW_ELSE
m IDENT m
= 61
c IDENT c
; 59
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
===== FOUND: instrukcja warunkowa if =====
} 125
===== FOUND: definicja funkcji 'main'=====
if KW_IF
( 40
a IDENT a
> 62
1 INT_NUMBER 1
) 41
then KW_THEN
b IDENT b
:= ASSIGN
a IDENT a
else KW_ELSE
===== FOUND: przypisanie =====
b IDENT b
:= ASSIGN
1 INT_NUMBER 1
; 59
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
if KW_IF
( 40
a IDENT a
> 62
b IDENT b
) 41
then KW_THEN
if KW_IF
( 40
a IDENT a
> 62
c IDENT c
) 41
then KW_THEN
m IDENT m
:= ASSIGN
a IDENT a
else KW_ELSE
===== FOUND: przypisanie =====
m IDENT m
:= ASSIGN
c IDENT c
else KW_ELSE
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
if KW_IF
( 40
b IDENT b
> 62
c IDENT c
) 41
then KW_THEN
m IDENT m
:= ASSIGN
b IDENT b
else KW_ELSE
===== FOUND: przypisanie =====
m IDENT m
:= ASSIGN
c IDENT c
; 59
===== FOUND: przypisanie =====
===== FOUND: instrukcja warunkowa if =====
===== FOUND: instrukcja warunkowa if =====
End KW_END
===== FOUND: blok =====
. 46
===== FOUND: PROGRAM is OK =====