Metody realizacji języków programowania lab 2007

Program zaliczeniowy

Zajęcia

Zadania

Laboratorium 1

• Działania: + - * / % (modulo)
• Liczby całkowite, także ujemne
• Liczby ujemne, to takie, które mają minus przed sobą, bez odstępu, np -34 jest liczbą ujemną, a - 34 jest operatorem - oraz liczbą 34
• Lekser ma być napisany ręcznie
• Dane wejściowe program ma czytać ze standardowego wejścia
• Wynik ma być wypisywany na standardowe wyjście
• Każda linia wejścia zawiera jedno wyrażenie do policzienia
• Kalkulator ma być odporny na błędy: w wypadku błędu ma wypisywać komunikat o błędzie (podając numer linii; pożądane jest też podawanie pozycji błędu w linii) i wznawiać obliczenia od kolejnej linii

• 1 2 - -3 +
• 1 2 *-4 -
• 3 3 + +
• 1 4 + 4 5 -
• 4 0 /

• -4
• 6
• Error in line 3: unexpected operator at character 6
• Error in line 4: unexpected end of expression at character 12
• Error in line 5: division by zero at character 4

• liczby zmiennopozycyjne: 4.42e+12, etc.
• stałe: pi, e
• liczby szestnastkowe: 0x45BaBa

Laboratorium 2

• Uruchomić program z mana, który zlicza liczbę linii i znaków
• Przerobić kalkulator ONP tak, żeby korzystał z Lex-a

Laboratorium 3-4

• Gramatyka:
  • E ::= E + T | E - T | T
  • T ::= T * F | T / F | F
  • F ::= X^F | -F | X
  • X ::= [liczba] | [e] | [pi] | ( E )
• każda linia wejścia zawiera jedno wyrażenie
• operacje: + - * / ^ (potęgowanie) - (minus unarny)
• liczby zmiennopozycyjne, również w notacji naukowej: 4.243e-12 mają być obsługiwane przez lexer
• stałe "pi" i "e" mają być obsługiwane przez lexer (ma zwracać wartość stałych)
• lekser ma być napisany z użyciem Lex-a
• parser ma być napisany ręcznie, jako parser LL(1)
• nie jest wymagane ścisłe trzymanie się schematu parsera LL(1); w szczególności nie trzeba sprowadzać gramatyki do postaci LL(1) - można posłużyć się rozszerzoną składnią EBNF i ręcznie obsłużyć lewostronną rekursję (jest to sugerowane)
• dopuszczalne jest używanie innego języka niż C/C++; wtedy trzeba użyć odpowiednika Lex-a
• potęgowanie ^ jest łączne prawostronnie, tzn. 3^3^3 = 3^27
• uwaga na minus unarny - właściwym miejscem jego obsłużenia jest parser, nie lekser; tzn. -3 powinno być zwrócone jako dwa tokeny: - oraz 3
• kalkulator ma tworzyć drzewo wyrażenia, zgodnie z łącznością operatorów
• kalkulator ma wypisywac drzewo wyrażenia w formacie ONP, akceptowalnym przez stary kalkulator ONP (tzn, jeśli wyrażenie ma tylko liczby całkowite i nie ma potęgowania animinusa unarnego - potęgowanie i liczby zmiennopozycyjne nie były wymagane w pierwszym zadaniu, a minus unarny był tylko przy liczbach)
• minus unarny należy w notacji ONP wypisywać jako tyldę ~
• należy spróbować połączyć oba programy unixowym pajpem (np. calcInfix | calcONP), co pozwoli otrzymywać od razu wynik wyrażenia
• sugerowane jest rozszerzenie kalkulatora ONP (tego przetłumaczonego na użycie lex-a) aby obsługiwał liczby zmiennopozycyjne, stałe, potęgowanie i minus unarny. Właściwe użycia lexa powinno sprawić, że nie będzie to skomplikowane ani czasochłonne
• kalkulator ma też obliczać wartość wyrażeń; sugerowane (ale nie wymagane!) jest użycie opcji commandline'owych z użyciem getopt (patrz 'man 3 getopt'). Dopuszczalne jest użycie flagi przy kompilacji, przełączającej tryby działania
• sugerowane jest zrobienie węzłów drzewa wyrażenia jako hierarchii klas z metodami wypiszONP() i licz(), odpowiednio wypisującymi poddrzewo w notacji ONP i wyliczającymi wartość. Metoda będzie abstrakcyjna w klasach bazowych i będzie przedefiniowana w podklasach.
• choć bardziej eleganckim sposobiem jest użycie wzorca projektowego visitor - polecane dla chętnych! (patrz też diagram klas dla wzorca visitor)
• Kalkulator ma obsługiwać błędy. Powienien wypisywać jakiego symbolu oczekiwał na wejściu, a jaki dostał
• należy zwrócić uwagę na to, czy kalkulator wypisuje wynik (lub postać ONP) od razu po wprowadzeniu linii i naciśnięciu enter; kalkulator nie powienien czekać na kolejny znak przed wypisaniem wyniku dla poprzedniej linii

• 1-2+-3
• 1 *(2 --4)
• 3 ^3^-2^2
• (1+ 3 )* ( 5 - 6)
• 3 - (4 - 4)

• 1 2 - 3 ~ +
• 1 2 4 ~ - *
• 3 3 2 2 ^ ~ ^ ^
• 1 3 + 5 6 - *
• 3 4 4 - -

Laboratorium 5-6

• Parser będzie stanowił część docelowego kompilatora.
• Parser ma być napisany przy użyciu yacc-a i lex-a.
• Dopuszczalne jest użycie innych generatorów parserów i lekserów, w szczególności generatorów przeznaczonych dla innych języków programowania (np. CUP, Coco, AntLR dla Javy, ocamlyacc i ocamllex dla ocamla, BNFC), ale parsera nie można pisać ręcznie
• Program nie musi nic robić ze sparsowanymi konstrukcjami języka. W szczególności pliki *.output nie mają obecnie znaczenia.
• Termin oddania zadania to 4 kwietnia.
• Kolejnym etapem będzie budowa drzewa składniowego, więc można też to zrobić (ale nie będzie to oceniane w ramach tego zadania).
• Użycie BNFC może znacznie uprościć parsowanie i budowę drzewa składni. BFNC generuje od razu klasy C++ dla drzewa składni, a wygenerowany parser buduje to drzewo. Nawet obejrzenie plików lexa i yacca wygenerowanych przez BNFC może być pouczające. Sugerowane jest więc przynajmniej "wypróbowanie" BNFC.

Laboratoria kolejne

Laboratoria kolejne

Last change: 2007-05-14

Back to my homepage