Zad. 1
Przekształć poniższą gramatykę do postaci LL(1), oblicz zbiory SELECT
oraz wszystkie potrzebne zbiory First i Follow:
\(\begin{align*}
L &\to E , L \mid E\\
E &\to( L ) \mid \varepsilon
\end{align*}
\)
Zad. 2
Polecenie jak wyzej:
\(\begin{align*}
L &\to L ; S \mid S\\
S &\to\{ L \} \mid \varepsilon
\end{align*}
\)
Zad. 3
Przekształćdo postaci LL(1) poniższą gramatykę, oblicz zbiory SELECT,
zrealizuj analizator składniowy działający metoda zejść rekurencyjnych
i dopisz do niego instrukcje liczące wartość wyrazenia (w pierwszej
produkcji najpierw liczymy "*", później "+"):
\(\begin{align*}
E &\to E * E + F \mid F\\
F &\to( E ) \mid num
\end{align*}
\)
Zad. 4
Przeksztalc ponizsza gramatyke do postaci LL(1), oblicz zbiory SELECT
Narysuj i uprosc diagramy skladniowe. Wyjasnij, jak na ich podstawie
zbudowac analizator skladniowy metoda zejsc rekurencyjnych:
W -> W @ P | P
P -> id | liczba | id ( L ) | ( W ) | ( W ) P
L -> W | W , L
Zad. 5-7
Przeksztalc do postaci LL(1) i oblicz zbiory SELECT dla gramatyk:
E -> E F F | epsilon
F -> G ? F F | G
G -> ( E ) | id
I -> J = I I | J
J -> J ? | id | id + id | < L >
L -> L I | epsilon
E -> E F | E F G | F
F -> id E ?
G -> G ( E ) | ( E ) | =
Zad 8 (z kolokwium)
Poniżej znajduje się gramatyka języka K1Z2, którego słowa reprezentują
wyrażenia arytmetyczne. Obok każdej produkcji jest informacja o
znaczeniu opisywanej przez nią konstrukcji języka:
E → ε wyrażenie o wartości 0
E → F - E różnica wartości wyrażeń F i E
E → F wartość wyrażenia F
F → F F * iloczyn wartości dwóch wyrażeń F
F → F ! silnia wartości wyrażenia F
F → G wartość wyrażenia G
G → ( E ) wartość wyrażenia E
G → + G G suma wartości dwóch wyrażeń G
Tekstowy zapis słów języka K1Z2 jest ciągiem znaków "-", "*", "!",
"(", ")" i "+", z których każdy reprezentuje odpowiedni symbol
terminalny gramatyki. Żadnych innych znaków, oprócz wymienionych
powyżej, w tekstowym zapisie słow tego języka nie ma.
Napisz program, który wczyta z wejścia wyrażenie języka K1Z2 i wypisze
na wyjście jego wartość.
Analizator składniowy będący częścią programu zrealizuj za pomocą
metody zejść rekurencyjnych.
W przypadku wykrycia błędu składniowego program powinien wypisać na
wyjście słowo "BLAD".
Uwaga: przymujemy, że silnia liczby mniejszej niż 1 jest równa 1.
Zad 9 (*)
a. Wykaż, że gramatyka
S → aSb | ab
jest LL(2), ale nie LL(1)
b. Wykaż, że gramatyka
S → aAaa | bAba
A → b | ε
jest LL(2), ale nie jest silnie LL(2)