ews15-d-grundsymbole-und-syntax

Vorlesung und Übung
Universität Paderborn
Wintersemester 2015/2016
Dr. Peter Pfahler
SPEZIFIKATION VON
GRUNDSYMBOLEN
UND SYNTAX
D-1
EWS, WS 2015/16, Pfahler
Grundsymbole (Wiederholung)
Ein Grundsymbol wird aus einer Folge von Zeichen des Alphabets gebildet.
$line = fgets ( $fp , 64 ) ;
Typische Grundsymbole in Programmiersprachen (Beispiele aus PHP)
Bezeichner (identifier)
Literale (literals)
Wortsymbole (keywords)
Spezialzeichen
Namen für Variable, Funktionen, ...
$line fgets
Zahlwerte, Zeichenreihen
64 "telefonbuch.txt"
kennzeichnen Sprachkonstrukte
while if
Operatoren, Separatoren
<= = ; { }
Formale Definition:
Reguläre Ausdrücke
EWS, WS 2015/16, Pfahler
D-2
Alphabete
Ein Alphabet ist eine nicht-leere Menge von Zeichen zur Bildung von Zeichenfolgen.
Alphabete werden in Formeln häufig mit  bezeichnet oder man ihnen individuelle Namen
oder benutzt sie unbenannt.
Beispiele:
=
Dualziffern =
Dezimalziffern =
Kleinbuchstaben =
ASCII =
{T, F}
{0, 1}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{a, b, ... z}
standardisierter Zeichensatz mit 128 Zeichen
Ein Wort über einem Alphabet A ist eine Folge von Zeichen aus A.
formal: eine Folge a1 a2 ... an, mit ai ist Element von A, für i = 1, ..., n.
n ist die Länge der Folge bzw. die Länge des Wortes.
Beispiel:
Wort der Länge 7 über dem Alphabet Dualziffer: 1001101
Die leere Folge bzw. das leere Wort wird mit  (epsilon) bezeichnet.
EWS, WS 2015/16, Pfahler
D-3
Reguläre Ausdrücke
Regulärer Ausdruck R
definiert eine Menge von Worten über einem Alphabet A, die Sprache L (R).
Ein regulärer Ausdruck kann aus folgenden 8 Formen rekursiv zusammengesetzt sein.
F und G seien reguläre Ausdrücke.
regulärer
Ausdruck R
Sprache L (R)
Erklärung
a
FG
F|G
ε
{a}
{ f g | f in L(F), g in L(G) }
{ f | f in LF) } U { g | g in L(G) }
{ε}
Zeichen a als Wort
Zusammenfügen von 2 Worten
Alternativen
das leere Wort („Epsilon“)
(F)
F+
F*
Fn
L(F)
{ f1 f2 ... fn | fi in L(F), für n>1, i=1,..., n}
{ ε } U L(F +)
{ f1 f2 ... fn | fi in L(F), füri = 1,..., n}
Klammerung
nicht-leere Folgen von Worten aus L(F)
Folgen von Worten aus L(F)
Folgen von genau n Worten aus L(F)
EWS, WS 2015/16, Pfahler
D-4
Beispiele für reguläre Ausdrücke
Alternativen
L(a)
L(a|b)
L(a(a|b))
L(a|ε)
L(a(a|ε))
L(b(a|ε)d)
{a}
{a, b}
{aa, ab}
{a,ε}
{aa, a}, da aε=a und εa=a
{bad, bd}
Folgen
L(a+ )
nicht-leere Folge von a
{a, aa, aaa, aaaa, ...}
beliebige Folge von a (auch leeres Wort)
{ε, a, aa, aaa, aaaa, ...}
nicht-leere Folge von Worten aus L(ab)
{ab, abab, ababab, .... }
{a, b, aa, ab, ba, bb, aaa, aab, ...}
{abab}
L(a*)
L((ab)+)
L((a|b)+)
L((ab)²)
EWS, WS 2015/16, Pfahler
D-5
Struktur regulärer Ausdrücke
1 1 (0 | 1)* 0 0
1
1
zusammenfügen, 5-fach
*
Folge
()
Klammern
|
Alternative
0
1
0
Zeichen
0
In Worten: Jedes Wort aus der Sprache dieses regulären Ausdruckes besteht aus
zwei 1,
gefolgt von beliebig vielen 0 oder 1,
gefolgt von zwei 0.
Alphabet: = {0,1}
EWS, WS 2015/16, Pfahler
D-6
Weitere Beispiele für reguläre Ausdrücke
Name
regulärer Ausdruck A
Worte aus seiner Sprache L(A)
Abc =
(a | b) (c | d | ε)
ac bc ad bd a b
Dig =
sLet =
cLet =
0 | 1 | ... | 9
a | b | ... | z
A | B | ... | Z
7
x
B
Let =
sLet | cLet
m
Bezeichner =
Let ( Let | Dig )*
Maximum
GeldBetrag =
Dig +,Dig 2
23,95 0,50
min3 a
Wenn Namen von regulären Ausdrücken in regulären Ausdrücken verwendet werden, müssen
sie von den Zeichen unterschieden werden können; hier Namen werden kursiv geschrieben.
Schreiben Sie einen regulären Ausdruck für Autokennzeichen, z.B. PB-AX 123
EWS, WS 2015/16, Pfahler
D-7
Beispiele für Definitionen von Grundsymbolen
Pascal_Identifier
= Let (Let | Dig)*
C_Identifier
= ( Let | _) (Let | _ | Dig)*
ADA_Identifier
= Let ( (_ | ε) (Let | Dig) )*
PHP_Var_Identifier
= $ ( Let | _) (Let | _ | Dig)*
Pascal_Real
= (Dig +. Dig +) (((e | E) (+ | -| ε) Dig +) | ) | (Dig +(e | E) (+ | - | ε) Dig +)
HexDig
= Dig | a | b | c | d | e | f | A | B | C | D | E | F
Versuchen Sie Beispiel-Worte zu bilden und die Form der definierten Grundsymbole in Worten
zu erklären.
EWS, WS 2015/16, Pfahler
D-8
Reguläre Ausdrücke als Textmuster
Reguläre Ausdrücke werden auch benutzt um Muster zu definieren, die in Texten erkannt
werden sollen.
Beispiele:
●
suche alle Dateinamen der Form ews(0|1|2|3|4|5|6|7|8|9)³.html
in der Schreibweise von Unix-sh:
ls ews[09][09][09].html
●
Aufruf der PHP-Funktion preg_match sucht ein Textmuster in einer Zeichenreihe
$absatz = "Dass er das so schnell versteht!";
if (preg_match ("/(d|D)ass/", $absatz)) {
echo "gefunden";
}
Die Schreibweise für reguläre Ausdrücke kann je nach konkreter Anwendung oder Sprache
eventuell leicht unterschiedlich sein.
EWS, WS 2015/16, Pfahler
D-9
Notation regulärer Ausdrücke in PHP
a
FG
F|G
(F)
F?
F+
F*
F{m,n}
F{m}
[abc]
[^abc]
[a-zA-Z]
.
das Zeichen a
Zusammenfügen von 2 Worten
Alternativen
Klammerung
Optionales F
nicht-leere Folge von Worten aus L(F)
beliebig lange Folge von Worten aus L(F)
Folge mit mindestens m und höchstens n von Worten aus L(F)
Folge mit genau m Worten aus L(F)
alternativ ein Zeichen aus der Klammer
alternativ ein anderes Zeichen als die in der Klammer
alternativ ein Zeichen aus Zeichenbereichen
beliebiges Zeichen
Anfang der Zeichenfolge (nichts darf vorangehen)
Ende der Zeichenfolge (nichts darf darauf folgen)
^
$
Beispiele: [^#]*
[0-9]{1,4}
beliebige Folgen, die # nicht enthalten
{0, 1, .... 01, 02, .... 001, 002, .... 0001, 0002, ....}
EWS, WS 2015/16, Pfahler
D-10
Beispiele regulärer Ausdrücke in PHP
Reguläre Ausdrücke kommen in PHP-Programmen immer als Zeichenreihenliterale (Strings) vor.
Sie werden durch / begrenzt und in " oder ' eingeschlossen, z. B. "/(1|0)/".
Statt Namen für reguläre Ausdrücke zu definieren, weisen wir die Zeichenreihe einer Variablen
zu, z. B.
$odig = "(0|1|2|3|4|5|6|7)";
$res = preg_match("/$odig{3}/", $line);
Variable
regulärer Ausdruck als PHP-String
$Abc =
"/(a|b)(c|d)?/";
$Anrede =
"/Sehr geehrte(r)? (Frau|Herr)/";
$Bezeichner =
"/[azAZ][azAZ09]*/";
$P_Exp
"/((e|E)(\+|)?[09]+)/";
=
$Pascal_Real = "/(([09]+\.[09]+)$P_Exp?)|([09]+$P_Exp)/";
EWS, WS 2015/16, Pfahler
D-11

Download Report