Пишем примитивный и никому не нужный компилятор

    Я считаю, что каждый программист должен написать свой компилятор.

    Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.

    В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.

    Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.

    Да, компилятор совершенно нагло основан на Tiny-С.

    Грамматика


    Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
    Уметь он будет очень мало:

    — единственный тип данных — int
    — все переменные — глобальные. Всего есть 26 переменных (a-z)
    — из математических операций поддерживаются только "+" и "-"
    — единственный оператор сравнения — это "<"
    — из конструкций языка — условные операторы if, if/else, while, do/while

    Все. Никаких массивов, функций, структур. Вот какая грамматика получается у нашего языка:

    <program> ::= <statement>
    <statement> ::= "if" <paren-expr> <statement> |
                     "if" <paren-expr> <statement> "else" <statement> |
                     "while" <paren-expr> <statement> |
                     "do" <statement> "while" <paren-expr> |
                     "{" { <statement> } "}" |
                     <expr> ";" |
                     ";"
    <paren-expr> ::= "(" <expr> ")"
    <expr> ::= <test> | <id> "=" <expr>
    <test> ::= <sum> | <sum> "<" <sum>
    <sum>  ::= <term> | <sum> "+" <term> | <sum> "-" <term>
    <term> ::= <id> | <int> | <paren-expr>
    <id>   ::= "a" | "b" | ... | "z"
    <int>  ::= <digit>, { <digit> }
    <digit> ::= "0" | "1" | ... | "9" 
    

    Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.

    Программа — это один оператор (statement).
    Операторы бывают условными (if..else...), циклическими (while...) и просто операторами (напр., «a=2+3»).
    Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
    Выражения — это либо сумма, либо присваивание переменной значения.
    Здесь сумма — это последовательность сложений-вычитаний термов.
    Терм — это число, переменная или выражение в скобках.
    Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.

    Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.

    Лексический анализатор


    На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.

    Итак, наш лексический анализатор должен узнавать следующие токены:

    — числа
    — идентификаторы-переменные
    — ключевые слова: if, else, while, do
    — символы +, -, <, =, {, }, (, ),;
    — конец файла

    Вот как выглядит его исходный код:

    class Lexer:
    
    	NUM, ID, IF, ELSE, WHILE, DO, LBRA, RBRA, LPAR, RPAR, PLUS, MINUS, LESS, \
    	EQUAL, SEMICOLON, EOF = range(16)
    
    	# специальные символы языка
    	SYMBOLS = { '{': LBRA, '}': RBRA, '=': EQUAL, ';': SEMICOLON, '(': LPAR,
    		')': RPAR, '+': PLUS, '-': MINUS, '<': LESS }
    
    	# ключевые слова
    	WORDS = { 'if': IF, 'else': ELSE, 'do': DO, 'while': WHILE }
    
    	# текущий символ, считанный из исходника
    	ch = ' ' # допустим, первый символ - это пробел
    
    	def error(self, msg):
    		print 'Lexer error: ', msg
    		sys.exit(1)
    
    	def getc(self):
    		self.ch = sys.stdin.read(1)
    	
    	def next_tok(self):
    		self.value = None
    		self.sym = None
    		while self.sym == None:
    			if len(self.ch) == 0:
    				self.sym = Lexer.EOF
    			elif self.ch.isspace():
    				self.getc()
    			elif self.ch in Lexer.SYMBOLS:
    				self.sym = Lexer.SYMBOLS[self.ch]
    				self.getc()
    			elif self.ch.isdigit():
    				intval = 0
    				while self.ch.isdigit():
    					intval = intval * 10 + int(self.ch)
    					self.getc()
    				self.value = intval
    				self.sym = Lexer.NUM
    			elif self.ch.isalpha():
    				ident = ''
    				while self.ch.isalpha():
    					ident = ident + self.ch.lower()
    					self.getc()
    				if ident in Lexer.WORDS:
    					self.sym = Lexer.WORDS[ident]
    				elif len(ident) == 1:
    					self.sym = Lexer.ID
    					self.value = ord(ident) - ord('a')
    				else:
    					self.error('Unknown identifier: ' + ident)
    			else:
    				self.error('Unexpected symbol: ' + self.ch)
    

    В методе next_tok() анализатор получает следующий токен. Тип токена можно получить из атрибута sym, а его значение (если это переменная или число) — из атрибута value.

    Анализатор игнорирует пробелы, проверяет, является ли текущий символ специальным символом языка, если нет — проверяет, является ли он числом или идентификатором. Т.е. встретив цифру 1, анализатор продолжит вычитывать символы, пока не встретит не-числовой символ. Аналогично проверяются идентификаторы (там вместо чисел буквы).

    Парсер


    Это, наверное, самый сложный компонент нашего компилятора. Его задача, используя токены, полученные от лексического анализатора, сформировать своего рода дерево, в котором иерархия и связи отображают структуру кода. Например:

    "if (a < 0) a = 5;"
    
    IF
    +-LESS
    |  +-VAR(a)
    |  +-NUM(0)
    +-SET
      +-VAR(a)
      +-NUM(5)
    


    Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR...), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.

    Для описания узлов введем класс Node. Вот код класса парсера и класса Node:

    class Node:
    	def __init__(self, kind, value = None, op1 = None, op2 = None, op3 = None):
    		self.kind = kind
    		self.value = value
    		self.op1 = op1
    		self.op2 = op2
    		self.op3 = op3
    
    class Parser:
    
    	VAR, CONST, ADD, SUB, LT, SET, IF1, IF2, WHILE, DO, EMPTY, SEQ, EXPR, PROG = range(14)
    
    	def __init__(self, lexer):
    		self.lexer = lexer
    
    	def error(self, msg):
    		print 'Parser error:', msg
    		sys.exit(1)
    
    	def term(self):
    		if self.lexer.sym == Lexer.ID:
    			n = Node(Parser.VAR, self.lexer.value)
    			self.lexer.next_tok()
    			return n
    		elif self.lexer.sym == Lexer.NUM:
    			n = Node(Parser.CONST, self.lexer.value)
    			self.lexer.next_tok()
    			return n
    		else:
    			return self.paren_expr()
    
    	def summa(self):
    		n = self.term()
    		while self.lexer.sym == Lexer.PLUS or self.lexer.sym == Lexer.MINUS:
    			if self.lexer.sym == Lexer.PLUS:
    				kind = Parser.ADD
    			else:
    				kind = Parser.SUB
    			self.lexer.next_tok()
    			n = Node(kind, op1 = n, op2 = self.term())
    		return n
    
    	def test(self):
    		n = self.summa()
    		if self.lexer.sym == Lexer.LESS:
    			self.lexer.next_tok()
    			n = Node(Parser.LT, op1 = n, op2 = self.summa())
    		return n
    
    	def expr(self):
    		if self.lexer.sym != Lexer.ID:
    			return self.test()
    		n = self.test()
    		if n.kind == Parser.VAR and self.lexer.sym == Lexer.EQUAL:
    			self.lexer.next_tok()
    			n = Node(Parser.SET, op1 = n, op2 = self.expr())
    		return n
    
    	def paren_expr(self):
    		if self.lexer.sym != Lexer.LPAR:
    			self.error('"(" expected')
    		self.lexer.next_tok()
    		n = self.expr()
    		if self.lexer.sym != Lexer.RPAR:
    			self.error('")" expected')
    		self.lexer.next_tok()
    		return n
    
    	def statement(self):
    		if self.lexer.sym == Lexer.IF:
    			n = Node(Parser.IF1)
    			self.lexer.next_tok()
    			n.op1 = self.paren_expr()
    			n.op2 = self.statement()
    			if self.lexer.sym == Lexer.ELSE:
    				n.kind = Parser.IF2
    				self.lexer.next_tok()
    				n.op3 = self.statement()
    		elif self.lexer.sym == Lexer.WHILE:
    			n = Node(Parser.WHILE)
    			self.lexer.next_tok()
    			n.op1 = self.paren_expr()
    			n.op2 = self.statement();
    		elif self.lexer.sym == Lexer.DO:
    			n = Node(Parser.DO)
    			self.lexer.next_tok()
    			n.op1 = self.statement()
    			if self.lexer.sym != Lexer.WHILE:
    				self.error('"while" expected')
    			self.lexer.next_tok()
    			n.op2 = self.paren_expr()
    			if self.lexer.sym != Lexer.SEMICOLON:
    				self.error('";" expected')
    		elif self.lexer.sym == Lexer.SEMICOLON:
    			n = Node(Parser.EMPTY)
    			self.lexer.next_tok()
    		elif self.lexer.sym == Lexer.LBRA:
    			n = Node(Parser.EMPTY)
    			self.lexer.next_tok()
    			while self.lexer.sym != Lexer.RBRA:
    				n = Node(Parser.SEQ, op1 = n, op2 = self.statement())
    			self.lexer.next_tok()
    		else:
    			n = Node(Parser.EXPR, op1 = self.expr())
    			if self.lexer.sym != Lexer.SEMICOLON:
    				self.error('";" expected')
    			self.lexer.next_tok()
    		return n
    
    	def parse(self):
    		self.lexer.next_tok()
    		node = Node(Parser.PROG, op1 = self.statement())
    		if (self.lexer.sym != Lexer.EOF):
    			self.error("Invalid statement syntax")
    		return node
    

    Этот парсер работает рекурсивно, начиная с метода parse().
    Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.

    Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.

    При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.

    Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.

    Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.

    На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.

    Машинный код


    Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:

    FETCH x - положить на стек значение переменной x
    STORE x - сохранить в переменной x значение с вершины стека
    PUSH  n - положить число n на вершину стека
    POP     - удалить число с вершины стека
    ADD     - сложить два числа на вершине стека
    SUB     - вычесть два числа на вершине стека
    LT      - сравнить два числа с вершины стека (a < b). Результат - 0 или 1
    JZ    a - если на вершине стека 0 - перейти к адресу a.
    JNZ   a - если на вершине стека не 0 - перейти к адресу a.
    JMP   a - перейти к адресу a
    HALT    - завершить работу
    

    Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:

    PUSH 2 STORE 0 PUSH 5 STORE 1
    

    Код виртуальной машины очень простой. Он весь описывается в методе run:

    IFETCH, ISTORE, IPUSH, IPOP, IADD, ISUB, ILT, JZ, JNZ, JMP, HALT = range(11)
    
    class VirtualMachine:
    
    	def run(self, program):
    		var = [0 for i in xrange(26)]
    		stack = []
    		pc = 0
    		while True:
    			op = program[pc]
    			if pc < len(program) - 1:
    				arg = program[pc+1]
    
    			if op == IFETCH: stack.append(var[arg]); pc += 2
    			elif op == ISTORE: var[arg] = stack.pop(); pc += 2
    			elif op == IPUSH: stack.append(arg); pc += 2
    			elif op == IPOP: stack.append(arg); stack.pop(); pc += 1
    			elif op == IADD: stack[-2] += stack[-1]; stack.pop(); pc += 1
    			elif op == ISUB: stack[-2] -= stack[-1]; stack.pop(); pc += 1
    			elif op == ILT: 
    				if stack[-2] < stack[-1]:
    					stack[-2] = 1
    				else:
    					stack[-2] = 0
    				stack.pop(); pc += 1
    			elif op == JZ: 
    				if stack.pop() == 0:
    					pc = arg
    				else:
    					pc += 2
    			elif op == JNZ: 
    				if stack.pop() != 0:
    					pc = arg
    				else:
    					pc += 2
    			elif op == JMP: pc = arg;
    			elif op == HALT: break
    
    		print 'Execution finished.'
    		for i in xrange(26):
    			if var[i] != 0:
    				print '%c = %d' % (chr(i+ord('a')), var[i])
    

    Осталось написать собственно компилятор — генератор кода.

    Компилятор


    Венец нашего творения. Вот его исходный код:

    class Compiler:
    	
    	program = []
    	pc = 0
    
    	def gen(self, command):
    		self.program.append(command)
    		self.pc = self.pc + 1
    	
    	def compile(self, node):
    		if node.kind == Parser.VAR:
    			self.gen(IFETCH)
    			self.gen(node.value)
    		elif node.kind == Parser.CONST:
    			self.gen(IPUSH)
    			self.gen(node.value)
    		elif node.kind == Parser.ADD:
    			self.compile(node.op1)
    			self.compile(node.op2)
    			self.gen(IADD)
    		elif node.kind == Parser.SUB:
    			self.compile(node.op1)
    			self.compile(node.op2)
    			self.gen(ISUB)
    		elif node.kind == Parser.LT:
    			self.compile(node.op1)
    			self.compile(node.op2)
    			self.gen(ILT)
    		elif node.kind == Parser.SET:
    			self.compile(node.op2)
    			self.gen(ISTORE)
    			self.gen(node.op1.value)
    		elif node.kind == Parser.IF1:
    			self.compile(node.op1)
    			self.gen(JZ); addr = self.pc; self.gen(0);
    			self.compile(node.op2)
    			self.program[addr] = self.pc
    		elif node.kind == Parser.IF2:
    			self.compile(node.op1)
    			self.gen(JZ); addr1 = self.pc; self.gen(0)
    			self.compile(node.op2)
    			self.gen(JMP); addr2 = self.pc; self.gen(0)
    			self.program[addr1] = self.pc
    			self.compile(node.op3)
    			self.program[addr2] = self.pc
    		elif node.kind == Parser.WHILE:
    			addr1 = self.pc
    			self.compile(node.op1)
    			self.gen(JZ); addr2 = self.pc; self.gen(0)
    			self.compile(node.op2)
    			self.gen(JMP); self.gen(addr1);
    			self.program[addr2] = self.pc
    		elif node.kind == Parser.DO:
    			addr = self.pc
    			self.compile(node.op1)
    			self.compile(node.op2)
    			self.gen(JNZ); 
    			self.gen(addr);
    		elif node.kind == Parser.SEQ:
    			self.compile(node.op1)
    			self.compile(node.op2)
    		elif node.kind == Parser.EXPR:
    			self.compile(node.op1);
    			self.gen(IPOP)
    		elif node.kind == Parser.PROG:
    			self.compile(node.op1);
    			self.gen(HALT)
    		return self.program
    
    

    Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
    В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.

    Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.

    Тестируем


    Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):

    echo " i =	3;"  | ./cc.py
    echo " { a=3; b=5; }"  | ./cc.py
    echo " { a = 1; b = 2; c = a + b; }"  | ./cc.py
    echo " { a = 5; b = 2; c = a - b; }"  | ./cc.py
    echo " { a = 5; b = 2; c = b < a; }"  | ./cc.py
    echo " { a = 5; if (a < 10) a = 33; }"  | ./cc.py
    echo " { a = 5; if (10 < a) a = 33; else { a = 1; b = 2; } }"  | ./cc.py
    echo " { a = 10; do { a = a - 2;}  while (3 < a); }" | ./cc.py
    echo " { a = 1; b = 5; while (a < b) { a = a + 3; }}" | ./cc.py
    

    Ответы машина выдавала вроде бы правильные.

    Что дальше?


    Применений у нашего компилятора нет. Зато получен опыт.
    Я надеюсь, вам еще больше хочется написать свой компилятор. Тогда лучше начинать с языков с простым синтаксисом, напр. TinyBasic или PL/0.
    Если вам хочется почитать исходники других компиляторов, то советую обратить внимание на работу Белларда (otcc), tinyc, tcc, smallC, lcc.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 67

      +39
      Мб перенести в компиляторы? Статья отличная, все по феншую. Лексер, парсер, компилятор, машина. Вот бы такую статью да не третьем курсе прочитать.
        –3
        Я на втором курсе написал компилятор подмножества Оберона-2 со стековой архитектурой процедур и функций за три вечера. Там же ничего сложного, но да, ЧСВ сильно поднимается, когда запускаешь решение задачи о Ханойских башнях на «своём» языке и оно работает.
          0
          Хм, странно, у нас компиляторы были обязательным предметом то ли на третьем, то ли на четвертом курсе. Вся группа что-то свое писала. Я думал, у всех это наряду с базами данных в обязательную ВУЗовскую программу входит.
            –1
            Именно так, просто у нас это было на втором курсе.
          0
          Ну, не всё по феншую, зато всё понятно.
            0
            И компактно :-)
            На Java с нормальным полиморфизмом и отвязкой через интерфейсы у меня около 40 классов и интерфейов на вычислитель выражений уходило :-)
          +10
          Супер! Кроме одного: зачем такое позиционирование, что «самый бесполезный» и «никому не нужный»?

          Очень полезный! Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.
          Стремление к этому подтолкнуло многих из нас стать разработчиками, программистами, электронщиками.
            +2
            Но ведь пользы от самого компилятора (от использования) — никакой. Польза от написания/разбирания принципов работы/чтения исходников/модифицирования — да, это есть. Но это что ли косвенная польза. Хотя, конечно, пост писался именно ради нее.
              0
              Ну раз ради нее, то и цель достигнута, и польза совсем не косвенная :) Спасибо за отличную статью!
                +1
                Пожалуйста :)
                +2
                Косвенная польза зачастую является самой важной ;)
                И вообще, категории косвенного и явного в жизни перепутаны, но это не меняет их сути:
                «Но мы знаем, что о главном не пишут в газетах, и о главном молчит телеграф»(с)
                0
                Именно. Полностью согласен. Только этого не понимают те, кто кричат налево и направо «велосипед!».

                Нет ничего полезнее, чем что-то разобрать, а потом собрать свое, прочувстовав «устройство» изнутри, создать, вдохнув новую жизнь, трансформировать, понять, в конце концов.

                В точку!
                +2
                Небольшое замечание про lcc — это один из самых кривых компиляторов, которые я когда-либо видел с точки зрения понятности кода. Там не то, что без поллитра, там без ящика водки не разберёшься.

                В общем, крайне не рекомендую для начинающих.
                  +2
                  Да, видимо не зря они его книжкой дополняют
                    +1
                    У меня было такое ощущение, что сорсы специально так написаны, чтобы без книжки было бы вообще ничего не понятно — чтобы книжка продавалась. Но и с книжкой там жесть и мракобесие.
                      0
                      Так, автор в статье писал о Tiny-C, TCC и LCC это как бы разные проекты. Я чего-то пропустил?
                        0
                        А я конкретно про lcc прокоментировал.
                  +1
                  Статья полезная, но при написании более сложного компилятора, лучше посмотреть в сторону генераторов компиляторов.
                    0
                    само собой, просто я не мог понять что такое, скажем, ANTLR, пока не написал свой парсер вручную с нуля.
                    +1
                    Не знаю насколько этот компилятор ненужный в прямом смысле (для компиляции) а вот косвенно мне он очень помог. (После прочтения пришла в голову одна интересная мысль которая до прочтения как-то даже не приходила в голову.)
                      +2
                      Не поделитесь?)
                      +3
                      Статья из жанра «делай как я» :)

                      Статья хорошая, но без теории на мой взгляд бесполезная.
                      Лексер (кажется) написан правильно, но нет ни слова про конечный автомат. Нет диаграммы состояний для грамматики.
                      Кстати, грамматика у вас правосторонняя или она просто не формализована?
                        0
                        А вообще судя по такому количеству голосов у статьи, похоже пора публиковать свой компилятор модифицированного HLL/0, который мы с другом писали на 4-м курсе ;)
                        Тема, видимо, актуальная.
                          +6
                          Скорее не актуальная, а редкая. Материалов такого размаха (и простоты) на эту тему не так и много, причём все они либо слишком поверхностные (на которые даже новички не смогут ответить ничего кроме «спасибо кэп») либо наоборот сильно «заумные» (опытные программисты также разве что поблагодарят кэпа, а новички же не поймут ровным счётом ничего)

                          Если вы сможете подобрать правильный баланс (чтоб и новички поняли, и опытные хотя бы с умилением улыбнулись) то не исключаю что плюсов хапните даже больше.
                            +2
                            А всё от того, что разработку компиляторов по обрывочным статьям не изучить. Книга дракона не зря написана, там уж профессионалы смогли скомпоновать материал так, чтобы можно было начать читать не зная даже что такое терминал.
                              0
                              Там не скомпоновали, а скорее упорядочили (от простого к сложному) но когда читаешь не книгу на 1000+ страниц, а коротенькую статью, то хочется чтоб было мало, но по делу. (Чтоб и просто, и с пользой, а не цитата из какой нибудь вики с припиской «остальное учите в институте»)
                        0
                        При описании граматики мне кажется вы путаете operator и statement. Это же две совершенно разные вещи.
                        Путаете не в том смысле что у неправильное или нелогичное описание, с этим вроде всё в порядке, а вот эти два термина используются нелогично, и даже в некоторых местах меняются между собой…
                          0
                          увы, есть некоторая путаница, просто statement на русском звучит как «оператор». Но, к сожалению от русского слова оператор в значении «оператор сложения» я тоже отказаться не смог. Потому да, несколько нелогично.
                            –2
                            >увы, есть некоторая путаница, просто statement на русском звучит как «оператор»

                            Разве? А мне кажется statement на русском будет «выражение».
                              –1
                              Я тоже так думал, но как тогда отличать expression и statement? В википедии статье statement соответствует статья «оператор».
                                +3
                                В обращении редакции третьего русского издания Страуструпа «ЯП С++» к читателю, переводчики пишут, что statement они будут переводить как «инструкция», так как во-первых, такой перевод периодически встречается в литературе, и, во-вторых, для слова «оператор» Страуструп использовал слово «operator». Здесь конечно всё в контексте плюсов, но факт в том, что statement можно понимать и как инструкция :)
                                –1
                                Выражение — Expression.
                                Statement — скорее конструкция или оператор (оператор цикла, условия).
                                  0
                                  В зависимости от контекста, да. Я подразумевал «выражение» в смысле «конструкция» :)
                            0
                            Понравилось. Еще интересно было бы почитать, как в подобных компилятора организовать замыкания, сборку мусора и другие современные штуки. Не планирует никто статью написать?
                              +1
                              Вопрос не к компилятору, а скорее к виртуальной машине, под которую генерируется байт-код.
                              +1
                              Давно мечтал написать компилятор, теперь появился еще один стимул это сделать. Спасибо за статью=)
                                –1
                                В далекие времена, когда я учился на 1-м курсе решил устроиться на работу. В качестве тестового задания сказали написать свой интерпретатор языка Паскаль. Задача была сделана за 2 месяца, ту работу бросил, но кайф от получения такого опыта остался на всю жизнь.

                                Всем начинающим программистом в качестве проверки на вшивость — такая задачка — просто удовольствие!
                                +2
                                Вот кстати, кому интересно напомню ссылку на потрясающий, на мой взгляд, цикл лекций на эту тему
                                habrahabr.ru/blogs/programming/99162/
                                  +3
                                  Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины
                                  С формальной точки зрения, это не компиляция, а трансляция.
                                    +6
                                    Рекомендую к прочтению «Книга Дракона-2» (Dragon Book-2) — «Компиляторы: принципы, технологии и инструменты», 2-е издание, Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман, 1184 стр., ISBN 978-5-8459-1349-4, «ВИЛЬЯМС», 2011

                                    Это основная книга по теме разработки компиляторов
                                      0
                                      Спасибо, не знал что вышла вторая редакция.
                                      0
                                      Вот ещё интересная статья Питера Норвига о написании крохотного интерпретатора Scheme на Python. Это поможет заметить и понять общие концепции в создании трансляторов, благо код Норвига прост, понятен и мал по размеру.
                                        –6
                                        Реализовали вы не компилятор, а интерпретатор (транслятор).
                                        Перевод с одного языка на другой. Не более.
                                          +1
                                          О боже, тогда javac ведь не компилятор!!11
                                          Если серьёзно, то компилятор автора всего лишь не превращает инструкции с операндами в поток байтов, но это не делает его менее компилятором.
                                          И вообще, «перевод с одного языка на другой»… А чем компиляторы, по-вашему, занимаются? То, что вы в своём ВУЗе реализуете подмножество x86 хардварно, ещё не делает вас спецом по теме трансляции, что прекрасно видно по вашему комментарию-придирке.
                                            +3
                                            Между прочим, человек, с одной стороны, прав.

                                            Транслятор — программа или техническое средство, выполняющее трансляцию программы, т.е. преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.

                                            Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором.

                                            С другой стороны, в той же книге дракона приводится такое определение:

                                            Компилятор — это программа, которая считывает текст программы, написанной на одном языке — исходном, и транслирует (переводит) его в эквивалентный текст на другом языке — целевом.

                                            Как можно видеть, определение компилятора из книги дракона эквивалентно определению транслятора, однако первые два определения транслятора и компилятора даны в соотв. с ГОСТ 19781-83.

                                            Что касается языкового процессора Java, то в книге дракона про это также упомянуто: «Языковой процессор Java объединяет в себе и компиляцию, и интерпретацию. Исходная программа на Java может сначала компилироваться в промежуточный вид (байт-код). Затем байт-код интерпретируется виртуальной машиной.» И далее картинка, чтобы ещё больше всех запутать:



                                            Пояснение можно найти на вики: «Некоторые компиляторы (например, Java) переводят программу не в машинный код, а в программу на некотором специально созданном низкоуровневом интрепретируемом языке. Такой язык — байт-код (в случае с Java Java-байт-код) — также можно считать языком машинных команд, поскольку в качестве его интерпретатора используется виртуальная машина. Байт-код не является машинным кодом какого-либо компьютера, то есть машинным кодом в прямом смысле слова, и может переноситься на различные компьютерные архитектуры без перекомпиляции. Байт-код интерпретируется (исполняется) виртуальной машиной.»

                                            Таким образом, дабы избежать взаимоисключающих параграфов, можно сказать, что:

                                            1) Транслятор — программа или техническое средство, выполняющее преобразование программы, представленной на одном из языков программирования (исходном), в программу на другом языке (целевом) и, в определённом смысле, равносильную первой.
                                            2) Компилятор — это транслятор, который преобразует программы в машинный язык, принимаемый и исполняемый непосредственно процессором, или в промежуточный код (байт-код Java, MSIL), предназначенный для дальнейшей интерпретации виртуальной машиной.

                                            Однако это так я думал пару минут назад, пока не прочел это: «Важной исторической особенностью компилятора, отражённой в его названии (англ. compile — собирать вместе, составлять), являлось то, что он мог производить как трансляцию так и компоновку (то есть состоял из двух частей — транслятора и компоновщика). Это связано с тем, что раздельные трансляция и компоновка как отдельные фазы компиляции выделились значительно позже появления компиляторов. В связи с этим, вместо термина «компилятор» иногда используют термин «транслятор» как его синоним, что, правда, терминологически неправильно: либо в старой литературе, либо когда хотят подчеркнуть его способность переводить программу в машинный код (и наоборот, используют термин «компилятор» для подчёркивания способности собирать из многих файлов один).»

                                            Таким образом получаем, что компилятор = транслятор + компоновщик. Хм. Истину ищите сами.

                                            Одно могу сказать точно, интерпретатор != транслятор, как утверждает sig.
                                            –1
                                            Минусуйте сколько хотите. Я «съел собаку» на теории компиляции и способен рассуждать на любую тему относительно данной дисциплины.
                                            К тому же, помимо написания «компилятора» как вы его гордо называете, я писал микропрограммы для машинных команд, из которых формировалась целевая программа генератором кода. Эта программа в дальнейшем запускалась на виртульной СМ ЭВМ 85 годов.
                                            upd:
                                            И еще, «минусовщики», отписывайтесь в комментариях — народ должен знать вас в лицо.
                                              0
                                              Надеюсь, я буду единственным, чтобы не засорять более тему спорами. Для таких придирчивых, как вы, могу пояснить, что я имел ввиду не грибные споры, а разговорные.
                                              Так вот, всё это замечательно, что вы вот такой крутой и писали микрокоманды, но вот какого лешего вы прицепились к автору топика? Даже не поблагодарили за хороший пост после этого. В посте ставилась задача — написать простой компилятор и уложиться в разумный объём. Задача выполнена. ОК, может, автор применил слегка неправильную терминологию. Но вот это ваше презрительное «не более» совершенно неуместно. Пока всё выглядит так, словно съеденная вами собака сбежала с кафедры терминологии и демагогии.
                                                –1
                                                У вас уже выборы начались, что вы так яростно мне крестики ставите возле моих постов?
                                              0
                                              Компилятор это и есть переводчик с одного языка на другой.
                                              0
                                              Спасибо за стаатью. Почитал вчера вечером за чашечкой кофе ваше творение. То, что было нужно.
                                                –1
                                                Автору респект не только за статью но и за ее позиционирование! Действительно от компилятора в прямом смысле толку мало, но именно для того, чтобы понять как все устроено и надо писать свои велосипеды. Я написал свой компилятор-транслятор на 5 курсе. Осталось подсадить дерево и вырастить сына.
                                                  +1
                                                  Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки.
                                                  Простые смертные студенты специальности «программное обеспечение вычислительной техники и автоматизированных систем» постигают и осиливают написание компилера си-лайт на 4ом курсе.
                                                    0
                                                    Тут всё зависит от уровня преподов и студентов. Например, я учил преподов программированию, а не они — меня. Какие уж тут компиляторы. У вас было лучше, рад за вас (честно).
                                                    +1
                                                    В топике не хватает ссылки на PLY (Python Lex-Yacc).
                                                      0
                                                      У меня есть идеи по реализации custom процессора в FPGA, есть ли кто-нибудь кому интересно реализовать компилятор под него? just for fun, естественно…
                                                        –1
                                                        > Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.

                                                        Напишите отладчик. Вот это уже действительно challenge ;)
                                                          0
                                                          Таки на карму-рейтинги мне всё равно, но если проминусовавший будет пробегать, попрошу аргументировать точку зрения, по поводу дебаггеров.
                                                          0
                                                          Вы так «аппетитно» написали, что мне захотелось тоже написать компилятор (на основе Вашего, но на LabVIEW). И это может получиться забавно — компилятор текстового языка на языке графическом.
                                                            0
                                                            >Это, наверное, самый сложный компонент нашего компилятора

                                                            В Real-World компиляторах, кстати, как правило — самый простой(не парсер конкретно, а вообще, часть, отвечающая за разбор).

                                                            Про грамматику надо было сказать. Грамматика, вроде бы, сводится к LL(1), значит надо было этот момент объяснить, переписать её соответствующим образом, и в коде сделать нормальный предикативный анализатор, а не какое-то его ad-hoc подобие, как сейчас.

                                                            Кстати, настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.
                                                              0
                                                              >предикативный
                                                              «предиктивный», всмысле

                                                              в 3 ночи голова не работает :)
                                                                0
                                                                > настоящие компиляторы выстраиванием AST занимаются довольно редко, и обычно генерируют код прямо в процессе разбора.

                                                                А оптимизации?
                                                                  0
                                                                  ну для высокоуровневых оптимизаций лучше подходит какое-то внутреннее представление типа flow graph
                                                                  0
                                                                  Еще про грамматики можно пару слов, какие бывают и в чём различия?

                                                                  [i]сейчас начал читать TAPL, до книги дракона не добирался еще.[/i]
                                                                0
                                                                А в TAPL разве есть про компиляторы?

                                                                Грамматики бывают разные, но если говорить про контекстно-свободные, то LL(k) грамматики это такие, для которых можно построить LL(k) анализатор, то есть парсер, разбирающий токены слева направо(первая L) сверху вних и строящий левый вывод(вторая L), заглядывающий вперед на k токенов, и, соответственно, работающий за линейное время и не требующий бэктрекинга. LL(1) парсер это, например, рекурсивно нисходящий предиктивный парсер, или аналогичный автомат со стеком.

                                                                LL(1) это очень узкий класс грамматик, но некоторые языки разрабатывались специально чтобы их можно было разобрать LL(1), например паскаль.

                                                                LL(1) грамматика не допускает левой рекурсии, так как это означает бесконечный цикл в анализаторе, и, кроме того, к правильной LL(1) грамматике должен быть применен left-factoring.

                                                                Пример, LL(1) для классических S-выражений:

                                                                expression -> STRING
                                                                              | SYMBOL
                                                                              | NUMBER
                                                                              | QUOTE expression
                                                                              | LEFT_PAREN parenExpression
                                                                
                                                                parenExpression -> RIGHT_PAREN
                                                                                   | expression restParenExpression
                                                                
                                                                restParenExpression -> RIGHT_PAREN
                                                                                       | DOT expression RIGHT_PAREN
                                                                                       | expression restParenExpression
                                                                
                                                                


                                                                  0
                                                                  Спасибо за ответ, внесу в закладки.

                                                                  В TAPL про компиляторы ничего толком пока нету, он весь про типы. Но чтобы писать свои компиляторы и проводить ресёрчи в области ЯП необходимо знать основы, имхо.
                                                                  0
                                                                  От чего же «примитивный и никому не нужный компилятор», следующим шагом в изучении можно и переписать его код на TinyC сделав его самодостаточным.

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое