Skip to content

Latest commit

 

History

History
131 lines (88 loc) · 3.96 KB

compilers.md

File metadata and controls

131 lines (88 loc) · 3.96 KB
Raw

Имплементиране на прост интерпретатор


Георги Наков, nakov.gl at gmail com
Марин Маринов, marinov.ms+tues at gmail com

Технологично училище "Електронни Системи"
07 Декември 2016г.

Какво представляват програмите?

  • текст написан в определена, предварително дефинирана граматика и синтаксис
  • граматиката напомня на тази от часовете по Български, но е много по-проста и регулярна (няма изключения)
  • синтакисът е ограничен и съдържа "ключови думи", които са запазени и имат специално значение

Как от текст стигаме до изпълнение?

  • първо трябва да разделими програмния текст на думи (също както и в естествения език)
  • прилагайки правилата на граматиката трябва да създадем структури, които съдържат казаното (в натуралния език това е разпознаване на изречението като такова и разделянето му на подлог, сказуемо и пр.)
  • ако казаното е граматически вярно, да се опитаме да го изпълним (да осмислим изречението и да изпълним това което е казано)

Формални имена

Всеки от тези етапи си има формално име:

  • разделянето на текста на думи - лексически анализ или tokenization
  • групиране и валидиране на думите спрямо граматиката - parsing
  • изпълнението - execution или evaluation

Каква е разликата между интерпретатор и компилатор?

Времето на изпълнение!

Интерпретатор Компилатор
  • tokenization
  • parsing
  • evaluation
  • tokenization
  • parsing
  • creation of executable
  • .. running the executable by third parties

Пример

Прост език, който съдържа едиствено числа и събиране. Кодът е псевдо код.

Tokenizer

token ADD        = "+"
token (Number n) = one or more of ["0".."9"]

Tokens[] getTokens(String str) {
    Tokens[] result = [];

    loop {
      str = skipWhitespace(str);

      if (str is empty)
          if (result is empty)
             throw "Empty input"
          else return result

      if (str is "+":rest) 
          result.push(ADD), str = rest;

      if (str is digits:rest)
          result.push(Number digits), str = rest;
      
      throw "Not a valid token"
    }
}

Parser

grammar Term = Number
             | Number "+" Term

data Expr = Const Number
          | Add Number Expr

Expr parse(Tokens[] toks) {
    if (toks is (n is Number):rest) {
       if (rest is "+":rest2)
           return Add n (parse rest2);
       
       if (rest is empty)
           return Const n
       
       throw "Extra input"
    }

    throw "Number expected"
}

Резултати

Input:  "1"
Tokens: [Number 1]
Parsed: Const (Number 1)

Input: "1 + 2 + 3"
Tokens: [Number 1, "+" Number 2, "+", Number 3]
Parsed: Add (Number 1) (Add (Number 2) (Number 3))

Input "1 + 2 + +"
Tokens: [Number 1, "+" Number 2, "+", "+"]
Parsed: throws "Number expected"