Projekt kompilatora - wyrażenia regularne

Analizator leksykalny musi skanować i identyfikować tylko skończony zbiór poprawnych ciągów znaków / tokenów / leksemów, które należą do używanego języka. Wyszukuje wzorzec zdefiniowany przez reguły języka.

Wyrażenia regularne mają możliwość wyrażania skończonych języków poprzez definiowanie wzorca dla skończonych ciągów symboli. Gramatyka zdefiniowana przez wyrażenia regularne jest znana jakoregular grammar. Język zdefiniowany przez gramatykę regularną jest znany jakoregular language.

Wyrażenie regularne jest ważną notacją przy określaniu wzorców. Każdy wzorzec pasuje do zestawu ciągów, więc wyrażenia regularne służą jako nazwy zestawu ciągów. Tokeny języka programowania można opisać zwykłymi językami. Specyfikacja wyrażeń regularnych jest przykładem definicji rekurencyjnej. Zwykłe języki są łatwe do zrozumienia i mają wydajną implementację.

Istnieje wiele praw algebraicznych, które są przestrzegane przez wyrażenia regularne, których można używać do manipulowania wyrażeniami regularnymi w równoważne formy.

Operacje

Różne operacje na językach to:

• Związek dwóch języków L i M jest zapisywany jako

  LUM = {s | s jest w L lub s w M}

• Łączenie dwóch języków L i M jest zapisywane jako

  LM = {st | s jest w L, at jest w M}

• Zamknięcie Kleene języka L jest zapisane jako

  L * = zero lub więcej występowania języka L.

Notacje

Jeśli r i s są wyrażeniami regularnymi oznaczającymi języki L (r) i L (s), to

• Union : (r) | (s) jest wyrażeniem regularnym oznaczającym L (r) UL (s)

• Concatenation : (r) (s) jest wyrażeniem regularnym oznaczającym L (r) L (s)

• Kleene closure : (r) * jest wyrażeniem regularnym oznaczającym (L (r)) *

• (r) jest wyrażeniem regularnym oznaczającym L (r)

Pierwszeństwo i łączność

• *, konkatenacja (.) i | (znak rury) są lewostronne
• * ma najwyższy priorytet
• Konkatenacja (.) Ma drugi najwyższy priorytet.
• | (znak potoku) ma najniższy priorytet ze wszystkich.

Przedstawianie prawidłowych tokenów języka w wyrażeniach regularnych

Jeśli x jest wyrażeniem regularnym, to:

• x * oznacza zero lub więcej wystąpień x.

  tzn. może generować {e, x, xx, xxx, xxxx,…}

• x + oznacza jedno lub więcej wystąpień x.

  tzn. może generować {x, xx, xxx, xxxx…} lub xx *

• x? oznacza co najwyżej jedno wystąpienie x

  tj. może generować {x} lub {e}.

[az] to wszystkie małe litery języka angielskiego.

[AZ] to wszystkie wielkie litery języka angielskiego.

[0-9] to wszystkie cyfry naturalne używane w matematyce.

Przedstawianie występowania symboli za pomocą wyrażeń regularnych

litera = [a - z] lub [A - Z]

cyfra = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 lub [0-9]

znak = [+ | -]

Reprezentowanie tokenów językowych przy użyciu wyrażeń regularnych

Dziesiętny = (znak) ^? (cyfra) ⁺

Identyfikator = (litera) (litera | cyfra) *

Jedynym problemem, jaki pozostał z analizatorem leksykalnym, jest to, jak zweryfikować poprawność wyrażenia regularnego używanego przy określaniu wzorców słów kluczowych języka. Dobrze przyjętym rozwiązaniem jest użycie automatów skończonych do weryfikacji.