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

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

Полный код проекта находится по адресуC2j-Compiler

предисловие

Файлы о таблице символов находятся в пакете symboltable.

Ранее мы построили таблицу синтаксического анализа, завершив автомат с конечным состоянием LALR(1) и сообщение сокращения, и формально завершили синтаксический анализ языка C. Следующим шагом является вход в часть семантического анализа.Как упоминалось во второй части, основная задача семантического анализа состоит в том, чтобы создать таблицу символов для записи переменных и типов переменных и найти предложения, которые не соответствуют семантике.

Описательная переменная

Есть два основных описания определений объявлений переменных в языке C.

  • Спецификатор

    Спецификаторы — это некоторые типы переменных описания, соответствующие языку C, или ключевые слова, такие как static и extern (ключевые слова, такие как extern, не используются в компиляторе, реализованном на этот раз, потому что extern может также включать компиляцию и компоновку нескольких исходных файлов)

  • декларатор

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

Таким образом можно завершить два класса, и логика обоих классов относительно проста:

Класс декларатора

  • declareType: используется для указания того, является ли текущий декларатор указателем, массивом или функцией.
  • numberOfElements, elements: если текущий тип является массивом, они представляют количество элементов массива и элементы массива.
public class Declarator {
    public static int POINTER = 0;
    public static int ARRAY = 1;
    public static int FUNCTION = 2;

    private int declareType;
    private int numberOfElements = 0;

    HashMap<Integer, Object> elements = null;

    public Declarator(int type) {
        this.declareType = type;
    }
    ...
}

Класс спецификатора

Спецификатор будет иметь больше атрибутов, но позже компилятор может поддерживать только четыре типа int, char, void, struct.

  • basicType: используется для указания типа текущей переменной

  • storageClass: Указывает способ хранения переменной (fixed, auto), здесь мы также размещаем здесь информацию о typedef, то есть, если встречается typedef, то storageClass будет установлен в TYPEDEF

  • ConstantValue и vStruct: это два специальных свойства. Они представляют типы перечисления и структуры. Причина, по которой они являются особыми, заключается в том, что с ними нужно обращаться по-особому. Если встреча с перечисляемым типом эквивалентна созданию Specifier, базовый тип которого является CONSTANT, соответствующее значение также является константным значением.

public class Specifier {
    /**
     * Variable types
     */
    public static int NONE = -1;
    public static int INT = 0;
    public static int CHAR = 1;
    public static int VOID = 2;
    public static int STRUCTURE = 3;
    public static int LABEL = 4;

    /**
     * storage
     */
    public static int FIXED = 0;
    public static int REGISTER = 1;
    public static int AUTO = 2;
    public static int TYPEDEF = 3;
    public static int CONSTANT = 4;

    public static int NO_OCLASS = 0;
    public static int PUBLIC = 1;
    public static int PRIVATE = 2;
    public static int EXTERN = 3;
    public static int COMMON = 4;

    private int basicType;
    private int storageClass;
    private int outputClass = NO_OCLASS;
    private boolean isLong = false;
    private boolean isSigned = false;
    private boolean isStatic = false;
    private boolean isExternal = false;
    private int constantValue = 0;
    private StructDefine vStruct = null;
}

Таблица дескрипторов

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

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

Эта структура данных имеет несколько основных условий как таблица символов:

  1. скорость Поскольку таблица символов требует частых вставок и поисковых запросов, скорость запросов и вставок должна быть достаточно высокой.
  2. гибкий Поскольку определение переменных может быть сложным, например, несколько модификаторов плюс указатели ((long int, long doube *), дизайн должен быть достаточно гибким.

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

Чтобы обеспечить два вышеуказанных условия, мы используем связанную хэш-таблицу для достижения

Эту картинку я нашел в сети, на самом деле это не так уж и сложно

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

symboltable.Symbol

Этот класс используется для описания символа в таблице символов.

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

Основные свойства:

  • уровень: используется для указания уровня переменной
  • дубликат: это переменная с тем же именем
  • args: если символ соответствует имени функции, то args указывает на список символов входного параметра функции.
  • следующий: указать на следующий переменный символ того же уровня
public class Symbol {
    String name;
    String rname;
    int level; 
    boolean duplicate; 
    Symbol args; 
    Symbol next;  
}

В настоящее время использование Symbol плюс предыдущие Specifier и Declarator имеет достаточную выразительную силу для описания символа, тогда вам нужно связать эти три класса, сначала добавьте TypeLink

TypeLink

TypeLink представляет Specifier или Declarator, и здесь лучше использовать наследование.

public class TypeLink {
    public boolean isDeclarator;
    /**
     * typedef int
     */
    public boolean isTypeDef;
    /**
     * Specifier or Declarator
     */
    public Object typeObject;

    private TypeLink next = null;

    public TypeLink(boolean isDeclarator, boolean typeDef, Object typeObj) {
        this.isDeclarator = isDeclarator;
        this.isTypeDef = typeDef;
        this.typeObject = typeObj;
    }

    public Object getTypeObject() {
        return typeObject;
    }

    public TypeLink toNext() {
        return next;
    }

    public void setNextLink(TypeLink obj) {
        this.next = obj;
    }

}

Таким образом, к символу необходимо добавить два атрибута.

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

public class Symbol {
    String name;
    String rname;
    int level;  
    boolean implicit;  
    boolean duplicate; 
    Symbol args;  
    Symbol next;

    TypeLink typeLinkBegin;
    TypeLink typeLinkEnd;
}

пример

После этого, например

long int (*e)[10];

можно выразить так

Symbol declartor declartor specifer
name:e declareType = PONITER declareType = array basicType = INT isLong = TRUE
-> -> -> ->

Определение символов структуры

This document has not talked StructDefine, this file is used to describe the structure, because of the complexity of the structure itself, so it will need special handling, but still the combination of structure variables pile nature, it can still using the above procedure described в

  • тег: название структуры
  • level: уровень вложенности структуры
  • Символ: соответствует переменной в структуре
public class StructDefine {
    private String tag;
    private int level;
    private Symbol fields;

    public StructDefine(String tag, int level, Symbol fields) {
        this.tag = tag;
        this.level = level;
        this.fields = fields;
    }
}

пример

См. пример определения структуры

struct dejavidwh {
    int array1[5];
    struct dejavudwh *pointer1;
} one;

резюме

Так что в конце просто нужно

private HashMap<String, ArrayList<Symbol>> symbolTable = new HashMap<>();
    private HashMap<String, StructDefine> structTable = new HashMap<>();

может описать таблицу символов

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

В этом разделе в основном описывается структура данных таблицы символов.Двумя ключевыми моментами являются

  1. Описательная переменная

    Итак, модификаторы и дескрипторы определены для описания переменной.

  2. связанная переменная

    Список символов для последовательного определения переменных

Категории