Давайте построим простой интерпретатор. Часть 13

Материалы ОП

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

Итак, давайте начнем!

Введение в семантический анализ

Хотя наша программа на Pascal может быть грамматически правильной, и парсер может успешно построить абстрактное синтаксическое дерево, программа все еще может содержать некоторые довольно серьезные ошибки. Чтобы отловить эти ошибки, нам нужно использовать абстрактное синтаксическое дерево и информацию из таблицы символов.

Почему мы не можем проверить наличие этих ошибок во время парсинга, то есть во время синтаксического анализа? Почему мы должны строить AST и что-то под названием таблица символов, чтобы сделать это?

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

Когда парсер закончил построение AST, мы знаем, что программа грамматически правильна; то есть ее синтаксис правилен в соответствии с нашими грамматическими правилами, и теперь мы можем отдельно сосредоточиться на проверке ошибок, которые требуют дополнительного контекста и информации, которой у парсера не было во время построения AST. Чтобы сделать это более конкретным, давайте взглянем на следующее выражение присваивания на Pascal:

x := x + y;

Парсер обработает его правильно, потому что грамматически выражение корректно (в соответствии с нашими ранее определенными грамматическими правилами для выражений присваивания и выражений). Но это еще не конец истории, потому что в Pascal есть требование, чтобы переменные были объявлены с соответствующими типами до их использования. Откуда парсер знает, были ли x и y уже объявлены?

Что ж, он этого не знает, и поэтому нам нужна отдельная фаза семантического анализа, чтобы ответить на вопрос (среди многих других) о том, были ли переменные объявлены до их использования.

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

Что вообще означает, что программа имеет смысл? Это во многом зависит от определения языка и требований языка.

Язык Pascal и, в частности, компилятор Free Pascal, предъявляют определенные требования, которые, если они не соблюдаются в программе, приведут к ошибке от компилятора fpc, указывающей на то, что программа не “имеет смысла”, что она некорректна, даже если синтаксис может выглядеть нормально. Вот некоторые из этих требований:

• Переменные должны быть объявлены до их использования
• Переменные должны иметь совпадающие типы при использовании в арифметических выражениях (это большая часть семантического анализа, называемая проверкой типов, которую мы рассмотрим отдельно)
• Не должно быть дублирующихся объявлений (Pascal запрещает, например, наличие локальной переменной в процедуре с тем же именем, что и один из формальных параметров процедуры)
• Ссылка на имя в вызове процедуры должна ссылаться на фактическую объявленную процедуру (в Pascal не имеет смысла, если в вызове процедуры foo() имя foo относится к переменной foo примитивного типа INTEGER)
• Вызов процедуры должен иметь правильное количество аргументов, и типы аргументов должны соответствовать типам формальных параметров в объявлении процедуры

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

После того, как мы реализуем фазу семантического анализа, структура нашего интерпретатора Pascal будет выглядеть примерно так:

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

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

Символы и таблицы символов

В следующем разделе мы обсудим, как реализовать некоторые семантические проверки и как построить таблицу символов: другими словами, мы обсудим, как выполнить семантический анализ наших программ на Pascal. Имейте в виду, что, хотя семантический анализ звучит причудливо и глубоко, это всего лишь еще один шаг после парсинга нашей программы и создания AST для проверки исходной программы на наличие некоторых дополнительных ошибок, которые парсер не смог отловить из-за отсутствия дополнительной информации (контекста).

Сегодня мы сосредоточимся на следующих двух статических семантических проверках*:

1. Чтобы переменные были объявлены до их использования
2. Чтобы не было дублирующихся объявлений переменных

*ПРИМЕЧАНИЕ: Статические семантические проверки - это проверки, которые мы можем сделать перед интерпретацией (оценкой) программы, то есть перед вызовом метода interpret для экземпляра класса Interpreter. Все требования Pascal, упомянутые ранее, могут быть обеспечены с помощью статических семантических проверок, путем прохода по AST и использования информации из таблицы символов.

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

Давайте начнем с нашей первой проверки и убедимся, что в наших программах на Pascal переменные объявляются до их использования. Взгляните на следующую синтаксически правильную, но семантически некорректную программу (ух… слишком много труднопроизносимых слов в одном предложении. :)

program Main;
   var x : integer;

begin
    x := y;
end.

В приведенной выше программе есть одно объявление переменной и две ссылки на переменные. Вы можете увидеть это на рисунке ниже:

Давайте на самом деле проверим, что наша программа синтаксически правильна и что наш парсер не выдает ошибку при ее парсинге. Как говорится, доверяй, но проверяй. :) Скачайте spi.py , запустите оболочку Python и убедитесь сами:

>>> from spi import Lexer, Parser
>>> text = """
program Main;
   var x : integer;

begin
    x := y;
end.
"""
>>>
>>> lexer = Lexer(text)
>>> parser = Parser(lexer)
>>> tree = parser.parse()
>>>

Видите? Никаких ошибок. Мы можем даже сгенерировать AST-диаграмму для этой программы, используя genastdot.py . Сначала сохраните исходный код в файл, скажем, semanticerror01.pas, и выполните следующие команды:

$ python genastdot.py semanticerror01.pas > semanticerror01.dot
$ dot -Tpng -o ast.png semanticerror01.dot

Вот AST-диаграмма:

Итак, это грамматически (синтаксически) правильная программа, но программа не имеет смысла, потому что мы даже не знаем, какой тип имеет переменная y (поэтому нам нужны объявления), и имеет ли смысл присваивать y переменной x. Что, если y - это строка, имеет ли смысл присваивать строку целому числу? Это не так, по крайней мере, в Pascal.

Итак, в приведенной выше программе есть семантическая ошибка, потому что переменная y не объявлена, и мы не знаем ее тип. Чтобы мы могли отлавливать подобные ошибки, нам нужно научиться проверять, что переменные объявлены до их использования. Итак, давайте научимся это делать.

Давайте внимательнее посмотрим на следующую синтаксически и семантически правильную программу:

program Main;
   var x, y : integer;

begin
    x := x + y;
end.

• В ней есть два объявления переменных: x и y
• В ней также есть три ссылки на переменные (x, еще одна x и y) в выражении присваивания x := x + y;

Программа грамматически правильна, все переменные объявлены, и мы видим, что сложение двух целых чисел и присваивание результата целому числу имеет смысл. Это здорово, но как нам программно проверить, что переменные (ссылки на переменные) x и y в выражении присваивания x := x +y; были объявлены?

Мы можем сделать это в несколько этапов, реализовав следующий алгоритм:

1. Пройтись по всем объявлениям переменных
2. Для каждого объявления переменной, которое вы встречаете, собрать всю необходимую информацию об объявленной переменной
3. Сохранить собранную информацию в некотором хранилище для дальнейшего использования, используя имя переменной в качестве ключа
4. Когда вы видите ссылку на переменную, например, в выражении присваивания x := x + y, выполнить поиск в хранилище по имени переменной, чтобы увидеть, есть ли в хранилище какая-либо информация о переменной. Если есть, то переменная была объявлена. Если нет, то переменная еще не была объявлена, что является семантической ошибкой.

Вот как может выглядеть блок-схема нашего алгоритма:

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

• A. Какую информацию о переменных нам нужно собрать?
• B. Где и как мы должны хранить собранную информацию?
• C. Как мы реализуем шаг “пройтись по всем объявлениям переменных”?

Наш план действий будет следующим:

1. Выяснить ответы на вопросы A, B и C выше.
2. Использовать ответы на A, B и C для реализации шагов алгоритма для нашей первой статической семантической проверки: проверки того, что переменные объявлены до их использования.

Итак, давайте начнем.

Давайте найдем ответ на вопрос “Какую информацию о переменных нам нужно собрать?”

Итак, какую необходимую информацию нам нужно собрать о переменной? Вот важные части:

• Имя (нам нужно знать имя объявленной переменной, потому что позже мы будем искать переменные по их именам)
• Категория (нам нужно знать, что это за идентификатор: переменная, тип, процедура и т. д.)
• Тип (эта информация понадобится нам для проверки типов)

Символы будут содержать эту информацию (имя, категорию и тип) о наших переменных. Что такое символ? Символ - это идентификатор некоторой программной сущности, такой как переменная, подпрограмма или встроенный тип.

В следующем примере программы у нас есть два объявления переменных, которые мы будем использовать для создания двух символов переменных: x и y.

В коде мы будем представлять символы с помощью класса под названием Symbol, который имеет поля name и type:

class Symbol(object):
    def __init__(self, name, type=None):
        self.name = name
        self.type = type

Как видите, класс принимает параметр name и необязательный параметр type (не все символы имеют связанную с ними информацию о типе, как мы увидим в ближайшее время).

А что насчет категории? Мы закодируем категорию в имя класса. В качестве альтернативы мы могли бы хранить категорию символа в выделенном поле category класса Symbol, как в:

class Symbol(object):
    def __init__(self, name, type=None):
        self.name = name
        self.type = type
        self.category = category

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

До сих пор я как бы обходил одну тему - тему встроенных типов. Если вы посмотрите на нашу программу-пример еще раз:

program Main;
   var x, y : integer;

begin
    x := x + y;
end.

Вы можете видеть, что переменные x и y объявлены как целые числа. Что такое тип integer? Целочисленный тип - это еще один вид символа, символ встроенного типа. Он называется встроенным, потому что его не нужно явно объявлять в программе на Pascal. Наш интерпретатор несет ответственность за объявление этого символа типа и предоставление его программистам:

Мы собираемся создать отдельный класс для встроенных типов под названием BuiltinTypeSymbol. Вот определение класса для наших встроенных типов:

class BuiltinTypeSymbol(Symbol):
    def __init__(self, name):
        super().__init__(name)

    def __str__(self):
        return self.name

    def __repr__(self):
        return "<{class_name}(name='{name}')>".format(
            class_name=self.__class__.__name__,
            name=self.name,
        )

Класс BuiltinTypeSymbol наследуется от класса Symbol, и его конструктор требует только имя типа, например, integer или real. Категория “встроенный тип” закодирована в имени класса, как мы обсуждали ранее, а параметр type из базового класса автоматически устанавливается в None, когда мы создаем новый экземпляр класса BuiltinTypeSymbol.

ПРИМЕЧАНИЕ

Методы с двойным подчеркиванием или dunder (как в “Double UNDERscore”) __str__ и __repr__ - это специальные методы Python. Мы определили их, чтобы иметь красивое отформатированное сообщение, когда мы печатаем объект символа в стандартный вывод.

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

Вот наша иерархия классов символов на данный момент:

Давайте поиграем со встроенными типами в оболочке Python. Скачайте файл интерпретатора и сохраните его как spi.py; запустите оболочку python из того же каталога, где вы сохранили файл spi.py, и поиграйте с классом, который мы только что определили, в интерактивном режиме:

$ python
>>> from spi import BuiltinTypeSymbol
>>> int_type = BuiltinTypeSymbol('integer')
>>> int_type
<BuiltinTypeSymbol(name='integer')>
>>>
>>> real_type = BuiltinTypeSymbol('real')
>>> real_type
<BuiltinTypeSymbol(name='real')>

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

Как мы можем представить их в коде? Давайте создадим класс VarSymbol:

class VarSymbol(Symbol):
    def __init__(self, name, type):
        super().__init__(name, type)

    def __str__(self):
        return "<{class_name}(name='{name}', type='{type}')>".format(
            class_name=self.__class__.__name__,
            name=self.name,
            type=self.type,
        )

    __repr__ = __str__

В этом классе мы сделали обязательными параметры name и type, а имя класса VarSymbol четко указывает на то, что экземпляр класса будет идентифицировать символ переменной (категория - variable). Параметр type является экземпляром класса BuiltinTypeSymbol.

Давайте вернемся в интерактивную оболочку Python, чтобы увидеть, как мы можем вручную создавать экземпляры наших символов переменных, теперь, когда мы знаем, как создавать экземпляры класса BuiltinTypeSymbol:

$ python
>>> from spi import BuiltinTypeSymbol, VarSymbol
>>> int_type = BuiltinTypeSymbol('integer')
>>> real_type = BuiltinTypeSymbol('real')
>>>
>>> var_x_symbol = VarSymbol('x', int_type)
>>> var_x_symbol
<VarSymbol(name='x', type='integer')>
>>>
>>> var_y_symbol = VarSymbol('y', real_type)
>>> var_y_symbol
<VarSymbol(name='y', type='real')>
>>>

Как видите, сначала мы создаем экземпляр символа встроенного типа, а затем передаем его в качестве второго параметра конструктору VarSymbol: символы переменных должны иметь как имя, так и тип, связанные с ними, как вы видели в различных объявлениях переменных, таких как var x : integer;

И вот полная иерархия символов, которые мы определили до сих пор, в визуальной форме:

Итак, теперь перейдем к ответу на вопрос “Где и как мы должны хранить собранную информацию?”

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

Ответ, как вы, вероятно, уже знаете, в таблице символов.

Что такое таблица символов? Таблица символов - это абстрактный тип данных для отслеживания различных символов в исходном коде. Думайте об этом как о словаре, где ключом является имя символа, а значением - экземпляр класса символа (или одного из его подклассов). Чтобы представить таблицу символов в коде, мы будем использовать выделенный класс для нее, метко названный SymbolTable. :) Чтобы хранить символы в таблице символов, мы добавим метод insert в наш класс таблицы символов. Метод insert будет принимать символ в качестве параметра и хранить его внутри упорядоченного словаря _symbols, используя имя символа в качестве ключа и экземпляр символа в качестве значения:

class SymbolTable(object):
    def __init__(self):
        self._symbols = {}

    def __str__(self):
        symtab_header = 'Symbol table contents'
        lines = ['\n', symtab_header, '_' * len(symtab_header)]
        lines.extend(
            ('%7s: %r' % (key, value))
            for key, value in self._symbols.items()
        )
        lines.append('\n')
        s = '\n'.join(lines)
        return s

    __repr__ = __str__

    def insert(self, symbol):
        print('Insert: %s' % symbol.name)
        self._symbols[symbol.name] = symbol

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

program SymTab1;
   var x, y : integer;

begin

end.

Скачайте symtab01.py , который содержит наш новый класс SymbolTable, и запустите его в командной строке. Вот как выглядит вывод для нашей программы выше:

$ python symtab01.py
Insert: INTEGER
Insert: x
Insert: y

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

А теперь давайте построим и заполним таблицу символов вручную в оболочке Python:

$ python
>>> from symtab01 import SymbolTable, BuiltinTypeSymbol, VarSymbol
>>> symtab = SymbolTable()
>>> int_type = BuiltinTypeSymbol('INTEGER')
>>> # now let's store the built-in type symbol in the symbol table
...
>>> symtab.insert(int_type)
Insert: INTEGER
>>>
>>> symtab

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>

>>> var_x_symbol = VarSymbol('x', int_type)
>>> symtab.insert(var_x_symbol)
Insert: x
>>> symtab

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>

>>> var_y_symbol = VarSymbol('y', int_type)
>>> symtab.insert(var_y_symbol)
Insert: y
>>> symtab

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

>>>

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

• A. Какую информацию о переменных нам нужно собрать?

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

• B. Где и как мы должны хранить собранную информацию?

Мы храним собранные символы в таблице символов, используя ее метод insert.

Теперь давайте найдем ответ на наш третий вопрос: “Как мы реализуем шаг “пройтись по всем объявлениям переменных”?”

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

Теперь у нас есть ответы на все три вопроса:

• A. Какую информацию о переменных нам нужно собрать?

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

• B. Где и как мы должны хранить собранную информацию?

Мы храним собранные символы в таблице символов, используя ее метод insert.

• C. Как мы реализуем шаг “пройтись по всем объявлениям переменных”?

Мы создадим нового посетителя AST, который будет выполнять некоторые действия при посещении узлов AST VarDecl.

Давайте создадим новый класс посетителя дерева и дадим ему имя SemanticAnalyzer. Взгляните на следующую программу-пример, например:

program SymTab2;
   var x, y : integer;

begin

end.

Чтобы иметь возможность анализировать приведенную выше программу, нам не нужно реализовывать все методы visit_xxx, только их подмножество. Ниже приведен скелет класса SemanticAnalyzer с достаточным количеством методов visit_xxx, чтобы иметь возможность успешно пройтись по AST программы-примера выше:

class SemanticAnalyzer(NodeVisitor):
    def __init__(self):
        self.symtab = SymbolTable()

    def visit_Block(self, node):
        for declaration in node.declarations:
            self.visit(declaration)
        self.visit(node.compound_statement)

    def visit_Program(self, node):
        self.visit(node.block)

    def visit_Compound(self, node):
        for child in node.children:
            self.visit(child)

    def visit_NoOp(self, node):
        pass

    def visit_VarDecl(self, node):
        #  Actions go here
        pass

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

Вот шаги алгоритма еще раз:

1. Пройтись по всем объявлениям переменных
2. Для каждого объявления переменной, которое вы встречаете, собрать всю необходимую информацию об объявленной переменной
3. Сохранить собранную информацию в некотором хранилище для дальнейшего использования, используя имя переменной в качестве ключа
4. Когда вы видите ссылку на переменную, например, в выражении присваивания x := x + y, выполнить поиск в хранилище по имени переменной, чтобы увидеть, есть ли в хранилище какая-либо информация о переменной. Если есть, то переменная была объявлена. Если нет, то переменная еще не была объявлена, что является семантической ошибкой.

Давайте реализуем эти шаги. На самом деле, единственное, что нам нужно сделать, это заполнить метод visit_VarDecl класса SemanticAnalyzer. Вот он, заполненный:

def visit_VarDecl(self, node):
    # For now, manually create a symbol for the INTEGER built-in type
    # and insert the type symbol in the symbol table.
    type_symbol = BuiltinTypeSymbol('INTEGER')
    self.symtab.insert(type_symbol)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.insert(var_symbol)

Если вы посмотрите на содержимое метода, вы увидите, что он фактически включает в себя все три шага:

1. Метод будет вызываться для каждого объявления переменной, как только мы вызовем метод visit экземпляра SemanticAnalyzer. Это охватывает шаг 1 алгоритма: “Пройтись по всем объявлениям переменных”
2. Для каждого объявления переменной метод visit_VarDecl будет собирать необходимую информацию и создавать экземпляр символа переменной. Это охватывает шаг 2 алгоритма: “Для каждого объявления переменной, которое вы встречаете, собрать всю необходимую информацию об объявленной переменной”
3. Метод visit_VarDecl будет хранить собранную информацию об объявлении переменной в таблице символов, используя метод insert таблицы символов. Это охватывает шаг 3 алгоритма: “Сохранить собранную информацию в некотором хранилище для дальнейшего использования, используя имя переменной в качестве ключа”

Чтобы увидеть все эти шаги в действии, скачайте файл symtab02.py и сначала изучите его исходный код. Затем запустите его в командной строке и изучите вывод:

$ python symtab02.py
Insert: INTEGER
Insert: x
Insert: INTEGER
Insert: y

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

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

Итак, давайте реализуем шаг 4 нашего алгоритма. Вот обновленная версия шага 4, отражающая введение символов и таблицы символов: Когда вы видите ссылку на переменную (имя), например, в выражении присваивания x := x + y, выполните поиск в таблице символов по имени переменной, чтобы увидеть, есть ли в таблице символ переменной, связанный с именем. Если есть, то переменная была объявлена. Если нет, то переменная еще не была объявлена, что является семантической ошибкой.

Чтобы реализовать шаг 4, нам нужно внести некоторые изменения в таблицу символов и семантический анализатор:

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

Во-первых, давайте обновим наш класс SymbolTable, добавив метод lookup, который будет отвечать за поиск символа по имени. Другими словами, метод lookup будет отвечать за разрешение имени переменной (ссылки на переменную) в ее объявление. Процесс сопоставления ссылки на переменную с ее объявлением называется разрешением имен. И вот наш метод lookup, который делает именно это, разрешение имен:

def lookup(self, name):
    print('Lookup: %s' % name)
    symbol = self._symbols.get(name)
    # 'symbol' is either an instance of the Symbol class or None
    return symbol

Метод принимает имя символа в качестве параметра и возвращает символ, если он его находит, или None, если нет. Все просто.

Пока мы этим занимаемся, давайте также обновим наш класс SymbolTable, чтобы инициализировать встроенные типы. Мы сделаем это, добавив метод _init_builtins и вызвав его в конструкторе SymbolTable. Метод _init_builtins вставит символ типа для integer и символ типа для real в таблицу символов.

Вот полный код для нашего обновленного класса SymbolTable:

class SymbolTable(object):
    def __init__(self):
        self._symbols = {}
        self._init_builtins()

    def _init_builtins(self):
        self.insert(BuiltinTypeSymbol('INTEGER'))
        self.insert(BuiltinTypeSymbol('REAL'))

    def __str__(self):
        symtab_header = 'Symbol table contents'
        lines = ['\n', symtab_header, '_' * len(symtab_header)]
        lines.extend(
            ('%7s: %r' % (key, value))
            for key, value in self._symbols.items()
        )
        lines.append('\n')
        s = '\n'.join(lines)
        return s

    __repr__ = __str__

    def insert(self, symbol):
        print('Insert: %s' % symbol.name)
        self._symbols[symbol.name] = symbol

    def lookup(self, name):
        print('Lookup: %s' % name)
        symbol = self._symbols.get(name)
        # 'symbol' is either an instance of the Symbol class or None
        return symbol

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

Изменение также исправит проблему с двойным выводом строки Insert: INTEGER, которую мы видели ранее.

Вот метод visit_VarDecl до изменения:

def visit_VarDecl(self, node):
    # For now, manually create a symbol for the INTEGER built-in type
    # and insert the type symbol in the symbol table.
    type_symbol = BuiltinTypeSymbol('INTEGER')
    self.symtab.insert(type_symbol)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.insert(var_symbol)

и после изменения:

def visit_VarDecl(self, node):
    type_name = node.type_node.value
    type_symbol = self.symtab.lookup(type_name)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.insert(var_symbol)

Давайте применим изменения к знакомой программе на Pascal, в которой есть только объявления переменных:

program SymTab3;
   var x, y : integer;

begin

end.

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

$ python symtab05.py
Insert: INTEGER
Insert: REAL
Lookup: INTEGER
Insert: x
Lookup: y
Error: Symbol(identifier) not found 'y'

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
   REAL: <BuiltinTypeSymbol(name='REAL')>
      x: <VarSymbol(name='x', type='INTEGER')>

Вы можете видеть сообщение об ошибке Error: Symbol(identifier) not found ‘y’ и содержимое таблицы символов.

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

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

Давайте взглянем на следующую программу, SymTab6:

program SymTab6;
   var x, y : integer;
   var y : real;
begin
   x := x + y;
end.

Переменная y была объявлена дважды: первый раз как integer, а второй раз как real.

Чтобы поймать эту семантическую ошибку, нам нужно изменить наш метод visit_VarDecl, чтобы проверить, есть ли в таблице символов символ с тем же именем, прежде чем вставлять новый символ. Вот наша новая версия метода:

def visit_VarDecl(self, node):
    type_name = node.type_node.value
    type_symbol = self.symtab.lookup(type_name)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)

    # Signal an error if the table alrady has a symbol
    # with the same name
    if self.symtab.lookup(var_name) is not None:
        raise Exception(
            "Error: Duplicate identifier '%s' found" % var_name
        )

    self.symtab.insert(var_symbol)

Файл symtab06.py содержит все изменения. Загрузите его и запустите в командной строке:

$ python symtab06.py
Insert: INTEGER
Insert: REAL
Lookup: INTEGER
Lookup: x
Insert: x
Lookup: INTEGER
Lookup: y
Insert: y
Lookup: REAL
Lookup: y
Error: Duplicate identifier 'y' found

Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
   REAL: <BuiltinTypeSymbol(name='REAL')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

Изучите вывод и содержимое таблицы символов. Убедитесь, что вы понимаете, что происходит.

Summary

Давайте быстро повторим, что мы узнали сегодня:

• Мы узнали больше о символах, таблицах символов и семантическом анализе в целом.
• Мы узнали о разрешении имен и о том, как семантический анализатор разрешает имена в их объявления.
• Мы узнали, как закодировать семантический анализатор, который проходит по AST, строит таблицу символов и выполняет базовые семантические проверки.

И, в качестве напоминания, структура нашего интерпретатора теперь выглядит так:

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

Получите преимущество и оставайтесь в тонусе. Подпишитесь на Beyond Basics бесплатно и получайте новые публикации, не пропуская ни одного момента!

Литература

• Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)
• Writing Compilers and Interpreters: A Software Engineering Approach
• Modern Compiler Implementation in Java
• Modern Compiler Design
• Compilers: Principles, Techniques, and Tools (2nd Edition)