[编译原理-词法分析(一)] 输入缓冲双缓冲区方案

Jamina ·

更新时间:2024-11-11

· 650 次阅读

前言

在实践中, 通常需要向前看一个字符. 
比如, 当读到一个 非字母或数字的字符 时才能确定已经读到一个标识符的结尾. 因此, 这个字符不是id词素的一部分. 
采用双缓冲区方案能够安全地处理向前看多个符号的问题. 然后, 将考虑一种改进方案, 使用"哨兵标记"来节约用于检查缓冲区末端的时间. {P72}

前情提要

一、缓冲区对
二、哨兵标记
三、实现双缓冲区

正文 一、缓冲区对

描述:
    两个交替读入的缓冲区, 容量为N个字符, 使用系统命令一次性将N个字符读入到缓冲区;
    如果输入字符不足N个, 则有特殊字符EOF来标记文件结尾;
    程序维护两个指针lexemeBegin和forward;
    lexemeBegin指向当前词素的开始处, 当前正试图确定这个词素的结尾;
    forward向前扫描, 直到与某个模式匹配为止;
    当确定该词素时, forward指向该词素结尾的字符;
    将词素作为摸个返回给语法分析器的词法单元的属性值记录;
    lexemeBegin指向该词素后的第一个字符, 然后将forward左移一个字符;
    在forward不断扫描中, 检查是否扫描到EOF, 如果是则将N个新字符读入另外一个缓冲区, 且将forward指向缓冲区头部;

二、哨兵标记

当采用双缓冲区方案, 那么每次向前移动forward指针时, 都需要检查是否到缓冲区结尾, 若是则加载另外一个缓冲区.
如果扩展每个缓冲区, 使它们在末尾包含一个哨兵(sentinel)字符, 就可以把缓冲区末尾的测试和当前字符的测试结合在一起, 这个字符选择不会出现在源程序中的 EOF标记.

三、实现双缓冲区

将使用标记来自哪个文件


namespace Lexical_Analysis {
    template 
    class Buffer {
    private:
        enum Tag { ONE, TWO }; // 缓冲区标号
    public:
        explicit Buffer(std::string _fileStr);
        ~Buffer() noexcept;
    public:
        char* lexemeBegin = nullptr;
        char* forward = nullptr;
        /**
         * @return 返回lexemeBegin 与 forward 的字符序列
         */
        std::string getString();
        /**
         * forward向前移动一个字符
         * @return 返回当前字符
         */
        char next();
        /**
         * @return 返回当前forward所指字符
         */
        char cur();
        /**
         * forward向后移动一个字符
         * @return 返回当前字符
         */
        char pre();
    private:
        std::string fileStr; // 文件路径
        std::ifstream fileStream; // 文件流
        char buffer_1[size];
        char buffer_2[size];
        Buffer::Tag bufferTag = Tag::ONE; // 哪个缓冲区
    private:
        /**
         * 从fileStream流读取字符序列
         */
        void read();
    public:
        bool is_end = false; // 是否读到结尾
    };
};


namespace Lexical_Analysis {
    template
    Buffer::Buffer(std::string _fileStr):fileStr(std::move(_fileStr)) {
        fileStream.open(fileStr);
        buffer_1[size - 1] = EOF;
        fileStream.read(buffer_1, size - 1);
        lexemeBegin = forward = &buffer_1[0];
    }
    template
    Buffer::~Buffer() noexcept {
        if (fileStream) {
            fileStream.close();
        }
    }
    template
    std::string Buffer::getString() {
        std::stringstream ss;
        char* current = lexemeBegin;
        while (current != forward) {
            if (*current == EOF) {
                if (bufferTag == Tag::ONE) {
                    current = &buffer_1[0];
                } else if (bufferTag == Tag::TWO) {
                    current = &buffer_2[0];
                }
            }
            ss << *current++;
        }
        return ss.str();
    }
    template
    void Buffer::read() {
        if (!fileStream) return ;
        /**
         * bufferTag 为当前从文件流读入的缓冲区标号
         * 将每个缓冲区的末尾设置为 哨兵标记
         */
        if (bufferTag == Tag::ONE) {
            // 当前在第一个缓冲区末尾, 装载第二个缓冲区
            buffer_2[size - 1] = EOF;
            fileStream.read(buffer_2, size - 1);
            // 设置Tag为第二个缓冲区, 并且设置forward为第二个缓冲区的开头
            bufferTag = Tag::TWO;
            forward = &buffer_2[0];
        } else if (bufferTag == Tag::TWO) {
            // 当前在第二个缓冲区末尾, 装载第一个缓冲区
            buffer_1[size - 1] = EOF;
            fileStream.read(buffer_1, size - 1);
            // 设置Tag为第一个缓冲区, 并且设置forward为第一个缓冲区的开头
            bufferTag = Tag::ONE;
            forward = &buffer_1[0];
        }
    }
    template
    char Buffer::next() {
        char c = *forward;
        if (c == '\0') {
            // 终止词法分析
            is_end = true;
            return '\0';
        }
        if (c == EOF) {
            // 已到缓冲区末尾标记
            read();
        }
        return *forward++;
    }
    template
    char Buffer::cur() {
        return *forward;
    }
    template
    char Buffer::pre() {
        /**
         * 会出现forward在某个缓冲区的第一个字符
         * 当回退时, 需要判断是否切换过缓冲区, 如果是则回退到另一个缓冲区的EOF
         * 如果没有, 则不执行任何操作
         */
        char c = *forward;
        if (forward == &buffer_2[0]) {
            // 如果当前为第二个缓冲区, 则必定切换过
            forward = &buffer_1[size - 1];
            return c;
        } else if (forward == &buffer_1[0] && buffer_2[0] != '\0') {
            // 当前为第一个缓冲区, 并且第二个缓冲区有数据, 则认为当前切换过缓冲区, 执行回退
            forward = &buffer_2[size - 1];
            return c;
        } else if (forward == &buffer_1[0] && buffer_2[0] == '\0') {
            // 当前为第一个缓冲区, 并且第二个缓冲区没有数据, 则认为当前没有切换过缓冲区, 不执行回退
            return c;
        }
        forward--;
        return c;
    }
};

尾记

只要从不需要越过实际词素向前看很远, 以至于这个词素的长度加上向前看的距离大于N,就决不会识别这个词素之前覆盖尚在缓冲区的词素 {P72}
lexemeBegin指针在第一个缓冲区, 而forward指针已经指向第二个缓冲区的EOF. 当forward向前移动一个字符时, 需要切换缓冲区, 这样会导致将第一个缓冲区覆盖.

作者：yanuas

输入缓冲双缓冲编译原理

1024 个赞