Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Ulex: Leksički Analizator Proizvođač za Unicon


Katrina Ray, Ray Pereda, i Clinton Jeffery

Tehnički izveštaj Unicon UTR - 02a

21. maj 2003


Sažetak

Ulek je softverski alat za izgradnju jezičkih procesora. On sprovodi podskup dobro poznatog UNIX C alata koji se zove lex(1) za programe napisane u Unicon i Icon. Ovaj dokument daje kratak opis Ulex i kako se koristi ova alatka.


Fakultet kompjuterskih nauka

Nju Meksiko Stejt univerziteta

Las Cruces, NM 88003


Škola za kompjuterske nauke

Univerziteta u Nevadi Las Vegas

Las Vegas, NV 89154


1.Uvod

Izgradnja jezičkog procesora kao što je kompajler je složen zadatak. Jezički procesor mora da bude u stanju da izvuče gramatičku strukturu rečenice u jeziku. Ovo izvlačenje je poznato kao raščlanivanje. Prvi korak u raščlanivanju je skeniranje da bi se odredile leksičke stavke ili "reči" u rečenici.

Ulex je alat za izgradnju skenera koji obavljaju leksičke analize. Ulex je skraćenica za Unicon Leksički Analizator. Dizajniran je tako da funkcioniše kao klasičan UNIKS program nazvan lex, osim što proizvodi Unicon kod pre nego C. Lex datira iz 1975 i dokumentovan je u [Lesk75].

Ulex koristi običnu notaciju izraza da precizira leksičku analizu, leksička struktura mnogih jezika može biti sažeto i precizno navedena korišćenjem ove notacije. Redovni izrazi podržani u Ulex dati su u tabeli 1.



Оperator

Opis

a

obični simboli bez operatora odgovaraju

.

tačka odgovara bilo kom pojedinačnom karakteru osim novog reda

|

alternacija odgovara ili prethodnom ili sledećem izrazu

bc

spajanje je implicitni binarni operator sa malim pravom prvenstva

*

odgovara nula ili više pojavljivanja prethodnog izraza

[ ]

odgovara bilo kom slovu unutar zagrada

+

odgovara jednom ili više pojavljivanja prethodnog izraza

?

odgovara nula ili jednom pojavljivanju prethodnog izraza

“…”

bukvalno odgovara slovima u navodnicima

(e)

grupiše redovne izraze, prevashodnog pravo prvenstva operatera

Tabela 1: Redovni izrazi u Ulex.



Ovaj dokument pretpostavlja da ste donekle upoznati sa redovnim izrazima, ako ne, možda ćete želeti da pročitate LEKS i Yacc,po [Levine92]. Ulex se obično koristi sa Iyacc, tvorcem alata za raščlanjivanje koji je prateći program za Ulex. Iyacc je dokumentovan u [Pereda00]. Ulex i Iyacc su dodatno opisani u [Jefferi03] .

2. Programska struktura Ulex-a

Ulex alatka uzima leksičku specifikaciju i proizvodi leksički analizator koji odgovara toj specifikaciji. Specifikacija se sastoji od liste redovnih izraza, sa pomoćnim kodovima, fragmentima, promenljivim i pomoćnim funkcijama. Krajnje generisan analizator je u obliku postupka po imenu yylex().

Svi Ulex programi se sastoje od datoteke sa ekstenzijom .l koja sadrži tri odeljka, odvojena linijama koje se sastoje od dva znaka procenta. Tri odeljka su definicioni odeljak, odeljak za pravila , kao i odeljak za procedure . Definicioni odeljak ima dve vrste komponenti. Macros definiše stenografiju redovnih izraza koji će se koristiti u sledećem odeljku. Code fragments ograđeni sa % {i}% su kopirani, doslovno, na generisani leksički analizator. Odeljak za pravila sadrži stvarne redovne izraze koji određuju leksičke analize koje treba da se izvedu. Svaki redovni izraz može biti praćen opcionim semantičkom akcijom umetnutom u vitičastoj zagradi, koja je deo Unicon koda, i koja će biti izvršena kad god redovni izraz odgovara. Odeljak za procedure se takođe kopira u ,doslovno, generisane leksičke analizatore.

Yylex() funkcija i njena povratna vrednost predstavljaju primarni interfejs između leksičkog analizatora i ostatka programa. yylex() vraća -1 ako zauzima ceo ulaz, vraćanje različitih brojevnih vrednosti iz semantičkih akcija u odeljku za pravila omogućavaju yylex() da prekine unos mnogobrojnih komada od 1 + slova (koji se nazivaju tokens),i da identifikuje različite vrste tokena koristeći različite celobrojne kodove. Kao dodatak povratnoj vrednosti, generisani leksički analizator takođe koristi nekoliko globalnih promenljivih. Njihova imena i značenja sumirana su u tabeli 2:


Naziv Promenljive

Opis

yyin

Datoteka iz koje će slova biti pročitana; default: &input

yytext

Niz slova usklađenih sa redovnim izrazima

yyleng

Dužina yytext (*yytext)

yychar

Brojevna kategorija većine nedavnih token

yylval

Leksičke vrednost(i) (često zapis) većine nedavnih tokena

Tabela 2: Ulex globalne promenljive.



3. Primer 1: Brojac Reci (Word Count) program

Postoji UNIKS program koji se zove vc, skraćenica za prebrojavanje reči, koja računa broj redova, reči, i slova u datoteci. Ovaj primer pokazuje kako da se izgradi takav program koristeći Ulex. Ukratko, mada pojednostavljeno, definicija reči je bilo koja sekvenca bez znaka za razmak, gde su znakovi za razmak blanks i tabs. Pogledajte Listing 1 za Ulex program koji posluje kao wc.


ws [ \t]

nonws [^ \t\n]


%{

global cc, wc, lc

%}


%%

{nonws}+ { cc +:= yyleng; wc +:= 1 }

{ws}+ { cc +:= yyleng }

\n { lc +:= 1; cc +:= 1 }

%%


procedure main()

cc := wc := lc := 0

yyulex()

write(right(lc, 8), right(wc, 8), right(cc, 8))

end


Listing 1. wc koji korisi Ulex.

U programu WordCount definicioni odeljak se sastoji od dve definicije, jedan za znak za razmak (ws) i jedan za znak bez razmaka(nonws). Ove definicije su praćene kodom da bi utvrdile tri globalne varijable: CC, wc, i LC. Ovo su brojači za slova, reči i redove, respektivno. Odeljak za pravila u ovom primeru sadrži tri pravila. Razmak, reči i novi redovi imaju pravilo koje odgovara i broji njihova pojavljivanja. Odeljak za procedure ima jednu preoceduru, glavnu(). Ona poziva leksički analizator, a zatim štampa prebrojane vrednosti.

4. Primer 2: Leksički Analizator za Desktop kalkulator

Prethodni primer pokazuje korišćenje Ulex za stvoranje samostalih programa. Međutim, yylex() se obično naziva iz raščlanjivača. yylex() funkcija može da se koristi za proizvodnju niza reči, tako da raščlanjivač, kao onaj generisan od strane iyacc programa, može da kombinuje te reči u rečenice. Tako da ima smisla proučavati kako se Ulex koristi u ovom kontekstu. Jedna očigledna razlika je da u prethodnom primeru, yylex() je samo jednom pozvan da obradi celu datoteku. Nasuprot tome, kada raščlanjivač koristi yylex(), on poziva analizator u više navrata, i yylex() vraća sa svakom reči koju pronađe. To će se pokazati na primeru koji sledi.

Kalkulator program je dovoljno jednostavan da se razume u jednom zasedanju i dovoljno složen da se dobije osećaj kako da koristite Ulex sa njegovim parser generator kolegom: Iyacc. U opštem programu desktop kalkulatora, korisnik ukucava složene formule, koje kalkulator procenjuje i zatim štampa rezultat. Generisani leksički analizator mora da prepozna reči ovog jezika, kojima će rukovati parser. U ovom slučaju reči su brojevi, matematički operatori i nazivi promenljivih.

Broj jedna ili više cifara, praćenim opcionom decimalnom tačkom i jedne ili više cifara. U redovnim izrazima, ovo može da se napiše kao:


[0-9]+(\.[0-9]+)?



Matematički operatori su jednostavne reči sastavljene od jednog slova. Imena promenljivih mogu biti bilo koje kombinacije slova, cifara i donjih crta. Dakle, da ih ne bi pomešali sa brojevima, preradite definiciju vodeći računa da promenljive ne počinju sa brojem. Ova definicija imena promenljive odgovara sledećem redovnom izrazu:


[a-zA-Z_][a-zA-Z0-9_]*



Setite se da postoje tri odeljka za svaki Ulex program: definicioni odeljak, odeljak za pravila, odeljak za procedure. Ulex program za usklađivanje reči kalkulatora je dat u listingu 2.


%{

# y_tab.icn sadrži celobrojne kodove za predstavljanje

# terminalne simbola NAME, NUMBER, iASSIGNMENT.

$ Uključuje y_tab.icn

%}


Slovo [a-zA-Z_]

digitalno slovo [a-zA-Z0-9_]


%%

{letter}{digiletter}* { yylval := yytext; return NAME }

[0-9]+(\.[0-9]+)? { yylval := numeric(yytext); return NUMBER }

\n {

return 0 # logical end-of-file

}

“:=” { return ASSIGNMENT }

[ \t]+ {

# ignore white space

}

. { return ord(yytext) }

%%


Listing2.Ulex program za prepoznavanje leksičkih elemenata kalkulatora.

Definicioni odeljak ima i komponentu koja je direktno kopirana na generički leksički analizator, kao i skup macros. Prvo pravilo odgovara imenima promenljivih, a drugo pravilo odgovara brojevima. Treće pravilo vraća 0 da ukaže parser da treba da proceni izraz. Četvrto pravilo omogućava parser da zna da je postajao operator zadatka, a peto se koristi da ignoriše znak razmaka. Poslednje pravilo odgovara svemu ostalom, uključujući i druge matematičke operatore. Numerička šifra znakova(npr. ASCII) se direktno vraća parser.

yylval se koristi za čuvanje rezultata kad god podudarimo ili ime promenljive ili broj. Ovako kada leksički analizator vraća brojni kod za ime ili broj, parser zna da potraži u yylval stvarna imena ili broj koji odgovara. Pošto Unicon omogućava promenljivim da zaržate bilo koju vrstu vrednosti, nema potrebe za komplikovanim konstruktima da bi se rukovalo činjenicom da različiti tokeni imaju različite vrste leksičkih vrednosti.

Primetite da odgovarajući parovi, kojima je dozvoljeno ovim skupom redovnih izraza, su donekle nejasni. Na primer, count10 može da odgovara imenu promenljive i onda celom broju, ili jednom ime nupromenljive . Ulex alatka je dizajnirana da odgovara najdužem podnizu ulaza koji mogu odgovarati redovnim izrazima. Tako će count10 biti odgovarajući kao jedna reč, koja je promenljiva u ovom slučaju. U slučaju kada dva različita izraza odgovaraju istom broju slova, prvo pravilo navedeno u specifikaciji će se koristiti.

5. Zaključak

Primeri u ovom radu predstavljaju kako Ulex može biti koristan u obradi jezika ili kao samostalna aplikacija, ili u vezi sa parserom. Ulex je još uvek u preliminarnom stanju, ali je sada spreman za testiranje, a kada sazri trebalo bi da da bude koristan za eksperimentalnu izradu kompajler prototipova.

ZAHVALNOST

Ulex alatka je prvenstveno rad Katrina Ray, ona je podržna od strane NMSU zajedništva i Narodne Biblioteke Medicine tokom svog razvoja.

Rej Pereda je napisao prvu verziju ovog dokumenta da opiše svoju iflex alatku.

Literatura

[Jeffery03] C. Jeffery, S. Mohamed, R. Pereda, and R. Parlett. Programming with Unicon. http;//unicon.sf.net/book/ub.pdf, 2003.

[Lesk75] M.E. Lesk and E. Schmidt. LEX – Lexical Analyzer Generator. Computer Science Technical Report No. 39, Bell Laboratories, Murray Hill New Jersey, October 1975.

[Levine92] J.R. Levine, T. Mason, and D. Brown. Lex & Yacc, O”Reilly & Associates, Cambridge, Massachusetts, 1992.

[Pereda00] Ray Pereda. Iyacc – a Parser Generator for Icon, Unicon Technical Report 03, http://unicon.sf.net/utr/utr3.pdf, February 2000.

Dodatak: Razlike između Ulex i UNIX lex (1)

Ovaj prilog sumira poznate razlike između Ulex i UNIX lex (1) alatki. Ulex je veliki podskup lex, ali ,za napomenu, ima nekoliko važnih ograničenja

Ne gledajuci napred(No lookahead) - lookahead operator / još uvek nije podržan

Naivne semanticke akcije(Naïve semantic actions) -Semantičke akcije moraju biti zatvorene u vitičaste zagrade

Bez Ponavljanja(No repetition)- ponavljanje operatora (npr. {2 : 5}) još uvek nije podržano.



Published (Last edited): 27-09-2012 , source: http://unicon.sourceforge.net/utr/utr2/utr2a.html