Лексирование Лиспа в Python
Меня заинтересовал язык Лисп, и я решил создать свой диалект. Это будет самый простой из когда-либо существовавших.
Как вы знаете, все в Лиспе представляет собой список (или, по крайней мере, этот диалект). Список состоит из команды, которая стоит в его начале, и, возможно, аргументов, которые сами являются списками. Используя эту информацию, я создал следующее.
class KList:
def __init__(self, command, args=None):
self.command = command
self.args = args
Таким образом, используя эту структуру, (+ 1 2) должен превратиться в KList('+', [KList('1'), KList('2')]) и преобразовать его. Мне нужен лексер, и моя проблема в том. Как я могу преобразовать его? Есть две вещи, которые важны для меня.
- Я просто ненавижу загружать квадриллион пакетов для простого проекта. Итак, решение без лексической библиотеки.
- Lisp — функциональный язык, и это может показаться странным, но я использую Python для функционального программирования, поэтому, пожалуйста, избегайте операторов и изменяющих переменных.
Ответы 1
Простой синтаксический анализатор на Лиспе может быть легко реализован, вы можете написать парсер с рекурсивным спуском сверху вниз. У вас есть отдельные считыватели, такие как считыватели целых чисел, строк, символов и т. д.:
class Reader:
def read_integer(self, stream):
pass
def read_string(self, stream):
pass
def read_symbol(self, stream):
pass
def read_whitespace(self, stream):
pass
В частности, считыватель составных форм:
def read_open_parenthesis(self, stream):
# read as many forms as possible until
# you reach ")"
pass
И вы добавляете основной ридер, который просматривает поток, проверяет, какие символы читаются, и вызывает любую необходимую ему функцию:
def read_form(self, in):
byte = stream.peek()
if byte.isdigit():
return self.read_integer(in)
if byte == '(':
_ = in.read_char() # read paren
return self.read_open_parenthesis(in)
# etc.
На самом деле читатель Common Lisp делает это, но программно. Существует таблица чтения, которая связывает символы с функциями чтения, и вы можете изменить эту таблицу чтения во время выполнения. Например, все цифры в этой таблице сопоставляются с некоторой функцией read-integer, но вы можете взломать ее, чтобы иметь другой считыватель.
Также обратите внимание, что вы должны интернировать символы в Лиспе, что означает, что вы создаете символ при первом его анализе, а затем используете тот же объект символа при следующем анализе того же символа, чтобы символы были идентичными.
(eq 'a 'a)
=> T
Что не обязательно относится к строкам:
(eq "a" "a")
=> NIL
(это может быть T для компилятора, который оптимизирует повторяющиеся строки)
С определенной точки зрения это очень простой подход, но, конечно, подход Common Lisp немного сложнее, есть много тонкостей, которые вы можете сначала игнорировать. Для более полного объяснения см. 2.2 Алгоритм чтения .
как вы включаете числа и строки в качестве команд?!
В случае, если команда начинается с " и заканчивается на ней. Это будет строка. Точно так же с цифрами. В случае, если она начинается с 0-9 или . и заканчивается ими.
Итак, вы делаете то, что я объясняю, вы анализируете различные типы на основе первого символа, который вы видите в исходном файле. В этом и заключается идея парсинга сверху вниз, позже я постараюсь объяснить подробнее.
это круто, но я на самом деле включаю числа и строки как команды. Я не знаю, ошибаюсь ли я здесь, но я хочу пройти фазу lex -> parse. Может быть, вы сами объясните алгоритм, так как я плохо читаю документы