Tema 1 LFA 2014-2015

Limbaje regulate

George Daniel MITRA

11 ianuarie 2015

Rezumat

Tema consta n implementarea unui program care afis,eaza toate subs, iruriledintr-un text care apart, in unui limbaj dat.

1 Specificat, ii tema

1.1 Cerint, a

Sa se implementeze un program care, primind o reprezentare a unui automatfinit determinist s, i un text, sa afis,eze toate subs, irurile textului care apart, inlimbajului automatului.

Solut, iile care nu folosesc FLEX vor fi depunctate dupa cum e ment, ionat nsect, iunea 5.

2 Specificat, ii mas, ina de test

Mas, ina de test ruleaza un sistem Linux x86 cu urmatoarele versiuni de programe:

GNU Make: 3.81 GCC: 4.4.5 G++: 4.4.5 flex: 2.5.35 Java: 1.6.0 20 (OpenJDK) Jflex: Folosit, i o arhiva .jar sau nis,te fis, iere .class pe care sa le introducet, i

n arhiva, ca n exemplul pentru tema 0.

In cazul n care reus,esc sa activez upload-ul pe vmchecker, aceste specificat, iisunt fixe. Altfel, trebuie sa specificat, i n README daca avet, i nevoie de oprocedura speciala la rulare. Voi anunt,a pe forum pana vineri, 16.01.2015 dacaam reus, it sa activez vmchecker.

1

2.1 Cont, inutul arhivei

Arhiva trebuie sa cont, ina:

surse, a caror organizare nu va e impusa un fis, ier Makefile care sa aiba target de build s, i run (Putet, i folosi o versiune

modificata a celui din tema 0)

un fis, ier README care sa cont, ina numele s, i grupa s, i maxim 20 de linii demaxim 80 de caractere n care sa descriet, i succint abordarea entru lexer.

2.2 Format README

Prima linie din README trebuie sa cont, ina numele vostru, as,a cum apare pecs.curs.pub.ro. Prenumele trebuie sa fie complet, numele sa fie scris cu ma-juscule, daca avet, i diacritice n nume, ele trebuie sa apara s, i salvat, i fis, ierul caUTF-8. Prima linie ar trebui sa arate as,a:

Nume: George Daniel MITRAA doua linie trebuie sa cont, ina grupa s, i seria. Grupa s, i seria trebuie sa fie

lipite, fara spat, ii ntre ele. Restant, ierii s, i vor scrie grupa curenta, nu grupa ncare erau cand au facut LFA. Exemplu:

Grupa: 333CBRestul textului trebuie sa ncapa n maxim 20 de linii s, i fiecare linie sa aiba

cel mult 80 de caractere.Scriet, i doar ceea ce e esent, ial!Fis, ierul trebuie sa se numeasca README, nu readme, ReadMe, README.txt,

readme.txt, read-me.doc, rEADME, README.md sau alte variante asemanatoresau nu.

2.3 Specificat, ii program

2.3.1 Intrari

Programul va citi dintr-un fis, ier numit input automatul finit, n formatul

specificat mai jos. Programul va citi dintr-un fis, ier numit text un text din

care va afis,a subs, irurile din limbaj.Se considera corect orice primes,te programul ca intrare.Simbolurile din text care nu apar n alfabet se trateaza ca separatori. Adica

o trecere prin automat care ncepe nainte de separator se ntrerupe s, i dupaseparator va ncepe o alta. Acest lucru va asigura timpi mai mici de rulare faraprea multe optimizari s, i va permite sa citit, i fisierul linie cu linie, fara a fi nevoiesa le concatenat, i.

2.3.2 Ies, iri

Programul va afis,a la ies, irea standard rezultatul, cate un subs, ir pe linie. S, irulvid nu se va afis,a fiindca nu are sens sa cautam s, irul vid ntr-un text.

2

3 Not, iuni introductive

3.1 Limbajul de descriere

Limbajul este descris printr-o gramatica BNF s, i foloses,te aceeas, i convent, ie deculori ca articolul Wikipedia despre BNF:

albastru - neterminali verde - operatori ai limbajului BNF s, i paranteze ajutatoare rosu - terminali (elemente care fac parte efectiv din limbajul descris)

3.2 Simbol, Alfabet, S, ir

3.2.1 Simbol

Atent, ie, se folosesc simboluri diferite fat, a de tema 0: ::= | | | ::= ( a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p

| q | r | s | t | u | v | w | x | y | z ) ::= ( A | B | C | D | E | F | G | H | I | J | K | L | M |

N | O | P | Q | R | S | T | U | V | W | X | Y | Z ) ::= ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ) ::= ( ! | # | $ | % | & | - | . | / | : | ; | < | > | = | @ | [ | ] | ? | + |

| | | | | | | | )

3.2.2 Alfabet

::= { ( , )* }

3.2.3 S, ir

Atent, ie, un cuvant e definit diferit fat, a de cazul expresiilor regulate, nemaiavands, irul vid:

::= ( )+

4 Automate Finite Deterministe(AFD)

4.1 Descriere

Un automat finit este un model de calcul care primes,te la intrare o banda desimboluri s, i s, i modifica starea interna n funct, ie de ce are la intrare. Acestapoate fi privit ca o cutie neagra cu nis,te stari ntre care face tranzit, ii n funct, iede intrare, la fiecare tranzit, ie mis,cand capul de citire la dreapta.

Formal, un automat finit determinist este un tuplu M = (K,, , s, F ), cuurmatoarele proprietat, i:

K este mult, imea starilor. K este finita, de unde vine s, i numele automa-tului;

este alfabetul din care sunt formate cuvintele acceptate de automat;

3

se numes,te funct, ie de tranzit, ie. : K K. (p, a) = q; p, q K; a nseamna ca automatul, daca se afla n starea p s, i primes,te pebanda a, trece n starea q. Fiindca este funct, ie, toate tranzit, iile dinfiecare stare pentru fiecare simbol trebuie sa fie definite.

s K este starea de start. Aceasta este starea n care se afla automatulnainte de a primi ceva pe banda.

F K este mult, imea starilor finale. Daca automatul se afla ntr-o staref F dupa ce a terminat de citit s, irul nseamna ca accepta s, irul.

4.2 Specificat, ii

In tema, un automat finit determinist este dat ca un tuplu, conform definit, iei: ::= ( , , , , (

| {} ) ) ::= { ( , )* } ::= ::= ( | | | ) + ::= ( ( , ) * ) ::= d( , )=

5 Punctaj

5.1 Checker

Checker-ul va oferi un punctaj ntre 0 s, i 100. Testele sunt publice.

5.2 Bonus s, i Depunctari

Implementarile care nu folosesc flex deloc pierd orice drept la bonus, dar ncasunt depunctate pentru ntarzieri.

Pentru ntarziere, depunctarea e de 2p pe zi. Pentru fis, iere README carenu respecta specificat, iile, depunctarea poate fi de pana la 30p.

Pentru temele trimise mai devreme, bonusul este de 10% * punctajul dat dechecker * min(numarul de zile ramase pana la deadline, 5).

Deadline soft pentru tema: 23.01.2015, ora 23:59. Calculul ntarzierilor s, ia bonusurilor se va face fat, a de ora 03:00 a zilei urmatoare. Deadline hard:28.01.2015, ora 23.59.

6 Sugestii

Va recomand sa ncepeti cat mai repede. E mai us,or decat credeti.Va recomand calduros sa folosit, i FLEX. Chiar daca pare mai greoi init, ial,

analiza lexicala va ies, i mai repede s, i va fi mai us,or de ntret, inut.

4

Bibliografie

[1] flex homepage

[2] Lexical Analysis with Flex

[3] Using flex

[4] jflex homepage

[5] jflex user manual

[6] jflex user manual in japanese

[7] Laborator 1 SO: Makefile

5

Specificatii temaCerinta

Specificatii masina de testContinutul arhiveiFormat READMESpecificatii programIntrariIesiri

Notiuni introductiveLimbajul de descriereSimbol, Alfabet, SirSimbolAlfabetSir

Automate Finite Deterministe(AFD)DescriereSpecificatii

PunctajCheckerBonus si Depunctari

SugestiiBibliografie