Laboratorium 1: Kalkulator dla ONP

Piszemy kalkulator dla odwrotnej notacji polskiej (wystarczy 4 działania + modulo).

Należy zwrócić uwagę na:

• subtelnosci leksykalne, np zwiazane z liczbami ujemnymi, np
  

  1 2 -3 ++
  1 2- 3 +
  1 2--3-

• "lekser" w tym zadaniu powinien być napisany ręcznie
• możliwe rozszerzenia: liczby zmiennoprzecinkowe, np -6.28e+23, .3E-4, pi; liczby szesnastkowe 0xCafeBabe etc..
• Porządne komunikaty o błędach

Po ukończeniu kalkulatora można go przerobić tak, żeby zamiast obliczać budował drzewo wyrażenia i wypisywał je w notacji infiksowej (nietrywialne: nawiasy)

Laboratorium 2: generatory analizatorów leksykalnych

Poznajemy generator analizatorów leksykalnych dla naszego języka programowania. Może to obejmować Flex (C/C++), Alex (Haskell), ewentualnie JFlex (Java) i inne generatory.

W programie napisanym na poprzednim laboratorium, analizator leksykalny zamieniamy na wygenerowany przy pomocy odpowiedniego generatora.

Flex

Omawiamy przykład analizatora stworzonego przy uzyciu Flexa, np.

%{
// #include "exp.tab.h" /* Definiuje leksemy, np. NUM */
#define NUM '9'
int yylval;
%}
%option noyywrap
%%
[0-9]+  {
         yylval = atoi( yytext ) ;
         return (int)NUM;
       }
.  { return (int)(yytext[0]); }
\n  { return (int)'\n'; }
%%
int main() { int lexem; while(lexem=yylex()) { ... } 
 return 0;
}

Uruchamianie:
flex -o lexer.c lexer.l

Wygenerowany plik (tu: lexer.c) zawiera funkcję yylex(), której kolejne wywołania dają kolejne leksemy (0 dla EOF jeśli nie ma innych wytycznych)

JFlex

Omawiamy przykład, np.

%%
%class Scanner
%type Symbol
%unicode
%line 
 
%{
  StringBuffer string = new StringBuffer();
  // Leksemy są klasy Symbol, zdefiniowanej poza tym plikiem
  private Symbol symbol(int type) {
    return new Symbol(type, yyline, -1);
  }
  private Symbol symbol(int type, Object value) {
    return new Symbol(type, yyline, -1, value);
  }
%}
 
WhiteSpace     = (LineTerminator | [ \t\f])
DecIntLiteral = 0 | [1-9][0-9]*
 
%%
(0|[1-9][0-9]*) 	{ return symbol(sym.NUM, new Integer(yytext())); }
{WhiteSpace}		{ }
.		{ System.out.println("Unexpected character:"+yytext());}

Z tej specyfikacji JFlex wygeneruje klasę (tu: Scanner) zawierającą kod leksera. Konstruktor tej klasy bierze jako argument klasy java.io.Reader reprezentujący strumień wejściowy. Kolejne wywołania metody yylex() z tej klasy dają kolejne leksemy (null dla EOF w tym wypadku)

Alex

Omawiamy przykład, np.

{
module CalcLex(alexScanTokens) where
import CalcToken(Token(..))
}
%wrapper "basic"
$digit = 0-9                    
tokens :-
  $white+                        ; -- whitespace
  "--".*                            ; -- comment
  $digit+                        {\s -> Int (read s)}
  [\=\+\-\*\/\(\)]               {\s -> Sym (head s)}

Przykład uzycia:

$ alex CalcLex.x
$ ghci CalcLex.hs
GHCi, version 6.12.1...
Ok, modules loaded: CalcLex, CalcTokens.
*CalcLex> alexScanTokens "let x = 1 in x +x"
[Let,Var "x",Sym '=',Int 1,In,Var "x",Sym '+',Var "x"]

Laboratorium 3-4: kalkulator dla notacji infiksowej metodą LL(1)

Na poprzednich zajęciach pisaliśmy kalkulator dla notacji postfiksowej (ONP). Tym razem piszemy kalkulator dla notacji infiksowej (czyli "zwykłej"). W sumie przeznaczamy na ten temat dwa zajęcia: na pierwszych tworzymy tylko parser, który sprawdza poprawność wejścia, na drugich rozszerzamy go o budowę i interpretację drzewa struktury.

Wychodzimy od gramatyki

\[ E \to E + E \mid E - E \mid E * E \mid E / E \mid (E) \mid n \]

Przekształcamy ją do gramatyki jednoznacznej, a potem dla postaci LL(1)

Piszemy parser metodą zejść rekurencyjnych.

Laboratorium 5: generatory parserów

Bison

Omawiamy przykład, np. kalkulator dla ONP

%{
#define YYDEBUG 1
#include <stdio.h>
 double atof(const char *s);
int yylex();
void yyerror(const char *s);
#define YYSTYPE double
%}
%token NUM
%% 
input:    /* empty */
        | input line 
        ;
line:     '\n'
        | exp '\n' { printf("\t%.10g\n", $1);}
        ;
exp:    NUM           { $$ = $1;      }
        | exp exp '+' { $$ = $1 + $2; }
        | exp exp '-' { $$ = $1 - $2; }
        | exp exp '*' { $$ = $1 * $2; }
        | exp exp '/' { $$ = $1 / $2; }
%%
void yyerror(const char * s) { puts(s); }
int main() {
   yydebug=0; /* 1 for debugging */
  yyparse();
}

Java CUP

Omwiamy przykład, np.

import java_cup.runtime.*;
 
terminal Integer NUM;
terminal SEMI, PLUS, STAR;
 
non terminal prog;
non terminal Integer exp;
 
prog ::= exp:e
	{: System.out.println("value = " + e); :} 
	SEMI
	;
 
exp ::= NUM:n
	{: RESULT = n; :}
	| exp:e1 exp:e2 PLUS
	{: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
	| exp:e1 exp:e2 STAR
	{: RESULT = new Integer(e1.intValue() * e2.intValue()); :} 
	;

Happy

Omawiamy przykład np.

{
module Main where
import Data.Char
}
 
%name calc
%tokentype { Token }
%error { parseError }
 
%token 
      int             { TokenInt $$ }
      '+'             { TokenPlus }
      '*'             { TokenTimes }
%%
Exp : Exp Exp '+' { $1 + $2 }
    | Exp Exp '*' { $1 * $2 }
| int  { $1 }
    ;
{
 
parseError :: [Token] -> a
parseError _ = error "Parse error"
 
data Token 
      = TokenInt Int
      | TokenPlus
      | TokenTimes
 deriving Show
 
lexer :: String -> [Token]
lexer [] = []
lexer (c:cs) 
      | isSpace c = lexer cs
      | isDigit c = lexNum (c:cs)
lexer ('+':cs) = TokenPlus : lexer cs
lexer ('*':cs) = TokenTimes : lexer cs
 
lexNum cs = TokenInt (read num) : lexer rest
      where (num,rest) = span isDigit cs
 
main = getContents >>= print . calc . lexer
}

Zadania

1. Uruchomić powyższy przykład
2. Zmodyfikować przykład tak aby zamiast obliczać wartośc wyrażenia budował drzewo struktury i wypisywał je (np. w notacji infiksowej, albo obnawiasowanej prefiksowej.
3. Napisać przy użyciu generatora parserów kalkulator dla notacji infiksowej (priorytety i łączność operatorów na razie rozwiązujemy przy użyciu klasycznej gramatyki
   E -> E + T  |  T ...

Laboratorium 6: generatory parserów: priorytety i obsługa błędów

Bison

Omawiamy przykład priorytetów, n.p.

%token NUM
%left '-' '+'
%left '*' '/'
%left NEG     /* leksem-widmo: minus unarny */
%right '^'    /* potęgowanie        */
%%
exp:      NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1,$3);}
        | '(' exp ')'        { $$ = $2;         }
;
%%

Omawiamy przykład obsługi błędów, n.p.

exp:      NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1,$3);}
        | '(' exp ')'        { $$ = $2;         }
        | '(' error ')' 
        { printf("Error in expression\n");$$ = 0;}
;

Studenci powinni zaimplementować powyzsze przykłady w swoich programach, poza tym piszą parser dla Javalette.

Java Cup

Priorytety:

precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;
 
	expr ::=  MINUS expr:e             
	          {: RESULT = new Integer(0 - e.intValue()); :} 
	          %prec UMINUS

Obsługa błędów:

 stmt ::= expr SEMI | while_stmt SEMI | if_stmt SEMI | ... |
	     error SEMI
	     ;

Happy

Tak samo jak Bison, np.

%left '+' '-'
%left '*' '/'
%left NEG
%%
 
Exp   :
      | Exp '+' Exp             { Plus $1 $3 }
      | Exp '-' Exp             { Minus $1 $3 }
      | Exp '*' Exp             { Times $1 $3 }
      | Exp '/' Exp             { Div $1 $3 }
      | '(' Exp ')'             { Brack $2 }
      | '-' Exp %prec NEG       { Negate $2 }
      | int                     { Int $1 }

BNFC

Omawiamy przykład, np.

entrypoints Exp;
 
EAdd.  Exp  ::= Exp "+" Exp1 ;
EMul.  Exp1 ::= Exp1 "*" Exp2 ;
ENum.  Exp2 ::= Integer ;
coercions Exp 2;

Studenci powinni

• skompilować i uruchomić ten przykład w swoim języku programowania
• przeanalizować kod wygenerowany przez BNFC
• rozszerzyć powyższy przykład o operatorym nawiasy, etc.
• ręcznie zmodyfikować wygenerowany przez BNFC parser

Laboratorium 7: maszyna wirtualna JVM; Jasmin

Omawiamy przykład kodu JVM, np.

.class  public Hello
.super  java/lang/Object
 
; standard initializer
.method public <init>()V
   aload_0
   invokespecial java/lang/Object/<init>()V
   return
.end method
 
.method public static main([Ljava/lang/String;)V
.limit stack 2
  getstatic  java/lang/System/out Ljava/io/PrintStream;
  ldc "Hello"
  invokevirtual  java/io/PrintStream/println(Ljava/lang/String;)V
  return
.end method

Kompilujemy prostą klasę np.

public class Inc  {
    public static void main(String[] args) {
	System.out.println(test1(41));
    }
    static int test1(int i) {
	return i+1;
    }
}

Następnie analizujemy kod przy pomocy javap -c, po czym zapisujemy go w formacie asemblera Jasmin.

Rozszerzyć kalkulator z poprzednich laboratoriów o generowanie kodu Jasmin.

Laboratorium 8: LLVM

Low Level Virtual Machine, http://llvm.org/

• maszyna rejestrowa, nieograniczona ilość rejestrów
• generacja kodu na rzeczywisty procesor prez alokację rejestrów
• biblioteka C++, ale także format tekstowy (na laboratorium zajmujemy się tylko tym ostatnim)
• kod czwórkowy:
  %t2 = add i32 %t0, %t1
• instrukcje są silnie typowane:
  

  %t5 = add double %t4, %t3
  store i32 %t2, i32* %loc_r

• nowy rejestr dla każdego wyniku (SSA - Static Single Assignment)
  

  Prosty przykład

  declare void @printInt(i32) ;  w innym module
  define i32 @main() {
         %i1 = add i32 2, 2
         call void @printInt(i32 %i1)
         ret i32 0
  }

  Uruchomienie

  Narzędzia dla LLVM są w katalogu PUBLIC/MRJP/Llvm (w tym pliki runtime.{ll,bc}

  $ llvm-as t2.ll
  $ llvm-link -o out.bc t2.bc runtime.bc
  $ lli out.bc
  4

  Silnia, rekurencyjnie

  define i32 @fact(i32 %n) {
          %c0 = icmp eq i32 %n, 0
          br i1 %c0, label %L0, label %L1
  L0:
          ret i32 1
  L1:
          %i1 = sub i32 %n, 1
          %i2 = call i32 @fact(i32 %i1)
          %i3 = mul i32 %n, %i2
          ret i32 %i3 
  }

  Uwaga:

  • argumenty funkcji są deklarowane
  • wszystko jest typowane, nawet warunki skoków
  • skoki warunkowe tylko z "else"

  Silnia, iteracyjnie

  Używając zmiennych lokalnych w pamięci

  declare void @printInt(i32)
  define i32 @main() {
  entry: 
  	%i1=call i32 @fact(i32 5)
  	call void @printInt(i32 %i1)
  	ret i32 0
  }
   
  ; r = 1
  ; i = n
  ; while (i > 1):
  ;   r = r * i
  ;   i = i -1
  ; return r
  ;;
   
  define i32 @fact(i32 %n) {
  entry: 
  ; local variables:
          %loc_r = alloca i32
  	%loc_i = alloca i32
  ; r = 1
  	store i32 1, i32* %loc_r
  ; i = n
          store i32 %n, i32* %loc_i
  	br label %L1
  ; while i > 1:
  L1:
   	%tmp_i1 = load i32* %loc_i
  	%c0 = icmp sle i32 %tmp_i1, 1
  	br i1 %c0, label %L3, label %L2
  ; loop body
  L2:
  ; r = r * i
          %tmp_i2 = load i32* %loc_r
  	%tmp_i3 = load i32* %loc_i
  	%tmp_i4 = mul i32 %tmp_i2, %tmp_i3
  	store i32 %tmp_i4, i32* %loc_r 
  ; i = i-1
  	%tmp_i5 = load i32* %loc_i
  	%tmp_i6 = sub i32 %tmp_i5, 1
  	store i32 %tmp_i6, i32* %loc_i
  	br label %L1
  L3:
  	%tmp_i8 = load i32* %loc_r
  	ret i32 %tmp_i8

  Używając rejestrów, w wersji SSA

  declare void @printInt(i32)
  define i32 @main() {
  entry: 
  	%i1=call i32 @fact(i32 5)
  	call void @printInt(i32 %i1)
  	ret i32 0
  }
   
  ; r = 1
  ; i = n
  ; while (i > 1):
  ;   r = r * i
  ;   i = i -1
   
  define i32 @fact(i32 %n) {
  entry: br label %L1 
  L1: 
  	%i.1 = phi i32 [%n, %entry], [%i.2, %L2]
  	%r.1 = phi i32 [1, %entry], [%r.2, %L2]
  	%c0 = icmp sle i32 %i.1, 1
  	br i1 %c0, label %L3, label %L2
  L2:
  	%r.2 = mul i32 %r.1, %i.1
  	%i.2 = sub i32 %i.1, 1
  	br label %L1
  L3:
  	ret i32 %r.1
  }

  Zadanie

  Rozszerz kalkulator o generowanie kodu dla LLVM

  Napisy w LLVM

  @hellostr = internal constant [6 x i8] c"Hello\00"
   
  declare void @printString(i8*)
  define i32 @main() {
  entry: 
         %t0 = bitcast [6 x i8]* @hellostr to i8* ; można też uzyć getelementptr
         call void @printString(i8* %t0)
         ret i32 0
  }

Laboratorium 9: asembler x86

Kompilujemy i uruchamiamy programy napisane na ćwiczeniach.

Najprostsza metoda zbudowania programu zawierającego funkcję w asemblerze:

gcc -o f f.s main.c

gdzie f.s jest plikiem zawierającym kod funkcji w asemblerze

main.c plik zwierający program główny w C, np.

int f(int);
int printf(char*,...);
int main() {
  printf("%d\n",f(5));
}

Uwaga: przy uruchamianiu na komputerze 32-bitowym potrzebna jeszcze będzie funkcja dostosowująca protokół wywołania i386 do omawianego na ćwiczeniach, np.

.globl fad
fad:	push %ebp
	mov %esp,%ebp
	//   In 32 bit ABI %edi and %esi are callee-save
	push %edi
	push %esi
	mov 8(%ebp), %edi
	mov 12(%ebp), %esi
	mov 16(%ebp), %edx
	mov 20(%ebp), %ecx
	call f
	pop %esi
	pop %edi
	pop %ebp
	ret

Lab 1 (English): RPN calculator

Write a calculator for the Reverse Polish Notation (aka postfix notation).

Pay careful attention to:

• lexical subtleties, e.g. ones related to negative numbers:
  

  1 2 -3 ++
  1 2- 3 + 
  1 2--3-

• the "lexer" in this task should be written by hand
• possible extensions: floating point numbers e.g. -6.28e+23, .3E-4, pi; hexadecimal numbers, e.g. 0xCafeBabe etc..
• decent error reporting
  When you're done, you can rewrite your program so that instead of computing the value of an expression it will build its tree and output it in infix notation (non-trivial: parentheses).

Lab 2 (en): lexer generators

Learn a lexer generator for your programming language. This can include Flex (C/C++), Alex (Haskell), possibly also JFlex (Java) and other generators.

In the program written in the previous session, replace the handwritten lexer by a generated one.

Flex

Discuss an example of a Flex analyser, e.g.

%{
#include "exp.tab.h" /* Defines lexems, like NUM etc. */
%}
%option noyywrap
%%
[[:digit:]]+  {
         yylval = atoi( yytext ) ;
         return (int)NUM;
       }
.  { return (int)(yytext[0]); }
\n  { return (int)'\n'; }
%%

Running Flex:

flex -o lexer.c lexer.l

The generated file will contain a function yylex() which will return one lexem at a time.

JFlex

Discuss an example, e.g.

%class Scanner
%unicode
%cup
%line 
 
%{
  StringBuffer string = new StringBuffer();
  // Leksemy są klasy Symbol, zdefiniowanej poza tym plikiem
  private Symbol symbol(int type) {
    return new Symbol(type, yyline, -1);
  }
  private Symbol symbol(int type, Object value) {
    return new Symbol(type, yyline, -1, value);
  }
%}
 
WhiteSpace     = (LineTerminator | [ \t\f])
DecIntLiteral = 0 | [1-9][0-9]*
 
%%
(0|[1-9][0-9]*) 	{ return symbol(sym.NUM, new Integer(yytext())); }
[\r\n\t\f ]		{ }
.		{ System.out.println("Unexpected character:"+yytext());}

From this specification JFlex generates a .java file with one class (for the above example: Scanner) that contains code for the scanner. The class will have a constructor taking a java.io.Reader from which the input is read. The class will also have a function yylex() returning the subsequent lexeme each time it is called.

Alex

Discuss an example, e.g.

{
module CalcLex(alexScanTokens) where
import CalcToken(Token(..))
}
%wrapper "basic"
$digit = 0-9                    
$alpha = [a-zA-Z]               
tokens :-
  $white+                        ; -- whitespace
  "--".*                         ; -- comment
  let                            { \s -> Let }
  in                             { \s -> In }
  $digit+                        {\s -> Int (read s)}
  [\=\+\-\*\/\(\)]               {\s -> Sym (head s)}
  $alpha [$alpha $digit \_ \']*  { \s -> Var s }

Running Alex:

ben@sowa$ alex CalcLex.x
ben@sowa$ ghci CalcLex.hs
GHCi, version 6.12.1...
Ok, modules loaded: CalcLex, CalcTokens.
*CalcLex> alexScanTokens "let x = 1 in x +x"
Loading package array-0.3.0.0 ... linking ... done.
[Let,Var "x",Sym '=',Int 1,In,Var "x",Sym '+',Var "x"]

Lab 3-4 (en): recursive descent parsing

The previous lab involved writing a calculator for the postfix notation (RPN). This time we wrtie a calculator for the infix (i.e. ordinary) notation.
In the first sessions we write a correctness-checking parser, then extend it to build and iterpret a parse tree.

Starting with the expression grammar

\[ E \to E + E \mid E - E \mid E * E \mid E / E \mid (E) \mid n \]

Transform it first to unambiguous form, then to LL(1).

Then write a recursive descent parser.

Lab 5 (en): parser generators

Bison

Discuss an example, e.g. RPN calculator

%{
#define YYDEBUG 1
#include <stdio.h>
 double atof(const char *s);
int yylex();
void yyerror(const char *s);
#define YYSTYPE double
%}
%token NUM
%% 
input:    /* empty */
        | input line 
        ;
line:     '\n'
        | exp '\n' { printf("\t%.10g\n", $1);}
        ;
exp:    NUM           { $$ = $1;      }
        | exp exp '+' { $$ = $1 + $2; }
        | exp exp '-' { $$ = $1 - $2; }
        | exp exp '*' { $$ = $1 * $2; }
        | exp exp '/' { $$ = $1 / $2; }
%%
void yyerror(const char * s) { puts(s); }
int main() {
   yydebug=0; /* 1 for debugging */
  yyparse();
}

Java CUP

Discuss an example, e.g.

import java_cup.runtime.*;
 
terminal Integer NUM;
terminal SEMI, PLUS, STAR;
 
non terminal prog;
non terminal Integer exp;
 
prog ::= exp:e
	{: System.out.println("value = " + e); :} 
	SEMI
	;
 
exp ::= NUM:n
	{: RESULT = n; :}
	| exp:e1 exp:e2 PLUS
	{: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
	| exp:e1 exp:e2 STAR
	{: RESULT = new Integer(e1.intValue() * e2.intValue()); :} 
	;

Happy

Discuss an example, e.g.

{
module Main where
import Data.Char
}
 
%name calc
%tokentype { Token }
%error { parseError }
 
%token 
      int             { TokenInt $$ }
      '+'             { TokenPlus }
      '*'             { TokenTimes }
%%
Exp : Exp Exp '+' { $1 + $2 }
    | Exp Exp '*' { $1 * $2 }
| int  { $1 }
    ;
{
 
parseError :: [Token] -> a
parseError _ = error "Parse error"
 
data Token 
      = TokenInt Int
      | TokenPlus
      | TokenTimes
 deriving Show
 
lexer :: String -> [Token]
lexer [] = []
lexer (c:cs) 
      | isSpace c = lexer cs
      | isDigit c = lexNum (c:cs)
lexer ('+':cs) = TokenPlus : lexer cs
lexer ('*':cs) = TokenTimes : lexer cs
 
lexNum cs = TokenInt (read num) : lexer rest
      where (num,rest) = span isDigit cs
 
main = getContents >>= print . calc . lexer
}

Zadania

1. Compile a run an example in your chosen language
2. Modify it to build a parse tree and write it out (e.g. in infix form, or parenthesised prefix form
3. Using a parser generator, write a calculator for the infix notation; for now, problems with operator precedence and binding direction are to be solved using the usual grammar
   E -> E + T  |  T ...

Lab 6 (en): parser generators - priorities, error handling, BNF Converter

Bison

Discuss an example of handling operator priorities e.g.

%token NUM
%left '-' '+'
%left '*' '/'
%left NEG     /* phantom lexeme: unary minus */
%right '^'    /* exponentiation       */
%%
exp:      NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1,$3);}
        | '(' exp ')'        { $$ = $2;         }
;
%%

Discuss an example of error handling, e.g.

exp:      NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1,$3);}
        | '(' exp ')'        { $$ = $2;         }
        | '(' error ')' 
        { printf("Error in expression\n");$$ = 0;}
;

The students should implement above examples in their code; apart from that thay write their Latte parsers.

Java Cup

Priorities:

precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;
 
	expr ::=  MINUS expr:e             
	          {: RESULT = new Integer(0 - e.intValue()); :} 
	          %prec UMINUS

Error handling:

 stmt ::= expr SEMI | while_stmt SEMI | if_stmt SEMI | ... |
	     error SEMI
	     ;

Happy

Similar to Bison, e.g.

%left '+' '-'
%left '*' '/'
%left NEG
%%
 
Exp   :
      | Exp '+' Exp             { Plus $1 $3 }
      | Exp '-' Exp             { Minus $1 $3 }
      | Exp '*' Exp             { Times $1 $3 }
      | Exp '/' Exp             { Div $1 $3 }
      | '(' Exp ')'             { Brack $2 }
      | '-' Exp %prec NEG       { Negate $2 }
      | int                     { Int $1 }

BNFC

Discuss an example, e.g.

entrypoints Exp;
 
EAdd.  Exp  ::= Exp "+" Exp1 ;
EMul.  Exp1 ::= Exp1 "*" Exp2 ;
ENum.  Exp2 ::= Integer ;
coercions Exp 2;

Students should

• compile and run this example in the chosen programming language
• analyse the BNFC-generated code
• extend the example with more operatros, parentheses, etc..
• try to modify the generated parser

Ćwiczenia 1: analiza leksykalna

1. Automat i wyrażenie regularne rozpoznające dla języka liczb binarnych podzielnych przez 3
2. Wyrażenie regularne dla komentarzy w C
3. Wyrażenie regularne dla napisow w stylu Pascalowym ( apostrof wewnatrz podwojnie, np:
   'Finnegan''s Wake'

4. Automat dla liczb dziesiętnych podzielnych przez 17
5. (z egzaminu 2007)
   Leksemami języka EZ1 są: “=”, “=>”, “==”, “<>” i “<=>”. Spacje, końce wiersza i komentarze
   od “(*” do najbliższego “*)” pełnią w tym języku rolę separatorów czyli taką, jak np. w Pascalu.
   Napisz analizator leksykalny języka EZ1, który będzie przekazywał informacje o kolejnych
   leksemach pobranych z wejścia. Analizator powinien wykrywać ewentualne błędy leksykalne.
   Uwaga: nie wolno korzystać z generatora analizatorów leksykalnych.

6. (z egzaminu 2008)
   Leksemami pewnego języka sa "0", "1", "/\", "\/" i "\" (bez cudzysłowów).
   Spacje, końce wiersza i komentarze od "//" do końca wiersza pełnią w tym języku role
   separatorów, czyli taką, jak np. w Pascalu.
   Napisz analizator leksykalny tego języka, udostepniający operację pobrania kolejnego
   leksemu z wejścia. Analizator powinien wykrywać ewentualne błędy leksykalne.
   Uwaga: nie wolno korzystać z generatora analizatorów leksykalnych.

Ćwiczenia 2: gramatyki bezkontekstowe

1. (Aho, Sethi, Ullmann) Rozważmy gramatykę
   \[ S \to aSbS | bSaS | \epsilon \]

   a) Budując dwa różne drzewa lewostronnego wyprowadzenia dla słowa \(abab\), wykaż, że gramatyka ta jest niejednoznaczna

   b) Zbuduj odpowiadające wyprowadzenia prawostronne dla \(abab\).

   c) Jaki język jest generowany przez tę gramatykę?

2. Napisz gramatykę dla języka wyrażeń regularnych? Czy ta gramatyka jest jednoznaczna? Jak można uczynić ją jednoznaczną?
3. Podać gramatykę wieloznaczną dla języka wyrażeń arytmetycznych.
   Wyprowadzić jakieś wyrażenie na 2 różne sposoby.
   Wykazać, że obliczenie wartości tego wyrażenia zależy od wybranego
   drzewa wywodu.

4. Jak wyżej, dla przykładu z wykładu
   if E1 then if E2 then S1 else S2 i gramatyki z wykładu

5. Przećwiczyć konsekwencje lewostronnej rekursji dla parsera
   zstępującego zbudowanego automatycznie np. jako automat z gramatyki.
   Zobaczyć, że stos się przepełni bez postępu na wejściu.

6. Udowodnić, że algorytm usuwania bezpośredniej lewostronnej rekursji
   tworzy gramatykę G' równoważną gramatyce G
   L(G) = L(G')

7. To samo dla lewostronnej faktoryzacji.

Ćwiczenia 3-4: analiza syntaktyczna metodą LL

Zad. 1
Przekształć poniższą gramatykę do postaci LL(1), oblicz zbiory SELECT
oraz wszystkie potrzebne zbiory First i Follow:

\(\begin{align*}
L &\to E , L \mid E\\
E &\to( L ) \mid \varepsilon
\end{align*}
\)

Zad. 2
Polecenie jak wyzej:

\(\begin{align*}
L &\to L ; S \mid S\\
S &\to\{ L \} \mid \varepsilon
\end{align*}
\)

Zad. 3
Przekształćdo postaci LL(1) poniższą gramatykę, oblicz zbiory SELECT,
zrealizuj analizator składniowy działający metoda zejść rekurencyjnych
i dopisz do niego instrukcje liczące wartość wyrazenia (w pierwszej
produkcji najpierw liczymy "*", później "+"):

\(\begin{align*}
E &\to E * E + F \mid F\\
F &\to( E ) \mid num
\end{align*}
\)

Zad. 4
Przeksztalc ponizsza gramatyke do postaci LL(1), oblicz zbiory SELECT
Narysuj i uprosc diagramy skladniowe. Wyjasnij, jak na ich podstawie
zbudowac analizator skladniowy metoda zejsc rekurencyjnych:

W -> W @ P | P
P -> id | liczba | id ( L ) | ( W ) | ( W ) P
L -> W | W , L

Zad. 5-7
Przeksztalc do postaci LL(1) i oblicz zbiory SELECT dla gramatyk:

E -> E F F | epsilon
F -> G ? F F | G
G -> ( E ) | id

I -> J = I I | J
J -> J ? | id | id + id | < L >
L -> L I | epsilon

E -> E F | E F G | F
F -> id E ?
G -> G ( E ) | ( E ) | =

Zad 8 (z kolokwium)

Poniżej znajduje się gramatyka języka K1Z2, którego słowa reprezentują
wyrażenia arytmetyczne. Obok każdej produkcji jest informacja o
znaczeniu opisywanej przez nią konstrukcji języka:

E → ε wyrażenie o wartości 0
E → F - E różnica wartości wyrażeń F i E
E → F wartość wyrażenia F
F → F F * iloczyn wartości dwóch wyrażeń F
F → F ! silnia wartości wyrażenia F
F → G wartość wyrażenia G
G → ( E ) wartość wyrażenia E
G → + G G suma wartości dwóch wyrażeń G

Tekstowy zapis słów języka K1Z2 jest ciągiem znaków "-", "*", "!",
"(", ")" i "+", z których każdy reprezentuje odpowiedni symbol
terminalny gramatyki. Żadnych innych znaków, oprócz wymienionych
powyżej, w tekstowym zapisie słow tego języka nie ma.
Napisz program, który wczyta z wejścia wyrażenie języka K1Z2 i wypisze
na wyjście jego wartość.
Analizator składniowy będący częścią programu zrealizuj za pomocą
metody zejść rekurencyjnych.
W przypadku wykrycia błędu składniowego program powinien wypisać na
wyjście słowo "BLAD".
Uwaga: przymujemy, że silnia liczby mniejszej niż 1 jest równa 1.

Zad 9 (*)
a. Wykaż, że gramatyka

S → aSb | ab

jest LL(2), ale nie LL(1)

b. Wykaż, że gramatyka

S → aAaa | bAba
A → b | ε

jest LL(2), ale nie jest silnie LL(2)

Ćwiczenia 5-6: analiza syntaktyczna metodą LR (2 tygodnie)

Jeśli nie zaznaczono inaczej, polecenie brzmi: stwórz najprostszy mozliwy automat LR (LR(0)<SLR(1)<LALR(1)<LR(1)) dla podanej gramatyki.

Standardowa konwencja: symbole terminalne złożone z małych liter i symboli (+,*,;,etc); symbole nieterminalne pisane wielkimi literami, pierwsza produkcja wyznacza symbol startowy)

0. Stwórz automat dla gramatyki z wykładu:
E -> E + T | T
T -> T * F | F
F -> n
dla pełnosci mozna też dodać produkcję
F -> (E)

1. (Ullman 4.35)
E -> E + T | T
T -> T F | F
F -> F * | a | b

2.
L -> ε | S L
S -> E | if E S | { L }
E -> id | id ( E )

3.
S -> ε | S E ; | S id = E ;
E -> id | num | ( E ) | - E

4. (Ullman 4.39)
S -> A a | b A c | d c | b d a
A -> d

5.(Ullman 4.40)
S -> A a | b A c | B c | b B a
A -> d
B -> d

6.
E -> A | A : A
A -> id | [ ] | [ L ]
L -> A | A , L

7. ( z kolokwium)
Dana jest gramatyka G:

A ­-> A x B | B
B ­-> B y C | C
C ­-> z A z | x

Czy można zbudować parser LR(0) dla gramatyki G ?
Czy można zbudować parser SLR dla gramatyki G ?
Czy można zbudować parser LR(1) dla gramatyki G ?

8. (z kolokwium)

Dana jest gramatyka języka K1Z3:

A → x C
A → B z
A → ε
B → ε
C → x B
C → x C y

Czy ta gramatyka jest LR(0) ? Czy jest SLR(1) ? Czy jest LALR(1) ? Czy
jest LR(1) ?
Odpowiedź na każde pytanie uzasadnij konstrując, za pomocą
odpowiedniej metody, tablicę sterującą analizatora składniowego lub
wskazując, dlaczego nie da się tego zrobić.

9. Do jakich klas LR/LL należy gramatyka

E → E E + | E E * | n

10. Wykaż, że gramatyka

S -> aF | bG
F -> Xc | Yd
G -> Xd | Yc
X -> ZA
Y -> ZB
Z → ε
A → ε
B → ε

jest LL(1), ale nie LALR(1)

Repetytorium

11. (kolokwium 2010)
Dana gramatyka G (symbolem startowym jest A)
A →abb
A → B
B → bBa
B → ε

(a) Sprowadź G do postaci LL(1) i oblicz wszystkie zbiory SELECT.
(b) Do jakich klas spośród LR(0),SLR(1),LALR(1),LR(1) należy G? Odpowiedź uzasadnij.

12. (kolokwium 2011/12)
Dana jest gramatyka G o symbolu początkowym A:

A → ABs | C
B → CBw | C
C → t | uAs

(s,t,u,w są symbolami terminalnymi).

(a) Czy dla języka L(G) można zbudować analizator składniowy metoda zejść rekurencyjnych ? Jeśli tak, to posługując się nią napisz taki analizator. Jeśli nie jest to możliwe, wyjaśnij dlaczego.

(b) Zbuduj tablice sterującą analizatora składniowego LR dla gramatyki G lub udowodnij, że nie jest to możliwe.

Ćwiczenia 7-8: analiza semantyczna (2 tygodnie)

Zadanie 1 (egzamin 2011)

Gramatyka G opisuje automat sterujący LR:

A -> P A | ε
P -> goto(n,n,n) | shift(n,n,n) | reduce(n,n,n) | accept(n,n)

gdzie n jest liczbą oznaczającą oznaczającą numer stanu, produkcji lub symbolu. Ciągi terminali n oddzielonych przecinkiem w produkcjach P oznaczają najpierw stan/stany, później ewentualnie produkcję, a na końcu symbol. Np. shift(1,2,6) oznacza operację shift w stanie 1 z przesunięciem symbolu 6 i przejściem do stanu 2.

Napisz na podstawie gramatyki G gramatykę atrybutywną, która ustawi atrybut sr dla A na true wtw gdy nie ma konfliktu shift/reduce. Załóż, że terminal n posiada atrybut v, reprezentujący jego wartość liczbową.

Zadanie 2 (Aho-Ullmann)

Rozważmy język programów opisany poniższą gramatyką, składających się z sekwencji deklaracji D poprzedzających pojedyncze wyrażenie W

P -> D;W
D -> D;D | id : T
T -> char | int | array [n] of T
W -> c | n | id | W mod W | W[W]

W gramatyce tej c oznacza stałą znakową, n - stałą liczbową.
1. Zapisz reguły sprawdzania typów dla tego języka (np. w postaci gramatyki atrybutywnej)
2. Rozszerz język o wskaźniki i reguły typowania dla nich
3. Używając zaprojektowanych wcześniej reguł wyznacz typy wyrażeń w następujących fragmentach programu:
a) c : char; i : int; c mod i mod 3
b) p : ^int; a: array[10] of int; a[p^]
4. Rozszerz język o typy postaci list of T (lista elementów typu T), wyrażenie konstruujące listę z głowy i ogona i wyrażenie nil reprezentujące listę pustą (która moze reprezentować listę pustą elementów dowolnego typu).

Zadanie 3 (egzamin 2007)

W pewnym języku programowania występuje typ real reprezentujący
liczby oraz mac(m,n) reprezentujący macierze wymiaru m * n o
wyrazach typu real. Napisz gramatykę atrybutywną dla produkcji mnożenia
(E -> E1 * E2) opisującą analizę typów (obliczone typy umieszczaj w
atrybucie E.typ).

Zadanie 4 (egzamin 2007)

Program w języku EZ2 składa się z ciągu definicji funkcji. Funkcje opisuje gramatyka

definicja-funkcji ::= identyfikator '(' wyrażenie ')' '=' wyrażenie
wyrażenie ::= wyrażenie operacja-arytmetyczna wyrażenie
  | identyfikator
  | stała-całkowita
  | identyfikator '(' wyrażenie ')'
  | 'let' identyfikator '=' wyrażenie 'in' wyrażenie

Przedostatnia produkcja oznacza wywołanie funkcji. Ostatnia oznacza deklarację i nadanie
wartości zmiennej lokalnej, która może przesłaniać zadeklarowane wcześniej zmienne, jak i
nazwy funkcji.
Zasięgiem deklaracji po 'let' jest wyrażenie po 'in'.
Funkcje mogą być rekurencyjne (także wzajemnie) i ich definicje mogą występować w dowolnej
kolejności (tzn. dowolna permutacja poprawnego ciągu definicji funkcji daje poprawny ciąg
definicji funkcji).
Programy w EZ2 operują wyłącznie na liczbach całkowitych.
Efektem działania programu w EZ2 jest wypisanie wyniku main(0)

a) Opisz zwięźle warunki poprawności kontekstowej programu EZ2, których spełnienie jest
niezbędne aby wykonanie programu było możliwe.
b) Opisz interfejs tablicy symboli dla EZ2
c) Uwzględniając powyższe, napisz fragment programu sprawdzający poprawność kontekstową
wyrażeń.

Zadanie 5 (egzamin 2009)

Dany jest język wyrażeń o gramatyce:

S → E
E → * E
E → & E
E → E := E
E → id

Identyfikatory występujące w wyrażeniach reprezentują zmienne typu prostego T.

Gwiazdka jest operatorem dereferencji (wyłuskania), który stosujemy do wskaźnika, by otrzymać wartość przezeń wskazywaną. Wyrazenie *E jest poprawne, jeśli E jest wskaźnikiem.

Ampersand (&) jest operatorem pobrania adresu, który daje wskaźnik do wartości wyrażenia, do którego ten operator stosujemy. Wyrażenie &E jest poprawne nawet, jesli E nie jest zmienną. W takiej sytuacji dostaniemy wskaźnik do zmiennej tymczasowej, przechowującej obliczoną wartość E.

Przypisanie E:=E jest poprawne, jeśli typy obu wyrażeń są równe, a lewa strona przypisania jest zmienną lub dereferencją wskaźnika.

Zbuduj, w oparciu o powyższą gramatykę bezkontekstową, gramatykę atrybutywną z regułami atrybutowania, ktore umieszczą na atrybucie S.ok wartość logiczną mowiącą, czy wyrażenie wyprowadzone z S jest poprawne.

Zadanie 6 (egzamin poprawkowy 2009)

W pewnym języku programowania występuje typ int reprezentujący liczby całkowite oraz typ list(t) reprezentujący listy o elementach typu t. Wszystkie elementy danej listy muszą być tego samego typu, aby lista była poprawna.
Do tworzenia list służy stała nil (pusta lista) i operator cons budujący listę, argumentami sa głowa i ogon listy. Operatory car i cdr daja odpowiedni głowę i ogon swojego argumentu.
Przykładowo: x = cons(1,cons(0,nil)) tworzy listę zawierającą dwa elementy: 1 i 0,car(x) = 1, cdr(x) = cons(0,nil).
Uzupełnij poniższą gramatykę o opis analizy typów (obliczone typy wyrażeń umieszczaj w atrybucie E.typ):

E → 0 | 1 | E+E | nil | cons(E,E) | car(E) | cdr(E)

.

Zadanie 7 (egzamin poprawkowy 2011)

Rozważmy język, którego składnię opisuje gramatyka w formie EBNF:

Program ::= {Funkcja}
Funkcja ::= id({id:Typ[,]})[:Typ] = Wyrażenie
Wyrażenie ::= num | id {Wyrażenie}
Typ ::= int | Typ -> Typ

Przykład poprawnego programu:

main() = f  42
f(r:int):int = s p q r
s (a:int->(int->int)->int, d:int->int->int, c:int):int =  a c (d c)
p(x:int, y:int->int) = x
q(x:int, y:int) = x

Zaproponuj system typów dla tego języka.

Zadanie 8 - kontrola typów (Marek Biskup)

Dana jest tablica symboli:

f : int -> double
a : int
g : (double, int) -> string
print: string -> void

Narysuj drzewo składniowe dla fragmentu kodu źródłowego

print( g( f( 1), a )  );

Określ typ każdego węzła.

Zadanie 9 - przeciążanie funkcji (Marek Biskup)

Dana jest tablica symboli:

f : int -> string
f : int -> double
g : double -> string
g : string -> void
h : string, double -> int

Narysuj drzewo składniowe dla fragmentu kodu źródłowego:

 h ( g( f(5), f(8) ) )

Przeprowadź analizę typów.

Wskazówka: Zgodnie z metodą przedstawioną w wykładzie analiza typów w przypadku przeciążania zwracanej wartości funkcji zachodzi w dwóch fazach:

1. wstępującej - idąc od liści do korzenia w każdym węźle wylicz listę możliwe typy,
2. zstępującej - idąc od korzenia do liści w każdym węźle określ jednoznacznie możliwy typ.

Zadanie 10 - L-wartości (Marek Biskup)

Fragment tablicy symboli kompilatora to

f : int -> void
g : int -> int
t : referencja (wskaźnik) do tablicy intów
i : int
d : double
r : referencja do obiektu klasy K, zawierającej
        a : int
        h : int -> K (wynikiem jest referencja do K)

Powiedz, które z poniższych wyrażeń są L-wartościami:

f
g
t
i
d
f(1)
g(1)
t[1]
t[g(1)]
i + 5
t[t[g(1)] + 5]
r
r.a
r.h(1)
r.h(1).a

Ćwiczenia 9-10: protokół wywołania funkcji (2 tygodnie)

Zadanie 1

Jezyk - C + przekazywanie parametrów przez referencję

Dany program

int f(int w, int& x);
void printInt(n);
 
int g(int y, int& z)
{
  int a=z, b;
  z = f(a+2,y);
  printInt(z);
  b = y;
  return b;
}

Zaplanuj rekord aktywacji dla funkcji g i przetłumacz ją

• z argumentami na stosie (x86 - architektura 32-bitowa)
• z argumentami w rejestrach (x86-64 - architektura 64-bitowa)

Zadanie 2 (egzamin 2008)

Język: oddzielnie kompilowane, rekurencyjne funkcje bez struktury blokowej, zmienne lokalne i wynik funkcji typu integer, dwa rodzaje parametrow: przez wartość (integer) oraz referencję (również do zmiennej typu integer). Składnia zbliżona do C++ (parametry przekazywane przez referencję są oznaczane jako typu int&).

Komputer: cztery rejestry uniwersalne R0,...,R3 i instrukcje
Ri:=Ri op Rj (op to +-*/)
Ri:=Rj
Ri:=n
INC Ri,n
LOAD Ri,n
LOAD Ri, [Rj]
STORE Ri,[Rj]
GOTO n
GOTO [Ri]
CALL Ri (adres skoku w rejestrze, ślad tamże)
plus potrzebne skoki warunkowe.
Notacja [Ri] oznacza komórkę pamięci o adresie w Ri

Zaprojektuj protokół wywołania i powrotu z funkcji i przetłumacz

extern int g(int& a);
int f(int a, int& b) {
  int c;
  c =  21 + g(a) + g(b);
  return c;
}

rozwiązanie powinno obejmować opis rekordu aktywacji funkcji f i istotny fragment rekordu aktywacji funkcji g.

Zadanie 3 (z egzaminu)

Rozważmy język D♭ ze strukturą blokową, dopuszczający zagnieżdżanie funkcji oraz przekazywanie ich jako parametrów (poza tym podobny do C), oraz fragment programu w nim:

int h(int a, int b, function int k(int)) {
  return k(a)  + k(b) ;
}
 
int g(int a) {
 int b;
 int f(int c) { return (b=a+c); }
 f(a);
 return h(a,b,f);
}

a. Zaprojektuj protokół wywołania i powrotu z funkcji dla tego języka.
b. Opisz rekordy aktywacji dla funkcji f,g,h
c. Wygeneruj kod dla podanego fragmentu programu.

Można przyjąć, że w języku D♭ nie występują wskaźniki do funkcji (ani w ogóle konstrukcje nie występujące w przytoczonym fragmencie programu).

Zadanie 4 (egzamin 2009)

Rozważmy język ze strukturą blokową, dopuszczający zagnieżdzanie procedur oraz trzy rodzaje parametrów:

* wejściowe (przekazywane przez wartość), oznaczane na liście parametrów formalnych słowem kluczowym in
* wyjściowe - kopiowane po powrocie z funkcji na zmienną będącą parametrem faktycznym, oznaczane out
* wejściowo-wyjściowe - przekazujące wartość do funkcji przy wywołaniu i z funkcji przy powrocie (inout)

Dalej, rozważmy fragment programu w tym języku:

program Foo;
procedure P(in int a,out int b);
  var int c;
  procedure Q(inout int b, out int c);
  begin 
    c := b / a;
    b := b - c
  end; (* Q *)
  procedure  R(inout int d) begin Q(d,c) end (* R *);
begin (* P *)
    c := a + 1;
    R(c)
    Q(c,b);
end; (* P *)

a. Zaprojektuj protokół wywołania i powrotu z procedur dla tego języka.
b. Opisz rekordy aktywacji dla procedur P,Q,R
c. Wygeneruj kod na maszynę stosową dla podanego fragmentu programu.

Zadanie 5

Jezyk: oddzielnie kompilowane, rekurencyjne funkcje bez struktury
blokowej, zmienne lokalne i wynik funkcji typu integer, dwa rodzaje
parametrow: przez wartosc (integer) oraz etykieta, skoki tylko nielokalne,
do etykiet przekazanych jako parametr.
Komputer: cztery rejestry uniwersalne R0,...,R3 i instrukcje
Ri:=Ri op Rj (op to +-*/)
Ri:=Rj
Ri:=n
INC Ri,n
LOAD Ri,arg
STORE Ri,arg
GOTO arg
CALL Ri (adres skoku w rejestrze, slad tez tam)
plus potrzebne skoki warunkowe.

Zaprojektowac protokol wywolania funkcji dla tego jezyka i przetlumaczyc:

function F(a,b,c);
var d,e,f,g;
begin
  g:=10;
  if a>0 then c:=a+b;
  repeat
    f:=a+b; e:=b; d:=a;
    f:=FUNKCJA((d+e)*f,(b+d)-(c*g),ETYKIETA);
    if f>0 then e:=(a+b)*(c*d) else e:=c*d;
ETYKIETA:
    e:=e-(c*d);
    a:=a+1
  until a=b;
  return e;
end;

(Oczywiscie interesuja nas tylko ciekawsze fragmenty)

Zadanie 6

W jezyku L-- istnieja rekurencyjne funkcje (z parametrami przekazywanymi
przez wartosc). Funkcje moga byc zagniezdzane, ale wewnatrz funkcji
widoczne sa jedynie zmienne i funkcje zadeklarowane w niej samej lub w
funkcji bezposrednio ja otaczajacej. Wszystkie zmienne lokalne, parametry
i funkcje sa typu integer. Przyklad programu:

function p();
  var p1; function q(a); begin ...end;
  function F(a,b); var c; function R(); begin ...end;
  begin {F}
    c:=1; if a<b then c:=F(Q(F(a+p1,b-1)),R()); return 5;
  end;
begin ... end;

Komputer ma rejestr adresowy A oraz wbudowany stos (o ograniczonej,
niewielkiej pojemnosci) sluzacy do obliczen arytmetycznych. Istnieja
miedzy innymi instrukcje:

PUSH A
PUSH n
PUSH (A+n)
PUSH * adres na czubku stosu zastepuje wartoscia spod tego adresu
POP A
POP (A+n)
POP * na czubku wartosc i adres, wykonujemy przypisanie
ADD, SUB ...
GOTO n
GOTO * adres skoku na czubku stosu
IFZERO n
IFNOTNEG n
CALL n slad zostaje na czubku stosu

Ponadto istniej funkcja ALLOC przydzielajaca obszar pamieci o rozmiarze na czubku stosu i zastepujaca rozmiar adresem obszaru. Jest tez procedura FREE zwalniajaca obszar o adresie na czubku stosu.

Zaprojektowac rekord aktywacji i protokol wywolania funkcji. (Rekordy aktywacji tworzymy i usuwamy przez ALLOC i FREE).

Napisac tlumaczenie funkcji F z przykladu powyzej.

Zadanie 7 (z kolokwium)

Dany jest język programowania, w którym:

• program składa się z funkcji, które można zagnieżdżać i wywoływać rekurencyjnie
• zasady widoczności zmiennych i parametrów w funkcjach zagnieżdżonych są takie, jak w Pascalu
• wszystkie dane (zmienne, parametry, wynik funkcji) są typu integer
• parametry funkcji mogą być przekazywane przez wartość lub przez zmienną (przekazywanie przez zmienną
  zaznaczone jest przez &)
• liczba argumentów funkcji może być zmienna (ostatnim argumentem jest wówczas ...), ale wywoływana funkcja
  zna liczbę argumentów, z którymi została wywołana (jako zmienną _argc); do argumentów bez nazwy odwołuje
  się poprzez tablicę _argv; argumenty bez nazwy są zawsze przekazywane przez wartość
• argumenty operacji arytmetycznych oraz parametry funkcji obliczane są od lewej do prawej

Maszyna docelowa ma pamięć składającą się ze słów, długość adresu jest równa długości słowa. Maszyna ma dwa
rejestry ogólnego przeznaczenia, R0 i R1, wskaźnik wierzchołka stosu SP i rejestr BP. Stos rośnie w kierunku
malejących adresów. Adresy można podawać bezpośrednio bądź w sposób indeksowany (np. [adres+10]).
Dostępne są następujące instrukcje:

MOV Rx, Ry – kopiuje zawartość Rx do Ry,
MOV adres, Ry – kopiuje zawartość pamięci spod adresu adres do Ry,
MOV Rx, adres – kopiuje zawartość rejestru Ry do pamięci pod adres adres,
ADD Rx, Ry, SUB Rx, Ry, MUL Rx, Ry – operacje arytmetyczne, ich wynik jest umieszczany w Rx,
PUSH num – odkłada na stos liczbę num,
PUSH Rx – odkłada na stos zawartość rejestru Rx,
POP Rx – zdejmuje ze stosu liczbę i umieszcza ją w Rx,
CALL adres – odkłada na stos adres kolejnej instrukcji i skacze pod adres adres,
RET – zdejmuje ze stosu liczbę, którą traktuje jako adres pod który skacze,
oraz inne, nieistotne dla treści zadania.

Zaprojektuj protokół wywołania i powrotu z funkcji tak, by możliwe było zaimplementowanie powyżej
przedstawionych cech języka programowania. Opisz jak wygląda prolog i epilog funkcji oraz jej wywołanie i do czego
są używane poszczególne rejestry.

Przedstaw na rysunku zawartość stosu (zaznaczając strzałkami SL-e i DL-e oraz pomijając zmienne tymczasowe) przed
wykonaniem linijki zaznaczonej przez (*) z poniższego programu, zakładając, że pierwszy wykonywany był wiersz
oznaczony (**):

int f1(int a, int b, int c) {
int f2(int &a) {
int f3(int b, ...) {
int c = f4(a)+_argv[0]+b;
return c;
};
a = 17;
return f3(c, 2)+b;
}
int f4(int c) {
(*)
return a+c;
}
return f2(b);
}
...
(**) f1(1,2,3);
...

Adresy funkcji przedstaw jako #nazwa, a adresy zmiennych przez ich nazwę w nawiasach kwadratowych.

Podaj wartość zwracaną przez wywołanie f1.

Zadanie 8

Przesledzic wykonanie programu (wczesniej trzeba rozplanowac rekord
aktywacji i omowic sposob przekazywania parametrow):

program A;
var aa:integer;
  function B(function bf:integer; var bv:integer):integer;
    function C(cc:integer):integer;
    begin
      c:=aa+bv+cc;
      aa:=E(cc)
    end;
  begin
    bv:=bv+1;
    if bv=2
      then B:=B(C,bv)
      else B:=(aa+bv)*D(bf)
  end;
  function D(function dd:integer):integer;
  begin
    D:=(2*aa)-dd(aa)
  end;
  function E(ee:integer):integer;
  begin
    E:=ee+2
  end;
begin
  aa:=1;
  writeln(B(D,aa))
end.

Ćwiczenia: asembler x86

Część zadań przygotował Tomasz Idziaszek.

Uwaga: jeśli nie zaznaczono inaczej, w ponizszych zadaniach kolejne argumenty funkcji przekazywane są w rejestrach EDI, ESI, EDX, ECX, zaś wynik zwracany w EAX. Funkcja musi zachowywać wartość rejestrów EBP i EBX.

Poniższe zadania nadają się również na laboratorium.

Zadanie 0

a. Napisz funkcję, która daje zawsze wynik 42 (uwaga na składnię!)

b. Napisz funkcję, która daje w wyniku swój argument.

Programista Tobiasz Niedbalski napisał powyższe funkcje następująco:

a.

.globl f
f:	
	mov 42, %eax
	ret

b.

f:	
	mov  %esi, %eax
	ret

Jakie mogły być tego efekty?

c. (lab) Napisz funkcję printInt(int n), która wypisuje swój argument

Zadanie 1

Zapisz w asemblerze x86 funkcję obliczającą silnię, w dwóch wersjach - rekurencyjnej oraz iteracyjnej (zanim zabierzemy się za silnię, można najpierw policzyć sumę [1..n]).

Zadanie 2

Zapisz w asemblerze kod dla prostego przypisania, np. x := (y + 17*x) / z.

Zakładamy, że adresy zmiennych są dostępne w tablicy symboli. Uwaga na dzielenie i różnice między l-wartościami i r-wartościami.

Przykładowe warianty adresów zmiennych:

Ćwiczenia 11-12: generowanie i ulepszanie kodu

Zadanie 1

Przetłumacz poniższy fragment programu na kod czwórkowy i sprowadź ten kod do postaci SSA. Wstaw funkcje \(\phi\) tylko tam, gdzie jest to konieczne. Pamiętaj o zmianie nazw (dodaniu indeksów) zmiennych.

while (a != 0) {
  if (a < 0) {
    b = 1;
  } else {
    b = -1;
  }
  a = a + b;
}

Zadanie 2

Dana funkcja

int g(int a,b,c,d,e,f)
{
  while(e) {
    a = b+c; d = d-c; e=a-f;
 
    if(e)
      f = a-d;
    else {
      b = d+f;
      e = a-c;
    }
    b = d+c;
  }
  return b;
}

Maszyna docelowa: 3 rejestry ogólnego przeznaczenia, wskaźnik stosu i ramki, operacje

LOAD Ri, m -przesłanie z pamieci do rejestru
STORE Rj, m - przeslanie z rejestru do pamieci
SUB Ri, RJ - Ri := Ri - Rj
ADD analogicznie

a. Wygenerować kod czwórkowy, zidentyfikować bloki proste narysować graf przepływu i określić zmienne zywe na początku i końcu każdego bloku prostego.

b. Wygenerować kod maszynowy dla pierwszego bloku {a=b+c itd} metodą opisów rejestrów i wartości

Zadanie 3

Dana funkcja

unsigned f(unsigned a) {
  int b = a+1;
  {
    unsigned a = b+1;
    unsigned c = a/2;
    if(c>0) return f(c);
    else return 0;
  }
}

Maszyna docelowa: 1 rejestr ogólnego przeznaczenia A, wskaźnik stosu i ramki, operacje

LOAD A, m ;przesłanie z pamieci do rejestru
STORE A, m ; przeslanie z rejestru do pamieci
SUB A, m ; A := A - M[m]
INC A ; A := A+1
SHL A ; A := 2*A
SHR A ; A := A/2
inne operacje analogicznie

a. Wygenerować kod czwórkowy, zidentyfikować bloki proste narysować graf przepływu i określić zmienne zywe na początku i końcu każdego bloku prostego.

b. Wygenerować kod dla opisanej maszyny

Zadanie 4 (egzamin 2008)

Podaj przykład programu w kodzie czwórkowym, który po wykonaniu podanego poniżej
ciągu optymalizacji uprości się do

return 42;

• w odpowiedzi powinien się znaleźć kod programu przed i po każdym kroku
  optymalizacji
• im krótszy przykład podasz, tym lepiej
• oczywiście, stosowane optymalizacje powinny zmieniać program.

Optymalizacje powinny zostać wykonane w następującej kolejności:
1. Propagacja kopii
2. Eliminacja martwego kodu
3. Eliminacja wspólnych podwyrażeń
4. Propagacja stałej
5. Zwijanie stałej
6. Propagacja stałej
7. Zwijanie stałej
8. Propagacja stałej
9. Eliminacja martwego kodu
10. Zwijanie stałej
11. Propagacja stałej
12. Eliminacja martwego kodu
Uwaga: w każdym kroku daną optymalizację można w razie potrzeby zastosować więcej niż
raz. Tym niemniej obowiązuje kryterium długości kodu wyjściowego.

Zadanie 5 (egzamin 2008)

Dana jest maszyna z dwoma rejestrami R0, R1 i instrukcjami:
Ri:=Ri-Rj odejmowanie zawartości Rj od zawartości Ri
Ri:=Ri/Rj dzielenie zawartości Ri przez zawartosc Rj
Ri:=id
zaladowanie do Ri wartości zmiennej
id:=Ri
zapisanie na zmiennej zawartości rejestru Ri
Ri:=Rj
przepisanie do Ri zawartości Rj
gdzie "i", "j" to 0 lub 1 a "id" to identyfikator zmiennej.
Korzystając z metody tablicy opisów wartości i rejestrów wygeneruj możliwie dobry kod dla
ciągu instrukcji, po którym żywe są zmienne "a" i "b":

x:=a; a:=b/a; b:=a-x; a:=b/x

Zadanie 6 (Egzamin 2008)

Dane są deklaracje:

var i,r:integer;
a,b:array [0..n] of integer;

Zakładając, że liczba całkowita zajmuje cztery adresowalne komórki pamięci, wygeneruj kod czwórkowy i narysuj graf przepływu sterowania dla fragmentu programu:

i:=1;
while a[i]=b[i] do
 i:=i+1;
r:=a[i]-b[i]

Przyjmując, ze na zakończenie tego fragmentu żyje tylko zmienna "r", zoptymalizuj wygenerowany wcześniej kod czworkowy, nazywając każdą z wykonanych optymalizacji.
Uwaga: Składnia Pascalowa, czyli "=" oznacza porównanie, a ":=" - przypisanie.

Zadanie 7 (Egzamin 2011)

Dana funkcja:

int f(int n) {
 int u=0, v=1, i=2, t;
 while(i<n) {
    t=u+v;  u=v; v=t;
    i=i+1;
 }
 return v;
}

a. Wygeneruj kod czwórkowy w postaci SSA, podziel go na bloki proste;
narysuj graf przeplywu sterowania.
b. Zastosuj (i nazwij) znane optymalizacje w celu ulepszenia kodu

Zadanie 8 (egzamin 2011)

Rozważmy funkcję

void sort(int n)
{
 int i,j,t;
 for (i = 0; i < n; i++)
    for (j = n-1; j > i; j--)
      if (A[j-1] > A[j]) {
    t = A[j-1];
        A[j-1] = A[j];
    A[j] = t;
      }
}

a. Wygeneruj kod czwórkowy dla powyższej procedury (bez protokołu wejścia i powrotu). Zidentyfikuj bloki proste i narysuj graf przepływu sterowania. Uwaga: odwołanie do elementu tablicy wymaga podania offsetu tego elementu w bajtach, int zajmuje 4 bajty, tablice indeksowane od 0.

b. Wykonaj kilka kroków optymalizacji uzyskanego kodu czwórkowego (wystarczy zastosować dokładnie 5 różnych rodzajów optymalizacji i je odpowiednio opisać.)

Zadanie (egzamin 2012)

Maszyna docelowa ma dwa rejestry ogólnego przeznaczenia R0,R1
oraz instrukcje (dla i,j=0,1, m oznacza komórkę pamięci):

Ri = Rj
Ri = m
m = Rj
Ri = Ri op Rj

"op" jest pewna operacją arytmetyczną; instrukcje operujące wyłącznie na rejestrach mają koszt 2, instrukcje z dostępem do pamięci mają koszt 7.

Rozważmy blok prosty, na końcu którego żywa jest (tylko) zmienna e:

c = b; 
a = a op c; 
d = b op a; 
e = d op e; 
e = a op e; 
a = c op b; 
e = a op e;

A. Wskaż zmienne żywe przed każdą z instrukcji.
B. Korzystając z metody opisu rejestrów i wartości, wygeneruj możliwie najlepszy (w sensie kosztu) kod dla tego bloku. Do komórek pamięci przechowujących zmienne można się odwoływać przez nazwę zmiennej (np. R0 = a).
Uwaga: na tym etapie należy generować kod maszynowy dokładnie dla podanego kodu czwórkowego, bez żadnych optymalizacji.

C. Jakie optymalizacje można zastosować do tego kodu czwórkowego? W jaki sposób wpłyną one na wynikowy kod maszynowy?

Ćwiczenia 4 - analiza semantyczna

Zadanie 1 (egzamin 2011)

Gramatyka G opisuje automat sterujący LR:

A -> P A | ε
P -> goto(n,n,n) | shift(n,n,n) | reduce(n,n,n) | accept(n,n)

gdzie n jest liczbą oznaczającą oznaczającą numer stanu, produkcji lub symbolu. Ciągi terminali n oddzielonych przecinkiem w produkcjach P oznaczają najpierw stan/stany, później ewentualnie produkcję, a na końcu symbol. Np. shift(1,2,6) oznacza operację shift w stanie 1 z przesunięciem symbolu 6 i przejściem do stanu 2.

Napisz na podstawie gramatyki G gramatykę atrybutywną, która ustawi atrybut sr dla A na true wtw gdy nie ma konfliktu shift/reduce. Załóż, że terminal n posiada atrybut v, reprezentujący jego wartość liczbową.

Zadanie 2 (Aho-Ullmann)

Rozważmy język programów opisany poniższą gramatyką, składających się z sekwencji deklaracji D poprzedzających pojedyncze wyrażenie W

P -> D;W
D -> D;D | id : T
T -> char | int | array [n] of T
W -> c | n | id | W mod W | W[W]

W gramatyce tej c oznacza stałą znakową, n - stałą liczbową.
1. Zapisz reguły sprawdzania typów dla tego języka (np. w postaci gramatyki atrybutywnej)
2. Rozszerz język o wskaźniki i reguły typowania dla nich
3. Używając zaprojektowanych wcześniej reguł wyznacz typy wyrażeń w następujących fragmentach programu:
a) c : char; i : int; c mod i mod 3
b) p : ^int; a: array[10] of int; a[p^]
4. Rozszerz język o typy postaci list of T (lista elementów typu T), wyrażenie konstruujące listę z głowy i ogona i wyrażenie nil reprezentujące listę pustą (która moze reprezentować listę pustą elementów dowolnego typu).

Zadanie 3 (egzamin 2007)

W pewnym języku programowania występuje typ real reprezentujący
liczby oraz mac(m,n) reprezentujący macierze wymiaru m * n o
wyrazach typu real. Napisz gramatykę atrybutywną dla produkcji mnożenia
(E -> E1 * E2) opisującą analizę typów (obliczone typy umieszczaj w
atrybucie E.typ).

Zadanie 4 (egzamin 2007)

Program w języku EZ2 składa się z ciągu definicji funkcji. Funkcje opisuje gramatyka

definicja-funkcji ::= identyfikator '(' wyrażenie ')' '=' wyrażenie
wyrażenie ::= wyrażenie operacja-arytmetyczna wyrażenie
  | identyfikator
  | stała-całkowita
  | identyfikator '(' wyrażenie ')'
  | 'let' identyfikator '=' wyrażenie 'in' wyrażenie

Przedostatnia produkcja oznacza wywołanie funkcji. Ostatnia oznacza deklarację i nadanie
wartości zmiennej lokalnej, która może przesłaniać zadeklarowane wcześniej zmienne, jak i
nazwy funkcji.
Zasięgiem deklaracji po 'let' jest wyrażenie po 'in'.
Funkcje mogą być rekurencyjne (także wzajemnie) i ich definicje mogą występować w dowolnej
kolejności (tzn. dowolna permutacja poprawnego ciągu definicji funkcji daje poprawny ciąg
definicji funkcji).
Programy w EZ2 operują wyłącznie na liczbach całkowitych.
Efektem działania programu w EZ2 jest wypisanie wyniku main(0)

a) Opisz zwięźle warunki poprawności kontekstowej programu EZ2, których spełnienie jest
niezbędne aby wykonanie programu było możliwe.
b) Opisz interfejs tablicy symboli dla EZ2
c) Uwzględniając powyższe, napisz fragment programu sprawdzający poprawność kontekstową
wyrażeń.

Zadanie 5 (egzamin 2009)

Dany jest język wyrażeń o gramatyce:

S → E
E → * E
E → & E
E → E := E
E → id

Identyfikatory występujące w wyrażeniach reprezentują zmienne typu prostego T.

Gwiazdka jest operatorem dereferencji (wyłuskania), który stosujemy do wskaźnika, by otrzymać wartość przezeń wskazywaną. Wyrazenie *E jest poprawne, jeśli E jest wskaźnikiem.

Ampersand (&) jest operatorem pobrania adresu, który daje wskaźnik do wartości wyrażenia, do którego ten operator stosujemy. Wyrażenie &E jest poprawne nawet, jesli E nie jest zmienną. W takiej sytuacji dostaniemy wskaźnik do zmiennej tymczasowej, przechowującej obliczoną wartość E.

Przypisanie E:=E jest poprawne, jeśli typy obu wyrażeń są równe, a lewa strona przypisania jest zmienną lub dereferencją wskaźnika.

Zbuduj, w oparciu o powyższą gramatykę bezkontekstową, gramatykę atrybutywną z regułami atrybutowania, ktore umieszczą na atrybucie S.ok wartość logiczną mowiącą, czy wyrażenie wyprowadzone z S jest poprawne.

Zadanie 6 (egzamin poprawkowy 2009)

W pewnym języku programowania występuje typ int reprezentujący liczby całkowite oraz typ list(t) reprezentujący listy o elementach typu t. Wszystkie elementy danej listy muszą być tego samego typu, aby lista była poprawna.
Do tworzenia list służy stała nil (pusta lista) i operator cons budujący listę, argumentami sa głowa i ogon listy. Operatory car i cdr daja odpowiedni głowę i ogon swojego argumentu.
Przykładowo: x = cons(1,cons(0,nil)) tworzy listę zawierającą dwa elementy: 1 i 0,car(x) = 1, cdr(x) = cons(0,nil).
Uzupełnij poniższą gramatykę o opis analizy typów (obliczone typy wyrażeń umieszczaj w atrybucie E.typ):

E → 0 | 1 | E+E | nil | cons(E,E) | car(E) | cdr(E)

.

Zadanie 7 (egzamin poprawkowy 2011)

Rozważmy język, którego składnię opisuje gramatyka w formie EBNF:

Program ::= {Funkcja}
Funkcja ::= id({id:Typ[,]})[:Typ] = Wyrażenie
Wyrażenie ::= num | id {Wyrażenie}
Typ ::= int | Typ -> Typ

Przykład poprawnego programu:

main() = f  42
f(r:int):int = s p q r
s (a:int->(int->int)->int, d:int->int->int, c:int):int =  a c (d c)
p(x:int, y:int->int) = x
q(x:int, y:int) = x

Zaproponuj system typów dla tego języka.

Laboratorium 7: tablica symboli

Tablica nazw

Zaprojektuj i zaimplementuj swoją tablicę nazw - strukturę danych dostarczającą operacji

• insert - wstawienie nazwy
• find - wyszukanie nazwy

W testowaniu moze pomóc poniższy kod:

void test() {
  NameTab nameTab;
  int identifiers = 0;
  while(yylex()) {
     identifiers ++;
     if(!nameTab.insert(yytext,yyleng)) 
       abort("FATAL: Pool memory exhausted");
  }   
  cout << "Identifier lexems: " << identifiers << endl;
  cout << "Repeats: " << nameTab.repeated << endl;

Lexer: https://gist.github.com/706400

[ben@students Nametab]$ find /usr/include -name \*.h | xargs cat | /usr/bin/time ./pooled
Identifier lexems: 3679282
Repeats: 3265862
2.94user 0.13system 0:03.11elapsed 98%CPU (0avgtext+0avgdata 67104maxresident)k
0inputs+0outputs (0major+4257minor)pagefaults 0swaps

Kalkulator ze zmiennymi

Rozszerz kalkulator o zmienne i przypisania, np

x = 2*2
y = x+1
y*y
25

Laboratorium 8: tablica symboli z zagnieżdzaniem

Rozszerzamy nasz kalkulator ze zmiennymi z poprzedniego laboratorium do prostego języka programowania ze strukturą blokową, na przykład

int a = 1;
int b = 2*a;
{
  int a = 3;
  b = a+b;
}
b-a;

alternatywnie

int a,b;
a = 1;
b = 2*a;
{
  int a ;
  a = 3;
  b = a+b;
}
b-a;

W tym celu należy zaimplementować tablicę symboli co najmniej z operacjami:

• wejście do zakresu
• dodanie definicji (identyfikator i jego wartość)
• odczytanie wartości identyfikatora
• modyfikacja identyfikatora
• opuszczenie zakresu

Mozna przyjąć, że deklaracja bez inicjalizatora nadaje wartość 0.

Laboratorium 9: kontrola typów

Rozszerzamy język z poprzedniego laboratorium o typ zmiennoprzecinkowy i kontrole typów, na przykład

int a,b;
double c;
a = 1;
b = 2*a;
{
  double a ;
  a = 3.14159;
  c = a+double(b);
}
int(c-a);

Laboratorium 10: kod czwórkowy

Kod czwórkowy

W PUBLIC/MRJP/Quadruples/ dostępny jest edukacyjny interpreter kodu czwórkowego iquadr}

Implementowany dialekt:

• program jest ciągiem otypowanych funkcji
• nieograniczona ilość rejestrów typu int i double, np. i0, d1
• zmienne lokalne i tymczasowe: t2 := a + t1 pisane jako $.i2 := a.i3 + $.i1 (identyfikator przed kropką ma charakter li tylko komentarza)
• brak zmiennych globalnych (tylko funkcje)
• konwersje między typami np. $.i1 := b.d0
• dodatkowa instrukcja print, np. print $.i0
• nie ma wbudowanego mechanizmu przekazywania parametrów
• dostęp do pamięci; adresowanie postaci {rejestr+stała}, np. {sp.i1-1} := 2,
  

  a.i3 := {bp.i2+1}

Przykłady

Liczby Fibonacciego

function main : int :
    $.d3 	:= 1.0
    lo.i0 	:= $.d3
    hi.i1 	:= lo.i0
    mx.i3 	:= 5000000
    mx.i2 	:= $.i3
    print lo.i0
L0:
    if hi.i1 >= mx.i2 goto L1
    print hi.i1
    $.i3 	:= lo.i0 + hi.i1
    hi.i1 	:= $.i3
    $.i3 	:= hi.i1 - lo.i0
    lo.i0 	:= $.i3
    goto L0
L1:
function end

Wywołanie funkcji z przekazywaniem argumentów w rejestrach:

function main : int :
  $.i0 := -40
  $.i0 := ~$.i0
  $.d0 := 3.14159
  call add
  print $.i0
function end
 
function add : int -> double -> int :
  $.i1 := b.d0
  result.i0 := a.i0 + $.i1
function end

Protokół wywołania funkcji przy użyciu stosu:

function main : int :
  sp.i1 := 512 
  bp.i2 := sp.i1
  {sp.i1-1} := 2
  {sp.i1-2} := 3
  sp.i1 := sp.i1 - 2
  call add
  print retval.i0
function end
 
function add : int -> int -> int :
  sp.i1 := sp.i1 - 1
  {sp.i1+0} := bp.i2
  bp.i2 := sp.i1
  a.i3 := {bp.i2+1}
  b.i4 := {bp.i2+2}
  retval.i0 := a.i3 + b.i4
function end

Zadania

1. Zakoduj i przetestuj prostą funkcję, np. silnię
2. Rozszerz kalkulator z poprzednich zajęć o funkcję generowania kodu czwórkowego
3. Dodaj instrukcje warunkowe, pętli,...