Lingwistyka matematyczna

interaktywna pomoc do laboratorium

  • start
  • teoria
  • laboratorium
  • ćwiczenia
  • linki
Analizator składniowy
Podstawy budowania wyrażeń regularnych
Przejście z definicji gramatyki na wyrażenia regularne

Teoria

  • Analizator składniowy
  • Diagramy składni
  • Analizator ster. składn.
  • ONP
  • Automaty


Katedra
Informatyki Stosowanej
  • 90-924 Łódź
  • ul. Stefanowskiego 18/22
  • katedra@kis.p.lodz.pl

Przejście z definicji gramatyki
na wyrażenia regularne

Istnieje możliwość przejścia od definicji gramatyki do wyrażenia regularnego. Warunkiem koniecznym jest, aby definicja nie zawierała rekurencyjnych wywołań symboli, ponieważ uniemożliwia to dokonanie podstawienia. Wyrażenia regularne najprościej jest uzyskać, kiedy gramatyka została zapisana w notacji MBNF, która jest zmodyfikowaną notacją BNF poszerzoną o symbole zamieszczone w poniższej tabeli:


Symbol w notacji MBNF

Znaczenie

Przykładowy odpowiednik w zapisie wyrażeń regularnych

[ ]Wystąpienie symbolu zero lub jeden raza?
{ }Wystąpienie symbolu zero, jeden lub więcej razya*
( )Grupa symboli[0-9]

Poniższy przykład ilustruje przejście z definicji gramatyki do wyrażenia regularnego, opisującego adres e-mail:


S = A@A.W
A = W{.W}
W = L{L}
L = a | b | c | ... | z

Należy podstawić symbole terminalne do kolejnych symboli pomocniczych, aż do symbolu początkowego.

  1. W = (a | b | c | ... | z) { (a | b | c | ... | z) }

  2. A = (a | b | c | ... | z) { (a | b | c | ... | z) } { . (a | b | c | ... | z) { (a | b | c | ... | z) } }

  3. S = (a | b | c | ... | z) { (a | b | c | ... | z) } { . (a | b | c | ... | z) { (a | b | c | ... | z) } } @ (a | b | c | ... | z) { (a | b | c | ... | z) } { . (a | b | c | ... | z) { (a | b | c | ... | z) } } . (a | b | c | ... | z) { (a | b | c | ... | z) }


Na podstawie rozwinięcia definicji symboli S ( punkt 3) można zapisać wyrażenie regularne:

^[a-z][a-z]* ( \.[a-z][a-z]* )* @ [a-z][a-z]* ( \. [a-z][a-z]* )* \. [a-z][a-z]*$

Jak pokazano w powyższysz przykładzie, przejście z definicji gramatyki do opisującego ją wyrażenia regularnego nie jest zbyt skomplikowane, pod warunkiem, że nie mamy do czynienia z rekurencją.

 

Katedra Informatyki Stosowanej | Wydzia EEiA | Politechnika Łódzka

copyright © Katedra Informatyki Stosowanej, designed by alpha studio
dostosowanie kodu i grafiki: Piotr Cieński