Zadania „pomagające” przygotować się do zaliczenia laborek - języków formalnych u Pana Sokołowskiego,

Nad każdym rysunkiem jest to co udało się z niego rozczytać (jeśli ktoś ma sposób lub sokoli wzrok by uzupełnić ........wykropkowankę.......... to proszę o uzupełnienie braków i wysłanie do poczekalni z nową daną i godziną w nazwie!!!!!

Nie ponoszę odpowiedzialnośći za zamieszczczona tu treść, wspomnę tylko że wcześniejszy rocznik miał „podobne zadania” różniące się danymi rzecz jasna.

WERSJA 1

Zadanie 1

Bla bla ...................................

Rys.	SŁOWA AKCEPTOWANE \ bb abeb babb abb

Uwaga: Słowa ......... lub ...... ..... ......... spełnione są wszystkie następujące warunki

- doszliśmy do stanu .........

-

-

zadanie2 Program (rekursywny parser zstępujący) podany na sąsiedniej stroniesprawdza zgodność ciągu znaków na wejściu z gramatyką posiadającą jeden nieterminal <wyrażenie>. Tylko sprawdza - to znaczy nie drukuje drzewa rozbioru a jedynie komunikat o zgodności ciągu z gramatyką (poprawność) lub niezgodność (błędność). Ciąg znaków na wejściu musi się kończyć kropką i zmianą wiersza, których do samego słowa opisanego przez gramatykę nie wliczamy. W ramkę obok wpisać gramatykę według której działa parser

<wyrażenie>::=

Studia dzienne wyklad 31.1.2005

2

Zadanie 3

Gramatyka (P)::= p | <P>q |<P>r <P>q jest niejednoznaczna

1. za 5 punktów: narysować dwa rózne drzewa wywodów słowa prpqqq

Drzewo 1 p r p q q q

Drzewo 2 p r p q q q

2. za 15 pkt narysować drzewo które dla tego słowa (skon......tuje....) ..........

występujący posługujący sie następującą tabelę pierwszeństwa

<P>

p

r

q

<P>

=

=

p

>

>

r

=

<

q

>

>

Drzewo: p r p q q q

Wykład 31.1.2005

//Parser rekursywny do zadania 2

(sorry ale nie chce mi się tego przepisywac )

Zadanie 4 Zakładamy że na każdą zmienna znakową przewidziane jest rezerwowanie 1 bajtu pamieci a na zmienna calkowita 4 bajty. Zakladamy też, że dane składające się na zmienną tablicową tab o deklaracji Struci { char a; int b, c; } tab [10][30]; zajmują spójny obszar pamięci zaczynający się od bajtu o adresie 1000. Które bajty zajmują zmienne wymienione obok

zmienne Pierwszy bajt Ostatni bajt Tab[0][0] Tab[5][10],a Tab[3][2],b Tab[0][0],c

Zadanie 5

W pamięci maszyny zostały umieszczone następujące liczby

Adres:	600	601	602	603	604	605	606	607
Zawartość:	4	601	-10	6	4	2	3	5

Następnie wykonano taki program(obok w ramce podaje znaczenie komend)

Loadn 0 Store 601 Load 600 Store 602 E: load 602 Ifnp K Decr 602 Load 601 Add 603 +[602] Goto E: K:

Loadn liczba - umieścić w rej. artmetycznym podaną liczbę Load adres - umieścić w rej. artmetycznym liczbę spod podanego adresu Store adres - umieścić pod podanym adresem zawartość rej. artmetycznego Sub adres - odjąc od liczby w rej. artmetycznym liczbę spod podanego adresu (wynik w rej. artmetycznym) Add adres - dodać od liczby w rej. artmetycznym liczbę spod podanego adresu (wynik w rej. artmetycznym) Decr adres - zmniejszyc liczbe pod podanym adresem o 1 Goto etyk - skoczyć do podanej etykiety Ifnp etyk - jeśli zawartośc rej. artmetycznego niedodatnia to skoczyć do podanej atykiety

Wpisz poniżej stan pamięci po wykonaniu tego programu

Adres:	600	601	602	603	604	605	606	607
Zawartość:

Uwaga: W tym zadaniu mamy do czynienia wyłącznie z liczbami całkowitymi i ....damy, że zajmują one osobne pozycje pamięci. Adres postaci „k +[l]” oznacza adres modyfikowany zawartością liczby spod adresu l.

WERSJA 2 (niekompletna , ale zawsze)

Treść zadań taka sama dla wszystkich wersji testów, tylko pozmieniane dane…

Zadanie 1

Poniższa gramatyka jest niejednoznaczna

<D> ::= <C> | <D> <C>

<C> ::= p | <C> > <C> | > <C> >

Narysuj dwa różne drzewa wywodu w tej gramatyce dla słowa p>p>p>p>p

<D>

p > p > p > p > p

<D>

Zadanie 2

Dla poniższego przykłady narysuj automat i napisz gramatyke

	a	b	c
P	Q	Q	Q
Q	R	R	R
R	P	P	P

Na wejściu jest Q

Na wyjściu P,R

Zadanie 3

Zamienić gramatykę bezkontekstową z zad. 1 na równoważną gramatykę bez lewostronnej rekursji ale za to z iteracją

Zadanie 4

Przy próbie wyznaczenia relacji pierwszenstwa dla gramatyki z zadania pierwszego może się zdarzyć że dla jakichś dwóch symboli p i q zachodzi jednocześni
oraz p < ∙ q.

Wymień poniżej wszystkie pary <p,q> dla których taki konflikt istotnie występuje.

Jak widać z fotki zadane zostały 2 pytania które nadal zostają bez odpowiedzi

1. w ten sposób pozbyliśmy się rekursji ale co z tą iteracją?

2. Jak to dalej szło? To porównanie firstów i lastów by można było wstawić wartości =, <, > do tabeli? Jak ktoś ma to w notatkach niech dopisze sposób konstrukcji + odpowiedzi do tabeli.

Liczę że wspólnymi siłami damy radę.

Prawdopodobnie niedługo nie mogę potwierdzić będę mógł przedstawić Wam podobną spreparowaną wersję tylko tym razem w celu przygotowania się do egzaminu, ale nie jest to na razie potwierdzone.

---