GDI Tutorium Formale Grammatiken - lukas

GDI Tutorium
Formale Grammatiken
5. Dez 2011, [email protected]
Begriffe
Det
Ent
erm
inis
mus
Zustand
on
rakti
t
s
b
A
Algor
ithmis
ches D
enken
Endl
sch
eid
bar
kei
t
t
toma
u
A
r
iche
Newsgroup-Diskussionen
– Passwortlänge
– RegEx Engine
Informatiker
–
–
–
–
–
Alan Turing
Stephen Cook
Noam Chomsky
Niklaus Wirth
Donald E. Knuth
Konzepte
–
–
–
–
Was ist eine Turingmaschine?
Wieso brauchen wir die Aussagenlogik?
Was ist das Halteproblem?
Was bedeutet Mächtigkeit einer Sprache?
→ heute unser Thema
Wie mächtig soll (m)eine Sprache sein?
C
TeX
PHP
Java
SGML/XML
POSIX RegEx
kontextfrei
rekursiv aufzählbar
rekursiv aufzählbar
kontextfrei
kontextfrei
regulär
a
a
{a}
a+
a+
{a, aa, aaa, ...}
Was hat sich an der Sprache verändert?
a
a
s
s
vs
a
Mächtigkeit nicht, aber Umfang
(Kardinalität der Kleeneschen Hülle)
Was ist RegEx?
Metazeichen: . | ()
Quantifier: ? + *
Was ist RegEx?
Metazeichen: . | ()
Quantifier: ? + *
Erweitert:
^ $ [] {,} [:class:]
... und jede Menge groupmagic
Was ist RegEx?
Metazeichen: . | ()
Quantifier: ? + *
Erweitert:
^ $ [] {,} [:class:]
... und jede Menge groupmagic
Wurde die Sprache mächtiger?
Nein, "(a|b|c)" ist "[abc]". "aaa?" ist "a{2,3}".
Aber die Sprache wurde ausdrucksstärker (weniger Zeichen!)
Was ist RegEx?
Metazeichen: . | ()
Quantifier: ? + *
Erweitert:
^ $ [] {,} [:class:]
... und jede Menge groupmagic
Wurde die Sprache mächtiger?
Nein, "(a|b|c)" ist "[abc]". "aaa?" ist "a{2,3}".
Aber die Sprache wurde ausdrucksstärker (weniger Zeichen!)
Ass2
python
C
#include <stdio.h>
#include <stdlib.h>
#define BUFFER_BLOCKSIZE 512
#define WORDLIST_BLOCKSIZE 50
#define SUCCESS 0
#define ERROR_NO_INPUT -1
#define ERROR_NO_WORDS -2
#define ERROR_OUT_OF_MEMORY -3
#define TRUE 1
#define FALSE 0
int memcopy(char *destination, char *source, unsigned size){unsigned
mem_iterator;for(mem_iterator=0; mem_iterator<size;mem_iterator++)
{destination[mem_iterator]=source[mem_iterator];}return SUCCESS;}int
appendString(char **input,char *buffer, unsigned int input_offset,unsigned
buffer_size){int status=SUCCESS;char *tmp_ptr;if ((*input) == NULL){tmp_ptr
=malloc((input_offset+buffer_size+1)*sizeof(char));}else{tmp_ptr=realloc
(*input,(input_offset+buffer_size+1)*sizeof(char));}if(tmp_ptr==NULL){status
=ERROR_OUT_OF_MEMORY;}else{(*input)=tmp_ptr;status=memcopy
(&(*input)[input_offset], buffer, buffer_size);(*input)[input_offset+
buffer_size]='\0';}return status;}
import sys, re
terms = []
for term in re.split('[\n .,]', sys.stdin.read()):
if term:
terms.append(term)
terms.reverse()
print('\n'.join(terms))
... und viel mehr
python
C
kontextfrei
ausdrucksstärker
begrenzt
kontextfrei
ausdrucksschwächer
umfangreicher
Begriffe
Umfang
Ausdrucksstärke
Mächtigkeit
Begriffe
Umfang
Ausdrucksstärke
Mächtigkeit
Kombinatorik
subjektiv
m
Begriffe
Re
gu
lä
r?
Mächtigkeit
m
te
n
o
K
?
i
e
r
xtf
Wozu RegEx?
– Haben scheinbar was mit
Programmiersprachen zu tun?!
– Fuzzy Pattern Matching!
if (var = 1) {
call();
}
if(var = 1) {
call();
}
if[\t\n ]*
if(var = 1) {
call();
}
Lexing with RegEx
(var = 1) {
call();
}
\(.*\)
?
Lexing with RegEx
(var = )1) {
call();
}
\(.*\)
Lexing with RegEx
Lexing with RegEx?
– Nicht alle Ausdrücke lassen sich
mit Regexi formulieren!
– RegEx ist nicht mächtig genug.
– C ist kontextfrei. RegEx ist regulär.
– Ausdrücke wie "wenn es mit Symbol
X beginnt, muss es mit Y beendet werden"
können nicht formuliert werden.
Kontextfreie Sprachen
Lightweight XML
S → TS | N | ε
T → <N>S</N>
N → aN|bN|cN|dN|eN|ε
Kontextfreie Sprachen
Lightweight XML
S → TS | N | ε
T → <N>S</N>
N → aN|bN|cN|dN|eN|ε
<a>b</a>
<a><b></b></a>
<e></e><a></a>
Kontextfreie Sprachen
Lightweight XML
Aber der tagname muss nicht
ident sein?
Stimmt, aber lässt sich in CFL
auch formulieren. Aber macht
den Ausdruck wesentlich länger.
Für CFL gibt es geeignetere
Notationen.
Kontextfreie Sprachen
Lightweight XML
Backus Naur Form
– Extended BNF
Wirth Syntax Notation
Definite Clause Grammar
Kontextfreie Sprachen
Lightweight XML
EBNF
<block> ::= "{" {<expr>} "}"
Mächtigkeit von Sprachen
= Grammatik
CFL können etwas, was RegEx nicht kann.
Kontext-sensitive Sprachen sind noch
mächtiger.
Auch andere Nonterminale
links erlaubt! :)
Turingmaschinen können "alles" lesen.
marvin10 :)
Mächtigkeit von Sprachen
Chomsky-Hierarchie
0
1
2
3
Rekursiv aufzählbar
Kontext-sensitiv
Kontext-frei
Regulär
Mächtigkeit von Sprachen
Wieso unterscheiden? Einfach nur Turingmaschinen?
– Rechenaufwand
– Komplexität des Interpreters
– Mächtigkeit der Sprache erkennbar
DSL: Binäroperationen
Wieso unterscheiden? Regex reicht.
[01]+[\||&|ꕕ][01]+
bo = new BinaryOperation("010&011");
System.out.println(bo.binstr());
Typesetting
Wieso unterscheiden? Turingmaschine reicht.
\newcommand{\gdi}{\emph{GDI}}
Foobar.
\gdi
\catcode 46 0
.gdi
Zusammenfassung
Wir unterscheiden 4 Mächtigkeiten.
Wir definieren Sprachen.
Sprachen sind entscheidbar.
Theoretische Informatik.
az+1b3xyaz-1
RegEx
☐
CFL
☑
AufgabeDrei
Deadline 8. Dez 23:59
AGs vermutlich Mi & Do.
Letzte Fragestunde heute.
Danke
Evaluation via TUGOnline
Danke für eure Mitarbeit.
Viel Glück noch.