Jeśli nie zaznaczono inaczej, polecenie brzmi: stwórz najprostszy mozliwy automat LR (LR(0)<SLR(1)<LALR(1)<LR(1)) dla podanej gramatyki.
Standardowa konwencja: symbole terminalne złożone z małych liter i symboli (+,*,;,etc); symbole nieterminalne pisane wielkimi literami, pierwsza produkcja wyznacza symbol startowy)
0. Stwórz automat dla gramatyki z wykładu:
E -> E + T | T
T -> T * F | F
F -> n
dla pełnosci mozna też dodać produkcję
F -> (E)
1. (Ullman 4.35)
E -> E + T | T
T -> T F | F
F -> F * | a | b
2.
L -> ε | S L
S -> E | if E S | { L }
E -> id | id ( E )
3.
S -> ε | S E ; | S id = E ;
E -> id | num | ( E ) | - E
4. (Ullman 4.39)
S -> A a | b A c | d c | b d a
A -> d
5.(Ullman 4.40)
S -> A a | b A c | B c | b B a
A -> d
B -> d
6.
E -> A | A : A
A -> id | [ ] | [ L ]
L -> A | A , L
7. ( z kolokwium)
Dana jest gramatyka G:
A -> A x B | B
B -> B y C | C
C -> z A z | x
Czy można zbudować parser LR(0) dla gramatyki G ?
Czy można zbudować parser SLR dla gramatyki G ?
Czy można zbudować parser LR(1) dla gramatyki G ?
8. (z kolokwium)
Dana jest gramatyka języka K1Z3:
A → x C
A → B z
A → ε
B → ε
C → x B
C → x C y
Czy ta gramatyka jest LR(0) ? Czy jest SLR(1) ? Czy jest LALR(1) ? Czy
jest LR(1) ?
Odpowiedź na każde pytanie uzasadnij konstrując, za pomocą
odpowiedniej metody, tablicę sterującą analizatora składniowego lub
wskazując, dlaczego nie da się tego zrobić.
9. Do jakich klas LR/LL należy gramatyka
E → E E + | E E * | n
10. Wykaż, że gramatyka
S -> aF | bG
F -> Xc | Yd
G -> Xd | Yc
X -> ZA
Y -> ZB
Z → ε
A → ε
B → ε
jest LL(1), ale nie LALR(1)
11. (kolokwium 2010)
Dana gramatyka G (symbolem startowym jest A)
A →abb
A → B
B → bBa
B → ε
(a) Sprowadź G do postaci LL(1) i oblicz wszystkie zbiory SELECT.
(b) Do jakich klas spośród LR(0),SLR(1),LALR(1),LR(1) należy G? Odpowiedź uzasadnij.
12. (kolokwium 2011/12)
Dana jest gramatyka G o symbolu początkowym A:
A → ABs | C
B → CBw | C
C → t | uAs
(s,t,u,w są symbolami terminalnymi).
(a) Czy dla języka L(G) można zbudować analizator składniowy metoda zejść rekurencyjnych ? Jeśli tak, to posługując się nią napisz taki analizator. Jeśli nie jest to możliwe, wyjaśnij dlaczego.
(b) Zbuduj tablice sterującą analizatora składniowego LR dla gramatyki G lub udowodnij, że nie jest to możliwe.