Свой компилятор под Linux

Свой компилятор под Linux

При проектировании какого-либо компилятора или интерпретатора в качестве инструмента, как правило, выбирают язык C. А что если планируется создать "небольшой язык программирования", просто так, забавы ради (или, может быть, для более серьезного применения)? Чего беспокоиться, если вы обладаете достаточно мощным инструментом — интерпретатором Python!

Для распознавания неделимых лексических единиц и разбора выражений будем использовать модули Python Lex-Yacc (PLY). Эти модули достаточно точно соответствуют традиционным lex/yacc. Если вы умеете пользоваться этими инструментами, то при работе с PLY у вас затруднений не будет. Скачать PLY можно с system.cs.uchicago.edu/ply .

В рабочий каталог нужно переписать модули lex.py и yacc.py. Само собой, потребуется и Python версии 2.1 или выше.

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

Лексемы. Что такое лексемы? Лексемы — это символы, подобные +, -, * или /, или слова, такие, как begin, end, if или while, которые могут выступать в качестве операндов в выражениях, зарезервированных или ключевых словах и т.п. Лексемы должны быть определены как регулярные выражения.

Определение языка программирования. Поскольку пишется компилятор для нашего конкретного языка программирования, то следует начать с определения этого языка, записав для него набор грамматических правил. Например, если предполагается введение в язык конструкции 'if-then-else-endif', то правило достаточно просто можно записать так:

if_statement : IF LPAREN statement RPAREN multiple-statements ELSE

multiple-statements ENDIF

где (1) IF, LPAREN, RPAREN, ELSE и ENDIF — лексемы для синтаксических единиц if, (, ), else и endif соответственно. (2) 'statement' и 'multiple-statements' — различные конструкции, для которых должны быть определены свои правила.

Грамматический разбор. Говоря простыми словами, грамматический разбор (в просторечии — парсинг, от английского to parse) есть проверка соответствия исходного текста программы заданному набору правил. Существуют различные методы разбора, но нам нет нужды вдаваться в детали. Вам достаточно лишь знать, что, имея набор правил, синтаксический анализатор производит разбор текста программы в соответствии с этим набором.

Реализация . Итак, приступим к созданию компилятора. Процесс компиляции делится на несколько этапов:

Выделение лексем.

Грамматический разбор.

Выполнение действий, определяемых семантикой языка.

Создание промежуточного кода.

Оптимизация.

Создание результирующего кода.

Набор правил. Как уже упоминалось, сначала необходимо определить язык программирования, для которого реализуется компилятор. Определитесь, какой набор конструкций и операторов вы хотите предоставить. Такие конструкции, как 'while', 'if', ' assignment statements' (операция присваивания) и пр., обычно имеются в большинстве языков программирования, также как и арифметические операторы, такие, как +, -, *, / и пр. Затем необходимо создать набор грамматических правил для вашего языка программирования. Набор правил для поддержки операции присваивания приводится ниже:

assign_statement : VAR EQUALS statement

statement : statement ADDOP term

| statement SUBOP term

| term

term : term MULOP factor

| term divOP factor

| factor

factor : VAR

| NUM

| LPAREN statement RPAREN

Здесь и далее мы будем придерживаться следующих соглашений о написании лексем и правил. Лексемы мы будем записывать в верхнем регистре (NUM, VAR, EQUALS, ADDOP, SUBOP, MULOP, divOP, LPAREN, RPAREN), а правила (assign_statement, statement, term, factor) — в нижнем.

Определение лексем и их анализ. Далее определим набор используемых лексем. В данном примере используется девять лексем — NUM, VAR, EQUALS, ADDOP, SUBOP, MULOP, divOP, LPAREN и RPAREN. Следующая программа реализует простейший лексический анализатор для нашего языка программирования:

import lex

# Список лексем. Обязателен.

tokens = (

'NUM',

'VAR',

'EQUALS',

'ADDOP',

'SUBOP',

'MULOP',

'divOP',

'LPAREN',

'RPAREN'

)

# Регулярные выражения для выделения лексем.

t_VAR = r'[a-zA-Z_][\w_]*'

t_EQUALS = r'='

t_ADDOP = r'\+'

t_SUBOP = r'-'

t_MULOP = r'\*'

t_divOP = r'/'

t_LPAREN = r'\('

t_RPAREN = r'\)'

# Регулярное выражение, требующее дополнительных действий.

def t_NUM(t) :

r'\d+'

try:

t.value = int(t.value)

except ValueError:

print "Строка %d: Число %s слишком велико!" % (t.lineno, t.value)

t.value = 0

return t

# Правило трассировки номеров строк.

def t_newline(t):

r'\n+'

t.lineno += len(t.value)

# Строка, содержащая игнорируемые символы (пробелы и символы табуляции).

t_ignore = ' \t'

# Правило обработки ошибок

def t_error(t):

print "Недопустимый символ '%s'" % t.value[0]

t.skip(1)

# Создать анализатор

lex.lex()

# Получить данные со стандартного ввода

data = raw_input()

lex.input(data)

# Выделение лексем

while 1 :

tok = lex.token()

if not tok :

break

print tok

Если вы хотите использовать зарезервированные слова, то, как правило, достаточно добавить соответствующее имя (идентификатор) и создать функцию, реализующую действие зарезервированного слова, как показано ниже:

reserved = {

'if' : 'IF',

'then' : 'THEN',

'else' : 'ELSE',

'while' : 'WHILE',

...

}

def t_VAR(t):

r'[a-zA-Z_][\w_]*'

t.type = reserved.get(t.value,'ID') # Проверка на зарезервированное слово

return t

Грамматический разбор. Если использовать модуль yacc.py, то грамматический разбор становится достаточно простым делом. Грамматический анализатор вызывает лексический анализатор для выделения отдельных лексем, так что нужно импортировать написанный ранее модуль лексического разбора. Сейчас для каждого правила необходимо определить функцию, реализующую семантику данного правила, и задокументировать собственно правило. Пример грамматического анализатора приведен ниже:

# Yacc example

import yacc

# Получить таблицу лексем от лексического анализатора,

# который был создан нами ранее

# Для этого.

from ourlex import tokens

__var_names = {}

def p_assign_statement(t) :

'assign_statement : VAR EQUALS statement'

__var_names[t[1]] = t[3]

def p_statement_plus(t) :

'statement : statement ADDOP term'

t[0] = t[1] + t[3]

def p_statement_minus(t) :

'statement : statement SUBOP term'

t[0] = t[1] - t[3]

def p_statement_term(t) :

'statement : term'

t[0] = t[1]

def p_term_times(t) :

'term : term MULOP factor'

t[0] = t[1] * t[3]

def p_term_div(t) :

'term : term divOP factor'

t[0] = t[1] / t[3]

def p_term_factor(t) :

'term : factor'

t[0] = t[1]

def p_factor_num(t) :

'factor : NUM'

t[0] = t[1]

def p_factor_var(t) :

'factor : VAR'

if __var_names.has_key(t[1]) :

t[0] = __var_names[t[1]]

else :

print "Имя переменной", t[1], " в строке ", t.lineno(1), "не определено."

def p_factor_expr(t):

'factor : LPAREN statement RPAREN'

t[0] = t[2]

# Обработка синтаксических ошибок

def p_error(t):

print "Синтаксическая ошибка!"

# Создать грамматический анализатор

yacc.yacc()

while 1:

try:

s = raw_input('enter > ')

except EOFError:

break

if not s: continue

yacc.parse(s)

Здесь каждая функция принимает единственный аргумент t — массив, содержащий грамматические элементы:

def p_statement_plus(t):

'statement : statement ADDOP term'

#

# t[0] t[1] t[2] t[3]

t[0] = t[1] + t[3]

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

Предположим, что в результате работы компилятора должен получаться код на языке ассемблера для процессора 8086. Примем за правило, что регистр 'bx' используется для хранения промежуточных результатов. Встретив очередной операнд, необходимо содержимое регистра 'ax' переписать в регистр 'bx', после чего в регистр 'ax' занести новый операнд. Таким образом, последний встреченный операнд (или результат операции) всегда будет содержаться в регистре 'ax'.

def p_factor_num(t) :

'factor : NUM'

__output_fp.write("\tmov bx,ax\n"%f) # bx <-- [ax]

__output_fp.write("\tmov ax,0x%x\n"%t[1]) # ax <-- t[1]

где, '__output_fp' — дескриптор результирующего файла.

После того, как операнды подготовлены к выполнению операции (унарной или бинарной), мы можем описать семантику операции, например, сложения:

def p_statement_plus(t) :

'statement : statement ADDOP term'

__output_fp.write("\tadd ax,bx\n")

# ax <-- [ax] + [bx]

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

Оптимизация. Если говорить о компиляторе языка C, то ассемблерный код получается сложнее, чем описано выше. В действительности компилятор производит сначала некоторый промежуточный код, затем этот код оптимизируется, и, наконец, создается окончательный вариант ассемблерного кода.

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

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

Еще один пример локальной оптимизации — оптимизация безусловных переходов:

jmp .L1

.

.

.

.

.

.L1 jmp .L2

.

.

.

.

.

.L2 add ax,bx

В этом случае число выполняемых инструкций безусловного перехода можно сократить, изменив первую команду jump:

jmp .L2

.

.

.

.

.

.L1 jmp .L2

.

.

.

.

.

.L2 add ax,bx

Существуют различные алгоритмы оптимизации. Методы, описанные выше, являются лишь первым маленьким шагом в направлении оптимизации по времени исполнения и размеру создаваемого кода.

Заключение. Примеры, приведенные выше, не являются полнофункциональным компилятором. Для их завершения требуется реализовать гораздо большее число привычных конструкций. Эти примеры можно рассматривать лишь как иллюстрацию написания соответствующих этим привычным конструкциям правил, регулярных выражений (для выделения лексем), функций грамматического разбора и функций реализации семантики языка.

По материалам Dinil Divakaran

Подготовил X-Stranger