GDI Tutorium Formale Grammatiken - lukas
Transcrição
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.