Własności języków regularnych
Lemat o pompowaniu
Własności języków regularnych. Analiza Niech L będzie językiem regularnym. Wtedy istnieje stała n t.że jeśli
z jest dowolnym słowem z L oraz |z| n, to z możemy przedstawić w
leksykalna
postaci z = uvw, gdzie |uv| n i |v| 1 oraz uviw należy do L dla
Języki formalne i techniki translacji - Wykład 3
każdego i 0.
n jest nie większe niż liczba stanów najmniejszego DFA
Maciek Gębala
akceptującego L.
Dowód
6 marca 2013
Na tablicy.
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Wykorzystanie Lematu o pompowaniu Własności języków regularnych
Dowodzenie że L nie jest regularny
1
Załóż, że L jest regularny i istnieje odpowiednie n.
Lemat. Klasa języków regularnych jest zamknięta na operację sumy,
2
Wybierz słowo z zgodnie z lematem (jego długość musi zależeć
dopełnienia, przecięcia, złożenia i domknięcia Kleene ego.
od n).
3
Pokaż, że dla każdego podziału z zgodnego z lematem istnieje i
Dowód
takie, że uviw " L.
/
Suma, złożenie i domknięcie Kleene ego: z definicji RE.
Dopełnienie: jeśli L akceptowany przez DFA M = (Q, Ł, �, q0, F ) to L
Przykład
akceptowany przez M = (Q, Ł, �, q0, Q \ F ).
2
L = { 0i : i " N }
Przecięcie: Jeśli L1 i L2 akceptowane przez odpowiednie DFA
M1 = (Q1, Ł, �1, q1, F1) i M2 = (Q2, Ł, �2, q2, F2), to L1 )" L2
Załóżmy, że L jest regularny i wez
my n z Lematu o pompowaniu.
2 akceptowany przez M = (Q1 � Q2, Ł, �, (q1, q2), F1 � F2), gdzie
Wez
my z = 0n .
�((p, q), a) = (�1(p, a), �2(q, a)).
z = uvw i |uv| n oraz |v| 1. Wez
my i = 2. Wtedy mamy
Suma: M = (Q1 � Q2, Ł, �, (q1, q2), (Q1 � Q2) \ ((Q1 \ F1) � (Q2 \ F2))).
n2 < |uv2w| = |uvw| + |v| n2 + n < (n + 1)2,
czyli uv2w " L. L nie jest regularny.
/
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Własności języków regularnych Analiza leksykalna
Lemat. Zbiór słów akceptowanych przez DFA M o n stanach jest
1
niepusty �!�! M akceptuje słowo o długości mniejszej niż n;
Rozbicie ciągu znaków wejściowych na symbole leksykalne (wyrazy
2
posiadające określone znaczenie). Ciąg symboli leksykalnych
nieskończony jeśli M akceptuje słowo o długości l, dla
stanowi wejście dla analizatora składniowego.
n l < 2n.
Podstawowe pojęcia
Lemat. Istnieje algorytm rozstrzygający czy dwa automaty
skończone są równoważne (akceptują te same języki).
Symbol leksykalny (token)
Leksem (symbol leksykalny może mieć wiele leksemów)
Dowód
Wzorzec
Wez
my M1 i M2 DFA akceptujące odpowiednio języki L1 i L2.
Jeśli L1 = L2 to (L1 )" L2) *" (L1 )" L2) niepusty.

Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Przykład symboli leksykalnych Zapis wzorca
Wzorce zapisujemy jako wyrażenia regularne.
Składnia wyrażeń rozszerzona aby umożliwić zwięzły zapis.
W opisie przez wyrażenia regularne używamy następujących
priorytetów: gwiazdka Kleene go, złożenie, suma.
Identyfikator_typu double
Identyfikator sqr Przykład
 ( (
Symbol leksykalny Wyrażenie regularne
Identyfikator x
Identyfikator
 ) )
Token Leksem
 ( \
 { {
 { \
KW_return return
Operator_binarny * Operator_binarny \
 ; ;
KW_return
 } }
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Implementacja analizatora leksykalnego Koncepcja FLEX-a
Wykorzystanie generatorów analizatorów leksykalnych (np. LEX,
FLEX).
Generowanie kodu analizatora na podstawie zadanej
Napisanie analizatora bezpośrednio w jakimś języku
specyfikacji.
programowania.
Domyślnie analizator jest w języku C.
Złożoność pamięciowa i czasowa automatów skończonych Wygenerowany kod z
ródłowy kompilujemy jako samodzielny
program lub moduł programu.
Automat Pamięć Czas
 funkcja wygenerowana przez LEX-a odpowiedzialna
DFA O(2|r|) O(|x|)
za działanie leksera (można ją wykorzystać w innej aplikacji).
NFA O(|r|) O(|x| � |r|)
gdzie |r| - długość wyrażenia regularnego, |x| - długość łańcucha
flex gcc
wejściowego.
Jednak implementacja DFA jest dużo łatwiejsza, a wielkość
zmniejsza się w trakcie minimalizacji.
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Specyfikacja pliku z
ródłowego Podstawowe reguły działania
Specyfikacja składa się z 3 części:
Niedopasowane znaki są przepisywane na wyjście.
Sekcja definicji.
Można definiować operacje puste (wzorzec bez reguły
Sekcja reguł przetwarzania, gdzie reguła składa się z dwóch
przetwarzania).
części
Wzorca (wyrażenia regularnego) Znaki specjalne poprzedzamy znakiem \.
Operacji (zapisanej w C)
Wzorce zawierające spacje ujmujemy w cudzysłów podwójny.
Sekcja podprogramów.
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Przykład Wyrażenia regularne w FLEX-ie
Wyrażenie Opis
Wzorzec od początku linii
Wzorzec do końca linii
Konkatenacja wzorców
alternatywa wzorców
domknięcie zwrotne
domkniecie dodatnie
opcjonalność (występuje 0 lub 1 raz)
trzykrotne powtórzenie wzorca
od dwóch do czterech powtórzeń
\ \
co najmniej dwa powtórzenia
nawiasy wyrażają priorytet
\ \
klasa znaków, jeden znak ze zbioru od a do z
dowolny znak spoza klasy
. dowolny znak (ale nie \n)
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna
Zmienne wbudowane Zasady dopasowywania
Co zrobi LEX jeśli tekst może się dopasować do kilku wzorców?
 wskaz
nik na ostatnio rozpoznany (dopasowany)
leksem;
Niejednoznaczność w LEX-ie rozstrzygana jest według 2 zasad:
 długość dopasowanego leksema;
1
Zasada najdłuższego dopasowania.
2
Zasada wcześniejszego dopasowania.
Maciek Gębala Własności języków regularnych. Analiza leksykalna Maciek Gębala Własności języków regularnych. Analiza leksykalna