Zajęcia P1. Analizator leksykalny (Flex + Bison, Linux)

1. Cel ćwiczeń

Celem ćwiczenia jest stworzenie prostego analizatora leksykalnego dla wybranego języka

programowania (C, Turbo Pascal, Modula, Ada). Zadaniem tworzonego analizatora
leksykalnego jest:

- rozpoznawania tokenów i określanie ich właściwej wartości
- eliminacja komentarzy i białych znaków
- wykrywanie wskazanych dyrektyw
- wykrywanie błędów analizy leksykalnej

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

4. Zadania do wykonania (analizator leksykalny)

A) Czynności wstępne

a) Ściągnięcie ze strony przedmiotu i przejrzenie wskazanych plików
b) Zapisanie informacji o autorze w plikach lexer.l i parser.y.
c) Wypisywanie własnego imienia i nazwiska na początku programu (funkcja main() w

parser.y).

d) Kompilacja programu z wykorzystaniem pliku Makefile lub za pomocą poleceń (pkt 3).
e) Uruchomienie programu

B) Wykrywanie tokenów

f) Wykrywanie słów kluczowych występujących w programie testowym.
g) Wykrywanie tokenów wieloznakowych występujących w pliku testowym (‘<=’, ‘++’ ‘:=’ -

zależne od użytego języka)

h) Wykrywanie identyfikatorów, liczb całkowitych i zmiennoprzecinkowych.
i) Wykrywanie literałów tekstowych (napisów) bez użycia mechanizmu stanów.
j) Wykrywanie stałych znakowych (liter i symboli) bez użycia mechanizmu stanów.
k) Wykrywanie tokenów jednoznakowych w tym znaku nowego wiersza (operatory,

interpunkcja).

UWAGI do podpunktu B!
- Dla KAŻDEGO wykrytego tokena należy za pomocą gotowej funkcji process_token()
wyświetlić w oddzielnym wierszu w 3 kolumnach: wykryty tekst, typ tokena oraz jego wartość

znakową (yytext). Wartość tokena (3 kolumna) powinna być wyświetlana wyłącznie dla
identyfikatorów, stałych liczbowych, znakowych oraz łańcuchowych (por. tab.P1_1).
- Ewentualną wartość tokena należy podstawić do odpowiedniego pola zmiennej yylval.
- Akcję należy zakończyć zwróceniem typu tokena: return( process_token( .. ) );
- Typy tokenów są zdefiniowana w pliku parser.y. Tokenów jednoznakowych nie trzeba
definiować, gdyż są one jednoznacznie identyfikowane przez swój kod ASCII.
C) Usuwanie (ignorowanie) komentarzy i białych znaków

l) Usuwanie białych znaków (spacja, tabulacja). UWAGA! musi się znaleźć w kodzie przed j)!!!
m) Usuwanie komentarzy jednowierszowych // bez użycia mechanizmu stanów (zależne od

języka).

n) Usuwanie komentarzy wielowierszowych (/* .. */, (*..*), {..}- zależne od języka)

bez użycia mechanizmu stanów.

D) Wykrywanie dyrektyw

o) Wykrywanie dyrektywy włączania plików (#include, $I – zależne od języka) bez użycia

mechanizmu stanów. Po wykryciu dyrektywy należy jedynie wyświetlić komunikat
„Przetwarzanie dyrektywy INCLUDE”.

E) Zaawansowane przetwarzanie z użyciem mechanizmu stanów (warunków
początkowych)

p) Wykrywanie łańcuchów znaków oraz usuwanie komentarzy wielowierszowych
q) Wykrywanie błędu nierozpoczęty komentarz
r) Wykrywanie błędów: niezamkniętego komentarza wielowierszowego oraz ciągów znaków

wraz ze wskazaniem wiersza, w którym zostały otwarte

INFORMACJE do podpunktu E)

• Przykładowa deklaracja stanów (ang. start conditions) w sekcji 1
%x stan1

stan2

• Dopasowanie do wyrażenia regularnego dla automatu znajdującego się w pewnym stanie
(sekcja 2):

<stan1>wyr_reg1 akcja1;

<stan1,stan2,INITIAL>wyr_reg2

akcja2;

lub

<*>wyr_reg2

akcja2;

• Zmiana stanu następuje po wykonaniu akcji:

<stan1>wyr_reg { .. BEGIN stan2; }

• Stan początkowy – INITIAL
• Stan bieżący - YYSTATE (dostępny jest również w 3 sekcji):

int yywrap() {

if ( YYSTATE == COMMENT )

printf( "Niezamknięty komentarz" );

...
}

Tabela P1_1. Pliki testowe i przykłady działania analizatora leksykalnego

Plik testowy TEST.C: Plik

testowy

TEST.PAS

:

/****************************************************/
/* Program ASCII - wyświetla znaki ASCII */
/****************************************************/
#include

<stdio.h>

#include

"test.h"

Program

ASCII; (* Wyświetla kody ASCII *)

Uses

crt, dos;

{$I MyFile.inc}
Var

i : Integer;

c : Char;

unsigned char

uc; // zmienna sterująca pętli

int

fromASCII = 128, toASCII = 255;

void

main( void )

{

printf("\n\n\nRozszerzone kody ASCII\n\n", uc, uc);

for

( uc = fromASCII; uc <= toASCII; uc++ )

{

printf( "%3d:%2c", uc, uc );

}
}
double

realTest = 12.34 + .56 + 78.; // test l.rzecz.

int

x1 = fromASCII + 2 * ( 20 + toASCII ); /* te

wiersze /* służą
* / wyłącznie celom testowym ;-) */
*/ // nieotwarty komentarz
"Niezamknięta stała tekstowa
/* niezamknięty komentarz

r : real;

Const

(* zakres wyświetlanych znaków *)

minASCII = 30;

maxASCII = 255;

Begin
ClrScr();

(*intro na czystym ekranie*)

Writeln( 'Kody ASCII od 30 do 255: (po 20
w wierszu):' );

For i := minASCII To maxASCII Do (*
wyświetlenie zadanych kodów ASCII *)

Write( Chr( i ) : 4 );

ReadKey; (* czekaj na naciśnięcie
klawisza *)
r := 12.34 * ( 56. + .67 ); { test liczb
rzeczywistych }
'Niezamknięta stała tekstowa
*) } { nieotwarte komentarze }
{

komentarz

wielowierszowy 1 }
(*

komentarz

wielowierszowy 2 *)
{

niezamknięty komentarz ...

End.

Początek przykładowego wyjścia analizatora leksykalnego (konkretne wartości typów
tokenów zależą od kolejności ich deklaracji w pliku parser.y)

Język C

Turbo Pascal

yytext Typ tokena Wartosc tokena zn.

Przetwarzanie dyrektywy: #include <stdio.h>
Przetwarzanie dyrektywy: #include "test.h"
unsigned KW_UNSIGNED
char KW_CHAR
uc IDENT uc
; 59
int KW_INT
fromASCII IDENT fromASCII
= 61
128 INT_NUMBER 128
, 44
toASCII IDENT toASCII
= 61
255 INT_NUMBER 255
; 59
void KW_VOID
main IDENT main
( 40
void KW_VOID
) 41
{ 123
printf IDENT printf
( 40
\n\n\nRozszerzone TEXT_CONST \n\n\nRozszerzone
, 44
uc IDENT uc
, 44
uc IDENT uc
) 41
; 59
for KW_FOR
( 40
uc IDENT uc
= 61
fromASCII IDENT fromASCII
; 59
uc IDENT uc
<= LE
toASCII IDENT toASCII
; 59
uc1 IDENT uc1
++ INC
) 41
{ 123
printf IDENT printf
( 40
%3d:%2c TEXT_CONST %3d:%2c
, 44
uc IDENT uc
, 44

yytext Typ tokena
Wart.tok.zn.

Program KW_PROGRAM
ASCII IDENT ASCII
; 59
Uses KW_USES
crt IDENT crt
, 44
dos IDENT dos
; 59
Var KW_VAR
i IDENT i
: 58
Integer KW_INTEGER
; 59
c IDENT c
: 58
Char KW_CHAR
; 59
r IDENT r
: 58
real IDENT real
; 59
Const KW_CONST
minASCII IDENT minASCII
= 61
30 INT_NUMBER 30
; 59
maxASCII IDENT maxASCII
= 61
255 INT_NUMBER 255
; 59
Begin KW_BEGIN
ClrScr IDENT ClrScr
( 40
) 41
; 59
Writeln IDENT Writeln
( 40
Kody ASCII od 30 TEXT_CONST Kody ASCII
) 41
; 59
For KW_FOR
i IDENT i
:= ASSIGN
minASCII IDENT minASCII
To KW_TO
maxASCII IDENT maxASCII
Do KW_DO
Write IDENT Write
( 40

uc IDENT uc
) 41
; 59
} 125
} 125
double KW_DOUBLE
realTest IDENT realTest
= 61
12.34 FLOAT_NUMBER 12.34
+ 43
.56 FLOAT_NUMBER .56
+ 43
78. FLOAT_NUMBER 78.
; 59
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
ERROR: unexpected end of comment in line 21

ERROR: text const not closed in line 20
Comment /* ..*/ not closed!

Chr IDENT Chr
( 40
i IDENT i
) 41
: 58
4 INT_NUMBER 4
) 41
; 59
ReadKey IDENT ReadKey
; 59
r IDENT r
:= ASSIGN
12.34 REAL_NUMBER 12.34
* 42
( 40
56. REAL_NUMBER 56.
+ 43
.67 REAL_NUMBER .67
) 41
; 59
ERROR: text const not closed in line 16
ERROR: unexpected end of comment in line 18
ERROR: unexpected end of comment in line 19
ERROR: comment { .. } not closed!

Tabela P1_2. Wybrane różnice pomiędzy językami C i Turbo Pascal

Token ID

tokena

C Turbo

Pascal

Uwagi

Komentarze

// komentarz \n
/* komentarz */

{ komentarz }
(*komentarz *)

Usuwane

Słowa kluczowe

KW_FOR,

KW_..

for, unsigned,
char

,

int

,

void

,

for,

program

,

uses

,

const

,

var

,

integer

,

char

,

to

,

do

,

begin

,

real

,

end

ID tokena zawiera
przedrostek KW_
oraz nazwę słowa
kluczowego

Włączanie plików
lub bibliotek

INCLUDE

#include
<name.ext>
#include "name.ext"

{$I 'name.ext'}

Wyłącznie
komunikat -
dyrektywy nie są
zwracane jako
tokeny

Białe znaki

spacja, tabulacja, \r

Usuwane

Literały tekstowe

TEXT_CONST

"Napis" 'Napis'

Stałe znakowe

CHAR

'a' 'a'

Identyfikator

IDENT

pierwsza litera, potem litera lub cyfra

Podkreślenie jest
traktowane jak
litera

Tokeny
wieloznakowe

LE

INC

ASSIGN

<=

++

<=

:=

Liczby całkowite
nieujemne

INT_NUMBER

zero lub sekwencja cyfr nie rozpoczynająca

się zerem

Liczby
zmiennoprzecinkowe

REAL_NUMBER

liczby bez wykładnika, cześć całkowito-

liczbowa albo ułamkowa jest opcjonalna

Rozróżnianie
wielkości liter

TAK

NIE