From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- Semestr 2/racket/egzamin/zad3.rkt | 347 -------------------------------------- 1 file changed, 347 deletions(-) delete mode 100644 Semestr 2/racket/egzamin/zad3.rkt (limited to 'Semestr 2/racket/egzamin/zad3.rkt') diff --git a/Semestr 2/racket/egzamin/zad3.rkt b/Semestr 2/racket/egzamin/zad3.rkt deleted file mode 100644 index 9bfed02..0000000 --- a/Semestr 2/racket/egzamin/zad3.rkt +++ /dev/null @@ -1,347 +0,0 @@ -#lang racket - -;; Oświadczam, że rozwiązanie zadania egzaminacyjnego przygotowałem -;; w pełni samodzielnie, korzystając wyłącznie z materiałów do wykładu, -;; notatek, podręcznika, oraz materiałów zacytowanych w treści rozwiązania. -;; Oświadczam że nie korzystałem w żadnej formie z pomocy osób trzecich -;; w przygotowaniu rozwiązania ani też takiej pomocy nie udzielałem -;; i nie udostępniałem nikomu swojego rozwiązania. - -;; ZADANIE 3 -;; ========= - -;; Z gramatykami bezkontekstowymi spotkaliście się już na Wstępie do -;; Informatyki. W tym zadaniu potraktujemy je jako dane dla naszych -;; programów. - -;; Przypomnijmy, że gramatyka bezkontekstowa składa się z -;; · skończonego zbioru *symboli nieterminalnych* -;; · skończonego zbioru *symboli terminalnych* -;; · wybranego nieterminalnego symbolu startowego -;; · zbioru *produkcji*, czyli par symbol nieterminalny - lista -;; (potencjalnie pusta) symboli terminalnych lub nieterminalnych - -;; Słowo (ciąg symboli terminalnych) możemy wyprowadzić z gramatyki, -;; jeśli możemy zacząć od ciągu składającego się z symbolu startowego -;; możemy użyć skończonej liczby produkcji z gramatyki przepisując -;; symbol nieterminalny na ciąg symboli mu odpowiadających (w danej -;; produkcji). - - -;; Przykład: poprawne nawiasowania - -;; Gramatyka składa się z jednego symbolu nieterminalnego, S (który -;; jest oczywiście symbolem startowym) i dwóch symboli terminalnych -;; "(" i ")", i zawiera następujące produkcje (zwyczajowo zapisywane -;; przy użyciu strzałki; zwróćcie uwagę że pierwszy ciąg jest pusty!): -;; S -> -;; S -> SS -;; S -> (S) - -;; W często spotykanej, bardziej zwięzłej, postaci BNF moglibyśmy tę -;; gramatykę zapisać tak (dbając trochę bardziej o wizualne -;; oddzielenie symboli terminalnych i nieterminalnych): -;; S ::= "" | SS | "(" S ")" -;; Mamy tu te same produkcje, ale tylko raz zapisujemy każdą z -;; powtarzających się lewych stron. - -;; Z gramatyki tej da się wyprowadzić wszystkie poprawnie rozstawione -;; ciągi nawiasów — zobaczmy jak wyprowadzić (na jeden ze sposobów) -;; ciąg "(()())". Zaczynamy, jak zawsze, od słowa złożonego z symbolu -;; startowego i przepisujemy: -;; S -> (S) -> (SS) -> ((S)S) -> ((S)(S)) -> (()(S)) -> (()()) - - -;; Zadanie cz. 1 - -;; Zdefiniuj reprezentację gramatyki jako typu danych w -;; Rackecie. Warto zastanowić się co można uprościć względem definicji -;; matematycznej — w szczególności możemy założyć że dowolne napisy -;; (typu string) są ciągami symboli terminalnych, i że nie musimy -;; podawać jawnie zbioru nieterminali; również reprezentacja produkcji -;; gramatyki jako worka z parami wejście-wyjście niekoniecznie jest -;; najwygodniejsza. - -;; Uwaga: w tym zadaniu nie wymagamy definiowania składni konkretnej i -;; parsowania, ale bardzo polecamy wybranie jakiejś formy, żeby móc -;; sensownie przetestować swoje rozwiązanie! - - -;; "Optymalizacja" gramatyk - -;; Gramatyki, podobnie jak programy, piszą ludzie — może więc zdarzyć -;; się że znajdą się tam śmieci. Mogą one mieć dwojaką formę: symboli -;; nieterminalnych, których nie da się wyprowadzić z symbolu -;; startowego, lub symboli nieterminalnych z których nie da się -;; wyprowadzić żadnego słowa terminalnego (tj. niezawierającego -;; symboli nieterminalnych). Przykładowo, do naszej gramatyki -;; moglibyśmy dodać symbole P i Q, i produkcje: -;; S -> ")(" P -;; P -> PP "qed" -;; Q -> "abc" - -;; Mimo że nasza gramatyka wygląda inaczej na pierwszy rzut oka, tak -;; naprawdę się nie zmieniła: do symbolu Q nie możemy dojść z symbolu -;; S, a więc "abc" nigdy nie wystąpi w słowie wyprowadzalnym z -;; gramatyki. Analogicznie, z P nie da się wyprowadzić żadnego słowa, -;; które nie zawierałoby symbolu P — a zatem żadnego słowa złożonego -;; tylko z symboli terminalnych. To znaczy, że naszą gramatykę możemy -;; uprościć wyrzucając z niej symbole nieterminalne (i produkcje które -;; ich używają) do których nie da się dojść (tj. są *nieosiągalne*) i -;; te, z których nie da się ułożyć słowa terminalnego (tj. są -;; *nieproduktywne*). Jeśli z naszej rozszerzonej gramatyki wyrzucimy -;; takie symbole, dostaniemy oczywiście gramatykę początkową. - - -;; Zadanie cz. 2 - -;; Dla swojej reprezentacji gramatyki z poprzedniej części zadania -;; napisz dwie procedury: cfg-unreachable, znajdującą symbole -;; nieterminalne które są nieosiągalne z symbolu startowego, i -;; cfg-unproductive, znajdującą symbole nieterminalne które nie są -;; produktywne. Następnie użyj tych procedur żeby zdefiniować -;; procedurę cfg-optimize, która uprości daną gramatykę usuwając z -;; niej symbole nieosiągalne i nieproduktywne, a także odpowiednie -;; produkcje. - -;; Rozwiązanie wpisz w poniższym pliku, i opatrz komentarzem -;; opisującym wybraną reprezentację (i podjęte przy jej projektowaniu -;; decyzje), a także zaimplementowane w cz. 2. algorytmy. - - - - - - -;; Zadanie 1 - -;; Reprezentacja jest docyś prosta, mianowicie stworzyłem struktury -;; terminal, non-terminal, rule oraz grammar. Dwa pierwsze to -;; po prostu jednoelementowe struktury utrzymujące nazwę symboli. -;; grammar to dwuelementowa struktura, jej pierwszym elementem -;; jest symbol startowy, a następnym produkcja, czyli lista reguł (listof rule), -;; a reguły to dwuelementowe struktury (symbol niterminalny - lista nonterminali lub termianli). -;; Generalnie dzięki temu, że mam te struktury terminal oraz non-terminal -;; to symbol nieterminalne i temrinalne mogą być czykolwiek. Dodatkowo -;; dla uproszczenia w miejscach, gdzie mam pewność że chodzi mi o -;; symbol nieterminalny, to nie opakowuję go w strukturę. -;; Przykładowo rules w gramatyce może wyglądać tak: -;; (list -;; (rule 'S (list (terminal ""))) -;; (rule 'S (list (non-terminal 'S) (non-terminal 'S))) -;; (rule 'S (list (terminal "(") (non-terminal 'S) (terminal ")")))) -;; Oczywiście symbol nieterminalny nie musi być racketowym symbolem, może być czymkolwiek. -;; Podobnie z symbolami terminalnymi. Proszę również zauważyć, że dzięki -;; strukturom non-terminal oraz terminal te same racketowe obiekty mogą być jednocześnie -;; terminalami oraz nieterminalami! -;; W tych parach na pierwszym miejscu nie jest non-terminal, tylko po prostu cokolwiek -;; no i oczywiście mam wtedy pewność że musi być to non-terminal, nie ma potrzeby -;; żeby pakować go również w tę strukturę. - - -;; Postanowiłem napisać parser (make-cfg q), generuje on gramatyki w bardzo konkretny sposób, -;; trochę ograniczo to czym mogą być symbole nieterminalne oraz terminalne, -;; ale nie wydaje mi się że i tak składnia jest bardzo wygodna i mało ograniczająca. - -;; Składnia konkretna naszych gramatyk wygląda bardzo podobnie do zapisu -;; przedstawionego w treści zadania. -;; np. gramatyka nawiasowania będzie wyglądać następująco: -;; '(grammar S (S ::= "" -- SS -- "(" S ")")) -;; ale mogłaby wyglądać też tak: -;; '(grammar S (S ::= "") (S ::= SS -- "(" S ")")) -;; a np. ta nieciekawa gramatyka przedstawiona w treści zadania: -;; '(grammar S (S ::= "] [" P) (P ::= PP "qed") (Q ::= "abc")) -;; Zatem będzie to lista, która na pierwszym miejscu ma symbol 'grammar -;; na drugim miejscu ma symbol startowy -;; następnie następuje lista produkcji w formacie: -;; ::= -;; Zalety: -;; - rozróżnienie w składni konkretnej symboli nieterminalnych i terminalnych -;; przez użycie symboli i stringów pozwala na to, aby symbole terminalne nazywały się tak -;; jak terminalne, tj. "S" nie jest tym samym co 'S. -;; - składnia wydaje się bardzo wygodna w użyciu, nie ma też problemu, żeby później dopisać -;; dodatkowe reguły dla jakiegoś nieterminala, -;; - parser jest całkiem łatwy w implementacji -;; Wady: -;; - symbole nieterminalne mogą składać się jedynie z jednego symbolu, zatem nie możemy robić ich -;; zbyt wiele. Jest tak dlatego, że np. tutaj (S ::= SS) nie chodzi mi o symbol SS, tylko -;; o sąsiadujące symbole SS (jednak gdyby nie używać parsera to normalnie moglibyśmy -;; mieć wieloznakowe symbole nieterminalne!). - -;; Dla przykładu taka gramatyka: -;; '(grammar S (S ::= "" -- SS -- "(" S ")" -- Q) (Q ::= "" -- QS -- "[" Q "]")) -;; będzie reprezentowana następująco: -;; (grammar -;; 'S -;; (list -;; (rule 'S (list (terminal ""))) -;; (rule 'S (list (non-terminal 'S) (non-terminal 'S))) -;; (rule 'S (list (terminal "(") (non-terminal 'S) (terminal ")"))) -;; (rule 'S (list (non-terminal 'Q))) -;; (rule 'Q (list (terminal ""))) -;; (rule 'Q (list (non-terminal 'Q) (non-terminal 'S))) -;; (rule 'Q (list (terminal "[") (non-terminal 'Q) (terminal "]"))))) - -;; Cała reprezentacja :D -(struct non-terminal (sym) #:transparent) -(struct terminal (sym) #:transparent) -(struct rule (nt xs) #:transparent) -(struct grammar (start rules) #:transparent) - - -;; PARSER -(define SEPARATOR '--) - -(define (split-at-symb symb xs) - (define (iter left right) - (cond - [(null? right) (cons left null)] - [(eq? symb (car right)) (cons left (cdr right))] - [else (iter (cons (car right) left) (cdr right))])) - (let ([res (iter null xs)]) - (cons (reverse (car res)) (cdr res)))) - -(define (split-by-separator xs) - (let ([res (split-at-symb SEPARATOR xs)]) - (if (null? (cdr res)) - res - (cons (car res) (split-by-separator (cdr res)))))) - -;; PARSER SKŁADNI KONKRETNEJ DO JEJ REPREZENTACJI -(define (make-cfg q) - (cond - [(and (list? q) (eq? 'grammar (first q))) - (grammar (second q) (append-map make-cfg (cddr q)))] - [(and (list? q) (eq? '::= (second q))) - (let ([nt (first q)] - [rules (split-by-separator (cddr q))]) - (map (lambda (x) (rule nt x)) (map make-prod rules)))])) - -(define (symbol->list s) - (map string->symbol - (map string - (string->list (symbol->string s))))) - -(define (make-prod xs) - (cond - [(null? xs) null] - [(string? (car xs)) (cons (terminal (car xs)) (make-prod (cdr xs)))] - [(symbol? (car xs)) (append (map non-terminal (symbol->list (car xs))) (make-prod (cdr xs)))] - [else (error "Invalid syntax in production" xs)])) - - -(define sample '(S ::= "" -- SS -- "(" S ")")) -(define sample2 '(grammar S (S ::= "" -- SS -- "(" S ")" -- Q) (Q ::= "" -- QQ -- "[" Q "]"))) -(define sample3 '(grammar S - (S ::= A B -- D E) - (A ::= "a") - (B ::= "b" C) - (C ::= "c") - (D ::= "d" F) - (E ::= "e") - (F ::= "f" D))) - -(define (sample-grammar) (make-cfg sample3)) - -;; zadanie 2 - -;; korzystam z algorytmów przedstawionych w tej książce: -;; https://bit.ly/3ev0NUA, konkretnie te ze stron 50-51 -;; Pozwoliłem sobie trochę zmienić przeznaczenie funkcji cfg-unreachable oraz cfg-unproductive -;; Zamiast zwracać nieproduktywne nieterminale, zwracają właśnie produktywne -;; i analogicznie w tym drugim. Po prostu taka implementacja jest dla mnie wygodniejsza, -;; a jest bardzo nieistotną zmianą koncepcyjną. -;; Stąd zmiana nazwy na cfg-productive oraz cfg-reachable - -;; cfg-productive działa w ten sposób: -;; Jakiś nieterminal nazywamy produktywnym, jeśli ma co najmniej jedną produktywną zasadę -;; Jakąś regułę nazywamy produktywną, jeśli składa się z terminali lub produktywnych nieterminali -;; Jasno widać, że wg tej definicji te nieterminale, które nie są produktywne, są nieproduktywne -;; wg definicji zadania, a cała reszta jest produktwna. - -;; Algorytm znajdowania produktywnych nieterminali: -;; Mamy listę produktywnych nieterminali P, początkowo pustą -;; 1. Stwórz nową listę P' -;; 2. Przejdź po liście reguł -;; -> jeśli dana reguła jest produktywna (wg P), dodaj jej nieterminal do P' -;; 3. Jeśli P != P', zrób P := P' i wróć do 1. -;; 4. Zwróć P - -;; Fajne w tym algorytmie jest to, że jeśli mamy jakiś nieterminal, którego -;; używamy w jakiejś regule, ale ten nieterminal nie ma zdefiniowanej żadnej reguły, -;; to nie zostanie oznaczony jako produktywny, co jest dla nas korzystne. - -;; Algorytm znajdowania osiągalnych nieterminali: -;; Traktujemy nitereminale jak wierzchołki w grafie a reguły jako listy sąsiedztwa. -;; Terminale są liśćmi, a nieterminale węzłami. Robimy po prostu DFSa z nieterminala -;; startowego i węzły do których dotrzemy oznaczamy jako osiągalne. - -;; Wg papierka który tutaj podałem, jeśli najpierw usuniemy nieproduktywne nieterminale, -;; a w następnej kolejności nieosiągalne, to nasza gramatyka stanie się regularna. -;; Wydaje się to w miarę sensowne -- pierszy algorytm to takie odcinanie liści i odcyklanie -;; grafu, a ten drugi to po prostu DFS. - -;; przydatne predykaty -- na productive-nt mam listę symboli niterminalnych -;; (nie struktury non-terminal, tylko te symbole!) -;; które wiem że są produktywne. -;; productive? sprawdza, czy nietermial jest produktywny -;; to drugie sprawdza czy reguła jest produktywna -;; (czyli czy składa się z produktywnych nonterminali lub terminali) -(define (productive? p productive-nt) - (or (terminal? p) (member (non-terminal-sym p) productive-nt))) -(define (rule-productive? r productive-nt) - (andmap (lambda (x) (productive? x productive-nt)) r)) - -;; zwraca listę produktywnych symboli (nie nonterminali!) -(define (cfg-productive g) - (define (find-productive-nt productive-nt rules) - (cond - [(null? rules) (remove-duplicates productive-nt)] - [(rule-productive? (rule-xs (car rules)) productive-nt) - (find-productive-nt (cons (rule-nt (car rules)) productive-nt) (cdr rules))] - [else (find-productive-nt productive-nt (cdr rules))])) - (define (iter productive-nt) - (let ([new-prod-nt (find-productive-nt productive-nt (grammar-rules g))]) - (if (equal? productive-nt new-prod-nt) - productive-nt - (iter new-prod-nt)))) - (iter null)) - -;; zwraca listę osiągalnych symboli -(define (cfg-reachable g) - (define (iter verts vis) - (cond - [(null? verts) vis] - [(member (car verts) vis) (iter (cdr verts) vis)] - [else (iter (cdr verts) (dfs (car verts) vis))])) - (define (dfs v vis) - (let* ([rules (filter (lambda (r) (eq? (rule-nt r) v)) (grammar-rules g))] - [verts (append-map (lambda (r) (rule-xs r)) rules)] - [verts (filter non-terminal? verts)] - [verts (map non-terminal-sym verts)]) - (iter verts (cons v vis)))) - (dfs (grammar-start g) null)) - - -;; robi z gramatyki g gramatykę regularną -(define (cfg-optimize g) - (let* ([productive-nt (cfg-productive g)] - [productive-rules (filter (lambda (r) - (rule-productive? (rule-xs r) productive-nt)) - (grammar-rules g))] - [new-g (grammar (grammar-start g) productive-rules)] ; <----- nowa gramatyka, bez nieproduktywnych - [reachable-nt (cfg-reachable new-g)] ; reguł i symboli nieterminalnych - [res-g (grammar (grammar-start new-g) (filter ; <----- dobra gramatyka - (lambda (r) (member (rule-nt r) reachable-nt)) - (grammar-rules new-g)))]) - res-g)) - -(define (test) (cfg-optimize (make-cfg sample3))) - -;; Pokazanie że symbole nie muszą być racketowymi symbolami :) -(define (test2) (cfg-optimize - (grammar '() - (list (cons '() (list (terminal '()))) - (cons '() (list (terminal "(") (non-terminal '()) (terminal ")"))) - (cons '() (list (non-terminal '()) (non-terminal '()))))))) - \ No newline at end of file -- cgit v1.2.3