Analiza leksykalna
Informacje, które udało nam się zgromadzić na temat Analiza leksykalna , zostały starannie sprawdzone i uporządkowane, aby były jak najbardziej przydatne. Prawdopodobnie trafiłeś tutaj, aby dowiedzieć się więcej na temat Analiza leksykalna . W Internecie łatwo zgubić się w gąszczu stron, które mówią o Analiza leksykalna , a jednocześnie nie podają tego, co chcemy wiedzieć o Analiza leksykalna . Mamy nadzieję, że dasz nam znać w komentarzach, czy podoba Ci się to, co przeczytałeś o Analiza leksykalna poniżej. Jeśli informacje o Analiza leksykalna , które podajemy, nie są tym, czego szukałeś, daj nam znać, abyśmy mogli codziennie ulepszać tę stronę.
.
W informatyce , analiza leksykalna , Lexing , segmentacji lub tokeny jest konwersja na cig znaków (tekst) na licie symboli ( tokeny w jzyku angielskim). Jest to cz pierwszej fazy acucha kompilacji . Symbole te s nastpnie zuywane podczas parsowania . Program wykonujcy analiz leksykaln nazywa si analizatorem leksykalnym , tokenizerem lub leksykiem. Analizator leksykalny jest zwykle czony z analizatorem skadni w celu analizy skadni tekstu.
leksem
Leksem to cig znaków w programu ródowego, który pasuje do wzorca o sownikowego symbolem, który analizowano za pomoc analizatora sownikowego jako przykad tego symbolu sownikowego.
Niektórzy autorzy uywaj terminu token do reprezentowania zarówno cigu znaków przetwarzanego przez analizator leksykalny, jak i struktury danych wytworzonej na wyjciu tego przetwarzania.
Termin leksem w informatyce nie ma takiego samego znaczenia jak leksem w jzykoznawstwie . W informatyce jego definicja jest podobna do definicji morfemu w jzykoznawstwie.
Jednostka leksykalna
Jednostka leksykalna lub leksykalny leksykalny lub prociej leksykalny element to para skadajca si z nazwy i opcjonalnej wartoci. Nazwa jednostki leksykalnej jest kategori jednostki leksykalnej.
Kilka przykadów nazw jednostek leksykalnych najczciej spotykanych:
- identyfikatory: nazwa zmiennych lub funkcji wybranych przez programist analizowanego kodu. Nie moe by zastrzeonym sowem w jzyku;
- sowa kluczowe: zastrzeone sowa jzyka;
- separatory (interpunkcja): proste znaki interpunkcyjne, takie jak kropki i przecinki, lub zoone, takie jak nawiasy i nawiasy kwadratowe;
- operatory ( operatory ) nakadajce symbole na argumenty i generujce wynik;
- literay ( literay ): sekwencja znaków reprezentujca warto liczbow, logik itp. ;
| Nazwisko | Wartoci |
|---|---|
| identyfikatory |
x, color, UP
|
| sowa kluczowe |
if, while, return
|
| interpunkcja |
}, (, ;
|
| operatorzy |
+, <, =
|
| literay |
true, 6.02e23, "music"
|
Nazw jednostki leksykalnej mona porówna do pojcia natury gramatycznej .
Gramatyka leksykalna
Te jzyki programowania czsto okrela zasady, jak gramatyka definiuje skadni do przyjcia. Reguy te czsto przybieraj posta wyrae regularnych i definiuj sekwencje znaków uywane do tworzenia leksemów.
Jzyki rozpoznawane przez wyraenie regularne nazywane s jzykami racjonalnymi . Moemy skojarzy automat skoczony z dowolnym wyraeniem regularnym . S te jzyki nieracjonalne.
Dwie z najwaniejszych kategorii jednostek leksykalnych to znaki spacji i komentarze. Oba s zdefiniowane w gramatyce wikszoci jzyków i objte leksykami, ale najczciej s uwaane za nieistotne; w najlepszym przypadku oddzielenie dwóch tokenów i nie generowanie ich samodzielnie. Od tego s dwa gówne wyjtki. Przede wszystkim tak zwane jzyki skadni podobne do wci, takie jak Python, które ograniczaj bloki kodu za pomoc wci i dla których znaki spacji s znaczce i dlatego mog generowa tokeny. Nastpnie w niektórych zastosowaniach lekserów, w tym niektórych narzdzi do debugowania lub eleganckich impresji (adne drukarki w jzyku angielskim), moe by konieczne zachowanie oryginalnego kodu ródowego w celu póniejszego wywietlenia uytkownikowi.
Analizator leksykalny
Nazywany analizatorem leksykalnym ( lexer English) dowolny program wykonujcy analiz leksykaln.
Analizator leksykalny suy do:
- wyeliminowa szum z tekstu ródowego: komentarze, spacje;
- rozpoznaj operatory i sowa kluczowe: +,>, if, return,;
- rozpoznaj identyfikatory, cigi literowe i liczby literaowe.
Gdy analizator leksykalny wykryje nieprawidowy leksem, zgasza bd. W przeciwiestwie do tego, kombinacje leksemów s zwykle pozostawione parserowi: na przykad typowy analizator leksykalny rozpoznaje nawiasy jako leksemy, ale nie sprawdza, czy otwarty nawias ( jest koniecznie powizany z nawiasem zamykajcym ) .
Analizator leksykalny mona napisa
- Rcznie: musimy zbudowa niedeterministyczny automat skoczony z wyraenia regularnego E, a nastpnie wykona go, aby okreli, czy acuch wejciowy naley do jzyka rozpoznawanego przez E;
- przez tabel opisujc automat i program korzystajcy z tej tabeli;
- przez generator analizatorów leksykalnych: Lex , Flex ., ANTLR , itp.
Chocia leksery s gównie uywane do pisania kompilatorów, s one wykorzystywane przy projektowaniu innych narzdzi do przetwarzania jzyków komputerowych, takich jak lint czy eleganckie systemy drukowania ( troff ).
Proces
Analiza leksykalna to pierwsza faza wspóczesnych procesów kompilacji . Analiz zwykle wykonuje si, przegldajc tekst ródowy tylko raz.
Polega na rozgraniczeniu i jeli to moliwe scharakteryzowaniu odcinków wejciowego cigu znaków w cigu leksemów, które zostan przekazane do innej formy analizy.
Na przykad instrukcja sum = 2 + 3;w jzyku C tworzy po analizie leksykalnej nastpujc list symboli:
| Warto | Kategoria leksykalna |
|---|---|
| suma | Nazwa Uytkownika |
| = | operator przypisania |
| 2 | dosowna liczba cakowita |
| + | operator dodawania |
| 3 | dosowna liczba cakowita |
| ; | koniec deklaracji |
Sekwencja znaków wejciowych, niejawnie podzielona spacjami, jak w jzykach naturalnych, zostaa przeksztacona w list szeciu jednostek leksykalnych:
[(identifiant, sum), (opérateur d'affectation, =), (entier littéral, 2), (operator, +), (entier littéral, 3), (fin de déclaration, ;)]
Ogólnie rzecz biorc, gdy jednostka leksykalna reprezentuje kilka leksemów, analizator leksykalny zapisuje wystarczajc ilo informacji, aby móc odtworzy oryginalny leksem i uy go podczas analizy semantycznej. Parser pobiera te informacje i przechowuje je w formie drzewa skadni abstrakcyjnej (AST). Jest to konieczne, aby unikn utraty informacji w przypadku numerów i identyfikatorów.
Leksemy s identyfikowane wedug regu ustalonych przez analizator leksykalny. Wród metod uywanych do identyfikacji leksemów znajdziemy: wyraenia regularne , okrelony cig znaków zwany flag , znaki zwane separatorami oraz sownik.
Analizator leksykalny na ogó nie przetwarza kombinacji jednostek leksykalnych, zadanie to jest pozostawione parserowi. Na przykad typowy analizator leksykalny moe rozpoznawa i przetwarza nawiasy, ale nie jest w stanie ich policzy i dlatego zweryfikowa, czy kady nawias zamykajcy ")" pasuje do poprzedzajcego nawiasu otwartego "(").
Analiza leksykalna cigu znaków odbywa si w trzech etapach:
- Skanowania , które segmenty posta cigu wejciowego do leksemów oraz przekierowuje je do kategorii leksykalnej (dosownym cakowit, operator dodawania, identyfikator, etc.);
- Ocena który konwertuje kady leksemu do wartoci.
ów
Pierwszy krok, skanowanie, jest zwykle wykonywany przez maszyn stanow . Automat ten posiada informacje niezbdne do przetworzenia wszystkich cigów znaków, które mog zawiera si w leksemie (kady znak tych cigów jest leksemem). Na przykad int moe zawiera wszystkie moliwe sekwencje cyfr . W wielu przypadkach pierwszy znaczcy znak odczytany moe by uyty do wywnioskowania natury biecego leksemu, a kady kolejny znak bdzie dodawany do wartoci tokena, a do odczytania niedopuszczalnego znaku. W niektórych jzykach regua moe by jednak bardziej zoona i wymaga cofania si na ju przeczytanych znakach. Na przykad w C znak L nie wystarcza do odrónienia identyfikatora zaczynajcego si od L od literau skadajcego si z tego pojedynczego znaku.
Ocena
Leksem to tylko cig znaków charakteryzujcy si typem. Aby zbudowa jednostk leksykaln, analizator leksykalny wymaga drugiego kroku, oceny, która wytwarza warto. Rodzaj leksemu w poczeniu z jego wartoci stanowi token, który nastpnie moe zosta dostarczony do parsera. Niektóre leksemy, takie jak te reprezentujce interpunkcj, nie maj rzeczywistej wartoci, wic ich funkcja oceny moe zwróci warto równ zero; potrzebny jest tylko ich typ. Podobnie, ocena moe cakowicie usun leksem, ukrywajc go przed parserem, tak jak w przypadku znaków spacji lub komentarzy. Ocena identyfikatorów jest czsto prosta, przekazujc bezporednio cig znaków stanowicy je w wartoci, ale dla wartoci liczbowych analizator leksykalny moe zdecydowa si na przeksztacenie ich w jednostk leksykaln w postaci cigów znaków (odroczenie ich przetwarzania analizy semantycznej) lub sam je oceni.
Nawet jeli jest moliwe, a nawet konieczne w przypadku niewielkiej liczby leksemów napisanie analizatora leksykalnego odrcznie, to czsto s one generowane przez narzdzia automatyczne. Narzdzia te ogólnie akceptuj wyraenia regularne opisujce autoryzowane leksemy. Kade wyraenie regularne jest powizane z regu produkcji dla gramatyki formalnej ocenianego jzyka. Narzdzia te mog generowa kod ródowy, który mona skompilowa i wykona, lub zbudowa tabel przej stanów dla automatu stanów.
Wyraenie regularne reprezentuje zwart wersj wzorca, który musz by zgodne z leksemami, aby utworzy prawidow jednostk leksykaln. Na przykad w przypadku jzyka opartego na jzyku francuskim identyfikatorem moe by dowolny znak alfabetyczny lub podkrelenie, po którym nastpuje dowolna sekwencja cyfr alfanumerycznych lub znaków ASCII i/lub podkrele. Ta sekwencja moe by reprezentowana przez nastpujcy cig znaków [a-zA-Z_][a-zA-Z_0-9]*.
Wyraenia regularne i generowane przez nie automaty skoczone nie s wystarczajco potne, aby obsuy wzorce rekurencyjne, takie jak te, które mona znale w jzykach Dyck . Te zabiegi s pozostawione analizatorowi skadni.
W starszych jzykach, takich jak ALGOL , pierwszy etap kompilacji nazywano rekonstrukcj linii, która polegaa na skanowaniu tekstu w poszukiwaniu sów kluczowych oraz usuwaniu spacji i komentarzy . Analizy leksykalne i skadniowe zostay wykonane przez pojedynczy program parser-lekser.
Limity
Zazwyczaj analiza leksykalna dziaa na poziomie sów . Czasami jednak moe by trudno odróni, czym jest sowo. Czsto analizatory leksykalne opieraj si na prostych heurystykach , na przykad:
- spacje i interpunkcja mog, ale nie musz by czci listy prawidowych leksemów;
- wszystkie cige cigi znaków alfanumerycznych mona interpretowa jako pojedynczy leksem;
- leksemy s oddzielone spacj lub interpunkcj;
W jzykach uywajcych spacji midzywyrazowych (jak wikszo jzyków programowania i jzyków naturalnych uywajcych alfabetu aciskiego) takie podejcie jest atwe do wdroenia. Mimo to istnieje wiele przypadków ( skurcze , emotikony , zoony, URI , itd. ), Które wymagaj bardziej skomplikowanej heurystyczne by przetwarzany przez analizator sownikowego. Klasycznym przykadem jest sekwencja znaków pochodzca z Nowego Jorku, która w jzyku angielskim tworzy jedno sowo, ale któr naiwnie mona rozdzieli na dwa lub nawet trzy leksemy.
Analiza leksykalna moe by szczególnie trudna w przypadku jzyków naturalnych pisanych w scriptio continua, dla których nie ma symbolu interpunkcji lub separacji leksemów, jak w staroytnej grece czy chiskim .
Wcicie jako skadnia
Niektóre jzyki, takie jak Python, uywaj wci do oddzielania bloków kodu . Analizator leksykalny musi zatem generowa jednostk leksykaln INDENT, gdy wcicie wzrasta, a jednostk leksykaln DEDENT, gdy jest zmniejszane. Te jednostki leksykalne odpowiadaj tym generowanym podczas odczytywania nawiasów kwadratowych otwierajcych { i zamykajcych } w jzykach takich jak C. Aby parser móg by uwzgldniony, musi by w stanie zachowa aktualny stan. wcicia (poniewa bloki mog by zagniedane jeden w drugim), co sprawia, e gramatyka analizowanego jzyka jest kontekstowa . INDENT-DEDENT zaley od kontekstu (w tym przypadku na poprzednim poziomie wcicia).
Generator analizatora leksykalnego
Analizatory leksykalne s czsto generowane przez narzdzia zwane generatorami analizatorów leksykalnych . Jednym z najczciej uywanych jest Lex wraz z generatorem parserów Yacc i ich darmowymi odpowiednikami Flex i Bison . Generatory te s form dedykowanego jzyka , przyjmujcego jako dane wejciowe specyfikacj leksykaln (zwykle wyraenia regularne i niektóre znaczniki) i generujcej leksykay.
Narzdzia te umoliwiaj szybki rozwój funkcjonalnego analizatora leksykalnego.
Lista generatorów analizatorów leksykalnych
- ANTLR : generuj leksyki i parsery
- DFASTAR: generuje automaty skoczone w C++
- Flex : darmowy wariant Lex
- Ragel : kompilator skoczonych automatów generujcy swoje wyniki w kodzie ródowym w jzykach: C , C ++ , Objective-C , Java , Go i Ruby
- re2c: generator lekserów dla C i C ++
- JavaCC : kompilator kompilator napisany w Javie
- JFLex: generator analizatorów leksykalnych dla Javy napisany w Javie
- AnnoFlex: kolejny generator analizatorów leksykalnych dla Javy napisany w Javie
- RE / flex: szybki wariant lex / flex dla C ++
- Quex: generator lekserów C i C++ napisany w Pythonie
- FsLex: generator lexera rozpoznajcy znaki ASCII i Unicode dla F #
- PLY: Implementacja Lex w Pythonie
Zoono algorytmiczna
Duym problemem jest wydajno lekserów, zwaszcza w stabilnych jzykach, w których lekser jest bardzo czsto nazywany (jak C lub HTML). Leksery generowane za pomoc Lex/Flex s uwaane za do szybkie, ale w niektórych przypadkach mog by od dwóch do trzech razy wolniejsze ni leksery pisane odrcznie lub narzdzia takie jak re2c.
Algorytm naiwny
- Dla kadego symbolu generujemy automat, który rozpoznaje wyraenie regularne powizane z symbolem. Ten automat bdzie oznaczony symbolem.
- Dopóki sowo nie zostao w peni przeanalizowane i nie ma bdu:
- Czytamy sowo litera po literze, przesuwajc automaty równolegle dla kadej litery.
- Gdy PLC wchodzi w stan kocowy, znalezione sowo podrzdne i identyfikator PLC s zachowywane.
- Jeli wszystkie sterowniki PLC s w stanie sink lub jeli sowo zostao w peni przeanalizowane:
- Jeeli aden PLC nie osign stanu kocowego: zwracany jest bd.
- W przeciwnym razie dodajemy par (najwiksze podsowo z automatem w stanie kocowym, typ automatu, który go znalaz) do listy bytów leksykalnych. Nastpnie zastpujemy si zaraz po tym podsowie, resetujemy automaty i kontynuujemy czytanie tego sowa.
Analiza zoonoci
W przypadku jzyków programowania algorytm ten czsto dziaa w czasie liniowym w odniesieniu do wielkoci sowa wejciowego. Zdarzaj si jednak patologiczne przypadki, w których algorytm dziaa w czasie kwadratowym, taki jak ten: z dwoma leksemami: a i a ab, wpis a n wymaga, aby algorytm doszed do koca wyrazu dla kadego a, które rozpozna . Zoono jest wtedy kwadratowa.
Inne algorytmy
Istniej inne algorytmy zdolne do analizy sowa w czasie liniowym.
Uwagi i referencje
Uwagi
Bibliografia
- Anatomy of a Compiler and The Tokenizer na stronie www.cs.man.ac.uk (dostp 5 stycznia 2018 r . ) .
- (w) Aho, Lam, Sethi i Ullman, Compilers Principles, Techniques & Tools, wydanie drugie , WorldCat, strona 111.
- (w) " Perl 5 Porters " na perldoc.perl.org .
- Terminy znormalizowane przez ISO / IEC 2382-15: 1999 Technika informatyczna - Sownictwo - Cz 15: Jzyki programowania
- Struktura i interpretacja programów komputerowych na stronie mitpress.mit.edu (dostp 5 stycznia 2018 r . ) .
- (w) Visser, E, Scannerless Generalized LR-Parsing , University of Amsterdam,.
- 2. Analiza leksykalna dokumentacja Pythona 3.6.4 , na stronie docs.python.org (dostp 6 stycznia 2018 r . ) .
- re2c .
- JFLEX .
- AnnoFlex .
- RE / Flex .
- Quex .
- FsLex .
- PLY .
- Peter Bumbulis i Donald D. Cowan , RE2C: bardziej wszechstronny generator skanerów , ACM Lett. Program. Jzyk. Syst. , tom. 2, n koci 1-4, s. 70-84 ( ISSN 1057-4514 , DOI 10.1145 / 176454.176487 , czytanie online , dostp 6 stycznia 2018 ).
- (w) Thomas Reps, " " Maximum-Muncha "w tokenizacja czasie liniowym " , Transakcje ACM na jzyki programowania i systemy , vol. 20, nr 2 ,( przeczytaj online ).
Zaczniki
Bibliografia
Powizane artykuy
- Gramatyka
- Kompilator kompilatora
- Analiza skadni
- Analiza semantyczna
- Lex (oprogramowanie)
- modele leksykonów (LMF)
Linki zewntrzne
Mamy nadzieję, że informacje, które zgromadziliśmy na temat Analiza leksykalna , były dla Ciebie przydatne. Jeśli tak, nie zapomnij polecić nas swoim przyjaciołom i rodzinie oraz pamiętaj, że zawsze możesz się z nami skontaktować, jeśli będziesz nas potrzebować. Jeśli mimo naszych starań uznasz, że informacje podane na temat _title nie są całkowicie poprawne lub że powinniśmy coś dodać lub poprawić, będziemy wdzięczni za poinformowanie nas o tym. Dostarczanie najlepszych i najbardziej wyczerpujących informacji na temat Analiza leksykalna i każdego innego tematu jest istotą tej strony internetowej; kierujemy się tym samym duchem, który inspirował twórców Encyclopedia Project, i z tego powodu mamy nadzieję, że to, co znalazłeś o Analiza leksykalna na tej stronie pomogło Ci poszerzyć swoją wiedzę.