YACC
Zadanie 1

Poprawny plik wejściowy zbudowany jest ze znaków * (gwiazdka), które tworzą w pliku kształt odwróconego trójkąta prostokątnego (wnętrze trójkąta też jest wypełnione znakami *). Oznacza to, że ostatnia linia w takim pliku zawiera dokładnie jeden znak *, przedostatnia linia zawiera dwa znaki *, trzecia linia od końca trzy znaki *, itd. aż do pierwszej linii w tym pliku. Reasumując, każda linia w tym pliku (za wyjątkiem ostatniej) ma zawsze o jeden znak * więcej niż linia, która występuje bezpośrednio po niej. Poprawnie zbudowany plik wejściowy może więc wyglądać następująco:

*****
****
***
**
*

Minimalny rozpatrywany trójkąt prostokątny składa się z dokładnie 1 linii i ma następującą postać:

*

Napisz program, który będzie rozpoznawał czy plik wejściowy zbudowany jest zgodnie z powyższymi założeniami. Jeżeli plik wejściowy jest poprawny, to powinien pojawić się komunikat OK, zaś w przeciwnym razie komunikat: Error. W programie nie wolno korzystać ze zmiennych globalnych.

Uwaga


Zadanie 2

W pliku wejściowym znajduje się ciąg znaków zgodny z wyrażeniem regularnym a*b*c*d*. Należy napisać analizator składniowy, który sprawdzi czy zadane wejście należy do języka anbncmdm, gdzie n, m są >= 1. Jeśli wyrażenie należy do języka należy wyprowadzić napis "OK", a w przeciwnym wypadku "Error".

Dany jest analizator leksykalny o postaci:

%%
[a-d]       { return(yytext[0]); }
" "|\t|\n   { ; }

Przykłady:

wejście:

aabbcccddd

wyjście:

OK

wejście:

abbcccddd

wyjście:

Error

Zadanie 3

W pliku wejściowym dany jest ciąg wywołań funkcji o postaci: nazwa funkcji, lewy nawias okrągły, (być może pusta) lista argumentów, prawy nawias i średnik. Lista argumentów składa się ze standardowych wyrażeń arytmetycznych (operatory '+', '-', '*' oraz liczby) oddzielonych przecinkami. Należy napisać translator tłumaczący wywołania na asembler w następujący sposób:

W programie nie wolno korzystać ze zmiennych globalnych.

Dany jest następujący analizator leksykalny:

%{
#include <stdlib.h>
#include "ytab.h"
%}
%%
\;                      { return(';'); }
\+                      { return('+'); }
\*                      { return('*'); }
\-                      { return('-'); }
\(                      { return('('); }
\)                      { return(')'); }
\,                      { return(','); }
[0-9]+                  { yylval.ival=atoi(yytext);
                          return(num);
                        }
[A-Za-z_][A-Za-z0-9_]*  { yylval.text=strdup(yytext);
                          return(id);
                        }
" "|\t|\n               { ; }

Przykład:

wejście:

fun1(3+4,5);
fun2(4*5+2,9,6);
fun3();

wyjście:

push 7
push 5
call fun1
add sp,2
push 22
push 9
push 6
call fun2
add sp,3
call fun3

Rozwiązanie:


Zadanie 4

Plik wejściowy składa się z pewnej liczby wierszy, które zbudowane są z liter 'x' (tylko małe litery). Litery te tworzą w takim pliku kształt trójkąta. Oznacza to, że liczba znaków w danym wierszu jest równa dokładnie numerowi tego wiersza licząc od początku pliku. A więc, pierwszy wiersz w pliku ma numer 1 i zawiera pojedynczą literę 'x', wiersz drugi ma numer 2 i musi zawierać dwie litery 'x', z kolei wiersz trzeci posiada numer 3 i trzy litery 'x', itd. Należy napisać program w YACC'u, który dla danego pliku wejściowego zbada fakt, czy jest on zbudowany zgodnie z powyższymi regułami. Jeśli tak, to powinien zostać wyświetlony napis: "OK", w przeciwnym wypadku musi pojawić się napis "Error !!!".

Na przykład dla poniższego pliku wejściowego:

x
xx
xxx
xxxx
xxxxx

Powinien pojawić się napis:

OK

Zaś na przykład dla pliku:

x
xx

xxxx
xxxxx

musi pojawić się napis:

Error !!!

Uwaga

Analizator leksykalny został już napisany i ma następującą postać:

%{
#include "ytab.h"
%}
%%
x { return('x'); }
\n { return('\n'); }

Napisz program, który (nie używając zmiennych globalnych) będzie rozpoznawał czy plik wejściowy zbudowany jest zgodnie z powyższymi założeniami.


Zadanie 5

Napisać program, który dla danej liczby całkowitej j oraz niepustego ciągu liczb naturalnych c0, c1, ..., cj, ..., cn podaje wartość elementu cj. Jeśli j>n to nie jest wyświetlana żadna liczba.

Wejście: Plik składa się z wiersza, w którym najpierw podawana jest wartość j, a po niej niepusty ciąg liczb poprzedzony znakiem ':'. Elementy ciągu są oddzielone między sobą przecinkami.

Wyjście:jeśli j<=n, to na wyjściu otrzymujemy liczbę cj ujętą w nawiasy prostokątne. W przeciwnym wypadku pojawiają się same nawiasy prostokątne.

Konstruując analizator nie wolno posługiwać się zmiennymi globalnymi.

Przykłady:

Dla pliku o postaci:

2 : 5, 7, 9, 1

Powinniśmy otrzymać wynik:

[9]

Dla pliku o postaci:

4 : 5, 7, 9, 11

Powinniśmy otrzymać wynik:

[]

Analizator leksykalny jest już napisany:

%{
#include <stdio.h>
int yywrap(void);
int yylex(void);
#include "ytab.h"
%} %%
\, { return(','); }
\: { return(':'); }
[0-9]+ { yylval = atoi(yytext); return(num); }
\n { ; }
. { ; }
%%
int yywrap(void)
{
return 1;
}

Rozwiązania:


Zadanie 6

Napisać analizator składniowy sprawdzający, czy wejście należy do języka opisanego wzorcem anbncn (n>=0).

Przykłady:

wejście:

aabbcc

wyjście:

OK

wejście:

aabbc

wyjście:

syntax error

Analizator leksykalny jest już gotowy:

%%
[abc]		{ return(yytext[0]); }
" "|\n	{ ; }

Analizator składniowy też jest już częściowo napisany:

%%
S : A B C
  ;
A : A 'a'
  |
  ;
B : B 'b'
  |
  ;
C : C 'c'
  |
  ;

Należy go uzupełnić.


Zadanie 7

Napisać program sprawdzający poprawność podzbioru wyrażeń logicznych. Wyrażenia ograniczone są do operatorów and i or, stałych true i false i nawiasów.

Na przykład dla pliku wejściowego o postaci:

false or true and (false or true)

powinniśmy otrzymać komunikat

OK

Oto kompletny analizator leksykalny:

%{
#include "ytab.h"
%}
%%
"or"		{ return or; }
"and"		{ return and; }
"true"	{ return true; }
"false"	{ return false; }
"("		{ return '('; }
")"		{ return ')'; }
" " | \n	{ ; }
.		{ yyerror; YY_FATAL("Unexpected character!"); }

i część analizatora składniowego:

%token or and true false
%%
S : E	{ printf("OK\n); }
  ;
E : E or T
  | T
  ;

należy uzupełnić parser


Zadanie 8

Napisać analizator składniowy dla języka anbn. Białe spacje i znaki nowej linii należy pominąć. Jeżeli dane wejściowe są poprawne, program powinien wydrukować odpowiedź "OK", w przeciwnym razie komunikat "Error" poprzedzony numerem linii, w której napotkany został pierwszy błąd. Na przykład, dla poniższych danych wejściowych:

aaa
b
bb

powinniśmy otrzymać odpowiedź:

OK

a dla następującego wejścia:

aaa
ba
bb
powinniśmy uzyskać komunikat o błędzie (numer rozpoczynający linię może być inny):

2: Syntax error

Zadanie 9

Napisać analizator sprawdzający czy dane wejściowe mają postać:

     c1|c2
gdzie c1 jest łańcuchem cyfr oktalnych a c2 jest lustrzanym odbiciem c1. Oba łańuchy mogą być puste - a więc plik składający się tylko ze znaku "|" jest również poprawny. Także dane wejściowe:

123|321

są poprawne, ale

1234|3321

są błędne. Jeżeli dane wejściowe są poprawne analizator powinien dac odpowiedź "OK", a w przeciwnym przypadku "Syntax error". Oto analizator leksykalny:

%%
[0-7]		{ return yytext[0]; }
"|"		{ return '|'; }
.		{ yyerror("illegal character"); YY_FATAL("Error !"); }