Spis treści:
Kompilowanie i uruchamianie analizatora składniowego z wykorzystaniem flexa i LLgena (Linux):
| skrypt powłoki | makefile |
|
|
Kompilowanie i uruchamianie analizatora składniowego z wykorzystaniem flexa i yacca (bisona) (Linux):
| skrypt powłoki | makefile |
|
|
Uwagi praktyczne wynikające z wieloletnich obserwacji walki z uruchamianiem programów:
1) nie kombinować zanim nie zbuduje się pomyślnie kilku projektów,
rozpoczynanie od ulepszania przedstawionego procesu często kończy się
porażką,
2) dla każdego zadania pobrać szkielet(y) - optymalizacja (lenistwo) pozostawia często śmieci i/lub błędne modyfikacje w pliku,
3) zwracać uwagę na katalog bieżący (w jednym katalogu edytuję, w innym, co innego, kompiluję i ... nic się nie zmienia),
4) przeczytanie zadania bardzo pomaga w jego rozwiązaniu !
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: Każda linia pliku zakończona jest znakiem końca wiersza (znak końca wiersza występuje także po ostatniej linii).
Analizator leksykalny:
%%
\* return '*';
\n return '\n';
. printf("Invalid character (%c) in input file in line: %d",yytext[0],yylineno);
--------------------------------------------------------
Przykładowe rozwiązanie (LLgen):
--------------------------------------------------------
Przykładowe rozwiązania (yacc):
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.
W programie nie wolno korzystać ze zmiennych globalnych.
Analizator leksykalny:
%%
[a-d] return yytext[0];
[ \t\n] ;
. printf("Invalid character (%c) in input file in line: %d",yytext[0],yylineno);
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 '+', '-', '*', '/', nawiasy okrągłe
'(' i ')' 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.
| dla yacca | dla LLgena |
%{
#include <stdio.h>
int yywrap(void);
int yylex(void);
#include "y.tab.h"
%}
%%
\; { return ';'; }
\+ { 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] ;
%%
int yywrap(void) { return 1; }
|
%{
#include <stdio.h>
int yywrap(void);
int yylex(void);
#include "Lpars.h"
extern union
{
char *text;
int ival;
} LLlval;
%}
%%
\; { return ';'; }
\+ { return '+'; }
\* { return '*'; }
\- { return '-'; }
\/ { return '/'; }
\( { return '('; }
\) { return ')'; }
\, { return ','; }
[0-9]+ {
LLlval.ival = atoi(yytext);
return num;
}
[A-Za-z_][a-zA-Z0-9_]* {
LLlval.text = strdup(yytext);
return id;
}
[ \t\n] ;
%%
int yywrap(void) { return 1; }
|
| wejście: | wyjście: |
fun1(3,5); fun2(4,9,6); fun3(); fun4(8-4-3,(3+2)/(7-2),8/4/2); |
push 3 push 5 call fun1 add sp,2 push 4 push 9 push 6 call fun2 add sp,3 call fun3 push 1 push 1 push 1 call fun4 add sp,3 |
--------------------------------------------------------
Przykładowe rozwiązanie (yacc):
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, 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:
%%
x return 'x';
\n return '\n';
. printf("Invalid character (%c) in input file in line: %d",yytext[0],yylineno);
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:
[]
| dla yacca | dla LLgena |
%%
\, { return ','; }
\: { return ':'; }
[0-9]+ { yylval = atoi(yytext);
return num; }
[ \t\n] { ; }
|
%{
...
extern int LLlval;
%}
%%
\, { return ','; }
\: { return ':'; }
[0-9]+ { LLlval = atoi(yytext);
return num; }
[ \t\n] { ; }
|
--------------------------------------------------------
Przykładowe rozwiązania (yacc):
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 { ; }
W programie nie wolno korzystać ze zmiennych globalnych.
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 "y.tab.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
W programie nie wolno korzystać ze zmiennych globalnych.
Napisać analizator składniowy dla języka anbn (n > 0). 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 :
Syntax error in line: 2
W programie nie wolno korzystać ze zmiennych globalnych.
Analizator leksykalny:
%%
[ab] return yytext[0];
[ \t\n] ;
. printf("Invalid character (%c) in input file in line: %d",yytext[0],yylineno);
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 '|'; }
W programie nie wolno korzystać ze zmiennych globalnych.