Egenskaber ved kontekstfri sprog [Martin, kap. 4.3-4.5, 6.1-6.3]
R -> C '+' R | C C -> S C | S S -> S '*' | P P -> a | b | c | ... | '(' R ')'Start-nonterminalen er R. Terminalsymboler er angivet med '...', og "a | b | c | ..." indeholder hvert symbol i det anvendte alfabet, som vi antager er givet på forhånd. Vi vil ikke gennemgå selve parseren her - det hører under kurset "Oversættelse" (dOvs).
Her er en anden grammatik G':
R -> R '+' R | R R | R '*' | a | b | c | ... | '(' R ')'
I denne opgave vil vi se hvordan regulære sprog kan bruges som abstraktioner af programmer skrevet i et simpelt programmeringssprog. Fra sådanne abstraktioner kan vi analysere visse aspekter af opførslen af programmerne.
Vi betragter et simpelt imperativt programmeringssprog, hvis syntax er beskrevet af følgende kontekstfri grammatik:
A | V | N | ( A + A ) | (A - A ) | ( A * A ) | |
B | true | false | ( A = A ) | ( A > A ) | ( B and B ) | ( B or B ) | ( not B ) | |
S | skip | V := A | ( S ; S ) | if B then S else S | while B do S | read( V ) | print( A ) |
V er en endelig mængde af variabelnavne, og N er en endelig mængde af heltal. (De præcise valg af disse mængder vil afhænge af de programmer, vi vil skrive.) Nonterminalen A repræsenterer aritmetiske udtryk, B repræsenterer booleske udtryk, og S repræsenterer "statements". Vi opfatter et program som en "statement", så S er start-nonterminal. Et program er således en streng, der kan deriveres af denne grammatik, startende fra S. Semantiken for programmeringssproget er som forventet. Operationen read(x) indlæser et heltal fra tastaturet og skriver det til x, mens print(A) udskriver værdien af A. Bemærk at grammatikken er utvetydig, idet der altid er parenteser om sammensamme udtryk.
Eksempel: Følgende program
read(n);(m:=1;(while n>0 do (m:=(m*n);n:=(n-1)));print(m))
udskriver n! (=1*2*...*n), under forudsætning af, at der indtastes et positivt heltal.
Givet et program s og en variabel x vil vi udtrække et regulært udtryk Sx(s) (over alfabetet ={r,w}), som viser hvordan programmet læser fra og skriver til x. En aflæsning svarer til et "r", og en tildeling svarer til et "w". Det regulære udtryk er defineret rekursivt i strukturen af s:
Ax(x) = r
Ax(V) = for Vx
Ax(N) =
Ax(( A1 + A2 )) = Ax(A1)Ax(A2)
Ax(( A1 - A2 )) = Ax(A1)Ax(A2)
Ax(( A1 * A2 )) = Ax(A1)Ax(A2)
Bx(true) =
Bx(false) =
Bx(( A1 = A2 )) = Ax(A1)Ax(A2)
Bx(( A1 > A2 )) = Ax(A1)Ax(A2)
Bx(( B1 and B2 )) = Bx(B1)Bx(B2)
Bx(( B1 or B2 )) = Bx(B1)Bx(B2)
Bx(( not B )) = Bx(B)
Sx(skip) =
Sx(x := A) = Ax(A)w
Sx(V := A) = Ax(A) for Vx
Sx(( S1 ; S2 )) = Sx(S1)Sx(S2)
Sx(if B then S1 else S2) = Bx(B)(Sx(S1)+Sx(S2))
Sx(while B do S) = Bx(B)(Sx(S)Bx(B))*
Sx(read( x )) = w
Sx(read( V )) = for Vx
Sx(print( A )) = Ax(A)
Eksempel: Hvis s er fakultetsprogrammet ovenfor, så er Sm(s)=w(rw)*r og Sn(s)=wr(rrwr)*.
Opgave 1: Hvad er Sx(x:=2;(if (x<y) then x:=(x*y) else y:=(y-1));z:=x) og Sx(if true then x:=y else y:=x) ?
Visse egenskaber ved programmer kan formaliseres ved hjælp af regulære udtryk. For eksempel, L(Sx(s))L(r*) er sand hvis og kun hvis der ikke er tildelinger til x i s.
Opgave 2: Argumentér for følgende:
Opgave 3: Skriv et regulært udtryk r så L(Sx(s))L(r) betyder at variablen x altid er initialiseret inden der læses fra den i s. (Dvs. når x aflæses i s, så ved vi, at der inden har været en tildeling til x.)
Opgave 4: Argumentér for at der findes en algoritme, der afgør følgende: x: L(Sx(s))L(r), givet et program s og et regulært udtryk r (hvor r beskriver en eller anden interessant egenskab ved programmer).
Kombineret med løsningen i opg. 3 har vi nu en programanalyse, der kan undersøge et givet program for om der er risiko for at uinitialiserede variable bliver aflæst, hvilket er en kilde til programmeringsfejl. En lignende analyse finder sted i Java-programmer, inden de får lov at køre.
Opgave 5: Skriv et program s sådan at hvis algoritmen fra opg. 4 anvendes på s hvor r vælges som det regulære udtryk fra opg. 3, så er resultatet forkert - i den forstand at algoritmen rapporterer at en uinitialiseret variabel måske bliver aflæst når s kører, selvom dette ikke er muligt.
Den sidste opgave viser hvordan programanalyser kan være konservative. Hvis de rapporterer "nej, der er ingen problemer", så kan vi være sikre på at dette er tilfældet, men hvis de rapporterer "ja, der er et problem", så kan det være forkert. Denne situation kan desværre ikke undgås, idet vores lille programmeringssprog er Turing-komplet, hvilket betyder, at dets udtrykskraft er lige så stor som Turingmaskiners, og for sådanne maskiner er problemet "givet et program s, er det muligt at det, mens det kører, aflæser en uinitialiseret variabel?" uafgørligt, hvilket vil blive bevist på kurset Beregnelighed og logik.
Argumentér for at ethvert regulært sprog også er kontekstfrit. (Vi har set 2 forskellige beviser for dette!)
Beskriv lukkethedsegenskaber for klassen af kontekstfri sprog.
Repetér beviset for pumping-lemmaet (for kontekstfri sprog). Argumentér med udgangspunkt i tegningen af en "lang" streng, der deriveres af en CFG på CNF (slide 23).
Martin 6.2 (a) (s.220)
Husk at forklare grundigt hvordan du bruger pumping-lemmaet [Martin, Theorem 6.1].
Dette er sidste obligatoriske opgave. Aftal afleveringsfristen med din instruktor, så der bliver tid til feedback inden eksamen.