Пишем свой язык программирования на Python. Часть 1. Лексер

Всем привет! Сегодня мы начнём писать язык программирования на Python!

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

Все мы знаем что наш язык программирования как то работает. Но как? Вот структура:

• Лексер делает токены

• Парсер строит AST

• Интерпретатор интерпретирует AST

Лексер возвращает токены. Вот пример:

# Строка: a = 5; b = 5;
# Вывод: 
[('a', 'ID'), ('=', 'RESERVED'), ('5', 'INT'), ...]

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

Кортеж где первая часть это какое то слово (число или ключевое слово) а вторая часть - его тег.

Да. Так и есть. Возвращается список таких кортежей (токенов).

Парсер строит AST. Давайте представим, что AST - это дерево. В нём много веток. Ветка 1 это будет присваивание. 1-ая ветка первой ветки в AST, это имя переменной. А 2-ая ветка первой ветки это значение.

Так работает парсер.

Интерпретатор наше дерево выполняет. Больше нечего интересного.

Правила.

Каждый язык программирования имеет свои правила.

Вот правила которые я придумал:

• Цикл while и do-while.

• Условие if-else.

• Лишь один типа данных (int).

• И присваивание (имя = значение;).

Вот пример кода (он си-подобный):

f = 1;
n = 5;
while (n > 1) {
  f = f * n;
  n = n - 1;
}

Ещё один (с условием if-else):

f = 120;
if (f == 120) {
  f = 5;
}
else {
  f = 120;
}

И последний (с do-while):

a = 5;
do {
  a = a - 1;
} while (a > 10);

У "a" будет значение 4. Но у данного цикла будут баги.

И наш язык программирования называется AlmostC (Почти C).

Библиотека lexer.py.

В данной библиотеке хранится лексер.

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

def lex(characters, tokens_regex):
    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:
            raise SyntaxError('Illegal character: %s' % characters[pos])
        else:
            pos = match.end(0)
    return tokens

Мы проходимся по регуляркам из списка token_exprs и находим нужное совпадение. Иначе ошибка.

В конце возвращаем токены.

Достаточно легко.

Файл almostc_lexer.py

В данном файле очень мало строчек кода.

Только список регулярок и функция для функции lex из файла lexer.py.

Вот код файла:

from lexer import *
import re

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

token_exprs = [
    (r'[ \n\t]+', None),
    (r'\(', RESERVED),
    (r'=', RESERVED),
    (r'while', RESERVED),
    (r'if', RESERVED),
    (r'do', RESERVED),
    (r'else', 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'==', RESERVED),
    (r'[0-9]+', INT),
    (r'[a-zA-Z][a-zA-Z0-9_]*', ID)
]

def almostc_lexer(chars):
  return lex(chars, token_exprs)

Всего три тега. RESERVED - ключевые слова (к примеру while), ID - идентификатор (имя переменной, к примеру: x) и INT - числа (0, 5, 93).

Дальше token_exprs - кортежи регулярок, схема такого кортежа: регулярка, тег.

1 - true.

0 - false.

Функция almostc_lexer(программа) - вернуть токены функции lex.

Итог.

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