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
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
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:
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.
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:
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ć.
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
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 bbpowinniśmy uzyskać komunikat o błędzie (numer rozpoczynający linię może być inny):
2: Syntax error
Napisać analizator sprawdzający czy dane wejściowe mają postać:
c1|c2gdzie 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 !"); }