Продолжаем наш вечерний концерт по заявкам радиослушателей. Тема сегодняшнего разговора - таблицы символов. Напоминаю, что в прошлые разы мы поговорили о синтаксических деревьях и способе их построения из исходника мной придуманного языка wend (сокращение от week-end). Вот краткое оглавление серии статей:
Таблицы символов: области видимости переменных и проверка типов (эта статья)
Стек и транслятор в питон без использования питоновских переменных
Транслятор в ассемблер
Рейтрейсинг :)
Вообще целевым языком является ассемблер, но пока что в качестве промежуточного результата я генерирую код на питоне. На данный момент вся генерация кода - это просто pretty print надстройка над синтаксическим деревом. Напоминаю, что на данный момент процесс "компиляции" выглядит следующим образом:
Лексер превращает поток символов исходного кода в поток лексем, парсер их разбирает, строя синтаксическое дерево. Ну а затем простым обходом дерева в глубину я выдаю код на целевом языке. В простых случаях это неплохо работает, но в конце прошлой статьи я специально оставил пару случаев, в которых компилятор ломается. Давайте вспомним один из них, слева исходник на wend, справа неверная трансляция в питон:
Я ожидаю, что код выведет на экран 3, в то время как питон мне показывает 0. Почему? Давайте разбираться. Для начала отложим wend в сторону и просто поговорим о питоне.
Области видимости переменных в питоне
Никакой Америки я не открою, но я с удивлением для себя обнаружил, что изрядное количество людей не знает, как работает связывание переменных в этом языке. Давайте рассмотрим простейший пример: у меня есть функция foo()
, которая выводит на экран значение переменной bar
, которая определена вне функции:
ssloy@home:~$ python3 <<<'
def foo():
print(bar)
bar = 0
foo()
print(bar)
'
0
0
Как и раньше, я разом привожу и код, и результат его выполнения. Вполне ожидаемо, что язык с неявным заданием переменных найдёт глобальную переменную bar
и выведет на экран два нуля. А что будет, если я попытаюсь не только вывести значение bar
, но ещё и записать в неё единицу?
ssloy@home:~$ python3 <<<'
def foo():
print(bar)
bar = 1
bar = 0
foo()
print(bar)
'
Traceback (most recent call last):
File "<stdin>", line 7, in <module>
File "<stdin>", line 3, in foo
UnboundLocalError: cannot access local variable 'bar' where it is not associated with a value
А случилась у нас ошибка компиляции, причём именно компиляции, а не вывалилось во время исполнения. Если же внутри функции переставить операции присваивания и вывода на экран, то всё прекрасно запускается, причём явно значение глобальной переменной bar
не меняется:
ssloy@home:~$ python3 <<<'
def foo():
bar = 1
print(bar)
bar = 0
foo()
print(bar)
'
1
0
Это совершенно не магия, это абсолютно нормально, и одновременно крайне контринтуитивно для новичков, пришедших в питон из языков с более строгим объявлением переменных. Питон, как и большинство других языков, разделяет переменные на локальные и на глобальные, причём на чтение контекст глобальный, а на запись локальный. Вот и получается, что если мы сначала попытаемся сделать print(bar)
, а потом присвоить bar = 1
, то питон знает, что bar
- локальная переменная, но ещё не была инициализирована, и ломается. Можно использовать слово global
, чтобы явно указать, что bar
должна быть глобальной переменной несмотря на то, что в неё идёт запись:
ssloy@home:~$ python3 <<<'
def foo():
global bar
bar = 1
print(bar)
bar = 0
foo()
print(bar)
'
1
1
Моя практика показывает, что обычно люди и ограничиваются двумя ключевыми словами global
/local
, забывая ещё про одно крайне любопытное: nonlocal
. Давайте рассмотрим следующий пример кода:
ssloy@home:~$ python3 <<<'
def counter():
count = -1
def increment():
nonlocal count
count += 1
return count
return increment
counter1 = counter()
counter2 = counter()
for _ in range(3):
print("outer counter:", counter1())
for _ in range(2):
print(" inner counter:", counter2())
'
outer counter: 0
inner counter: 0
inner counter: 1
outer counter: 1
inner counter: 2
inner counter: 3
outer counter: 2
inner counter: 4
inner counter: 5
Здесь есть функция counter()
со вложенной функцией increment()
, при этом increment()
ссылается на переменную count
, которая не является ни локальной для increment()
, ни глобальной. Переменная count
является локальной для функции counter()
, и increment()
ссылается на локальную переменную окружающего контекста.
Я создал два счётчика counter1
и counter2
, они могут считать независимо друг от друга, поскольку ссылаются на два разных экземпляра переменной count
. Эта магия называется замыканием, и это исключительно мощный инструмент, который использовать нужно, но осторожно, чтобы не ломать мозг тем, кто будет поддерживать ваш код :)
Возвращаясь к нашим баранам, вот так должен выглядеть корректный перевод с wend на питон, обратите внимание на появление двух строк с ключевым словом nonlocal
:
Ёлочные игрушки
Теперь давайте разбираться, как научить компилятор добавлять подобную информацию. Нам нужно изменить процесс компиляции, добавив один этап семантического анализа, который будет вызван непосредственно после построения синтаксического дерева:
Парсер нам выращивает новогоднюю ёлку, а семантический анализатор развешивает на ней ёлочные игрушки (кстати, это не шутка, компиляторщики реально пользуются таким жаргоном). Ну а дальше генерация кода на целевом языке идёт из украшенной ёлки. Вот так выглядит синтаксическое дерево для нашего примера после прохода семантического анализатора:
Обратите внимание на информацию, помеченную красным, она и была добавлена анализатором. Самое удобное место для её хранения - это словарь deco
, который я предусмотрел для каждого узла дерева. Пока что я там хранил всякое типа номера строки в исходном файле для сигнализирования об ошибках, а теперь оно пригодится для семантического анализа.
Надеюсь, что в целом понятно, какую информацию нам нужно добавить дереву. Но как именно это сделать? И тут приходят на помощь таблицы символов.
Таблицы символов
Давайте я отрисую анимацию работы примитивного семантического анализатора:
Мне нужна структура данных, в которую я буду постепенно добавлять (и удалять!) информацию об областях видимости переменных. Делать я это буду, обходя синтаксическое дерево в глубину. Для компактности отображения в моей анимации нарисовано не само синтаксическое дерево, а исходный код, но надо понимать, что он к этому моменту давно выкинут, и работаю я с деревом. Просто проход по строчкам исходного кода сильно легче нарисовать, а он в точности соответствует обходу синтаксического дерева в глубину.
В моём языке области видимости в точности соответствуют функциям, так что, начав с корня дерева, я открываю новую область видимости переменных: push_scope(main)
. Затем я добавляю в мою таблицу все локальные переменные: add_var(x)
. На моей анимации я отрисовал тип переменной, поскольку он всё равно маячит в коде, но на данный момент он мне не нужен, я на него буду смотреть когда-нибудь потом, когда займусь проверкой типов.
Следующий узел в моём синтаксическом дереве - вложенная функция f
. Открываем новую область видимости, создавая вложенную таблицу: push_scope(f)
, и добавляем в неё все локальные переменные, тут только один аргумент add_var(y)
. Аналогично происходит и с функцией g
: push_scope(g)
, add_var(y)
.
И вот тут самое интересное: мы встречаемся с узлом Assign
, который соответствует строчке x = y + 1
. В нашем синтаксическом дереве о переменной x
мы знаем только её идентификатор, просто строку, ничего больше. Давайте узнаем о ней побольше: find_var(x)
. Мы знаем, что находимся на третьем уровне вложенности, поэтому давайте посмотрим, есть ли в текущей области видимости запись о x
.? Нет, нету. На втором уровне? Тоже нет. На третьем? Есть, нашлась! Таким образом, мы можем сказать второму и третьему блоку видимости, что в них используется нелокальная переменная x
.
А заодно (задел на будущее) мы нашли тип переменной, и сейчас можно проверить, совпадает ли тип переменной в инструкции присваивания: мы знаем, что справа стоит ArithOp
, он обязан быть целочисленным. Если x
имеет другой тип, самое время свалиться с ошибкой.
Мы разобрались с функциональностью таблицы символов, давайте перейдём к имплементации. Я сделал крайне примитивно:
class SymbolTable():
def __init__(self):
self.variables = [{}] # stack of variable symbol tables
self.ret_stack = [ None ] # stack of enclosing function symbols, useful for return statements
def add_var(self, name, deco):
if name in self.variables[-1]:
raise Exception('Double declaration of the variable %s' % name)
self.variables[-1][name] = deco
def push_scope(self, deco):
self.variables.append({})
self.ret_stack.append(deco)
def pop_scope(self):
self.variables.pop()
self.ret_stack.pop()
def find_var(self, name):
for i in reversed(range(len(self.variables))):
if name in self.variables[i]:
return self.variables[i][name]
raise Exception('No declaration for the variable %s' % name)
Я храню вложенные области видимости как список словарей, ключами которых являются идентификаторы, а значениями - украшение deco
соответствующего узла синтаксического дерева (в deco
хранится тип переменной). При входе в область видимости я добавляю словарь (push_scope
), при выходе удаляю (pop_scope
). Ну и параллельно я храню такой же список украшений из узлов-функций, что позволит синтаксическому анализатору добавить в дерево информацию о нелокальных переменных.
Вот так выглядит код семантического анализатора, это просто примитивный обход дерева в глубину, который делает запросы к таблице символов каждый раз, как встречает какую-нибудь переменную:
Hidden text
from syntree import *
from symtable import *
def build_symtable(ast):
if not isinstance(ast, Function) or ast.name != 'main' or ast.deco['type'] != Type.VOID or len(ast.args)>0:
raise Exception('Cannot find a valid entry point')
symtable = SymbolTable()
process_scope(ast, symtable)
def process_scope(fun, symtable):
fun.deco['nonlocal'] = set() # set of nonlocal variable names in the function body, used in "readable" python transpilation only
symtable.push_scope(fun.deco)
for v in fun.args: # process function arguments
symtable.add_var(*v)
for v in fun.var: # process local variables
symtable.add_var(*v)
for f in fun.fun: # then process nested function bodies
process_scope(f, symtable)
for s in fun.body: # process the list of statements
process_stat(s, symtable)
symtable.pop_scope()
def process_stat(n, symtable): # process "statement" syntax tree nodes
if isinstance(n, Print):
process_expr(n.expr, symtable)
elif isinstance(n, Return):
if n.expr is None: return
process_expr(n.expr, symtable)
elif isinstance(n, Assign):
process_expr(n.expr, symtable)
deco = symtable.find_var(n.name)
update_nonlocals(n.name, symtable) # used in "readable" python transpilation only
elif isinstance(n, FunCall): # no type checking is necessary
process_expr(n, symtable)
elif isinstance(n, While):
process_expr(n.expr, symtable)
for s in n.body:
process_stat(s, symtable)
elif isinstance(n, IfThenElse):
process_expr(n.expr, symtable)
for s in n.ibody + n.ebody:
process_stat(s, symtable)
else:
raise Exception('Unknown statement type')
def process_expr(n, symtable): # process "expression" syntax tree nodes
if isinstance(n, ArithOp):
process_expr(n.left, symtable)
process_expr(n.right, symtable)
elif isinstance(n, LogicOp):
process_expr(n.left, symtable)
process_expr(n.right, symtable)
elif isinstance(n, Integer):
pass
elif isinstance(n, Boolean):
pass
elif isinstance(n, Var):
deco = symtable.find_var(n.name)
update_nonlocals(n.name, symtable) # used in "readable" python transpilation only
elif isinstance(n, FunCall):
for s in n.args:
process_expr(s, symtable)
elif isinstance(n, String):
pass
else:
raise Exception('Unknown expression type', n)
def update_nonlocals(var, symtable): # add the variable name to the set of nonlocals
for i in reversed(range(len(symtable.variables))): # for all the enclosing scopes until we find the instance
if var in symtable.variables[i]: break # used in "readable" python transpilation only
symtable.ret_stack[i]['nonlocal'].add(var)
Рабочий коммит доступен здесь, теперь scope.wend компилируется корректно!
Проверка типов и перегрузка функций
Мы уже встретились с рудиментарной проверкой типов переменных, но для полной картины мира нам нужно ещё добавить в таблицу символов функции, ведь когда мы встречаемся с вызовом f(x+1)
, то мы не знаем ничего про тип, возвращаемый f
, потому что узел дереваFunCall
хранит только идентификатор f
, ничего больше. Всё крайне тривиально: параллельно списку словарей символов переменных давайте заведём список словарей символов функций, и будем их добавлять перед открытием соответствующей области видимости.
В словаре переменных ключом являлся идентификатор переменной, с функциями самую малость сложнее: я хочу уметь перегружать функции, поэтому идентификатор не является уникальным ключом. Не страшно, я в качестве ключа буду хранить сигнатуру функции, которая является простым кортежем (идентификатор, список типов аргументов).
Я добавил десяток строчек в модуль symtable.py и накидал исключений при несоотвествии типов в семантический анализатор analyzer.py, смотрите на изменения в коде.
Последним штрихом я добавил перегрузку функций: для этого мне достаточно к имени функции приклеить уникальный суффикс, и вуаля, у нас есть полностью корректно работающий компилятор из wend в python!
Текущий код брать по тегу v0.0.3.
В следующем выпуске
В этот раз мы починили компилятор, использовав ключевое слово nonlocal
. Но давайте не будем терять из виду то, что вообще-то целевым языком является не питон, а ассемблер, а он про замыкания не знает уж точно ничего! Поэтому в следующий раз мы поговорим про генерацию кода по-прежнему на питоне, но в принципе без использования переменных внутри функций. У меня будут только четыре глобальных переменных, и помимо них никакой другой использовать нельзя: я буду эмулировать регистры и стек. И вот тут выдаваемый код по-настоящему потеряет читаемость, так что, снявши голову, по волосам не плачут, можно уже и ассемблер генерировать :)
Слева направо: исходник на wend, трансляция в питон с использованием ключевого слова nonlocal
, трансляция в питон с использованием стека, структурно очень близкий к ассемблерному коду.
Развлекуха
Ну и в качестве финальной развлекухи я позволил себе запрограммировать фантазию на тему игры arcanoid:
Если кому интересно, то вот соответствующий код на C, всего 65 строчек. Любые мысли по улучшению приветствуются, а также кидайте идеи интересного короткого кода!