Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
56
ROZDZIAŁ2.PROSTYTRANSLATORSTEROWANYSKŁADNIĄ
2.2.7.Ćwiczeniadopodrozdziału2.2
Ćwiczenie2.2.1:Rozważmygramatykębezkontekstową
S
→SS+|SS*|a
(a)Pokaż,jakwygenerowaćciągaa+a∗ztejgramatyki.
(b)Skonstruujdrzeworozbiorudlategociągu.
(c)Jakijęzykgenerujetagramatyka?Odpowiedźuzasadnij.
Ćwiczenie2.2.2:
Jakijęzykjestgenerowanyprzezponiższegramatyki?
Uzasadnijodpowiedźwkażdymprzypadku.
(a)S→0S1|01
(b)S→+SS|-SS|a
(c)S→S(S)S|ć
(d)S
→aSbS|bSaS|ć
(e)S→a|S+S|SS|S*|(S)
Ćwiczenie2.2.3:Którezgramatykwćwiczeniu2.2.2sąniejednoznaczne?
Ćwiczenie2.2.4:
Skonstruujjednoznaczną,bezkontekstowągramatykędla
każdegozponiższychjęzyków.Wkażdymprzypadkuwykaż,żeproponowana
gramatykajestpoprawna.
1.
Wyrażeniaarytmetycznewnotacjipostfiksowej(odwrotnejnotacjipol-
skiej).
2.Lewostronniełącznelistyidentyfikatorówrozdzielanychprzecinkami.
3.Prawostronniełącznelistyidentyfikatorówrozdzielanychprzecinkami.
4.
Wyrażeniaarytmetycznedlaliczbcałkowitychiidentyfikatorówzczterema
operatoramidwuargumentowymi+,-,∗,/.
!e)
Dołączjednoargumentowyplusiminusdooperatorówarytmetycznych
zpunktu(d).
Ćwiczenie2.2.5:
(a)
Wykaż,żewszystkieciągidwójkowegenerowaneprzez
poniższągramatykęmająwartościpodzielneprzez3.Wskazówka:użyj
indukcjipoliczbiewęzłówwdrzewierozbioru.
num→11|1001|num0|numnum
(b)
Czytagramatykagenerujewszystkieciągidwójkowe,którychwartośćjest
podzielnaprzez3?
Ćwiczenie2.2.6:
Skonstruujbezkontekstowągramatykędogenerowaniarzym-
skichcyfr.
