Skip to content

battista26/python-compiler

BranchesTags

Repository files navigation

Proje 3 Bütün Compiler Tasarımı

Python'da PLY (Python Lex-Yacc) kullanılarak tümüyle çalışan compiler projesi.

Lexical Analysis -> Syntax Analysis(AST) -> Semantic Analysis (Type Checking & Scoping) -> Bytecode Generation -> Stack-Tabanlı Virtual Machine ile execution

Gereksinimler

Python 3.x
PLY kütüphanesi

pip install ply

Nasıl Çalıştırılır

Kendiniz yazarak test etmek istiyorsanız.

python main.py
  1. Bu komut çalıştırıldığında code3 değerinin içindeki source kodu parse eder.
  2. AST yapısı oluşturulur.
  3. Semantic analiz yapılır.
  4. Bytecode oluşturulur
  5. program.bytecode dosyasına bytecode kaydedilir.
  6. Bytecode Virtual Machine'de çalıştırılır.
    (program.bytecode üzerinden okunma yapılmıyor, sadece test amaçlı oluşturulmakta)

Başka bir yöntem ise test case'leri çalıştırmak

python test_cases.py

Programlama Dilinin Syntax, Gramer ve Abstract Syntax Tree

Veri tipleri:

  • int Integer sayılar (ör: 5, -10)
  • float Float sayılar (ör: 3.14)
  • bool Bool değerleri (ör: true, false)
  • string String literal (ör: "Hello World")

Syntax örnekleri:

Artık değer bildiriminde veri tipi yazılması gerekiyor. let ile yazmayı kaldırdım. Bunun nedeni ise fonksiyon parametrelerinde veri tiplerinin belirtilmemesi karışıklığa sebep oluyor.

int x = 11;
float armistice = 11.11;
string msg = "Outer Wilds";
bool metalGear = true;

Fonksiyonlar:

return tipi ve parametreleri belirtilmek zorunda.

int topla(int a, int b) {
  return a + b;
}

Control Flow:

if (x > 5) {
    x = x - 1;
} else {
    x = x + 1;
}

while (num > 0) {
    num = num - 1;
}

for (i = 0; i < 10; i = i + 1) {
    # Döngü gövdesi
}

Yorumlar: # ile başlayan satırlarla yorum yazılabilir

Gramer (EBNF)

/* High Level Structure */
program          ::= statement_list?
statement_list   ::= statement | statement_list statement
statement        ::= var_decl 
                   | func_decl 
                   | assignment_stmt 
                   | if_stmt 
                   | while_stmt 
                   | for_stmt 
                   | return_stmt 
                   | expr_stmt 
                   | blok

blok             ::= "{" statement_list "}" | "{" "}"

/* Data Types */
tip              ::= "int" | "float" | "bool" | "string" | "void"

/* Declarations */
var_decl         ::= tip TANIMLAYICI ("=" expression)? ";"
func_decl        ::= tip TANIMLAYICI "(" param_list? ")" blok
param_list       ::= param ("," param)*
param            ::= tip TANIMLAYICI

/* Control Flow */
if_stmt          ::= "if" "(" expression ")" blok ("else" blok)?
while_stmt       ::= "while" "(" expression ")" blok
for_stmt         ::= "for" "(" for_init expression ";" assignment ")" blok
for_init         ::= var_decl | assignment_stmt

/* Statements */
assignment_stmt  ::= assignment ";"
assignment       ::= TANIMLAYICI "=" expression
return_stmt      ::= "return" expression ";"
expr_stmt        ::= expression ";"

/* Expressions */
expression       ::= expression BINOP expression
                   | UNARYOP expression
                   | "(" expression ")"
                   | func_call
                   | LITERAL
                   | TANIMLAYICI

func_call        ::= TANIMLAYICI "(" arg_list? ")"
arg_list         ::= expression ("," expression)*

/* Terminals / Tokens */
BINOP            ::= "+" | "-" | "*" | "/" | "%" 
                   | "==" | "!=" | "<" | ">" | "<=" | ">=" 
                   | "&&" | "||"
UNARYOP          ::= "-" | "!"
LITERAL          ::= TAMSAYI | ONDALIKLI | "true" | "false" | STRING
TANIMLAYICI      ::= [a-zA-Z_][a-zA-Z0-9_]*

AST Node Yapısı

ast_structure.py dosyasında sınıflandırılmalar bulunmakta.

  • Program: Root node, statement'ların listesini içerir.

  • Blok: {} gibi bloklari temsil eder.

  • Declarationlar:

    • DegiskenBildir: Değişken adı ve verilen değer (None da olarabilir).

    • FonksiyonBildir: Fonksiyon adı, parametre listesi ve gövde bloğu bulundurur.

  • Statementlar:

    • IfStatement: Condition, doğru bloğu ve opsiyonel else bloğu.

    • WhileStatement: Condition ve gövde bloğu.

    • ForStatement: Initialization, condition, update ve gövde.

    • ReturnStatement: Dönüş değeri döndürür.

    • Atama: Değişken ismi ve yeni değer.

  • Expressionlar:

    • BinaryOp: Sol, operatör, sağ node'u.

    • UnaryOp: Operatör ve expression node'u.

    • FonksiyonCall: Fonksiyon adı ve argüman listesi.

    • Literal: Değer ve tür (int, float, bool).

    • Tanimlayici: Değişken adı araması.

İmplementasyon Detayları

Code generation'dan önce Semantic Analysis için Visitor Pattern (semantic_analyzer.py) kullanılıyor.

  • Symbol Table: (symbol_table.py) Scope'u stack olarak belirtir (Global -> Fonksiyon -> Blok)
  • Scope Resolution: { ... } şeklindeki bloklardan çıkıldığında değişkenler sembol tablosundan kaldırılır.
    (Not: Bu sadece fonksiyonlarda geçerli, normal bloklarda scope kaybolur.)
int x = 10;

if (true) {
    int x = 20;
    x = x + 5;  # Gövdede x = 25
}

Output'u (Normalde Scope Resolution'a göre 10 olmalı)

--- VM Calisiyor ---
 > Defined x = 10
 > Defined x = 20
--- VM Bitti ---
Final Global Memory: {'x': 25}

Ama fonksiyonlarda durum farklı

int x = 10;

int topla(int a, int b) {
    int x = 25;
    return a + b + x;
}
int sonuc = topla(5, 15); # 5 + 15 + 25 = 45

Yukarıdaki gibi sonda x = 25 olmasını beklerken x = 10 değerini koruyor.

--- VM Calisiyor ---
 > Defined x = 10
 > Defined topla = 5
 > Defined b = 15
 > Defined a = 5
 > Defined x = 25
 > Defined sonuc = 45
--- VM Bitti ---
Final Global Memory: {'x': 10, 'topla': 5, 'sonuc': 45}
  • Type Checking:
    • Değişkenler atanan değerlere uyuşmalı
    • Binary operasyonları (ör: +, >) uyumlu tipler arasında olmalı
    • Fonksiyon argümanları belirtilen tipe şekle uymalı
    • Fonksiyon return değeri belirtilen tipte return tipi döndürür

Kullanılan Mimari: Stack-Based Bytecode

MIPS/x86 spesifik hardware register'ları kullandığı için platform-independent Bytecode daha kolay.

Ayrıca compiler Python'da yazıldığından VM ile test etmek daha basit.

Bazı Eksiklerler

Array, Struct, Pointer gibi veri yapıları eklenmedi. Optimizasyonlar implemente edilmedi.
Input, print gibi fonksiyonlar diğer dillerin kütüphanelerinde olan fonksiyonlar yok.

Örnek Outputlar

Lexical Analysis

int x = 5 * 3 + 5;

float x = 5.0 * 3.0 + 5.0;

$$$$

Verilen input: 'int x = 5 * 3 + 5;'

TOKEN TYPE                VALUE           LINE  POS
-------------------------------------------------------
TIP_INT                   int             1     0
TANIMLAYICI               x               1     4
ATAMA                     =               1     6
TAMSAYI                   5               1     8
CARP                      *               1     10
TAMSAYI                   3               1     12
TOPLA                     +               1     14
TAMSAYI                   5               1     16
NOKTALI_VIRGUL            ;               1     17

Verilen input: 'float x = 5.0 * 3.0 + 5.0;'

TOKEN TYPE                VALUE           LINE  POS    
-------------------------------------------------------
TIP_FLOAT                 float           1     0      
TANIMLAYICI               x               1     6
ATAMA                     =               1     8
ONDALIKLI                 5.0             1     10
CARP                      *               1     14
ONDALIKLI                 3.0             1     16
TOPLA                     +               1     20
ONDALIKLI                 5.0             1     22
NOKTALI_VIRGUL            ;               1     25

Verilen input: '$$$$'

TOKEN TYPE                VALUE           LINE  POS
-------------------------------------------------------
Geçersiz karakter '$'
Geçersiz karakter '$'
Geçersiz karakter '$'
Geçersiz karakter '$'

Göründüğü gibi integer ve float arasındaki TIP_INT, TIP_FLOAT ve TAMSAYI, ONDALIKLI farkını görebiliyoruz.

Ayrıca dolar işaretini ($) gramere tanımlamadığımdan, lexer hata veriyor.

Parsing

int x = 5 * 3 + 5;

float x = 5.0 * 3.0 + 5.0;

string hatali = 34;

PARSER OUTPUT (Abstract Syntax Tree)
------------------------------------------------------------
Program
  statements: [
    DegiskenBildir
      isim: x
      tip: int
      deger:
        BinaryOp
          sol:
            BinaryOp
              sol:
                Literal
                  deger: 5
                  tip: int
              op: *
              sag:
                Literal
                  deger: 3
                  tip: int
          op: +
          sag:
            Literal
              deger: 5
              tip: int
  ]
============================================================

PARSER OUTPUT (Abstract Syntax Tree)
------------------------------------------------------------
Program
  statements: [
    DegiskenBildir
      isim: x
      tip: float
      deger:
        BinaryOp
          sol:
            BinaryOp
              sol:
                Literal
                  deger: 5.0
                  tip: float
              op: *
              sag:
                Literal
                  deger: 3.0
                  tip: float
          op: +
          sag:
            Literal
              deger: 5.0
              tip: float
  ]
============================================================

============================================================
PARSER OUTPUT (Abstract Syntax Tree)
------------------------------------------------------------
Program
  statements: [
    DegiskenBildir
      isim: hatali
      tip: string
      deger:
        Literal
          deger: 34
          tip: int
  ]
============================================================

Göründüğü gibi semantic olarak string'e integer atanamaz ancak syntax olarak yanlış bir şey olmadığından AST'yi görebiliyoruz.

Buradaki AST biraz daha düzgün gözükmesi için print_ast fonksiyonununu kullandım. Ayrıca, int x = 5 * 3 + 5;'in farklı bir biçimde gösterimi

alt text

Semantic Analysis (Type Checking & Scoping)

int x = 10;
  
void hesapla(int a) {
  int sonuc = a + x;
}

int x = 10;

void hesapla(int a) {
  void topla(int b) {
    int sonuc = a + b;
  }
}

string hatali = 34;

Verilen Kod:
int x = 10;
    
    void hesapla(int a) {
        int sonuc = a + x;
    }
------------------------------------------------------------
Analiz Basliyor...
        --- Blok Scope (Derinlik: 2) ---
          sonuc: {'type': 'int', 'category': 'var'}
        ------------------------------
    --- Fonksiyon: hesapla (Derinlik: 1) ---
      a: {'type': 'int', 'category': 'param'}
    ------------------------------
--- Global Scope (Derinlik: 0) ---
  x: {'type': 'int', 'category': 'var'}
  hesapla: {'type': 'function', 'category': 'func', 'params': ['int'], 'return_type': 'void'}
------------------------------
Analiz Bitti.

Verilen Kod:
int x = 10;

    void hesapla(int a) {
        void topla(int b) {
            int sonuc = a + b;
        }
    }
------------------------------------------------------------
Analiz Basliyor...
                --- Blok Scope (Derinlik: 4) ---
                  sonuc: {'type': 'int', 'category': 'var'}
                ------------------------------
            --- Fonksiyon: topla (Derinlik: 3) ---
              b: {'type': 'int', 'category': 'param'}
            ------------------------------
        --- Blok Scope (Derinlik: 2) ---
          topla: {'type': 'function', 'category': 'func', 'params': ['int'], 'return_type': 'void'}
        ------------------------------
    --- Fonksiyon: hesapla (Derinlik: 1) ---
      a: {'type': 'int', 'category': 'param'}
    ------------------------------
--- Global Scope (Derinlik: 0) ---
  x: {'type': 'int', 'category': 'var'}
  hesapla: {'type': 'function', 'category': 'func', 'params': ['int'], 'return_type': 'void'}
------------------------------
Analiz Bitti.

--- Semantic Analysis ---
Analiz Basliyor...
KRITIK SEMANTIC HATASI: HATA: hatali degiskeni 'string' turunde ama 'int' atandi.

Bu bölümde, global'den derinleşerek scope'un farklı derinliklerdeki variable'larını gözlemliyoruz.

Yanlış değişken atamasında ise hata gözlemliyoruz.

Oluşan Bytecode (program.bytecode)

0  : LOAD_CONST      5
1  : LOAD_CONST      3
2  : MUL
3  : LOAD_CONST      5
4  : ADD
5  : DEF_VAR         x
6  : HALT

Virtual Machine

--- VM Calisiyor ---
 > Defined x = 20
--- VM Bitti ---
Final Global Memory: {'x': 20}

Bütün Compiler Output (Tüm programın nasıl çalıştığını görmek için)

python main.py
==========================================

--- Compiler Design Project ---

--- Source Code ---
int x = 5 + 3;


--- Lexical Analysis ---
Tipi: TIP_INT         Degeri: int
Tipi: TANIMLAYICI     Degeri: x
Tipi: ATAMA           Degeri: =
Tipi: TAMSAYI         Degeri: 5
Tipi: TOPLA           Degeri: +
Tipi: TAMSAYI         Degeri: 3
Tipi: NOKTALI_VIRGUL  Degeri: ;
------------------------------------


--- Syntax Analysis (Parsing) ---
AST Tree Olusturuldu:
Program
  statements: [
    DegiskenBildir
      isim: x
      tip: int
      deger:
        BinaryOp
          sol:
            Literal
              deger: 5
              tip: int
          op: +
          sag:
            Literal
              deger: 3
              tip: int
  ]

--- Semantic Analysis ---
Analiz Basliyor...
--- Global Scope (Derinlik: 0) ---
  x: {'type': 'int', 'category': 'var'}
------------------------------
Analiz Bitti.
----------------------------


--- Bytecode Generation ---
0  : LOAD_CONST      5
1  : LOAD_CONST      3
2  : ADD
3  : STORE_VAR       x
4  : HALT
------------------------------


[INFO] Bytecode'program.bytecode' dosyasina kaydedildi.

--- Virtual Machine Execution ---
--- VM Calisiyor ---
 > x = 8
Program sonlandi.
--- VM Bitti ---
Final Memory State: {'x': 8}
==========================================

About

This project is a stack-based compiler made in Python using PLY. Includes Lexical Analysis, Syntax Analysis (AST Node), Semantic Analysis (Type Checking & Scoping), Bytecode Generation, Virtual Machine execution

Topics

parser ply lexer code-generation compiler-design semantic-analysis yacc-lex

Resources

Readme

License

MIT license
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages