Написание компилятора с нуля (1): система ввода и лексический анализ

переводчик
Написание компилятора с нуля (1): система ввода и лексический анализ

предисловие

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

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

В начале будет написан интерпретатор языка C, а AST будет напрямую проходиться и выполняться напрямую, а затем будет добавляться сгенерированная часть кода, то есть скомпилированная в байт-код Java

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

Официально начать

Есть в основном эти части для завершения компилятора

  • лексический анализ

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

  • Разбор

Он в основном делится на грамматический анализ сверху вниз и снизу вверх, как правило, рекурсивный спуск, LL (1), LR (1), LALR (1) несколько методов достижения. Результатом этого шага является синтаксическое дерево.

  • Семантический анализ

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

  • генерация кода

Здесь обычно создается независимый от платформы промежуточный язык (IR), который ближе к нижнему слою.На этом этапе вводится AST, а выводится IR.

  • Оптимизация кода

Работа этого шага такая же, как и название: оптимизация кода, повышение производительности и т. д.

  • генерация объектного кода

Задача этого шага — сгенерировать язык ассемблера, зависящий от платформы.

Выше это почти компилятор в общем смысле, но можно и исполняемые файлы генерировать в том числе и вызывать ассемблер компоновщика

Горизонтальное время ограничено в C2j-Compiler, для последних трех шагов AST напрямую проходит для генерации целевого байт-кода Java без какой-либо оптимизации. Лексический анализ написан вручную, а синтаксический анализ использует таблицу синтаксического анализа LALR(1).

система ввода

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

В системе ввода есть три основных файла

  • FileHandler.java
  • DiskFileHandler.java
  • Input.java

FileHadnler

В качестве входного интерфейса DiskFileHandler реализует этот интерфейс для чтения из файла. Существует три основных метода

void open();
int close();
int read(byte[] buf, int begin, int end);

Среди них чтение — это копирование указанной длины данных в указанный буфер и указание начальной позиции буфера.

Полный исходный код на моем складеdejavudwh

Input

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

inputAdvance должен получить ввод из предыдущей позиции.Перед получением ввода он проверит, нужен ли флеш-буфер.

public byte inputAdvance() {
        char enter = '\n';

        if (isReadEnd()) {
            return 0;
        }

        if (!readEof && flush(false) < 0) {
            //缓冲区出错
            return -1;
        }

        if (inputBuf[next] == enter) {
            curCharLineno++;
        }

        endCurCharPos++;

        return inputBuf[next++];
}

Основная логика flush заключается в том, чтобы судить о том, пересек ли следующий указатель опасную позицию, или же force равно true, то есть требуется принудительный сброс, а затем вызывается fillbuf для заполнения буфера.

private int flush(boolean force) {
        int noMoreCharToRead = 0;
        int flushOk = 1;

        int shiftPart, copyPart, leftEdge;
        if (isReadEnd()) {
            return noMoreCharToRead;
        }

        if (readEof) {
            return flushOk;
        }

        if (next > DANGER || force) {
            leftEdge = next;
            copyPart = bufferEndFlag - leftEdge;
            System.arraycopy(inputBuf, leftEdge, inputBuf, 0, copyPart);
            if (fillBuf(copyPart) == 0) {
                System.err.println("Internal Error, flush: Buffer full, can't read");
            }

            startCurCharPos -= leftEdge;
            endCurCharPos -= leftEdge;
            next  -= leftEdge;
        }

        return flushOk;
}

private int fillBuf(int startPos) {
        int need;
        int got;
        need = END - startPos;
        if (need < 0) {
            System.err.println("Internal Error (fill buf): Bad read-request starting addr.");
        }

        if (need == 0) {
            return 0;
        }

        if ((got = fileHandler.read(inputBuf, startPos, need)) == -1) {
            System.err.println("Can't read input file");
        }

        bufferEndFlag = startPos + got;
        if (got < need) {
            //输入流已经到末尾
            readEof = true;
        }

        return got;
}

лексический анализ

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

В Lexer есть два файла:

  • Token.java
  • Lexer.java

Token

Токен в основном используется для идентификации каждого токена, который в основном используется в лексера, какNAMEдля представления идентификаторов, NUMBER для представления чисел и STRUCT для представления ключевого слова struct.

//terminals
NAME, TYPE, STRUCT, CLASS, LP, RP, LB, RB, PLUS, LC, RC, NUMBER, STRING, QUEST, COLON,
RELOP, ANDAND, OR, AND, EQUOP, SHIFTOP, DIVOP, XOR, MINUS, INCOP, DECOP, STRUCTOP,
RETURN, IF, ELSE, SWITCH, CASE, DEFAULT, BREAK, WHILE, FOR, DO, CONTINUE, GOTO,

Lexer

И Lexer использует предыдущий ввод для чтения входного потока для вывода потока токена.

public void advance() {
        lookAhead = lex();
}

Основная логика Lexer находится в lex(), каждый раз, когда он использует inputAdvance для чтения из входного потока, пока не встретится пустой символ или символ новой строки, он представляет конец по крайней мере одного токена,(Если вы встретите здесь двойные кавычки, то есть пробелы в строке нельзя рассматривать как пробелы), а затем начать анализ.

Код слишком длинный и вырезана только его часть.Логика очень проста.Кроме того, комментарии не обрабатывались при написании в начале и не добавлялись позже.

for (int i = 0; i < current.length(); i++) {
                length = 0;
                text = current.substring(i, i + 1);
                switch (current.charAt(i)) {
                    case ';':
                        current = current.substring(1);
                        return Token.SEMI.ordinal();
                    case '+':
                        if (i + 1 < current.length() && current.charAt(i + 1) == '+') {
                            current = current.substring(2);
                            return Token.INCOP.ordinal();
                        }

                        current = current.substring(1);
                        return Token.PLUS.ordinal();

                    case '-':
                        if (i + 1 < current.length() && current.charAt(i + 1) == '>') {
                            current = current.substring(2);
                            return Token.STRUCTOP.ordinal();
                        } else if (i + 1 < current.length() && current.charAt(i + 1) == '-') {
                            current = current.substring(2);
                            return Token.DECOP.ordinal();
                        }

                        current = current.substring(1);
                        return Token.MINUS.ordinal();

                        ...
                        ...
}

На этом система ввода и лексический анализ закончены.

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

Категории