Как создать лексер на python

Python Lex-Yacc

Чтобы установить PLY на вашем компьютере для python2 / 3, выполните действия, описанные ниже:

1. Скачать исходный код здесь .
2. Распакуйте загруженный zip-файл
3. Перейдите в распакованный ply-3.10 папку
4. Выполните следующую команду в терминале: python setup.py install

Если вы выполнили все вышеперечисленное, теперь вы сможете использовать модуль PLY. Вы можете проверить это, открыв интерпретатор питона и набрав import ply.lex .

Примечание: Не используйте pip установить PLY, он установит битый дистрибутив на вашей машине.

«Привет, мир!» PLY — простой калькулятор

Давайте продемонстрируем силу PLY на простом примере: эта программа примет арифметическое выражение в качестве строкового ввода и попытается его решить.

Откройте ваш любимый редактор и скопируйте следующий код:

from ply import lex import ply.yacc as yacc tokens = ( 'PLUS', 'MINUS', 'TIMES', 'DIV', 'LPAREN', 'RPAREN', 'NUMBER', ) t_ignore = '\t' t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIV = r'/' t_LPAREN = r'\(' t_RPAREN = r'\)' def t_NUMBER( t ) : r'[0-9]+' t.value = int( t.value ) return t def t_newline( t ): r'\n+' t.lexer.lineno += len( t.value ) def t_error( t ): print("Invalid Token:",t.value[0]) t.lexer.skip( 1 ) lexer = lex.lex() precedence = ( ( 'left', 'PLUS', 'MINUS' ), ( 'left', 'TIMES', 'DIV' ), ( 'nonassoc', 'UMINUS' ) ) def p_add( p ) : 'expr : expr PLUS expr' p[0] = p[1] + p[3] def p_sub( p ) : 'expr : expr MINUS expr' p[0] = p[1] - p[3] def p_expr2uminus( p ) : 'expr : MINUS expr %prec UMINUS' p[0] = - p[2] def p_mult_div( p ) : '''expr : expr TIMES expr | expr DIV expr''' if p[2] == '*' : p[0] = p[1] * p[3] else : if p[3] == 0 : print("Can't divide by 0") raise ZeroDivisionError('integer division by 0') p[0] = p[1] / p[3] def p_expr2NUM( p ) : 'expr : NUMBER' p[0] = p[1] def p_parens( p ) : 'expr : LPAREN expr RPAREN' p[0] = p[2] def p_error( p ): print("Syntax error in input!") parser = yacc.yacc() res = parser.parse("-4*-(3-5)") # the input print(res) 

Сохраните этот файл как calc.py и запустить его.

Какой правильный ответ на -4 * — (3 — 5) .

Часть 1: токенизация ввода с помощью Lex

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

В этом разделе приводится простой пример того , как разметить пользовательского ввода, а затем разбивает его построчно.

 import ply.lex as lex # List of token names. This is always required tokens = [ 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', ] # Regular expression rules for simple tokens t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIVIDE = r'/' t_LPAREN = r'\(' t_RPAREN = r'\)' # A regular expression rule with some action code def t_NUMBER(t): r'\d+' t.value = int(t.value) return t # Define a rule so we can track line numbers def t_newline(t): r'\n+' t.lexer.lineno += len(t.value) # A string containing ignored characters (spaces and tabs) t_ignore = '\t' # Error handling rule def t_error(t): print("Illegal character '%s'" % t.value[0]) t.lexer.skip(1) # Build the lexer lexer = lex.lex() # Give the lexer some input lexer.input(data) # Tokenize while True: tok = lexer.token() if not tok: break # No more input print(tok) 

Сохраните этот файл как calclex.py .Мы будем использовать это при создании нашего парсера Yacc.

Сломать

1. Импорт модуля с помощью import ply.lex

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

 tokens = [ 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', ] 

tokens также могут быть кортеж строк (а не строка), где каждая строка обозначает маркер , как и раньше.

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

• Для простых лексем, регулярное выражение может быть задано в виде строки: t_PLUS = r’\+’

Построить лексер используя lexer = lex.lex() .

## Вы также можете поместить все в класс и вызвать экземпляр класса, чтобы определить лексер. Например:

 import ply.lex as lex class MyLexer(object): . # everything relating to token rules and error handling comes here as usual # Build the lexer def build(self, **kwargs): self.lexer = lex.lex(module=self, **kwargs) def test(self, data): self.lexer.input(data) for token in self.lexer.token(): print(token) # Build the lexer and try it out m = MyLexer() m.build() # Build the lexer m.test("3 + 4") # 

Обеспечить ввод с помощью lexer.input(data) , где данные является строкой

Для того, чтобы получить маркеры, используйте lexer.token() , который возвращает лексемы совпавшие. Вы можете перебрать лексер в цикле, как в:

ибо я в лексере:

 print(i) 

Часть 2: парсинг токенизированного ввода с помощью Yacc

В этом разделе объясняется, как обрабатывается входной токен из части 1 — это делается с помощью контекстно-свободных грамматик (CFG). Грамматика должна быть указана, а токены обрабатываются в соответствии с грамматикой. Под капотом парсер использует LALR-парсер.

# Yacc example import ply.yacc as yacc # Get the token map from the lexer. This is required. from calclex import tokens def p_expression_plus(p): 'expression : expression PLUS term' p[0] = p[1] + p[3] def p_expression_minus(p): 'expression : expression MINUS term' p[0] = p[1] - p[3] def p_expression_term(p): 'expression : term' p[0] = p[1] def p_term_times(p): 'term : term TIMES factor' p[0] = p[1] * p[3] def p_term_div(p): 'term : term DIVIDE factor' p[0] = p[1] / p[3] def p_term_factor(p): 'term : factor' p[0] = p[1] def p_factor_num(p): 'factor : NUMBER' p[0] = p[1] def p_factor_expr(p): 'factor : LPAREN expression RPAREN' p[0] = p[2] # Error rule for syntax errors def p_error(p): print("Syntax error in input!") # Build the parser parser = yacc.yacc() while True: try: s = raw_input('calc >') except EOFError: break if not s: continue result = parser.parse(s) print(result) 

Сломать

Каждое правило грамматики определяется функцией, в которой строка документации для этой функции содержит соответствующую контекстно-независимую грамматическую спецификацию. Операторы, составляющие тело функции, реализуют семантические действия правила. Каждая функция принимает один аргумент p, который представляет собой последовательность, содержащую значения каждого грамматического символа в соответствующем правиле. Значения p[i] сопоставляются грамматические символы , как показано здесь:

 def p_expression_plus(p): 'expression : expression PLUS term' # ^ ^ ^ ^ # p[0] p[1] p[2] p[3] p[0] = p[1] + p[3] 

• Для лексем, «ценность» соответствующий p[i] является таким же , как p.value атрибута , назначенным в модуле лексического анализатора. Таким образом, PLUS будет иметь значение + .

Обратите внимание , что функция может иметь любое имя, до тех пор , как оно предваряется p_ .

• p_error(p) правило, определяется , чтобы поймать синтаксические ошибки ( такие же , как yyerror в YACC / зубров).

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

 def p_binary_operators(p): '''expression : expression PLUS term | expression MINUS term term : term TIMES factor | term DIVIDE factor''' if p[2] == '+': p[0] = p[1] + p[3] elif p[2] == '-': p[0] = p[1] - p[3] elif p[2] == '*': p[0] = p[1] * p[3] elif p[2] == '/': p[0] = p[1] / p[3] 

Символьные литералы могут использоваться вместо токенов.

 def p_binary_operators(p): '''expression : expression '+' term | expression '-' term term : term '*' factor | term '/' factor''' if p[2] == '+': p[0] = p[1] + p[3] elif p[2] == '-': p[0] = p[1] - p[3] elif p[2] == '*': p[0] = p[1] * p[3] elif p[2] == '/': p[0] = p[1] / p[3] 

Конечно, литералы должны быть указаны в модуле lexer.

• Чтобы явно задать начальный символ, используйте start = ‘foo’ , где foo некоторая нетерминал.

Установка приоритета и ассоциативности может быть выполнена с помощью переменной приоритета.

 precedence = ( ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), # Unary minus operator ) 

Жетоны упорядочены по возрастанию. nonassoc означает , что эти маркеры не ассоциируют. Это значит , что — то вроде a < b < c незаконна тогда a < b по - прежнему законно.

Простой интерпретатор с нуля на Python (перевод) #1

2013-12-17 в 7:37, admin , рубрики: python, интерпретатор, Питон, с нуля, метки: python, интерпретатор, Питон, с нуля

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

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

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

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

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

x := 1

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

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: %sn' % 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'[ nt]+', 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'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.

Напишите lexer

Операция вложения для Lexer'a
Здравствуйте. Пишу программу (Lexer) для чтения кода. Хочу понять, как встроенный языки.

AST, Lexer и PABC.NET
Решил задать маленький вопрос (вернее, большой): недавно поставил себе цель - написать.

ANTLR. Как создать Lexer/Parser?
Используется: Visual Studio - 2019 Для установки `ANTLR` я использую.

напишите программу на паскале. если можно напишите в комментах что где делаете.
1)Найти наибольший элемент матрицы X(4,5). Записать единицы в те строку и столбец, где он.

1287 / 672 / 365
Регистрация: 07.01.2019
Сообщений: 2,237

Начинайте с самого простого

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

KEYWORDS = { 'var':'RESERVED', '=':'RESERVED' } LINE = 'var x = "hello"' def lex(LINE,KEYWORDS): ret = [] lines = LINE.split() for line in lines: if line in KEYWORDS: ret.append((line, KEYWORDS[line])) else: ret.append((line, 'NORMAL')) return ret # Мне надо получить tokens = lex(LINE,KEYWORDS) print(tokens)

170 / 122 / 61
Регистрация: 06.02.2015
Сообщений: 300
Для конкретного примера неоптимальное решение
Кликните здесь для просмотра всего текста

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

KEYWORDS = { 'var':'RESERVED', '=':'RESERVED', ';':'END', } LINE = 'var x = "hello world!";' def lex(LINE,KEYWORDS): k=0 tmp=[] res=[] for i in range(len(LINE)): if LINE[i]==" ": tmp=LINE.split(LINE[i],k) k=k+1 for i in range(len(tmp)): if ";" in tmp[i]: tmp.append(";") tmp[i]=tmp[i].replace(";","") for i in range(len(tmp)): if tmp[i] in KEYWORDS: res.append([tmp[i],KEYWORDS[tmp[i]]]) else: if all(x.isalpha() or x.isspace() or '' in x or "" in x for x in tmp[i]): res.append([tmp[i],'NORMAL']) return res tokens = lex(LINE,KEYWORDS) # [('var','RESERVED'),('x','NORMAL'),('=','RESERVED'),('"hello world!"','NORMAL'),(';','END')] print(tokens)

Автоматизируй это!

7102 / 4606 / 1214
Регистрация: 30.03.2015
Сообщений: 13,218
Записей в блоге: 29

Сообщение было отмечено Hyppoprogramm как решение

Решение

Hyppoprogramm, ты пойми -это не простая задача, нельзя разбивать по пробелу как помогли тебе выше, так как знак типа точки с запятой могут быть вплотную к выражению и вообще юзер может без пробелов все ввести и тогда по какому признаку разбивать?
вот пример, но только для твоей конкретной задачи (обрати внимание и на ключевые слова), дальше давай сам, жажду увидеть твой код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

import re KEYWORDS = {'RESERVED': ['var', '='], 'END': [';']} def lexer(line: str, keywords: dict) -> list: result = [] quoted_text = re.findall('"(.*?)"', line) if quoted_text: line = line.replace('"' + quoted_text[0] + '"', '$REPLACED ') for word in line.split(): for k, v in keywords.items(): if word in v: result.append((word, k)) break else: word = word if word != '$REPLACED' else '"' + quoted_text[0] + '"' result.append((word, 'NORMAL')) return result LINE = 'var x = "hello world!";' tokens = lexer(LINE, KEYWORDS) print(lexer(LINE, KEYWORDS))

131 / 117 / 29
Регистрация: 09.07.2019
Сообщений: 1,068
Записей в блоге: 4

Welemir1, большое спасибо! Получилось!
P.S. Немного исправил код:
Исправил словарь ключевых слов и заменил in на ==

Автоматизируй это!

7102 / 4606 / 1214
Регистрация: 30.03.2015
Сообщений: 13,218
Записей в блоге: 29

Сообщение от Hyppoprogramm

Получилось!

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

131 / 117 / 29
Регистрация: 09.07.2019
Сообщений: 1,068
Записей в блоге: 4
И кстате, подумал немного и получил ответ на предыдущий вопрос.
Кому интересно, вот полный код:
Кликните здесь для просмотра всего текста

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

KEYWORDS = { 'var':'RESERVED', '=':'RESERVED', '+':'RESERVED' } LINE = 'var abc = "some" + "text";' import re def lex(line: str, keywords: dict) -> list: result = [] quoted_text = re.findall('"(.*?)"', line) quoted_text += re.findall("'(.*?)'",line) if quoted_text: line = line.replace('"' + quoted_text[0] + '"', '$REPLACED ') for word in line.split()[:-1]: for v, k in keywords.items(): if word in v: result.append((word, k)) break else: word = word if word != '$REPLACED' else '"' + quoted_text[0] + '"' result.append((word, 'NORMAL')) word = line.split()[-1] END = word[-1] word = word[:-1] for v, k in keywords.items(): if word in v: result.append((word, k)) break else: word = word if word != '$REPLACED' else '"' + quoted_text[0] + '"' result.append((word, 'NORMAL')) result.append((END,'END')) return result tokens = lex(LINE, KEYWORDS) print(lex(LINE, KEYWORDS)) # [('var','RESERVED'),('abc','NORMAL'),('=','RESERVED'),('"some"','NORMAL'),('+','RESERVED'),('"text"','NORMAL'),(';','END')]

Как создать свой язык программирования: теория, инструменты и советы от практика

На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием Pinecone. Я не рискну назвать его законченным, но использовать его уже можно — он содержит для этого достаточно элементов, таких как переменные, функции и пользовательские структуры данных. Если хотите ознакомиться с ним перед прочтением, предлагаю посетить официальную страницу и репозиторий на GitHub.

Введение

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

Тем не менее, я написал абсолютно новый язык. И он работает. Наверное, я что-то делаю правильно.

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

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

Первые шаги

«А с чего вообще начинать?» — вопрос, который другие разработчики часто задают, узнав, что я пишу свой язык. В этой части постараюсь подробно на него ответить.

Компилируемый или интерпретируемый?

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

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

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

Выбор языка

Своеобразный мета-шаг: язык программирования сам является программой, которую надо написать на каком-то языке. Я выбрал C++ из-за производительности, большого набора функциональных возможностей, и просто потому что он мне нравится.

Но в целом совет можно дать такой:

• интерпретируемый ЯП крайне рекомендуется писать на компилируемом ЯП (C, C++, Swift). Иначе потери производительности будут расти как снежный ком, пока мета-интерпретатор интерпретирует ваш интерпретатор;
• компилируемый ЯП можно писать на интерпретируемом ЯП (Python, JS). Возрастёт время компиляции, но не время выполнения программы.

Проектирование архитектуры

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

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

Первый шаг в большинстве ЯП — это лексический анализ. Говоря по-простому, он представляет собой разбиение текста на токены, то есть единицы языка: переменные, названия функций (идентификаторы), операторы, числа. Таким образом, подав лексеру на вход строку с исходным кодом, мы получим на выходе список всех токенов, которые в ней содержатся.

Обращения к исходному коду уже не будет происходить на следующих этапах, поэтому лексер должен выдать всю необходимую для них информацию.

Flex

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

Одним из основных таких инструментов является Flex — генератор лексических анализаторов. Он принимает на вход файл с описанием грамматики языка, а потом создаёт программу на C, которая в свою очередь анализирует строку и выдаёт нужный результат.

Моё решение

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

Синтаксический анализатор / парсер

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

Bison

На этом шаге я также думал использовать стороннюю библиотеку, рассматривая Bison для генерации синтаксического анализатора. Он во многом похож на Flex — пользовательский файл с синтаксическими правилами структурируется с помощью программы на языке C. Но я снова отказался от средств автоматизации.

Преимущества кастомных программ

С лексером моё решение писать и использовать свой код (длиной около 200 строк) было довольно очевидным: я люблю задачки, а эта к тому же относительно тривиальная. С парсером другая история: сейчас длина кода для него — 750 строк, и это уже третья попытка (первые две были просто ужасны).

Тем не менее, я решил делать парсер сам. Вот основные причины:

• минимизация переключения контекста;
• упрощение сборки;
• желание справиться с задачей самостоятельно.

В целесообразности решения меня убедило высказывание Уолтера Брайта (создателя языка D) в одной из его статей:

Абстрактный семантический граф

В этой части я реализовал структуру, по своей сути наиболее близкую к «промежуточному представлению» (intermediate representation) в LLVM. Существует небольшая, но важная разница между абстрактным синтаксическим деревом (АСД) и абстрактным семантическим графом (АСГ).

АСГ vs АСД

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

Запуск

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

Варианты компиляции

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

Написать свой компилятор

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

LLVM

LLVM — это коллекция инструментов для компиляции, которой пользуются, например, разработчики Swift, Rust и Clang. Я решил остановиться на этом варианте, но опять не рассчитал сложности задачи, которую перед собой поставил. Для меня проблемой оказалось не освоение ассемблера, а работа с огромной многосоставной библиотекой.

Транспайлинг

Мне всё же нужно было какое-то решение, поэтому я написал то, что точно будет работать: транспайлер (transpiler) из Pinecone в C++ — он производит компиляцию по типу «исходный код в исходный код», а также добавил возможность автоматической компиляции вывода с GCC. Такой способ не является ни масштабируемым, ни кроссплатформенным, но на данный момент хотя бы работает почти для всех программ на Pinecone, это уже хорошо.

Дальнейшие планы

Сейчас мне не достаёт необходимой практики, но в будущем я собираюсь от начала и до конца реализовать компилятор Pinecone с помощью LLVM — инструмент мне нравится и руководства к нему хорошие. Пока что интерпретатора хватает для примитивных программ, а транспайлер справляется с более сложными.

Заключение

Надеюсь, эта статья окажется кому-нибудь полезной. Я крайне рекомендую хотя бы попробовать написать свой язык, несмотря на то, что придётся разбираться во множестве деталей реализации — это обучающий, развивающий и просто интересный эксперимент.

Вот общие советы от меня (разумеется, довольно субъективные):

• если у вас нет предпочтений и вы сомневаетесь, компилируемый или интерпретируемый писать язык, выбирайте второе. Интерпретируемые языки обычно проще проектировать, собирать и учить;
• с лексерами и парсерами делайте, что хотите. Использование средств автоматизации зависит от вашего желания, опыта и конкретной ситуации;
• если вы не готовы / не хотите тратить время и силы (много времени и сил) на придумывание собственной стратегии разработки ЯП, следуйте цепочке действий, описанной в этой статье. Я вложил в неё много усилий и она работает;
• опять же, если не хватает времени / мотивации / опыта / желания или ещё чего-нибудь для написания классического ЯП, попробуйте написать эзотерический, типа Brainfuck. (Советуем помнить, что если язык написан развлечения ради, это не значит, что писать его — тоже сплошное развлечение. — прим. перев.)

Я делал довольно много ошибок по ходу разработки, но большую часть кода, на которую они могли повлиять, я уже переписал. Язык сейчас неплохо функционирует и будет развиваться (на момент написания статьи его можно было собрать на Linux и с переменным успехом на macOS, но не на Windows).

О том, что ввязался в историю с созданием Pinecone, ни в коем случае не жалею — это отличный эксперимент, и он только начался.