Teoria kompilacji i kompilatory (2021/22)

Zadanie 1 (5 pkt.) Mamy gramatykę z następującymi produkcjami:
S⇒S# ∣ LS \Rightarrow S\#\ |\ L
L⇒a(S) ∣ aL \Rightarrow a(S)\ |\ a
Należy zbudować dla tej gramatyki parser LL(k) i przeparsować napis wejściowy:
a(a#)#a(a\#)\#

  1. Usunąć lewostronną rekursję
    S⇒LS′S \Rightarrow LS'
    S′⇒#S′ ∣ ϵS' \Rightarrow \#S'\ |\ \epsilon
    L⇒a(S) ∣ aL \Rightarrow a(S)\ |\ a

  2. Usunąć lewostronną faktroyzację
    S⇒LS′S \Rightarrow LS'
    S′⇒#S′ ∣ ϵS' \Rightarrow \#S'\ |\ \epsilon
    L⇒aL′L \Rightarrow aL'
    L′⇒(S) ∣ ϵL' \Rightarrow (S)\ |\ \epsilon

  3. Wyznaczyć zbiory FIRST i FOLLOW

    FIRST FOLLOW
    SS aa $,)\$, )
    S′S' #,ϵ\#, \epsilon $,)\$, )
    LL aa #,$,)\#, \$, )
    L′L' (,ϵ(, \epsilon #,$,)\#, \$, )

  4. Zbudować tablicę parsera
    1. S⇒LS′1.\ S \Rightarrow LS'
    2. S′⇒#S′2.\ S' \Rightarrow \#S'
    3. S′⇒ϵ3.\ S' \Rightarrow \epsilon
    4. L⇒aL′4.\ L \Rightarrow aL'
    5. L′⇒(S)5.\ L' \Rightarrow (S)
    6. L′⇒ϵ6.\ L' \Rightarrow \epsilon

    aa #\# (( )) $\$
    SS (LS′,1)(LS', 1)
    S′S' (#S′,2)(\#S', 2) (ϵ,3)(\epsilon, 3) (ϵ,3)\epsilon, 3)
    LL (aL′,4)(aL', 4)
    L′L' (ϵ,6)(\epsilon, 6) ((S),5)((S), 5) (ϵ,6)(\epsilon, 6) (ϵ,6)(\epsilon, 6)

  5. Przeparsować napis wejściowy a(a#)#a(a\#)\#

    • %\% - dno stosu
    • $\$ - koniec wejścia
    stos wejście przejścia
    S%S\% a(a#)#$a(a\#)\#\$ ϵ\epsilon
    LS′%LS'\% a(a#)#$a(a\#)\#\$ 11
    aL′S′%aL'S'\% a(a#)#$a(a\#)\#\$ 1,41, 4
    L′S′%L'S'\% (a#)#$(a\#)\#\$ 1,41, 4
    (S)S′%(S)S'\% (a#)#$(a\#)\#\$ 1,4,51, 4, 5
    S)S′%S)S'\% a#)#$a\#)\#\$ 1,4,51, 4, 5
    LS′)S′%LS')S'\% a#)#$a\#)\#\$ 1,4,5,11, 4, 5, 1
    aL′S′)S′%aL'S')S'\% a#)#$a\#)\#\$ 1,4,5,1,41, 4, 5, 1, 4
    L′S′)S′%L'S')S'\% #)#$\#)\#\$ 1,4,5,1,41, 4, 5, 1, 4
    S′)S′%S')S'\% #)#$\#)\#\$ 1,4,5,1,4,61, 4, 5, 1, 4, 6
    #S′)S′%\#S')S'\% #)#$\#)\#\$ 1,4,5,1,4,6,21, 4, 5, 1, 4, 6, 2
    S′)S′%S')S'\% )#$)\#\$ 1,4,5,1,4,6,21, 4, 5, 1, 4, 6, 2
    )S′%)S'\% )#$)\#\$ 1,4,5,1,4,6,2,31, 4, 5, 1, 4, 6, 2, 3
    S′%S'\% #$\#\$ 1,4,5,1,4,6,2,31, 4, 5, 1, 4, 6, 2, 3
    #S′%\#S'\% #$\#\$ 1,4,5,1,4,6,2,3,21, 4, 5, 1, 4, 6, 2, 3, 2
    S′%S'\% $\$ 1,4,5,1,4,6,2,3,21, 4, 5, 1, 4, 6, 2, 3, 2
    %\% $\$ 1,4,5,1,4,6,2,3,2,31, 4, 5, 1, 4, 6, 2, 3, 2, 3

Zadanie 2 (5 pkt.) Dana jest gramatyka G=({n,#,(,)},{E},{E→E#n ∣ (E) ∣ n},E)G=(\{n,\#,(,)\}, \{E\}, \{E \rightarrow E\#n\ |\ (E)\ |\ n\}, E),
a) proszę przedstawić poszczególne kroki konstrukcji parsera SLR(1)
b) proszę przedstawić działanie parsera (stos, wejście i podejmowane akcje) dla łańcucha:
(n#n)#n(n\#n)\#n
c) proszę przedstawić wywód tego łańcucha (o ile istnieje) znaleziony w wyniku działania parsera

  1. Wzbogacić gramatykę
    0. E′⇒E0.\ E' \Rightarrow E
    1. E⇒E#n1.\ E \Rightarrow E\#n
    2. E⇒(E)2.\ E \Rightarrow (E)
    3. E⇒n3.\ E \Rightarrow n
  2. Funkcje przejścia
    I0={[E′⇒∙E],[E⇒∙E#n],[E⇒∙(E)],[E⇒∙n]}I_0 = \{[E' \Rightarrow \bullet E], [E \Rightarrow \bullet E\#n], [E \Rightarrow \bullet (E)], [E \Rightarrow \bullet n]\}
    I1=GOTO(I0,E)={[E′⇒E∙],[E⇒E∙#n]}I_1 = \text{GOTO}(I_0, E) = \{[E' \Rightarrow E \bullet], [E \Rightarrow E \bullet \#n]\}
    I2=GOTO(I0,()={[E⇒(∙E)],[E⇒∙E#n],[E⇒∙(E)],[E⇒∙n]}I_2 = \text{GOTO}(I_0, {(}) = \{[E \Rightarrow (\bullet E)], [E \Rightarrow \bullet E\#n], [E \Rightarrow \bullet (E)], [E \Rightarrow \bullet n]\}
    I3=GOTO(I0,n)={[E⇒n∙]}I_3 = \text{GOTO}(I_0, n) = \{[E \Rightarrow n \bullet]\}
    I4=GOTO(I1,#)={E⇒E#∙n}I_4 = \text{GOTO}(I_1, \#) = \{E \Rightarrow E\# \bullet n\}
    I5=GOTO(I2,E)={[E⇒(E∙)],[E⇒E∙#n]}I_5 = \text{GOTO}(I_2, E) = \{[E \Rightarrow (E \bullet )], [E \Rightarrow E \bullet \#n]\}
    I2=GOTO(I2,()={[E⇒(∙E)],[E⇒∙E#n],[E⇒∙(E)],[E⇒∙n]}I_2 = \text{GOTO}(I_2, {(}) = \{[E \Rightarrow (\bullet E)], [E \Rightarrow \bullet E\#n], [E \Rightarrow \bullet (E)], [E \Rightarrow \bullet n]\}
    I3=GOTO(I2,n)={[E⇒n∙]}I_3 = \text{GOTO}(I_2, n) = \{[E \Rightarrow n \bullet]\}
    I6=GOTO(I4,n)={[E⇒E#n∙]}I_6 = \text{GOTO}(I_4, n) = \{[E \Rightarrow E\#n \bullet]\}
    I7=GOTO(I5,))={[E⇒(E)∙]}I_7 = \text{GOTO}(I_5, {)}) = \{[E \Rightarrow (E) \bullet]\}
    I4=GOTO(I5,#)={E⇒E#∙n}I_4 = \text{GOTO}(I_5, \#) = \{E \Rightarrow E\# \bullet n\}
  3. Wyznaczyć zbiory FIRST i FOLLOW
    FIRST FOLLOW
    E′E' (,n(, n $\$
    EE (,n(, n $,#,)\$, \#, )
  4. Zbudować tablicę parsera
    #\# nn (( )) $\$ EE
    I0I_0 s3s_3 s2s_2 I1I_1
    I1I_1 s4s_4 acc\text{acc}
    I2I_2 s3s_3 s2s_2 I5I_5
    I3I_3 r3r_3 r3r_3 r3r_3
    I4I_4 s6s_6
    I5I_5 s4s_4 s7s_7
    I6I_6 r1r_1 r1r_1 r1r_1
    I7I_7 r2r_2 r2r_2 r2r_2
  5. Przeparsować łańcuch (n#n)#n(n\#n)\#n
    stos wejsćie akcja
    0 (n#n)#n$(n\#n)\#n\$ przesunięcie
    0 ( 2 n#n)#n$n\#n)\#n\$ przesunięcie
    0 ( 2 n 3 #n)#n$\#n)\#n\$ redukcja zgodnie z E⇒nE \Rightarrow n
    0 ( 2 E 5 #n)#n$\#n)\#n\$ przesunięcie
    0 ( 2 E 5 # 4 n)#n$n)\#n\$ przesunięcie
    0 ( 2 E 5 # 4 n 6 )#n$)\#n\$ redukcja zgodnie z E⇒E#nE \Rightarrow E\#n
    0 ( 2 E 5 )#n$)\#n\$ przesunięcie
    0 ( 2 E 5 ) 7 #n$\#n\$ redukcja zgodnie z E⇒(E)E \Rightarrow (E)
    0 E 1 #n$\#n\$ przesunięcie
    0 E 1 # 4 n$n\$ przesunięcie
    0 E 1 # 4 n 6 $\$ redukcja zgodnie z E⇒E#nE \Rightarrow E\#n
    0 E 1 $\$ akceptacja
  6. Przedstawić wywód dla łańcucha (n#n)#n(n\#n)\#n
    E⇒E#n⇒(E)#n⇒(E#n)#n⇒(n#n)#nE \Rightarrow E\#n \Rightarrow (E)\#n \Rightarrow (E\#n)\#n \Rightarrow (n\#n)\#n