aboutsummaryrefslogtreecommitdiff
path: root/Semestr 2/racket/egzamin/zad3.rkt
blob: 9bfed020e0fe62d5eb1219e549b65174386c6f2d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
#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:
;; <non-terminal> ::= <lista produkcji, produkcje oddzielone są separatorem -->
;; 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 '())))))))