Zadanie 1

Napisać wyrażenia regularne dla flex-a do rozpoznawania liczb. Mają one rozpoznawać zwykłe liczby całkowite w notacji dziesiętnej, liczby całkowite w notacji szesnastkowej, tak jak w C: `0x1ab' i liczby zmiennopozycyjne (te muszą zawierać kropkę dziesiętną, np: `.001', `100.' `3.1415'). W szczególności chcemy odróżniać liczby dziesiętne, szesnastkowe i zmiennopozycyjne. Uwaga: Zakładamy że liczby dziesiętne i liczby zmiennopozycyjne nie zawierają zer na początku.

Zadanie 2

Mamy następującą gramatykę:

S : S S | 'x'

Jak wygląda język generowany przez tą gramatykę. Pokazać że gramatyka ta nie jest jednoznaczna zaś ilość drzew rozbioru rośnie wykładniczo z długością słowa (dokładnie jest to liczba Catalana: ((2*n-2)!)/(((n-1)!*(n-1)!)*n) ).

Zadanie 3

Zakładamy że każda prawa strona reguły gramatyki zaczyna się od nawiasu otwierającego a kończy się nawiasem zamykającym. Nawiasy nie występują w środku reguły. Ponadto zakładamy że dla różnych symboli pomocniczych prawe strony reguł są różne. Opisać słownie jak można przeprowadzić analizę syntaktyczną dla takiej gramatyki.

Zadanie 4

Napisać gramatykę bezkontekstową opisującą listy składające się z pewnej liczby symboli 'x' oddzielonych średnikami. Dopuszczamy użycie kilku średników do oddzielenia dwu 'x'-ów i średnik na końcu. Np:

x;;x;x;

Zadanie 5

Napisać gramatykę bezkontekstową opisującą listy odzielone średnikami których elementami są listy 'x' oddzielonych precinkami, np:

x,x;x,x,x;x,x

Uwaga: ten opis jest celowo nieprecyzyjny, proszę uzupełnić szczeguły według uznania i wyjaśnić jak się one tłumaczą na gramatykę.

Zadanie 6

Symbolami końcowymi jęzka są nawiasy '(', ')', '[', ']', '{', '}'. Napisać gramatykę dla układów poprawnie zagniżdżonych nawiasów (nawiasowi otwierającemu ma odpowiadać nawias zamykający tego samego rodzaju), np:

([]([][]))[]()

Zadanie 7

Pokazać że gramatyka:

S: A 'r' | B 'l' ;
A: /* puste */ | 'x' A ;
B: /* puste */ | B 'x' ;

jest jednoznaczna i można dla niej podać prosty algorytm analizy syntaktycznej.