|
Создание компилятора на Python
|
1. Введение1.1 ЦельПри проектировании какого-либо компилятора или интерпретатора в качестве инструмента, как правило, выбирают язык C. А что если планируется создать "небольшой язык программирования" , просто так, забавы ради (или, может быть, для более серьёзного применения)? Чего беспокоиться, если вы обладаете достаточно мощным инструментом -- интерпретатором Python! 1.2 ИнструментыДля распознавания токенов (неделимых лексических единиц) и разбора выражений будем использовать модули Python Lex-Yacc (PLY). Эти модули достаточно точно соответствуют традиционным lex/yacc. Если вы умеете пользоваться этими инструментами, то при работе с PLY у вас затруднений не будет. Скачать PLY можно с system.cs.uchicago.edu/ply. В рабочий каталог нужно переписать модули lex.py и yacc.py. Само собой, потребуется и Python версии 2.1 или выше. 2. Первый шагПеред тем, как углубиться в детали реализации, пройдемся по основным терминам и понятиям. 2.1 ЛексемыЧто такое лексемы? Лексемы -- это символы, подобные +, -, * или /, или это слова, такие как begin, end, if или while, которые могут выступать в качестве операндов в выражениях, зарезервированных или ключевых слов и т.п. Лексемы должны быть определены как регулярные выражения. 2.2 Определение языка программированияПоскольку пишется компилятор для нашего конкретного языка программирования, то следует начать с определения этого языка, записав для него набор грамматических правил. Например, если предполагается введение в язык конструкции 'if-then-else-endif', то правило достаточно просто можно записать так:
if_statement : IF LPAREN statement RPAREN multiple-statements ELSE
multiple-statements ENDIF
где (1) IF, LPAREN, RPAREN, ELSE и ENDIF -- лексемы для
синтаксических единиц 2.3 Грамматический разборГоворя простыми словами, грамматический разбор (в просторечие -- парсинг, от английского to parse, не путать с пирсингом -- прим. ред. :) есть проверка соответствия исходного текста программы заданному набору правил. Существуют различные методы разбора, но нам нет нужды вдаваться в детали. Вам достаточно лишь знать, что, имея набор правил (см. пример выше), синтаксический анализатор производит разбор текста программы в соответствии с этим набором. 3. РеализацияИтак, приступим к созданию компилятора. Процесс компиляции делится на несколько этапов.
3.1 Набор правилКак уже упоминалось, сначала необходимо определить язык программирования, для которого реализуется компилятор. Определитесь, какой набор конструкций и операторов вы хотите предоставить. Такие конструкции, как '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) -- в нижнем. 3.2 Определение лексем и их анализДалее определим набор используемых лексем. В данном примере используется девять лексем -- 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
3.3 Грамматический разборЕсли использовать модуль 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 -- массив (на самом деле удобный Python'овый не-модифицируемый "массивосписок" -- tuple. прим. ред.), содержащий грамматические элементы:
def p_statement_plus(t):
'statement : statement ADDOP term'
# ^ ^ ^ ^
# t[0] t[1] t[2] t[3]
t[0] = t[1] + t[3]
3.4 СемантикаСемантика определяет последовательность действий, которые должен выполнить грамматический анализатор, когда ему удается свести входной поток до одного конкретного правила. В нашем примере семантика соответствует программе-интерпретатору. В случае простого компилятора, результатом работы может оказаться соответствующий правилу ассемблерный код. Предположим, что в результате работы компилятора должен получаться код на языке ассемблера для процессора 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]
Аналогичным образом, встретив объявление переменной, можно предусмотреть выбрать регистр процессора для ее хранения (локальные переменные предпочтительнее размещать на стеке), и запомнить выделенный регистр в словаре. Всякий раз, когда встречается ссылка на имя переменной, используя имя переменной в качестве ключа можно найти имя соответствующего регистра. 3.5 ОптимизацияЕсли говорить о компиляторе языка C, то ассемблерный код получается сложнее, чем описано выше. В действительности компилятор производит сначала некоторый промежуточный код, затем этот код оптимизируется и, наконец, создается окончательный вариант ассемблерного кода. Тема оптимизации кода слишком обширна, чтобы обсуждать ее здесь, поэтому остановимся лишь на самом простом методе оптимизации - локальная оптимизация [peephole optimization]. Простейший способ выполнения локальной оптимизации -- написать участок кода на языке ассемблера вручную и сравнить его с кодом, создаваемым вашим компилятором. Например, если в имеющемся наборе отсутствует инструкция умножения, то вы можете заставить компилятор производить код, выполняющий умножение, через последовательность сложений. В качестве оптимизации можно предложить проверять величину операндов, и если один из них равен 1, то в качестве результата можно сразу принять второй операнд, минуя цикл сложений. Далее, поскольку величина множителя (количество значимых бит прим. перев.) определяет количество итераций, в качестве множителя можно назначать меньший из операндов. Еще один пример локальной оптимизации -- оптимизация безусловных переходов:
jmp .L1
.
.
.
.
.
.L1 jmp .L2
.
.
.
.
.
.L2 add ax,bx
В этом случае, число выполняемых инструкций безусловного перехода можно
сократить, изменив первую команду
jmp .L2
.
.
.
.
.
.L1 jmp .L2
.
.
.
.
.
.L2 add ax,bx
Существуют различные алгоритмы оптимизации. Методы, описанные выше, являются лишь первым маленьким шагом в направлении оптимизации по времени исполнения и размеру создаваемого кода. 4. Что дальше?Примеры, приведенные выше, не являются полнофункциональным компилятором. Для их завершения требуется реализовать гораздо большее число привычных конструкций. Эти примеры можно рассматривать лишь как иллюстрацию написания соответствующих этим привычным конструкциям правил, регулярных выражений (для выделения лексем), функций грамматического разбора и функций реализации семантики языка. Dinil DivakaranЯ -- студент последнего года по специальности "Информатика" [computer science] в колледже GEC Thrissur в Керале, Индия.
Copyright (C) 2002, Dinil Divakaran.
|
|
Вернуться на главную страницу |