Samenvatting hoorcolleges Vertalerbouw J.H. Jongejan 7 juni 2010
LaTeX van Hedde Bosman en Jan Jongejan.
1
Inhoudsopgave 1 Voorbeeld van een vertaling 1.1 Brontaal (source language) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Doeltaal (object- of target-language) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3
2 Fasen in een vertaler 2.1 Symbol Table . . . . . 2.2 Scanner . . . . . . . . 2.3 Parser . . . . . . . . . 2.4 Semantische analyse . 2.5 Genereratie tussencode 2.6 Code optimalisatie . . 2.7 Code generatie . . . . 2.8 Assembly . . . . . . .
. . . . . . . .
3 4 4 4 4 5 6 6 6
. . . .
6 7 8 8 8
4 De structuur van een Reguliere Expressie 4.1 Berekening van functiewaarden in de knopen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Constructie accepterend programma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9 9 10
5 Grammatica’s 5.1 Constructie van een equivalente gereduceerde grammatica . . . . . . . . . . . . . . . . . . . . .
11 11
6 Stapelautomaten
11
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
3 Talen en Automaten in het kort 3.1 Reguliere expressies . . . . . . . . . . . . 3.1.1 Lemma van Arden . . . . . . . . . 3.1.2 Omzetting reguliere grammatica in 3.2 Automaten . . . . . . . . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . RE . . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
7 Implementatie van een topdown parser 7.1 Topdown parser met expliciete stapel . . . . . . . . . . . . . . . . 7.2 Implementatie recursive descent parser (zonder error recovery) . 7.3 Recursive descent parser met errorrecovery . . . . . . . . . . . . 7.3.1 Hulpprocedures . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Foutafhandeling tijdens semantische analyse (geen tentamenstof)
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . .
13 13 14 16 16 17
8 Bottom-up parser 8.1 Het bepalen van de toestanden van de stapelautomaat . . . . . . . . . . . . . . . . . . . . . . . 8.2 Action en Goto table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 LR(1) sets of items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18 18 19 20
9 Attributengrammatica’s (g´ e´ en tentamenstof )
21
10 Code generatie 10.1 Representatie codesegment van een procedure aanroep . 10.1.1 Code segment procedure declaratie . . . . . . . . 10.1.2 Code bij een procedure aanroep . . . . . . . . . . 10.2 Representatie AR van een (procedure) block . . . . . . . 10.2.1 Naamgeving binnen blocks (of hoofdprogramma) 10.2.2 Naamgeving in een programma met procedures . 10.2.3 Geheugengebruik tijdens de activation van r2 . . 10.3 Voorbeeld van gebruik van functies als parameters . . . 10.3.1 Formele procedure parameters . . . . . . . . . . 10.3.2 Geheugengebruik in vb4 . . . . . . . . . . . . . .
2
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . .
. . . . . . . . . .
23 23 24 24 24 24 25 27 27 28 28
1
Voorbeeld van een vertaling
1.1
Brontaal (source language)
{ N ≥0 } x := 0; while (x + 1) * (x + 1) <= N do x:= x + 1; { x2 ≤ N < (x + 1)2 }
1.2
Doeltaal (object- of target-language)
M(x) := 0 lw: R0 := M(x) R0 := R0 + 1 R1 := R0 R1 := R1 * R0 cc := R1 ? N jmpgtr lew M(x) := R0 jmp lw lew:
2
Fasen in een vertaler 6
Bronprogramma
6 ?
frontend
Scanner Analyse
?
Parser ?
Semantische analyse ? 6
?
Generatie tussencode ? 6
?
Code optimalisatie backend
@@ I @ }Z @ Z Z @ Z @ Z @ Z @ R Z yXX X ~ XXX Z X z X
-
9
Synthese
Symbol table
: >
?
Code generatie ?
=
Assembly Doelprogramma ?
?
?
Alle fasen gebruiken een module voor de foutafhandeling. De fasen “Semantische analyse” en “Generatie tussencode” worden gezien als semantische acties.
3
2.1
Symbol Table
De symbol table bevat: string table attribuutwaarden voor elke constante, type, variabele en procedure-identifier
2.2
Scanner
De lexicale analyse. Invoer: Rij characters (letters, leestekens, ...). Beschrijving: Reguliere Expressies (formeel). Uitvoer: • Rij tokens • Evt. foutmeldingen Taken: • Groeperen van deelrijen characters in invoer tot tokens • Signaleren van onjuiste characters • Verwijderen van spaties en commentaar
2.3
Parser
De contextvrije of syntactische analyse. Invoer: Rij tokens Beschrijving: Contextvrije Grammatica (CFG) (formeel). Uitvoer: • Een syntax tree (semantische boom) of een parse tree • Evt. foutmeldingen Taken: • Bepalen van de structuur van de rij tokens (tree) • Controleren van de invoer en signaleren van de fouten
2.4
Semantische analyse
Invoer: Semantische boom of parsetree Beschrijving: of Contextvrije grammatica aangevuld met semantische routines of Attributengrammatica (formeel) of Natuurlijke taal Uitvoer: • (Gewijzigde) Semantische boom • Evt. foutmeldingen Taken: 4
• Verwerken van declaraties • Controleren of gebruikte identifiers gedeclareerd zijn • Controleren of programma type correct is • Identificeren van operatoren • impliciete co¨ercies expliciet maken een programma voorbeeldje (♠ geeft een fout aan): PROGRAM vb; VAR s : SET OF [0 .. 31] ; k,l : integer ; r1,r2 : real ; PROCEDURE p (f1: integer; VAR f2: BEGIN f2 := f1 * f1; END (* p *)
integer)
BEGIN k := m ; // m ♠ s := l ; // l geen set ♠ s := s * [8 .. 15] ; // doorsnede r2 := 2 * r2 ; // coercie 2.0 p(k, 3, l) END (* vb *)
2.5
// 2 params, 3 args ♠
Genereratie tussencode
Invoer: Semantische boom Beschrijving: of Attributen grammatica of Semantische routines Uitvoer: of Tussencode (3-adres instructies) of Register Transfers (zie §1.2) Taak: Omvormen van de semantische boom naar tussencode
5
2.6
Code optimalisatie
Invoer: Tussencode Beschrijving: ... Uitvoer: Tussencode (van dezelfde vorm als de invoer) Taak: Wijzigen van de tussencode zodanig dat het aantal operaties tijdens uitvoering van het vertaalde programma wordt teruggebracht
2.7
Code generatie
Invoer: Tussencode Beschrijving: ... Uitvoer: Rij (pseudo-) machine instructies Taken: • Afbeelden van variabelen op het geheugen van de doelmachine • Kiezen van de instructies (code selection) • Peephole optimalisatie • Register allocatie
2.8
Assembly
Invoer: Rij (pseudo-) machine instructies Beschrijving: ... Uitvoer: Tabellen met machine instructies en overige gegevens voor de linker/loader Taak: Instructies in het gewenste formaat coderen en wegschrijven
3
Talen en Automaten in het kort
Een alfabet T is een niet lege eindige verzameling symbolen. Een rij a1 a2 . . . an van n symbolen ai , 1 ≤ i ≤ n uit een alfabet T wordt een string over het alfabet T genoemd. De lege string, notatie ε, is de string die geen symbolen bevat. De lengte van een string s = a1 a2 . . . an , notatie |s| is het aantal symbolen in de string s. |ε| = 0. T ∗ is de verzameling van alle strings over het alfabet T , inclusief de lege string. Op de verzameling T ∗ is de volgende binaire operatie gedefinieerd: De concatenatie van de strings u = a1 a2 . . . an ∈ T ∗ en v = b1 b2 . . . bm ∈ T ∗ , notatie uv is de string uv = a1 a2 . . . an b1 b2 . . . bm ∈ T ∗ Bovendien geldt voor alle u ∈ T ∗ : εu = uε = u. De concatenatie is een associatieve operatie. Zij x = uv met u, v ∈ T ∗ , dan noemen we u een prefix van x en v een suffix van x. Een taal L over een alfabet T is een deelverzameling van T ∗ . Het product (concatenatie van verzamelingen) van twee talen L1 en L2 , notatie L1 .L2 , is de verzameling strings u1 u2 met u1 ∈ L1 en u2 ∈ L2 : notatie L1 .L2 . Dit product is associatief. Het eenheidselement is {ε} . De nde macht van een taal L (n ≥ 0) wordt gedefineerd door: L0 = {ε} Ln = L.Ln−1 (n ≥ 1) S n De transitieve afsluiting L+ van een taal L wordt gedefineerd door: L+ = ∞ n=1 L
6
De star of de (Kleene) closure van een taal L, notatie L∗ , wordt gedefineerd door: L∗ = L0 ∪ L+ Een grammatica G is een 4-tupel (T, N, P, S) waarin: T het alfabet van eindsymbolen is (Terminals). N het alfabet van hulpsymbolen is (Nonterminals). (V = T ∪ N wordt het volledige alfabet of Vocabulaire genoemd) P een eindige verzameling producties is, dat wil zeggen expressies van de vorm ϕ → ψ met ϕ ∈ (T ∪ N )+ en ψ ∈ (T ∪ N )∗ . S het startsymbool van de grammatica G is. (S ∈ N ). Zij G = (T, N, P, S) een grammatica. De string X 0 heet direct afleidbaar van X, X leidt direct tot X 0 , of X genereert X 0 wanneer er strings σ, τ, ϕ en ψ ∈ (T ∪ N )∗ zijn zodanig dat X = σϕτ en X 0 = σψτ en ϕ → ψ ∈ P . Notatie: X⇒X 0 of X ⇒ X 0 . G
De relatie ⇒∗ (of ⇒∗ ) op (T ∪N )∗ is de reflexieve transitieve afsluiting van de relatie ⇒ (of ⇒) op (T ∪N )∗ . G
G
Wanneer X⇒∗ X 0 zeggen we dat X 0 afleidbaar is van X, of dat X leidt tot X 0 , of dat X in nul of meer G
stappen X 0 genereert. Een string ϕ ∈ (T ∪ N )∗ heet een zinsvorm (sentential form) van de grammatica G wanneer S⇒∗ ϕ. G
Bevat een zinsvorm ϕ uitsluitend eindsymbolen, ϕ ∈ T ∗ dan noemen we ϕ een zin (sentence) van G. De taal gegenereerd door de grammatica G, notatie L(G), is de verzameling zinnen van G. Twee grammatica’s G1 en G2 zijn equivalent dan en slechts dan wanneer L(G1 ) = L(G2 ).
3.1
Reguliere expressies
Een reguliere expressie (RE) over een alfabet T en de door deze RE beschreven taal worden als volgt gedefinieerd: 1. ∅ is een RE voor de taal ∅ en ε is een RE voor {ε} 2. a is een RE voor {a} als a ∈ T 3. Wanneer E1 en E2 RE’s over T zijn die de talen L(E1 ) en L(E2 ) beschrijven dan is: (E1 |E2 ) of (E1 + E2 ) een RE voor L(E1 ) ∪ L(E2 ), (E1 E2 ) een RE voor L(E1 ).L(E2 ) en (E1 ∗ ) een RE voor L(E1 )∗ . Twee RE’s E1 en E2 over een alfabet T zijn equivalent dan en slechts dan wanneer L(E1 ) = L(E2 ). Notatie: E1 = E2 . Als E1 , E2 en E3 RE’s over een alfabet T zijn, dan geldt: a) E1 |E1 = E1
, E1 |∅ = E1
b) E1 |E2 = E2 |E1 c) (E1 |E2 )|E3 = E1 |(E2 |E3 ) = E1 |E2 |E3 d) (E1 E2 )E3 = E1 (E2 E3 ) = E1 E2 E3 e) E1 ε = εE1 = E1
, E1 ∅ = ∅E1 = ∅
f) (E1 |E2 )E3 = E1 E3 |E2 E3 g) E1 (E2 |E3 ) = E1 E2 |E1 E3 h) E1 ∗ E1 ∗ = E1 ∗ i) (E1 ∗ )∗ = E1 ∗ 7
j) E1 E1 ∗ = E1 ∗ E1
, E1 (E2 E1 )∗ = (E1 E2 )∗ E1
k) ε|E1 E1 ∗ = E1 ∗ l) ε∗ = ε
, ∅∗ = ε
m) (E1 ∗ |E2 ∗ )∗ = (E1 |E2 )∗ = (E1 ∗ E2 ∗ )∗ n) (E1 ∗ E2 )∗ E1 ∗ = (E1 |E2 )∗ o) (E1 ∗ E2 )∗ = (E1 |E2 )∗ E2 |ε p) (E1 E2 ∗ )∗ = E1 (E1 |E2 )∗ |ε 3.1.1
Lemma van Arden
E1 = E2 ∗ E3 ⇒ E1 = E2 E1 |E3 en E1 = E2 E1 |E3 ∧ ε 6∈ L(E2 ) ⇒ E1 = E2 ∗ E3 3.1.2
Omzetting reguliere grammatica in RE
De taal gegenereerd uit een symbool X ∈ V van een grammatica G is: L(X) = {u|u ∈ T ∗ ∧ X⇒∗ u} G
• De reguliere grammatica wordt geschreven als een stelsel vergelijkingen in de onbekende nonterminals. Alle producties in G met dezelfde nonterminal als linkerlid worden samengevat in ´e´en vergelijking. • Het stelsel vergelijkingen wordt opgelost door middel van een schoonveegproces. • De RE voor het startsymbool van G is een beschrijving van de taal die door de grammatica gegenereerd wordt.
3.2
Automaten
Een eindige automaat (FA) bestaat uit een invoerband, een leeskop en een besturingseenheid. rest van de invoer XXX X
’ e e n
s t r i n g ’
Invoerband
6Leeskop
Besturingseenheid Een (niet-deterministische) eindige automaat (NFA) is een 5-tupel (Q, Σ, δ, q0 , F ) met: Q het toestandsalfabet, Σ het invoeralfabet, δ de (totale) overgangsfunctie: δ : Q × (Σ ∪ {ε}) → 2Q , Hierbij is 2Q de verzameling van alle deelverzamelingen van Q. q0 ∈ Q de begintoestand, F ⊆ Q de verzameling accepterende toestanden.
8
Een configuratie van de NFA N = (Q, Σ, δ, q0 , F ) is een expressie van de vorm: qx met q ∈ Q en x ∈ Σ∗ Op de verzameling configuraties van de NFA N wordt de relatie ⇒ (gaat in ´e´en stap over in) gedefinieerd door: N
qx⇒q 0 x dan en slechts dan als q 0 ∈ δ(q, ε) en N
qax⇒q 0 x dan en slechts dan als q 0 ∈ δ(q, a) voor a ∈ Σ, x ∈ Σ∗ en q, q 0 ∈ Q. N
(⇒∗ is de reflexieve transitieve afsluiting.) N
Een string x ∈ Σ∗ wordt door de NFA N geaccepteerd dan en slechts dan wanneer ∃(q : q ∈ F : q0 x⇒∗ q). N
L(N ) = {x|x ∈ Σ∗ ∧ ∃(q : q ∈ F : q0 x⇒∗ q)} is de geaccepteerde taal. Een NFA is een deterministische eindige N
automaat (DFA) dan en slechts dan als: ∀(q : q ∈ Q : δ(q, ε) = ∅) ∧ ∀(a, q : a ∈ Σ ∧ q ∈ Q : #(δ(q, a)) ≤ 1) Een voorspellende (deterministische) eindige automaat (PFA) is een 6-tupel (Q, Σ, δ, q0 , F, A) met: Q het toestandsalfabet, Σ het invoeralfabet (⊥6∈ Σ), δ de functie δ : Q × (Σ ∪ {⊥} → Q × A de (gedeeltelijke) overgangsfunctie, q0 de begintoestand, q0 ∈ Q, F ⊆ Q de verzameling accepterende toestanden, A het alfabet {Read, Skip} (Actie-alfabet). De overgangsfunctie δ voldoet aan: ∀(q, q 0 : q, q 0 ∈ Q : δ(q, ⊥) 6= (q 0 , Read)). Een configuratie van de PFA is een expressie van de vorm: qx ⊥ met q ∈ Q en x ∈ Σ∗ . Op de verzameling configuraties van de PFA P wordt de relatie ⇒ gedefinieerd door: P
qax ⊥ ⇒q 0 x ⊥ dan en slechts dan als δ(q, a) = (q 0 , Read), en P
qax ⊥ ⇒q 0 ax ⊥ dan en slechts dan als δ(q, a) = (q 0 , Skip), en P
q ⊥ ⇒q 0 ⊥ dan en slechts dan als δ(q, ⊥) = (q 0 , Skip), P
voor a ∈ Σ, x ∈ Σ∗ en q, q 0 ∈ Q. ⇒∗ is de reflexieve transitieve afsluiting van ⇒. Als duidelijk is uit de context wie P is laten we die P weg P
P
(⇒). Een string x ∈ Σ∗ wordt door de PFA geaccepteerd dan en slechts dan als ∃(q : q ∈ F : q0 x ⊥ ⇒∗ q ⊥). De door PFA P geaccepteerde taal is L(P ) = {x|x ∈ Σ∗ ∧ ∃(q : q ∈ F : q0 x ⊥ ⇒∗ q ⊥)}. P
4
De structuur van een Reguliere Expressie
Een reguliere expressie kunnen we representeren door middel van een boomstructuur op dezelfde wijze als we dat met rekenkundige ezpressies kunnen.
4.1
Berekening van functiewaarden in de knopen
In knoop k worden nullable(k) en first(k) berekend aan de hand van de vorm van de knoop: knoop(k) ε a (a ∈ Σ) k1 |k2
nullable(k) true false nullable(k1 ) ∨ nullable(k2 )
k1 k2
nullable(k1 ) ∧ nullable(k2 )
∗
k1 k1 +
true nullable(k1 ) 9
knoop(k) ε a (a ∈ Σ) k1 |k2
first(k) ∅ {a} first(k1 ) ∪ first(k2 )
k1 k2
IF nullable(k1 ) THEN first(k1 ) ∪ first(k2 ) ELSE first(k1 )
k1 ∗
first(k1 )
+
first(k1 )
k1
In knoop ki wordt de functie follow berekend. Voor de wortel van de boom k0 geldt: follow(k0 ) = ∅. Voor de overige knopen ki wordt de waarde berekend aan de hand van de ouderknoop k: knoop(k) k1 |k2
follow(ki ) follow(k1 ) := follow(k) ; follow(k2 ) := follow(k)
k1 k2
IF nullable(k2 ) THEN follow(k1 ) := follow(k) ∪ first(k2 ) ELSE follow(k1 ) := first(k2 ) ; follow(k2 ) := follow(k)
k1 ∗
follow(k1 ) := follow(k) ∪ first(k1 )
+
k1 follow(k1 ) := follow(k) ∪ first(k1 ) De functie LA wordt gedefinieerd door: LA(k) = IF nullable(k) THEN first(k) ∪ follow(k) ELSE first(k)
4.2
Constructie accepterend programma
De afbeelding τ zet nu een knoop van de boom voor een RE om naar een accepterend programmafragment voor die knoop. τ (ε):
(* SKIP *)
τ (a):
IF nextcl = a THEN getcl ELSE error IF nextcl ∈LA(k1 ) THEN τ (k1 ) ELSE τ (k2 )
τ (k1 |k2 ): τ (k1 k2 ): ∗
τ (k1 ) ; τ (k2 )
τ (k1 ):
WHILE nextcl ∈ first(k1 ) DO τ (k1 )
τ (k1 + ):
REPEAT τ (k1 ) UNTIL nextcl 6∈ first(k1 )
Hierbij zijn de characters in classes opgedeeld (alle digits, alle letters, etc.). De procedure getcl leest het volgende invoercharacter en bepaalt de waarde van de variabele nextcl.
10
5
Grammatica’s
Een grammatica is een 4-tupel (T, N, P, S), met V = T ∪ N , is gereduceerd dan en slechts dan wanneer: ∀(X : X ∈ V : ∃(u, v, x : u, v, x ∈ T ∗ : S ⇒∗ uXv ⇒∗ uxv)) Een symbool X ∈ V termineert dan en slechts dan wanneer: ∃(x : x ∈ T ∗ : X ⇒∗ x) Een symbool X ∈ V heet bereikbaar dan en slechts dan wanneer: ∃(u, v : u, v ∈ T ∗ : S ⇒∗ uXv)
5.1
Constructie van een equivalente gereduceerde grammatica
Bepaal eerst de verzameling terminerende non-terminals in G. Verwijder alle overige non-terminals uit N en alle producties waarin niet-terminerende non-terminals voorkomen uit P. Resultaat: equivalente grammatica G0 = (T, N 0 , P 0 , S) Bepaal vervolgens in G0 de verzameling bereikbare symbolen. Verwijder alle niet bereikbare symbolen en de producties waarin de niet bereikbare symbolen voorkomen. Resultaat: equivalente gereduceerde grammatica G00 = (T 00 , N 00 , P 00 , S)
6
Stapelautomaten a + b * c
Invoerband
Leeskop
6
+ Lees/schrijfkop T .
Besturingseenheid
Stapel Een (niet-deterministische) stapelautomaat (NPDA) is een 7-tupel (Q, Σ, Γ, δ, q0 , Z, F ) met: Q het toestandsalfabet, Σ het invoeralfabet, Γ het stapelalfabet, δ de totale stapelfunctie, δ : Γ × Q × (Σ ∪ {ε}) → 2Γ
∗ ×Q
,
q0 ∈ Q de begintoestand, Z ∈ Γ het startsymbool op de stapel, F ⊆ Q de verzameling accepterende toestanden. Constructie van een NPDA corresponderend met een CFG (T, N, P, S): Kies: Σ = T Γ = T ∪ N (= V ) Q = {q0 } Z = S F = {q0 } δ wordt alsvolgt gedefinieerd: δ(a, q0 , a) = {(ε, q0 )} voor a ∈ T δ(X, q0 , a) = ∅ voor a ∈ T, X ∈ V, a 6= X δ(A, q0 , ε) = {(ϕ, q0 )|A → ϕ ∈ P } voor A ∈ N Een configuratie van een NPDA is een 3-tupel (γ, q, x) met γ ∈ Γ∗ , q ∈ Q en x ∈ Σ∗ . Op de verzameling configuraties van de NPDA N wordt de relatie ⇒ (gaat in ´e´en stap over in) gedefinieerd door: N
11
(cα, q, ax)⇒(βα, q 0 , x) dan en slechts dan als (β, q 0 ) ∈ δ(c, q, a) en N
(cα, q, x)⇒(βα, q 0 , x) dan en slechts dan als (β, q 0 ) ∈ δ(c, q, ε). N
(⇒∗ is de reflexieve transitieve afsluiting van ⇒.) N
N
Waar mogelijk laten we die N weg. Een string x ∈ Σ∗ wordt door een NPDA geaccepteerd dan en slechts dan als: (Z, q0 , x)⇒∗ (ε, q, ε). De taal geaccepteerd door de NPDA N is: L(N ) = {x|x ∈ Σ∗ ∧ ∃(q : q ∈ Q : (Z, q0 , x)⇒∗ (ε, q, ε))}. N
Een voorspellende stapelautomaat (PPDA) is een 5-tupel (Σ, Γ, δ, Z, A) met: Σ het invoeralfabet (⊥6∈ Σ), Γ het stapelalfabet (⊥6∈ Γ), ∗ ×A
δ de stapelfunctie, δ : Γ × (Σ ∪ {⊥}) → 2Γ
,
Z ∈ Γ het startsymbool op de stapel, A (Action) het actie alfabet {Read, Skip}. De stapelfunctie voldoet aan: ∀(c, γ : c ∈ Γ ∧ γ ∈ Γ∗ : (γ, Read) 6∈ δ(c, ⊥)) Een configuratie van een PPDA is een paar (γ ⊥, x ⊥) met γ ∈ Γ∗ en x ∈ Σ∗ . Op de verzameling configuraties van de PPDA P wordt de relatie ⇒ (gaat in ´e´en stap over in) gedefinieerd P
door: (cγ ⊥, ax ⊥)⇒(βγ ⊥, x ⊥) dan en slechts dan (β, Read) ∈ δ(c, a) P
(cγ ⊥, ax ⊥)⇒(βγ ⊥, ax ⊥) dan en slechts dan (β, Skip) ∈ δ(c, a) P
(cγ ⊥, ⊥)⇒(βγ ⊥, ⊥) dan en slechts dan (β, Skip) ∈ δ(c, ⊥) P
⇒∗ is de reflexieve transitieve afsluiting van ⇒.) P
P
Waar mogelijk laten we P weg. Een string x ∈ Σ∗ wordt door een PPDA geaccepteerd dan en slechts dan als: (S ⊥, x ⊥)⇒∗ (⊥, ⊥). De door PPDA P geaccepteerde taal is: L(P ) = {x|x ∈ Σ∗ ∧ (S ⊥, x ⊥)⇒∗ (⊥, ⊥)}. P
Een PPDA is deterministisch dan en slechts dan als ∀(c, a : c ∈ Γ ∧ a ∈ (Σ ∪ {⊥}) : #(δ(c, a)) ≤ 1) We gaan in het vervolg uit van de uitgebreide grammatica G0 van grammatica G: = (T ∪ {⊥}, N ∪ Z, P ∪ {Z ⇒ S ⊥}, Z). Als dat geen verwarring wekt zullen we ook in de uitgebreide grammatica spreken over T, N, S, P . G0
De lookaheadset LA(A → α) van een productie A → α ∈ P is gelijk aan {a|a ∈ T ∪ {⊥} ∧ ∃(w, y, ϕ : w ∈ T ∗ ∧ (y = ε ∨ y ∈ T ∗ .{⊥}) ∧ ϕ ∈ V ∗ : S ⊥ ⇒∗ wAϕ ⊥ ⇒wαϕ ⊥⇒∗ way). GL
G
Die LA lijkt nogal lastig te bepalen. Verderop blijkt dit toch efficient te kunnen. Constructie van een PPDA corresponderend met de uitgebreide grammatica van G: Kies: Σ = T 0 Γ = T0 ∪ N0 Z = Z (startsymbool van G0 ) De stapelfunctie δ wordt gedefinieerd door: δ(a, a) = {(ε, Read)} voor a ∈ T δ(a, b) = ∅ voor a ∈ T, b ∈ T ∪ {⊥}, b 6= a δ(A, b) = {(α, Skip)|A → α ∈ P ∧ b ∈ LA(A → α)} δ(A, b) = ∅ als geen van de voorgaande geldt De met G0 corresponderende PPDA is deterministisch dan en slechts dan als: ∀(A → α, A → β ∈ P ∧ α 6= β : LA(A → α) ∩ LA(A → β)= ∅) 12
Voor G0 worden de volgende functies gedefinieerd: first : V ∗ → 2T first(ϕ) = {b|b ∈ T ∧ ∃(σ : σ ∈ V ∗ : ϕ⇒∗ bσ)} G
nullable : V ∗ → Boolean nullable(ϕ) = ϕ⇒∗ ε G
follow : N → 2T follow(A) = {b|b ∈ T ∧ ∃(B, σ, τ : B ∈ N ∧ σ ∈ V ∗ ∧ τ ∈ V ∗ : B ⇒+ σAbτ ) G
richters : P → 2T richters(A → α) = IF nullable(α) THEN first(α) ∪ follow(A) ELSE first(α) FI
Wanneer een grammatica gereduceerd is geldt voor elke productie A → α ∈ P : richters(A → α) = LA(A → α) Een grammatica is LL(1) dan en slechts dan als voor elk tweetal producties A → α en A → β, met zelfde linkerlid A en α 6= β, geldt: LA(A → α) ∩ LA(A → β) = ∅ Een LL(1) grammatica is niet ambigu. Wanneer een gereduceerde grammatica een linksrecursieve nonterminal bevat is deze grammatica zeker niet LL(1).
7
Implementatie van een topdown parser
We gaan uit van een gereduceerde LL(1) grammatica. De eerste implementatie gebruikt een expliciete stapel datastructuur.
7.1
Topdown parser met expliciete stapel
We implementeren een topdown parser voor de uitgebreide grammatica voor GE . De grammatica GE kent de volgende producties: , , , , , ,
E T X X Y Y F
→ → → → → → →
TX FY +T X ∗F Y a | b | c | (E)
13
BEGIN (* initialisaties *) nextsym ; (* initialisatie variabele sym *) initstack ; push(⊥); push(E); (* stack: E ⊥ *) WHILE top 6=⊥ DO BEGIN CASE top OF a, b, c, (, ), ∗, +: IF sym = top THEN BEGIN pop; nextsym END ELSE error E: IF sym ∈ {a, b, c, (} THEN BEGIN (* richters E → T X *) pop; push(X); push(T ) END ELSE error T: IF sym ∈ {a, b, c, (} THEN BEGIN pop; push(Y ); push(F ) END ELSE error X: IF sym ∈ {+} THEN BEGIN (* richters X → +T X *) pop; push(X); push(T ); push(+) END ELSE IF sym ∈ {), ⊥} THEN (* richters X → *) pop ELSE error ... END (* CASE *) END (* WHILE *) IF sym 6=⊥ THEN error; (* acceptatie *) END
7.2
Implementatie recursive descent parser (zonder error recovery)
De tweede implementatie gebruikt een verzameling recursieve procedures: recursive descent. Voor het herkennen van een terminal: PROCEDURE match(fs : tsymbol); BEGIN IF sym = fs THEN nextsym ELSE error END (* match *) Het hoofdprogramma corresponderend met extra product Z → S ⊥:
14
BEGIN (* initialisaties *) nextsym ; (* initialisatie sym *) pS; IF sym 6=⊥ THEN error; (* acceptatie *) END Voor een string ϕ ∈ V ∗ worden de statements τ (ϕ) gegenereerd: (* SKIP *)
als ϕ = ε
match(a)
als ϕ = a ∈ T
pA
als ϕ = A ∈ N
τ (ψ) ; τ (X)
als ϕ = ψX met ψ ∈ V + en X ∈ V
Voor het herkennen van een A ∈ N met m ≥ 2 producties A → ϕ1 , A → ϕ2 , . . ., A → ϕm : PROCEDURE pA; BEGIN IF sym ∈ LA(A → ϕ1 ) THEN BEGIN τ (ϕ1 ) END ELSE IF sym ∈ LA(A → ϕ2 ) THEN BEGIN τ (ϕ2 ) ... END ELSE IF sym ∈ LA(A → ϕm ) THEN BEGIN τ (ϕm ) END ELSE error END (* pA *); Voor het herkennen van A ∈ N die precies ´e´en productie A → ϕ heeft: PROCEDURE pA; BEGIN τ (ϕ) END (* pA *); We kunnen ons een test uitsparen met een simpele truc. Kies voor elke nonterminal A ∈ N ´e´en productieregel als default regel, en wel juuist die productie die het snelst termineert. Verwissel die productie nu met A → ϕm . Het nieuwe recept luidt dan alsvolgt: PROCEDURE pA; (* A → ϕm als default regel *) BEGIN IF sym ∈ LA(A → ϕ1 ) THEN BEGIN τ (ϕ1 ) END ELSE IF sym ∈ LA(A → ϕ2 ) THEN BEGIN τ (ϕ2 ) ... END ELSE IF sym ∈ LA(A → ϕm−1 ) THEN BEGIN τ (ϕm−1 ) END ELSE BEGIN τ (ϕm ) END END (* pA *);
15
7.3
Recursive descent parser met errorrecovery
Als we een fout hebben aangetroffen in de invoer is de parser in een geblokkeerde configuratie. Eerst wat hulpdefinities: Een string u ∈ T ∗ is een geldige prefix van de taal L(G) dan en slechts dan wanneer ∃(v : v ∈ T ∗ : uv ∈ L(G)). Een string v ∈ T ∗ met uv ∈ L(G) wordt een voortzetting (continuation) van de geldige prefix u genoemd. Het symbool a ∈ T in de string xay (x, y ∈ T ∗ ) is het foutsymbool van deze string dan en slechts dan wanneer x een geldige prefix is en xa niet een geldige prefix is. Voor een bepaalde voortzetting v van een geldige prefix x wordt de verzameling anchors gedefinieerd door: anchors(v) = {a ∈ T | ∃(vp : vp ∈ T ∗ : vp is een prefix van v ∧xvp a is een geldige prefix} Stel a ∈ T is het foutsymbool in xay en S ⊥ ⇒∗ xϕ ⊥, met ϕ ⊥= X1 X2 . . . Xn (n ≥ 1, Xi ∈ V , dan wordt L
de (geblokkeerde) configuratie (ϕ ⊥, ay) hersteld door de volgende acties uit te voeren: 1. Bepaal de voortzetting v = v1 v2 . . . vn uit X1 X2 . . . Xn zodanig dat Xi ⇒∗ vi door uitsluitend default producties toe te passen. S 2. Bepaal de verzameling keys, gedefineerd door keys = ni=1 first(Xi ). Deze keys zullen we gebruiken als implementatie van anchors(v). 3. Verwijder de vooroplopende symbolen van ay die niet tot de verzameling keys behoren. Geef voor elk verwijderd symbool een foutmelding. Rest van de invoer is ky 0 (een suffix van ay) en k ∈ keys. 4. Wijzig de configuratie, te beginnen met (ϕ ⊥, ky 0 ), zolang k niet geaccepteerd kan worden, door de stappen uit te voeren die corresponderen met het verwerken van een aantal vooroplopende symbolen (via default producties) van de voortzetting v. Geef voor elk ’toegevoegd’ symbool een foutmelding. Hierna laten we zien hoe dit ge¨ımplemteerd kan worden. 7.3.1
Hulpprocedures
PROCEDURE deletion; Verzorg foutmelding:
’sym’ deleted
PROCEDURE insertion (fs : tsymbol); Verzorg foutmelding: ’fs’ inserted PROCEDURE delete (keys : tsymbolset); BEGIN WHILE NOT (sym IN keys) DO BEGIN deletion; nextsym END { POST sym ∈ keys } END (* delete *); Voor het herkennen van een terminal:
16
PROCEDURE match(fs : tsymbol; keys: BEGIN IF fs = sym THEN nextsym ELSE BEGIN delete({f s} + keys); IF sym = fs THEN nextsym ELSE insertion(fs) END END (* match *)
tsymbolset);
Hoofdprogramma corresponderend met de extra productie Z → S ⊥: BEGIN (* initialisaties *) nextsym (* initialisatie sym *) pS({⊥}); delete({⊥}); (* finalisatie *) END Voor een string ϕ ∈ V ∗ worden de statements τ (ϕ, keys) gegenereerd: τ (ϕ, keys) (* SKIP *)
als ϕ = ε
match(a, keys)
als ϕ = a ∈ T
pA(keys)
als ϕ = A ∈ N
τ (ψ, keys + first(X)); τ (X, keys)
als ϕ = ψX met ψ ∈ V + en X ∈ V
Voor het herkennen van een string uit L(A) voor A ∈ N met precies ´e´en productie A → ϕ: PROCEDURE pA(keys : tsymbolset); BEGIN τ (ϕ, keys) END (* pA *); Voor het herkennen van een string uit L(A) voor A ∈ N met m ≥ 2 producties A → ϕi (1 ≤ i ≤ m), waarbij A → ϕm de defaultproductie voor A is. (Alleen ϕm is eventueel nullable!) PROCEDURE pA(keys : tsymbolset); BEGIN delete(first(A) + keys); IF sym ∈ first(ϕ1 ) THEN BEGIN τ (ϕ1 , keys) END ELSE IF sym ∈ first(ϕ2 ) THEN BEGIN τ (ϕ2 , keys) ... END ELSE IF sym ∈ first(ϕm−1 ) THEN BEGIN τ (ϕm−1 , keys) END ELSE BEGIN τ (ϕm , keys) END END (* pA *);
7.4
Foutafhandeling tijdens semantische analyse (geen tentamenstof )
Statische semantische fouten worden ontdekt tijdens het berekenen van de attributen van de knopen van de abstract syntax tree (AST), en wel bij de controle of de attribuutwaarden aan bepaalde voorwaarden (de context conditions) voldoen. 17
Doel: • Signaleren van meerdere semantische fouten in de programmatekst in ´e´en vertaalslag. Overbodige foutmeldingen moeten worden vermeden evenals niet terechte foutmeldingen (spurious errors). • Herstelactie van een semantische fout moet eenvoudig uitgevoerd kunnen worden. • In geen geval mag een foutief programma worden geaccepteerd. Uitgangspunt: Een syntactisch correct programma of daarmee corresponderende AST. Inventarisatie mogelijke semantische fouten: 1. Symbolen die door de parser zijn verwijderd (delete actie in error recovery). 2. Symbolen die door de parser zijn toegevoegd (insert actie in error recovery). 3. Niet gedeclareerde identifiers worden gebruikt. 4. Het gebruik van een identifier is niet consistent met de declaratie. 5. Dubbel gedeclareerde identifiers in een block 6. Bij typecontrole van expressies: het gebruik van een operator is niet consistent met de definitie.
8
Bottom-up parser
We introduceren het begrip item: een productie met ergens in de rechterkant een ‘.’, de voortgangswijzer, bijvoorbeeld ‘E → T. + E’. De T is herkend, we verwachten nog een string afleidbaar uit ‘+E’. We leiden nu een bottom-up parser af bij de producties: 1) 2) 3) 4) 5)
8.1
S → aSB S→A A→c B → bB B→c
Het bepalen van de toestanden van de stapelautomaat
De closure berekening van een toestand van de stapelautomaat: C := "kernel"; repeat oldC := C; forall A → α.Bβ ∈ C do forall B → γ ∈ P do C := C ∪ B → .γ until oldC = C
18
1.
2.
, , , ,
Z → S· ⊥
2 3 4 5
6.
S → aS · B B → ·bB B → ·c
,7 ,8 ,9
7.
S → aSB·
red
8.
B →b·B B → ·bB B → ·c
, 10 ,8 ,9
acc
S → a · SB S → ·aSB S → ·A A → ·c
, , , ,
6 3 4 5
9.
B → c·
red
4.
S → A·
red
10.
B → bB·
red
5.
A → c·
red
3.
8.2
Z → ·S ⊥ S → ·aSB S → ·A A → ·c
Action en Goto table
Een item van de vorm ‘A → α.tβ’ met t ∈ T geeft een shift aktie aan (lees t van de input). Een item van de vorm ‘A → α.’ geeft een reduce aktie aan, dat wil zeggen pas de productie A → α in omgekeerde richting toe. Soms bevat een toestand zowel een shift als een reduce aktie. We noemen dat een shift/reduce conflict. Een tweede soort conflict is wanneer er in een toestand twee verschillende reducties mogelijk zijn: reduce/reduce conflict. Een voorbeeld: bij de grammatica G met productieregels 1) 2) 3) 4) 5) 6)
E →E+T E→T T →T ∗F T →F F → id F → (E)
kunnen we opnieuw de toestanden van de herkennende automaat uitrekenen en daaruit de action en goto table construeren. We zien een shift/reduce conflict in de uitgerekende toestanden 2 en 9. We kunnen echter een keuze maken door gebruik te maken van follow(E). Kies voor reductie wanneer het inputsymbol in follow(E) zit en doe anders een shift. Dit alles vinden we terug in de Action en Goto table: 0 1 2 3 4 5 6 7 8 9 10 11
id S4
+
*
S6 R2 R4 R5
S7! R4 R5
S4 S4 S4
(
)
⊥
R2 R4 R5
ACC R2 R4 R5
S5 S5 S5 S6 R1 R3 R6
S7! R3 R6
S11 R1 R3 R6
E 1
T 2
F 3
8
2 9
3 3 10
R1 R3 R6
Om een keuze te maken uit twee reducties moet de doorsnede van de follow sets van beide linkerleden disjunct zijn. Wanneer we zo alle conflicten hebben kunnen oplossen heet de grammatica Simpel LR(1) (SLR(1)). Lukt dit niet met follow informatie dan hebben we een krachtiger parsing algoritme nodig.
19
8.3
LR(1) sets of items
Een LR(1) item is een paar, bestaande uit een gewoon (LR(0)) item en een lookahead symbol, bijvoorbeeld (E → T. + E, ‘)0 ). Als LR(1) voorbeeld nemen we de volgende producties: 1) Z → S ⊥ 2) S → E = E 3) S → f 4) E → E + T 5) E → T 6) T → T + f 7) T → f De LR(1) berekening van de closure van een toestand lijkt erg op die van LR(0): C := "kernel"; repeat oldC := C; forall (A → α.Bβ, a) ∈ C do forall B → γ ∈ P do forall b ∈ f irst(βa) do C := C ∪ (B → .γ, b) until oldC = C Voor de gegeven producties leidt dit tot de volgende toestanden: 1. Z → ·S ⊥ , {?} 8. S → E = E· , {⊥} S → ·E = E , {⊥} E → E · +T , {⊥, +} S → ·f , {⊥} , E → ·T , {=, +} 9. E → T· , {⊥, +} E → ·E + T , {=, +} T → T · ∗f , {⊥, +, ∗} T → ·f , {=, +, ∗} , T → ·T ∗ f , {=, +, ∗} 10. T → f · , {⊥, +, ∗} , 2. Z → S· ⊥ , {?} 11. T → f · , {=, +, ∗} , 3. S → E· = E , {⊥} 12. E → E + T · , {=, +} E → E · +T , {=, +} T → T · ∗f , {=, +, ∗} , 4. E → T · , {=, +} 13. T → T ∗ ·f , {=, +, ∗} T → T · ∗f , {=, +, ∗} , 14. T → T ∗ f · , {=, +, ∗} 5. S → f · , {⊥} , T → f· , {=, +, ∗} 15. E → E + ·T , {⊥, +} T → ·f , {⊥, +, ∗} 6. S → E = ·E , {⊥} T → ·T ∗ f , {⊥, +, ∗} E → ·E + T , {⊥, +} , E → ·T , {⊥, +} 16. E → E + T · , {⊥, +} T → ·f , {⊥, +, ∗} T → T · ∗f , {⊥, +, ∗} T → ·T ∗ f , {⊥, +, ∗} , 17. T → T ∗ ·f , {⊥, +, ∗} 7. E → E + ·T , {=, +} , T → ·T ∗ f , {=, +, ∗} 18. T → T ∗ f · , {⊥, +, ∗} T → ·f , {=, +, ∗} , We zien een shift/reduce conflict in toestanden 4, 8, 9, 12 en 16. Bovendien een reduce/reduce conflict in toestand 5. Hierbij is het conflict in toestand 5 niet oplosbaar met follow informatie, zodat deze grammatica
20
niet SLR(1) is. We zien dat alle conflicten wel opgelost worden met de LR(1) sets of items. Deze grammatica is daarom LR(1). Bij de grammatica G met productieregels 1) 2) 3) 4) 5) 6)
Z→S⊥ S→AB A A→aA vinden we: A→b B→B b B→
1.
Z → ·S ⊥ S → ·ABA A → ·aA A → ·b
, , , ,
2.
Z → S· ⊥
3.
4.
5.
{} {⊥} {a, b} {a, b}
6.
S → AB · A B →B·b A → ·aA A → ·b
, , , ,
{⊥} {a, b} {⊥} {⊥}
, {}
7.
A → aA·
, {a, b}
S → A · BA B → ·Bb B→·
, {⊥} , {a, b} , {a, b}
8.
S → ABA·
, {⊥}
9.
B → Bb· A → b·
, {a.b} , {⊥}
A→a·A A → ·aA A → ·b
, {a, b} , {a, b} , {a, b}
10.
A→a·A A → ·aA A → ·b
, {⊥} , {⊥} , {⊥}
A → b·
, {a, b} 11.
A → b·
, {⊥}
12. A → aA· , {⊥} Meerdere toestanden zijn gelijk qua eerste component maar verschillen in de tweede component van ieder LR(1) item. Wat gebuert er wanneer we die toestanden mergen? Te mergen toestanden zijn: (4, 10), (5, 11), (7, 12). Mergen levert geen reduce/reduce conflicten op, dan noemen we de grammatica Lookahead LR(1) (LALR(1)). Opmerking bij toestand 9: niet SLR(1), wel LR(1). De Action en Goto tabel zijn nu:
*
9
a b 1 S4 S5 2 3 R6 R6 4* S4 S5 5* R4 R4 6 S4 S9 7* R3 R3 8 R2 R2 9 R5 R5 = gemerged
⊥
S 2
A 3
acc R6
B
6 7
R4 8 R3 R2 R4!
Attributengrammatica’s (g´ e´ en tentamenstof )
Grammatica: int denot : radix :
digit SEQUENCE, radix PACK digit SEQUENCE
{ digit < radix and intdenot < 32767} { radix ∈ {2, 8, 10} } 21
Correcte zinnen: 1101(2), 1101(10), 776(8) Production int denot
: number , radix PACK . radix : digit ; radix1 , digit . digit : ’∅’ ; ... ; ’9’ . number : digit ; number1 , digit . NT attributen-types int denot V {syn} radix R{syn} digit V {syn} number V {syn}, R{inh}
Attribute Rule { number.R := radix.R; int denot.V := number.V; CHECK radix.R IN [2,8,10] } { radix.R := digit.V } { radix.R := 10 * radix1 .R + digit.V } { digit.V := ∅ } ... { digit.V := 9 } { number.V := digit.V; check digit.V < number.R } { number1 .R := number.R; number.V := number.R * number1 .V + digit.V; CHECK digit.V < number.R AND number.V ≤ 32767 }
radnum/int denot
T:
@ @ @
( radix )
number @ @ @
number
digit
digit
digit
’7’
’8’
’7’ V CDG(T):
V 3 ? -
(R V)
> o S S S = ( R-V ) V 6
V
R 6
V V = Val R = Rad
22
10
Code generatie
10.1
Representatie codesegment van een procedure aanroep
Vertaling van de declaratie τ (PROC p; block_p) en van de aanroep τ (p) moeten we zodanig op elkaar afstemmen dat: 1. het codesegment τ (PROC p; block_p) ´e´en keer in het doelprogramma voorkomt, 2. tijdens de uitvoering van de instructies in τ (p) de regie wordt overgedragen aan τ (PROC p; block_p), en 3. na de uitvoering van de instructies in τ (PROC p; block_p) de regie wordt overgedragen aan de volgende instructie na de juiste aanroep τ (p) PROGRAM vb1; VAR a, i :
INTEGER;
PROCEDURE p (VAR x : INTEGER); VAR b, i : INTEGER; BEGIN ... i ... a ... b ... p(b) ... END BEGIN ... i ... a ... END (* vb1 *)
i ...
p(i) ...
Tijdens de 2e activation van p: Codesegment vb1
Aanroep p
AR vb1 waarde a = A0 waarde i = I0 ra(1)
Codesegment p
Aanroep p
AR p waarde x = I0 waarde b = B1 waarde i = I1
(1)
AR p waarde x = B1 waarde b = B2 waarde i = I2
(2)
ra(2)
23
10.1.1
Code segment procedure declaratie
τ (PROC p; block p) : proc entry lab p: τ (block p) proc exit’ dst := pop(returnstack) proc exit { jump dst 10.1.2
; o.a. geheugenbeheer ; o.a. geheugenbeheer
} return
Code bij een procedure aanroep
τ (p) :
retlab:
10.2
parameter prelude ; klaarzetten van de parameters push(returnstack,retlab) } call lab p jump lab p parameter postlude ; evt result parameters kopi¨eren
Representatie AR van een (procedure) block
1. plaats van variabele of parameter in AR, 2. toegang tot variabele in een levend AR, 3. instructies bij block entry/exit en bij proc entry/exit 4. geheugenbeheer 5. parameter overdracht en instructies in parameter prelude/postlude. Conventie: identifier (variabele identifier) om een variable in de programmatekst aan te geven. naam (variabele naam) om een variabele tijdens compilatie aan te geven. adres om een variabele tijdens de uitvoering van het vertaalde programma te vinden. 10.2.1
Naamgeving binnen blocks (of hoofdprogramma)
Vb2: B0 : DECLARE a, b, c : INTEGER; BEGIN ... B1 : DECLARE d, e, f : INTEGER; BEGIN ... d ... b ... END B1 ; ... B2 : DECLARE g, h : INTEGER; BEGIN ... h ... c ... END B2 ; END B0 ;
24
gereserveerd geheugen
6 5 4 3 2 1 0
f e d c b a
h g Activation B1
Activation B2
Activation B0
Plaats B0 B1 B2
-
direct bereikbare identifiers a, b, c a, b, c, d, e, f a, b, c, g, h
-
-
tijd
namen (= adressen) 0, 1, 2 0, 1, 2, 3, 4, 5 0, 1, 2, 3, 4
Naamgeving: Opeenvolgende identifiers in een block krijgen opeenvolgende namen. De eerste identifier in het buitenste block krijgt de naam 0 (nul). De eerste identifier in een binnenblock krijgt de naam 1+ naam van de laatste identifier uit het direct omvattende block. 10.2.2
Naamgeving in een programma met procedures
PROGRAM vb3; VAR a, b, c :
INTEGER; (* voorlopige namen:
PROCEDURE p; VAR d, e, f : BEGIN ... END (* p *) PROCEDURE q; VAR g, h :
0, 1, 2 *)
INTEGER (* voorlopige namen:
INTEGER (* voorlopige namen:
0, 1, 2 *)
0, 1 *)
PROCEDURE r; VAR i, j, k : INTEGER (* voorlopige namen 0, 1, 2 *) BEGIN ... p2 ... r2 ... END (* r *) BEGIN ... r1 ... END (* q *) BEGIN ... p1 ... END (* vb3 *)
q ...
25
gereserveerd geheugen
11 10 9 8 7 5 4 3 2 1 0
c b a
f e d
h g p1
-
Plaats vb3 p1 q r1
p2 r2
direct bereikbare identifiers a, b, c a, b, c d, e, f a, b, c g, h a, b, c g, h i, j, k a, b, c d, e, f a, b, c g, h i, j, k
k j i
f e d
p2
k j i
-
r2
r1
-
-
q
vb3
-
-
tijd
verband tussen namen en adressen adres = naam adres = naam adres = naam+3 adres = naam adres = naam+3 adres = naam adres = naam+3 adres = naam+5 adres = naam adres = naam+8 adres = naam adres = naam+3 adres = naam+8
Dit gaan we verder in detail uitwerken. Een naam is nu een paar. We houden een functie display bij, zodanig dat de naam (x.PN,disp) wordt afgebeeld op adres(x) = display(x.PN) + disp. Implementatie van de functie display kan op drie manieren gerealiseerd worden: 1. Tijdens de uitvoering van de huidige procedure (curr) zijn de functiewaarden van display opgeslagen in de registers R.0 tot en met R.curr.PN (R.l = display(l)). Het assignment k := g (met name(k)=(2,2) en name(g)=(1,0)) wordt dan omgezet naar: M(R2+2) := M(R1+0) 2. Tijdens de uitvoering van de huidige procedure zijn de functiewaarden van display opgeslagen in een tabel in het geheugen. Als D0 het beginadres is van de tabel wordt het assignment k := g: R0 := M(D0+2); R1 := M(D0+1); M(R0+2) := M(R1+0) 3. Tijdens de uitvoering van de huidige procedure zijn een aantal functiewaarden van display in het geheugen opgeslagen. Deze opgeslagen waarden vormen een linked list: de statische keten (static chain). De overige functie-waarden zijn opgeslagen in registers; met name zit in register LNB (local name base) display(curr). Merk op dat k nu naam (2,3) heeft, omdat plaats (2,0) nu de start van de statische keten (static link (SL)) bevat. Het assignment k := g wordt nu: R0 := M(LNB); M(LNB+3) := M(R0+0) 4. We hebben nog geen rekening gehouden met het korrekt terugplaatsen van de oude LNB bij het verlaten van een procedure. Daarom passen we opnieuw de naamgeving aan, in r2 beginnen de lokalen nu bij 2 (ipv. 0), en in p2 bij 1 (ipv. 0).
26
10.2.3 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
10.3
Geheugengebruik tijdens de activation van r2 k j i old LNB SL k j i old LNB SL h g
6
AR r2 6 3 ?
Vertaling van k := g (in r): R0 := M(LNB) M(LNB+4) := M(R0 +1)
6
AR r1 3 3 ? 6
AR q
old LNB 0 ? c 6 b AR vb3 a ?
Voorbeeld van gebruik van functies als parameters
PROGRAM form; VAR s1, s2 : INTEGER; FUNCTION kwadr(v: INTEGER) : INTEGER; BEGIN kwadr := v*v END (* kwadr *); FUNCTION derdem(v: INTEGER) : INTEGER; BEGIN derdem := v*v*v END (* derdem *); PROCEDURE sommeer(van, tot : INTEGER; FUNCTION f(i : INTEGER) : INTEGER; VAR som : INTEGER); VAR k : INTEGER; BEGIN som := 0; for k := van TO tot DO som := som + f(k); END (* sommeer *) BEGIN sommeer(0, 100, kwadr, s1); sommeer(0, 100, derdem, s2); END (* form *) Dit is duidelijk een verrijking van de brontaal!
27
10.3.1
Formele procedure parameters
PROGRAM vb4; PROCEDURE a (PROCEDURE fp); PROCEDURE b; BEGIN ... fp ... END (* b *); BEGIN ... b ... END (* a *); PROCEDURE c; PROCEDURE d; PROCEDURE e; BEGIN ... END (* e *) BEGIN ... a(e) ... END (* d *) BEGIN ... a1 (d) ... END (* c *); BEGIN ... c ... END (* vb4 *)
10.3.2
Geheugengebruik in vb4
Herinner je dat we in procedures met P N = 1 de namen van lokale variabelen bij 1 beginnen te nummeren en voor P N ≥ 2 bij 2 beginnen te nummeren. In de volgende figuur zien we het geheugengebruik op het moment dat e aangeroepen is.
28
a8 6
a7
old LNB: a6 AR e a4 ? SL: 6
a6
a5
old LNB: a5 AR b a5 ? SL: param fp: e 6 AR a2 a 4 old LNB: ? 6
a4
old LNB: a3 AR d a1 ? SL:
a3
old LNB: a2 AR b a2 ? SL:
6
6
display(0..3) = (0,a1 ,a4 ,a7 )
display(0..2) = (0,a5 ,a6 )
display(0..1) = (0,a5 )
display(0..2) = (0,a1 ,a4 )
display(0..2) = (0,a2 ,a3 )
display(0..1) = (0,a2 )
AR a1 a2
a1
old LNB: a1 ? param fp: d 6 AR c old LNB: 0 ? 6
display(0..1) = (0,a1 )
display(0..0) = (0)
AR vb4 .
0
?
Procedure b weet niet wie procedure fp in werkelijkheid is. Als b de parameter aan wil roepen heeft hij de SL van fp nodig en zijn startadres. Een formele procedure parameter wordt dus op de stack gerepresenteerd door een paar (startadres,static link).
29
