Дизайнер интерфейсов
0,0
рейтинг
17 декабря 2013 в 11:37

Разработка → Простой интерпретатор с нуля на Python (перевод) #1 из песочницы tutorial



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


В этом цикле статей я попытаюсь захватить часть этой простоты путем написания простого интерпретатора для обычного императивного языка IMP (IMperative Language). Интерпретатор будет написан на Питоне, потому что это простой и широко известный язык. Также, питон-код похож на псевдокод, и даже если вы не знаете его [питон], у вас получится понять код. Парсинг будет выполнен с помощью простого набора комбинаторов, написанных с нуля (подробнее расскажу в следующей части). Никаких дополнительных библиотек не будет использовано, кроме sys (для I/O), re (регулярные выражения в лексере) и unittest (для проверки работоспособности нашей поделки).

Сущность языка IMP

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

Присвоения (все переменные являются глобальные и принимают только integer):

x := 1


Условия:

if x = 1 then 
  y := 2 
else 
  y := 3
end


Цикл while:

while x < 10 do 
  x := x + 1
end


Составные операторы (разделенные ;):

x := 1; 
y := 2


Это всего-лишь игрушечный язык. Но вы можете расширить его до уровня полезности как у Python или Lua. Я лишь хотел сохранить его настолько простым, насколько смогу.

А вот тут пример программы, которая вычисляет факториал:

n := 5;
p := 1;
while n > 0 do
  p := p * n;
  n := n - 1
end


Язык IMP не умеет читать входные данные (input), т.е. в начале программы нужно создать все нужные переменные и присвоить им значения. Также, язык не умеет выводить что-либо: интерпретатор выведет результат в конце.

Структура интерпретатора

Ядро интерпретатора является ничем иным, как промежуточным представлением (intermediate representation, IR). Оно будет представлять наши IMP-программы в памяти. Так как IMP простой как 3 рубля, IR будет напрямую соответствовать синтаксису языка; мы создадим по классу для каждой единицы синтаксиса. Конечно, в более сложном языке вы хотели бы использовать еще и семантическую представление, которое намного легче для анализа или исполнения.

Всего три стадии интерпретации:
  • Разобрать символы исходного кода на токены.
  • Собрать все токены в абстрактное синтаксическое дерево (abstract syntax tree, AST). AST и есть наша IR.
  • Исполнить AST и вывести результат в конце.


Процессом разделения символов на токены называется лексинг (lexing), а занимается этим лексер (lexer). Токены являют собой короткие, удобоваримые строки, содержащие самые основные части программы, такие как числа, идентификаторы, ключевые слова и операторы. Лексер будет пропускать пробелы и комментарии, так как они игнорируются интерпретатором.

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


Эта статься будет сосредоточена исключительно на лексере. Сначала мы напишем общую лекс-библиотеку а затем уже лексер для IMP. Следующие части будут сфокусированы на парсере и исполнителе.

Лексер

По правде говоря, лексические операции очень просты и основываются на регулярных выражениях. Если вы с ними не знакомы, то можете прочитать официальную документацию.

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

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

Вот код из библиотеки лексера:

import sys
import re

def lex(characters, token_exprs):
	pos = 0
	tokens = []
	while pos < len(characters):
		match = None
		for token_expr in token_exprs:
			pattern, tag = token_expr
			regex = re.compile(pattern)
			match = regex.match(characters, pos)
			if match:
				text = match.group(0)
				if tag:
					token = (text, tag)
					tokens.append(token)
				break
		if not match:
			sys.stderr.write('Illegal character: %s\n' % characters[pos])
			sys.exit(1)
		else:
			pos = match.end(0)
	return tokens


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

Лексер IMP

С учетом кода выше, создание лексера для нашего языка становится очень простым. Для начала определим серию тегов для токенов. Для языка нужно всего лишь 3 тега. RESERVED для зарезервированных слов или операторов, INT для чисел, ID для идентификаторов.

import lexer

RESERVED = 'RESERVED'
INT      = 'INT'
ID       = 'ID'


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

token_exprs = [
    (r'[ \n\t]+',              None),
    (r'#[^\n]*',               None),


После этого следуют все наши операторы и зарезервированные слова.

    (r'\:=',                   RESERVED),
    (r'\(',                    RESERVED),
    (r'\)',                    RESERVED),
    (r';',                     RESERVED),
    (r'\+',                    RESERVED),
    (r'-',                     RESERVED),
    (r'\*',                    RESERVED),
    (r'/',                     RESERVED),
    (r'<=', RESERVED),
    (r'<', RESERVED),
    (r'>=', RESERVED),
    (r'>', RESERVED),
    (r'=',                     RESERVED),
    (r'!=',                    RESERVED),
    (r'and',                   RESERVED),
    (r'or',                    RESERVED),
    (r'not',                   RESERVED),
    (r'if',                    RESERVED),
    (r'then',                  RESERVED),
    (r'else',                  RESERVED),
    (r'while',                 RESERVED),
    (r'do',                    RESERVED),
    (r'end',                   RESERVED),


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

    (r'[0-9]+',                INT),
    (r'[A-Za-z][A-Za-z0-9_]*', ID),
]


Когда наши регэкспы определены, мы можем создать обертку над функцией lex:

def imp_lex(characters):
    return lexer.lex(characters, token_exprs)


Если вы дочитали до этих слов, то вам, скорее всего, будет интересно как работает наше чудо. Вот код для теста:

import sys
from imp_lexer import *

if __name__ == '__main__':
    filename = sys.argv[1]
    file = open(filename)
    characters = file.read()
    file.close()
    tokens = imp_lex(characters)
    for token in tokens:
        print token


$ python imp.py hello.imp


Скачать полный исходный код: imp-interpreter.tar.gz
Автор оригинальной статьи — Jay Conrod.

UPD: Спасибо пользователю zeLark за исправление бага, связанного с порядком определения шаблонов.
Матвей Правосудов @shoucken
карма
0,0
рейтинг 0,0
Дизайнер интерфейсов
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (14)

  • 0
    > Если вообще ничего не совпало, то мы рапортуем об ошибке и скрипт становится героем.

    У автора в оригинале нет идиоматики, почему она есть в переводе: о каком герое речь?
    • +3
      Become an hero, очевидно.
      • 0
        А это вы на какой вопрос ответили и почему такой ответ должен быть очевиден? %)
        В оригинале: «If there is no matching regular expression, we report an error and quit».
        • 0
          Возможно, перегнул со знанием интернет-мемов.
          • +3
            Мемы мемами, но раз уж это перевод, то неплохо бы, чтобы он им оставался: вот когда автор мем употребит, тогда и переводчику не зазорно.
  • +1
    Если не критично совсем уж с нуля, существует проект PLY (Python Lex-Yacc).
    На одном из курсов Udacity на его основе создают простейший браузер.
  • +2
    Надо написать на IMP какой-нибудь ещё интерпретатор, чтобы глубже было.
  • +3
    Если будет интересно, переведу еще 3 части из этой же серии.
    • 0
      Да, интересно!
  • +1
    Забавно. Совсем недавно написал почти такую же статью, только с более практичной целью.
  • 0
    По моему лучше не читать весь файл сразу, а анализировать его построчно. Для компилятор/парсера latex это помогало мне работать с большими файлами.
  • 0
    На самом деле, исправление по определению порядка следования шаблонов операторов сделал не я, а пользователь zeLark, он просто readonly еще
  • 0
    Больше спасибо за статью, обязательно прочитаю и все остальные части.
    Тема очень интересная и я в свободное время ей занимаюсь.
    Когда-то я писал движок вики-подобного языка разметки. Первая ошибка, которую я допустил было смешивание уровней токенизации и построения дерева из последовательности токенов (т.е. tokenizer / lexer). Полученная штука была жутковатой, в частности, её было сложно модифицировать, было множество специальных кейсов, введение новых синтаксисов вводило новые специальные кейсы и ломало работу уже существующих.
    Потом я писал шаблонизатор, в нём я осуществил разбивку этих двух этапов, в результате код стал очень простой и здоровый. Собственно, этот шаг мне видится разумным, но есть один связанный вопрос, который меня занимает.

    Предположим у нас есть некоторый ЯП. Что считать токеном? Пусть в ЯП есть литералы строк: набор символов заключённых в двойные кавычки. По сути, это может быть один токен, который достаточно легко описать одной регуляркой (если регулярки поддерживают ленивость). Но если пойти дальше, то оказывается, что внутри строки тоже не всё так просто, могут быть эскейп последовательности, существует интерполяция. НО при этом внутри строки не действуют обычные токены языка. То есть внутри строки нет for, if, нет чисел и нет других строк. И ещё там важны пробелы, т.е. это значащие символы. Это означает, что токен строки это отдельный подъязык со своей грамматикой.
    Получается, что на этапе токенизации мы должны заморачиваться с каким-то переключением контекста итп вещами, хотя этот этап должен быть очень простым. Налицо анализ последовательности токенов. То есть уровни всё таки как-то проникают друг в друга!? Мой вопрос в том, как разрешается это затруднение? Где кончается токенизация и начинается синтаксический анализ?

    Заранее спасибо.
    • 0
      upd: Использовал парсер-комбинаторы.

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