Zadanie 1

Poniższa gramatyka opisuje strukturę instrukcji warunkowych w wielu językach programowania ('i' jest skrótem dla 'if', 'e' jest skrótem dla 'else', 'x' oznacza inne instrukcje, 'w' oznacza warunek (wyrażenie logiczne).

instr : 'i' war instr elsei | 'x' ;
elsei : /* puste */ | 'e' instr ;
war : 'w' ;

'bison' dla tej gramatyki zgłasza jeden konflikt przesunięcie/redukcja. Domyślny mechanizm rozstrzygania konfliktów 'bison'-a wybiera w tym miejscu przesunięcie co wiąże część 'elsei' z najbliższą instrukcją 'i'. Dobrać deklaracje priorytetu tak by 'bison' wykonał redukcję. Jaki będzie efekt tej modyfikacji dla języka akceptowanego przez analizator syntaktyczny? Czy można w ten sposób spowodować by 'bison' związał część 'elsei' z najdalszą instukcją 'i'?

Uwaga: Polecenie `info bison' pozwala przeglądać instrukcję `bison'-a. Jeśli w części `Grammar File' punkt `Declarations' wybierzemy podpunkt `Precedence Decl' to dostaniemy podsumowanie informacji o deklaracjach priorytetu (warto też odwiedzić podpunkt `Operator Precedence' w części o algorytmie `bison'-a).

Zadanie 2

Rozważmy język składający się z poprawnie zagnieżdżonych nawiasów dwu rodzajów (tzn. jedna para to '(' i ')' a druga to '[' i ']') , z tym że stopień zadnieżdżenia nie może przekroczyć ustalonego N. Uzasadnić że język ten można opisać gramatyką bezkontekstową wielkości proporcjonalnej do N. Pokazać że minimaly automat deterministyczny akceptujący ten język musi mieć wykładniczą względem N liczbę stanów. Porównać to z przypadkiem nawiasów jednego rodzaju.

Zadanie 3

Na symbolach pomocniczych gramatyki bezkontektowej wprowadzamy relację równoważności ~ zdefiniowaną następująco: A ~ B wtedy i tylko wtedy gdy B pojawia się w pewnej frazie wyprowadzanej z A i A pojawia się w pewnej frazie wyprowadzanej z B. Klasy abstrakcj tej relacji nazywamy klasami wzajemnie rekursywnych symboli pomocniczych. Rozważmy teraz relację "B pojawia się w pewnej frazie wyprowadzanej z A". Pokazać że ta relacja jest dobrze zdefiniowana na klasach abstrakcji ~ (tzn. wynik nie zależy od wyboru reprezentantów) i zadaje porządek częściowy. Powiemy że gramatyka jest mocno regularna jeśli dla każedej klasy wzajemnie rekursywnych symboli pomocniczych nowa gramatyka w której pozostałe symbole traktujemy jako symbole końcowe jest lewostronnie lib prawostronnie liniowa. Gramatykę nazywamy lewostronnie liniową jeśli symbole pomocnicze występują tylko jako pierwsze symbole po prawej stronie reguł. Podobnie Gramatykę nazywamy prawostronnie liniową jeśli symbole pomocnicze występują tylko jako ostatnie symbole po prawej stronie reguł. W szczególności prawa strona dowolnej reguły zawiera co najwyżej jeden symbol pomocniczy. Pokazać że gramatyka mocno regularna definiuje język regularny. Pokazać że minimalny automat skończony rozpoznający język definiowany przez gramatykę mocno regularną może mieć rozmiar wykładniczy względem rozmiaru gramatyki.

Zadanie 4

Niekiedy chcemy aproksymować gramatyki bezkontekstowe gramatykami definującymi języki regularne. Poniżej podajemy jedną z takich konstrukcji. Najpierw wyznaczamy klasy wzajemnie rekursywnych symboli pomocniczych. Jeśli gramatyka otrzymana przez potraktowanie pozostałych symboli gramatyki jako końcowe nie jest prawostronnie liniowa to dla każdego symbolu danej klasy wprowadzamy nowy dodatkowy symbol. Dalej oryginalne symbole klasy będę oznaczał przez A_i (z odpowiednim i) a dodane przez B_i. Regułę

A_0 : a_0A_1a_1A_2...A_na_n ;

gdzie a_i są ciągami symboli traktowanych jako końcowe (tzn. symboli końcowych oraz pomocniczych spoza naszej klasy), zastępuję kolekcją reguł:

A_0 : a_0A_1 ;
B_1 : a_1A_2 ;
...
B_n : a_nB_0 ;

Ponadto dodaję reguły mówiące że dowolne B_i może wyprowadzać ciąg pusty. Pokazać że tak otrzymana gramatyka jest mocno regularna i że definowany przez nią język zawiera język generowany przez oryginalną gramatykę. Jak wygląda gramatyka otrzymana z następującej gramatyki dla wyrażeń:

E : E '+' T | T ;
T : T '*' F | F ;
F : '(' E ')' | 'x' ;

Komentarz1: Idea konstrukcji jest taka że w nowej gramatyce A_i wyprowadza to co w starej plus ogon, tzn. pozostałą część słowa. B_i wyprowadza ogon, czyli to co jest po A_i. Jeśli porównać wyprowadzenia w obu gramtykach to w nowej A_i pojawia się na początku wyprowadzenia A_i w starej a B_i na końcu wyprowadzenia A_i w starej.

Komentarz2: Ta konstrukcja pozwala aproksymować przekrój języków bezkontekstowych: dla języków regularnych przekrój daje się obliczać. Jeśli aproksymacje się nie przecinają to oryginalne jezyki też sie nie przecinają. Jeśli aproksymacje się przecinają to można znaleźć najkrótsze słowo w przekroju aproksymacji. Jeśli to słowo należy do oryginalnych języków to przekrój jest niepusty. W przeciwnym razie potrzebujemy lepszą aproksymację (konstrukcję powyżej można zmodyfikować tak by otrzymać ciąg coraz lepszych aproksymacji).