Gramatykę bezkontekstową nazywamy regularną jeśli każda prawa strona reguły zawiera co najwyżej jeden symbol pomocniczy i ten symbol występuje na końcu, np:

S : 'x' S
  | 'y' 'z' 't' S
  | 'a'
  ;

Zadanie 1

Uzasadnić że język może być opisany gramatyką regularną wtedy i tylko wtedy gdy jest on rozpoznawany przez automat skończony.

Zadanie 2

Symbolami rachunku zdań są zmienne (wszystkie zmienne są reprezentowane przez pojadynczy symbol), negacja, iloczyn, suma, implikacja i nawiasy. Negacja ma najwyższy priorytet, następnie iloczyn, potem suma. Implikacja ma najniższy priorytet. Iloczyn i suma są łaczne. Dla uniknięcia nieporozumień przyjmiemy że implikacja jest niełączliwa (tzn. wymaga jawnych nawiasów). Napisać gramatykę akceptującą poprawne składniowo zdania rachunku zdań (nie interesuje nas w tej chwili ich wartość logiczna).

Zadanie 3

Dla poniższej gramatyki wyznaczyć symbole wyprowadzające słowo puste. Symbolami końcowymi są ARRAY, CONST, ID, LICZBA, OF, TYPE i znaki pojawiające się w gramatyce.

deklaracje : stale typy ;

stale : stale ';' stala
      | /* puste */
      ;

stala : CONST ID '=' LICZBA ;

typy : typy typ
     | /* puste */
     ;

typ : TYPE ID = typ1 ;

typ1 : ID
     | array '[' LICZBA ']' OF typ1
     ;

Zadanie 4

Wyznaczyć zbiory `FIRST' i 'FOLLOW' dla reguł poniższej gramatyki (symbolem początkowym jest `S').

S : T 'x' ;
T : A | B ;
A : 'a' | /* puste */ ;
B : 'b' | /* puste */ ;

Czy ta gramatyka jest LL(1). Jaki problem ma analizator syntaktyczny?

Zadanie 5

Mamy poniższą gramatykę (w notacji Bisona):

S : B ';' ;
B : 'b' I2 'e' ;
I2 : /* puste */ | I2 I ';'
I : 't' X | 'v' X | 'x' '=' E
  | B | 'i' C 'd' I2 'e'
  | 'i' C 'd' I2 'o' I2 'e'
  | 'w' C 'd' I2 'e' ;
X : 'x' | 'x' ',' X ;
E : 'x' | 'x' '+' E ;
C : E '=' E

Przerobić ją zachowując język, i wprowadzając możliwie małe zmiany, tak by można było użyć metodę LL(1). Wskazówka: Użyć metodę motację EBNF lub diagramy syntaktyczne.

Komentarz1: Dla skrócenia rachunków używam tylko jednoznakowych symboli końcowych, lecz można sobie wyobrażać że 'x' to dowolny identyfikator, 'b', 'd', 'e', 'i', 'o', 't', 'v' i 'w' to słowa kluczowe ("begin", "do", "end", "if", "otherwise", "type", "var" i "while" odpowiednio). Przerobienie tego na porządny język programowania pozostawiam Państwa wyobraźni...

Komentarz2: Reguły dla średnika są tak dobrane by sama instrukcja nie zawieała średnika, ale po każdej musi się pojawić dokładnie jeden średnik.