Masimaro's blog - c++
type: channel
link: https://www.masimaro.top/tag/c/
items: 使用C++20 的协程创建通用的生成器
items: C++ 20 协程的探索
items: Emacs 折腾日记(三十)——打造C++ IDE 续
items: Emacs 折腾日记(二十九)—— 打造C++ IDE
items: 使用CMake跨平台的一些经验
items: CMake 基础
items: 从0开始自制解释器——重构代码
items: 从0开始自制解释器——添加对括号的支持
items: 从0开始自制解释器——添加对乘除法的支持
items: 从0开始自制解释器——实现多位整数的加减法计算器

使用C++20 的协程创建通用的生成器
type: item
date: 2026-06-04T11:14:00+08:00
description: 在上一篇中，我们通过拆解一个简单的例子描述了C++20 处理协程的过程。在此先简单的回顾一下各个部分的作用回顾promise_type主要提供一些与协程相关的接口：initial_suspend： 协程实例创建时执行，通过返回值来决定协程创建的同时执行还是等待final_suspend: 协程实例执行完之后是暂停还是继续，继续意味着会销毁这个实例yield_value/await_transform: 协程函数中执行 co_yield/co_await 时负责将后面的操作数转化为等待体awaiter 对象get_return_object: 返回协程对象return_void / return_value: 真正获取协程函数 co_return 的返回值unhandled_exception 协程函数发生异常时调用等待体是协程函数中调用 co_await/co_yield 时创建, 主要用来告诉编译器遇到这两个操作符时应该继续执行还是等待, 关于等待体 awaiter 它有如下几个接口:bool await_ready() : 根据返回值决定是继续还是等待await_suspend(coroutine_handle<>) : 协程被挂起时调用await_resume() : 协程被恢复时调用关于等待体，标准库有两个简单的实现: suspend_always 和 suspend_never改进生成器c++ 23 中存在一个标准的生成器 std::generator，我们利用这个生成器可以将整个程序修改为:#include <coroutine> #include <iostream> #include <generator> #include <ranges> std::generator<int> fibonacci() { int a = 0; int b = 1; for (;;) { co_yield a; int next = a + b; a = b; b = next; } } int main() { for (auto x : fibonacci() | std::views::take(10)) { std::cout << x << std::endl; } return 0; }本文的目标是最终完成一个简单的、可用的、贴近标准库的 std::generator，进一步理解协程的原理 我们还是按照上一篇的组织方式，先放出完整的源代码，然后依次说明重要的点:#include <coroutine> #include <iostream> #include <generator> #include <ranges> template<typename T> struct Generator { struct promise_type { std::suspend_always initial_suspend() { return std::suspend_always{}; } std::suspend_always final_suspend() noexcept { return std::suspend_always{}; } void unhandled_exception() noexcept { _exp = std::current_exception(); } Generator get_return_object() { return Generator(std::coroutine_handle<promise_type>::from_promise(*this)); } void return_void() {} std::suspend_always yield_value(T value) { _value = std::move(value); return std::suspend_always{}; } void rethrow_if_exception() { if (_exp) throw _exp; } T _value = {}; std::exception_ptr _exp = nullptr; }; Generator(std::coroutine_handle<promise_type> h) : _handle(h) {} ~Generator() { if (_handle) _handle.destroy(); } Generator(const Generator&) = delete; Generator& operator=(const Generator&) = delete; Generator(Generator&& other) noexcep…

C++ 20 协程的探索
type: item
date: 2026-05-25T11:49:00+08:00
description: C++ 20 中新增的协程特性可以说是近几年更新的最重要的一个特性。早在我使用python的时候，我就体会到python中的协程和它在处理list时使用yield 的优雅。现在C++ 也支持了协程，我们可以实现类似python中的功能了完整的协程例子在python中，我们可以实现如下的函数def fibonacci(n): a, b = 0, 1 for _ in range(n): yield a # 暂停函数，返回a a, b = b, a + b # 使用生成器 for num in fibonacci(5): print(num)早期的C++ 中我们只能使用std::vector<int> fibonacci(int n) { vector<int> res; int a = 0, b = 1; for(int i = 0; i < n; i++) { int c = a + b; a = b; b = c; res.push_back(c); } } for(auto i : fibonacci(5)) std::cout << i << std::endl;上面两个对比，python示例的特点在于它不是每次调用都计算指定范围内的所有结果，而是每调用一次接着上一次的进行调用，能极大的提升运行效率。一个好的消息是，在C++20 中新增了协程，我们也能实现类似的功能。而坏消息就是C++20 的协程设计成了底层的“语言特性骨架”，没有提供开箱即用的高层库，所以它的概念相对复杂。#include <coroutine> struct Generator { struct promise_type { int currentValue; std::suspend_always initial_suspend() { return std::suspend_always{}; } std::suspend_always final_suspend() noexcept { return std::suspend_always{}; } auto yield_value(int value) { currentValue = value; return std::suspend_always{}; } Generator get_return_object() { return Generator{ std::coroutine_handle<promise_type>::from_promise(*this) }; } void return_void() {} void unhandled_exception() { std::terminate(); } }; std::coroutine_handle<promise_type> h; Generator(std::coroutine_handle<promise_type> handle) : h(handle) {} ~Generator() { if (h) h.destroy(); } bool move_next() { if (!h || h.done()) return false; h.resume(); return !h.done(); } int get_value() { return h.promise().currentValue; } }; Generator fibonacci(int n) { int a = 0; int b = 1; int i = 0; while (i < n) { co_yield a; int next = a + b; a = b; b = next; i++; } } int _tmain(int argc, TCHAR* argv[]) { Generator generator = fibonacci(10); while (generator.move_next()) { std::cout << generator.get_value() << std::endl; } return 0; }比起python的版本，它确实复杂了不少。但是我们可以从逻辑上一一拆解协程实现原理首先我们知道，普通的函数是通过栈来存储数据的，在调用时首先经过参数压栈，然后在栈中初始化函数的局部变量，接着执行函数代码。在函数退出时要在接收返回值的内存处初始化返回值对象，最后执行出栈操作清理整个函数栈。协程函数是可以随时挂起并回退到调用处，或者由外部直接恢复执行的，所以在回到调用位置时并没有执行函数栈的清理操作，而且需要保存函数当前执行的上下文环境，在需要的时候进行恢复。C++的协程采用的是无栈的设计，也就是说协程函数本身并没有…

Emacs 折腾日记(三十)——打造C++ IDE 续
type: item
date: 2025-09-18T21:23:25+08:00
description: 上一篇博客中，我完成了C++ IDE初步工作，包括代码的高亮、折叠、跳转以及补全等工作。但是作为IDE来说功能还有点不够，就我个人而言作为IDE来说它还需要具备一键编译运行和调试功能。这篇文章就来记录我是如何实现上述功能的编译运行我使用的演示项目比较简单，它的文件结构如下:. ├── include │ └── head.h └── src ├── add.cpp ├── div.cpp ├── main.cpp ├── mult.cpp └── sub.cpp它分为两个目录分别保存头文件和源文件。其中头文件只有一个定义各个接口函数，而接口函数的实现就放到各自定义的cpp文件中。这里使用加减乘除的四则运算的实现来作为演示。这里我分别演示一下Make文件和CMake构建的项目是如何实现一键编译运行的。Make构建的项目针对上前面介绍的简单项目，我们可以写出如下的Makefile# 编译器设置 # 定义项目根目录 ROOT_DIR := $(dir $(abspath $(lastword $(MAKEFILE_LIST)))) CXX := g++ CXXFLAGS := -Iinclude -Wall -Wextra -pedantic -std=c++11 -MMD -MP LDFLAGS := EXE_OUTPUT := $(ROOT_DIR)bin TARGET := $(EXE_OUTPUT)/app $(info TARGET = $(TARGET)) # 源文件和对象文件设置 SRC_DIR := src SRCS := $(wildcard $(SRC_DIR)/*.cpp) OBJ_DIR := $(ROOT_DIR)build/obj OBJS := $(patsubst $(SRC_DIR)/%.cpp,$(OBJ_DIR)/%.o,$(SRCS)) DEPS := $(OBJS:.o=.d) # 默认目标（第一个目标） all: $(TARGET) # 链接生成可执行文件 $(TARGET): $(OBJS) @mkdir -p $(@D) $(CXX) $(LDFLAGS) $^ -o $@ # 编译源文件并生成依赖 $(OBJ_DIR)/%.o: $(SRC_DIR)/%.cpp | $(OBJ_DIR) $(CXX) $(CXXFLAGS) -c $< -o $@ # 创建对象文件目录 $(OBJ_DIR): mkdir -p $@ # 包含自动生成的依赖关系 -include $(DEPS) # 清理生成的文件 clean: rm -rf $(TARGET) build .PHONY: all clean 上面我们定义了头文件路径为include 目录，并且规定了中间文件生成在 build/obj 中，最后定义了生成可执行程序在 bin/app 中对于编译来说，Emacs内置了 compile 命令，它会自动执行 make -k 命令，但是如果我在使用Emacs的过程中切换到了其他目录的话，还需要特别指定Makefile 所在的路径，对我来说我希望能在尽可能少输入参数的情况下完成同样的操作，不太希望每次都指定项目根目录，好在之前配置的projectile 插件帮助我们识别出来了项目的根目录。所以这里可以使用 projectile-compile-project 来自动指定根目录并编译。从上面的截图可以看到，flycheck 提示了几个错误，这是因为项目没有生成 compile_commands.json文件，所以lsp服务器无法跨文件分析，导致找不到头文件。原始的make 命令并不支持生成 compile_commands.json 文件，我们可以通过 bear 命令来完成这个工作，它的用法比较简单，只需要使用 bear -- <your-build-command> 即可, 对于使用make编译的项目来说 <your-build-command> 代表的就是 make 命令。我们需要考虑的一个问题是，如何将bear加入到编译命令中，也就是将它自动生成的 make -k 给替换掉，第二个问题是如果当前目录在其他目录下，如何保证 compile_commands.json 永远生成在根目录下Emacs中有一个变量 compile-command 保存了编译的命令，如果我们使用Emacs自带的compile来编译可以通过修改它来实现，而 projectile-compile-project 则是通过变量 projectile-project-compilation-cmd 来保存编译命令，默认是nil，对于使用 projectile 我们通过修改这个变量的值从而修改编译时使用的命令。另外既然 proj…

Emacs 折腾日记(二十九)—— 打造C++ IDE
type: item
date: 2025-08-08T10:01:28+08:00
description: 在介绍vim配置的时候介绍过lsp的相关基础知识。简单来说lsp是一个协议，它以C/S架构的形式进行组织，lsp负责分析语法，给出具体的语法单元，完成跳转等功能的核心实现。而客户端则负责接收用户的操作请求并呈现具体结果。这样做的好处是将核心服务和客户端显示分离出来，核心部分重用，客户端则可以由各个编辑器自己实现，使各种编辑器都有相同的核心功能体验。对于Emacs来说，由lsp-mode 提供核心客户端库，管理服务器生命周期、消息路由及基础功能。另外也有 lsp-ui 这种增强UI模块，提供实时信息侧边栏（lsp-ui-sideline）、代码透镜（Code Lens）、悬浮文档等下面来介绍如何使用它们配置一个基础的lsp功能lsp-mode根据官方给出的配置，我们可以组一个基础的配置(use-package lsp-mode :ensure t :init ;; set prefix for lsp-command-keymap (few alternatives - "C-l", "C-c l") (setq lsp-keymap-prefix "C-c l") :hook ( ;; if you want which-key integration (lsp-mode . lsp-enable-which-key-integration)) :commands (lsp lsp-deferred))这里我们只是安装了一个客户端，想要真正实现lsp的功能，还需要针对具体的语言下载一个服务端，可以通过 lsp-install-server 来下载如果我们希望能像vscode那样，以悬浮窗口的形式显示符号的定义、声明或者注释文档，那么我们需要使用 lsp-ui 这个插件(use-package lsp-ui :ensure t :after (lsp-mode) :config (setq lsp-ui-doc-position 'top))这里我通过 lsp-ui-doc-position 来定义显示的窗口在上方，一般的编辑器默认是显示在光标所在的位置，但是我觉得显示在光标位置会影响我阅读后续的代码，所以我将它显示在上面，如果各位读者希望它像其他编辑器那样显示在光标位置可以修改参数为 at-point项目管理上述的lsp配置完之后，它只能使用当前buffer中的内容进行语法补全提示，也就是说我在其他的位置定义的函数和类在当前buffer中是无法识别到的。我们需要结合项目一起来使用。我们可以使用名为 projectile 的插件来进行项目管理(use-package projectile :ensure t :init (setq projectile-project-search-path '("~/projects/" "~/work/" "~/playground")) :config (define-key projectile-mode-map (kbd "C-c C-p") 'projectile-command-map) (global-set-key (kbd "C-c p") 'projectile-command-map) (projectile-mode +1)) (use-package counsel-projectile :ensure t :after(projectile) :init (counsel-projectile-mode))这里我们额外安装了 counsel-projectile 用来与 counsel 结合进行搜索语法检查语法检查方面，目前主流的插件是 flycheck 和 flymake，但是好像 flycheck 使用的人多一些，所以这里我也采用 flycheck。(use-package flycheck :ensure t :config (setq truncate-lines nil) ; 如果单行信息很长会自动换行 :hook (prog-mode . flycheck-mode))这里我们仅在编程的时候开启语法检查。同样的， flycheck 是一个前端，用来显示结果的，具体检查的核心功能是通过后端来实现的。后端的程序可以在官方网站上找到。状态栏显示相关的lsp信息现在是时候来修改以下状态栏的显示了，根据配置vim的经验，我还是希望主要显示当前编辑的模式、文件名、文件编码、lsp服务器、语法错误信息等。这里我使用 doom-modeline 来完成这个功能(use-package doom-modeline :ensure t :init (doom-modeline-mode 1) :config (setq doom-modeline-height 30) (s…

使用CMake跨平台的一些经验
type: item
date: 2025-04-12T09:00:00+08:00
description: 使用CMake构建工程的一个原因是不希望Windows上有一个工程文件，Linux又单独配置一套工程文件。我们希望对于整个工程只配置一便，就可以直接编译运行。CMake本身也具备这样的特性，脚本只用写一次，在其他平台能自动构建工程。这里谈的跨平台主要是如何组织工程和编写CMake来针对Windows和Linux进行一些特殊的处理，在这里说说我常用的几种办法介绍这些方法的前提是有一些代码只能在Windows上跑，例如调用Win32 API或者使用GDI/GDI+，而在Linux上也有一些Windows不支持的代码。我们就需要一些方法来隔离开这两套代码。假设现在有一个项目，它有一套共同的接口对外提供功能，而在Windows上和Linux上各有一份代码来实现这些接口。可以假设有一套图形相关的功能，对外采用统一的接口，具体实现时Windows上使用GDI+，而Linux上使用其他方案来实现。现在整个项目的目录结构如下. ├── include └── platform ├── linux └── windowsinclude 目录用来对外提供接口，是导出的头文件。platform隔离了Windows和Linux上的实现代码。使用宏来控制我们知道Windows和Linux平台有特定编译器定义的宏，根据这些宏是否定义我们可以知道当前是在Linux还是Windows上编译，是需要编译成32位或者64位程序，又或者编译成debug版本或者release版本。例如下面是我用的简单的判断版本的方式#define MY_PLATFORM_WINDOWS 0 #define MY_PLATFORM_LINUX 1 #define MY_PLATFORM_APPLE 2 #define MY_PLATFORM_ANDROID 3 #define MY_PLATFORM_UNIX 4 #define MY_ARCH32 1 #define MY_ARCH64 2 #if defined(_WIN32) || defined(_WIN64) #define MY_PLATFORM MY_PLATFORM_WINDOWS #ifdef _WIN64 #define PLATFORM_NAME "Windows 64-bit" #define MY_ARCH MY_ARCH64 #else #define PLATFORM_NAME "Windows 32-bit" #define MY_ARCH MY_ARCH32 #endif #elif defined(__APPLE__) #include "TargetConditionals.h" #define MY_PLATFORM MY_PLATFORM_APPLE #ifdef ARCHX64 #define MY_ARCH MO_ARCH64 #else #define MY_ARCH MO_ARCH32 #endif #if TARGET_IPHONE_SIMULATOR #define PLATFORM_NAME "iOS Simulator" #elif TARGET_OS_IPHONE #define PLATFORM_NAME "iOS" #elif TARGET_OS_MAC #define PLATFORM_NAME "macOS" #endif #elif defined(__linux__) #define MY_PLATFORM MY_PLATFORM_LINUX #if defined (ARCHX64) || defined (__x86_64__) #define MY_ARCH MY_ARCH64 #else #define MY_ARCH MY_ARCH32 #endif #define PLATFORM_NAME "Linux" #elif defined(__unix__) #ifdef ARCHX64 #define MY_ARCH MY_ARCH64 #else #define MY_ARCH MY_ARCH32 #endif #define PLATFORM_NAME "Unix" #define MY_PLATFORM MY_PLATFORM_UNIX #else #error "Unknown platform" #endif上面代码根据一些常见的编译器宏来决定是什么版本，并且根据不同的版本将MY_PLATFORM 进行赋值。后面只需要使用 MY_PLATFORM 进行版本判断即可。同样的关于架构使用 MY_ARCH 来判断。例如根据架构来定义不同的数据长度#if (MY_PLATFORM == MY_PLATFORM_WINDOWS) typedef __in…

CMake 基础
type: item
date: 2025-04-01T18:02:00+08:00
description: 很遗憾直到现在才开始接触cmake，过去都在微软的vs IDE上编写c++程序，即使引用第三方的库直接使用cmake也能编译成功，很少关注它本身的内容。但是现在我有一项工作的内容就是将在Windows平台上的c++程序移植到Linux平台上。我想选择cmake作为支持跨平台的构建工具。因此提前学了点cmake的基础知识。cmake本身并不能直接编译和链接程序，它是一个构建程序。主要作用就是根据cmake脚本来生成Makefile文件，以供nmake、gun make等工具来生成可执行程序。编译exe简单的hello world使用cmake需要提供一个CMakeLists.txt 的脚本文件，这个名称是固定的，位置一般在项目的根目录。假设现在有一个简单的hello world程序，它的项目目录可能如下v1 ├── CMakeLists.txt ├── main.cpp我们可以使用如下cmake脚本cmake_minimum_required(VERSION 3.15) set(CMAKE_CXX_STANDARD 11) project(test) add_executable(hello ./main.cpp)第一句的含义是指定使用cmake最小的版本为3.15；第二句的含义是使用c++ 11标准第三句的含义是指定项目名称第四句的含义是生成可执行程序的名称为hello，并且指定要编译的源文件是当前目录下的 main.cpp 文件。工程中有多个源文件时，add_executable 后面可以加多个源文件路径一般来说cmake脚本都会包含这么几条语句脚本编写完毕后，需要使用cmake命令进行编译。该命令可以接受一个参数用于指定CMakeLists.txt 文件所在的路径，执行之后会生成一大堆中间文件和对应的Makefile文件。这些都会生成在当前执行cmake命令时所在路径。所以为了便于管理，一般会在适当位置建立一个新的build目录。这个时候整个命令如下mkdir build cd build cmake .. make前面我们在项目根目录下新建一个build目录用于保存中间文件，然后切换到build目录中。接着执行cmake命令并给出对应CMakeLists.txt 所在的路径。执行成功后会在build目录中生成一个Makefile文件，最后就是执行make命令来生成可执行程序这样最简单的一个hello world工程就编译完成了。指定可执行程序的路径生成的可执行文件路径就在当前的build目录下，如果我们要指定可执行程序的路径，可以使用变量 EXECUTABLE_OUTPUT_PATH。它是cmake内置的变量，保存的是可执行程序输出的路径。在cmake中可以使用set来给变量赋值。到此我们的cmake脚本可能是这样的cmake_minimum_required(VERSION 3.15) set(CMAKE_CXX_STANDARD 11) project(test) set(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin) add_executable(hello ./main.cpp)这里涉及到cmake中变量的定义和使用。其实cmake中变量特别简单，cmake中的变量全都是字符串，定义和设置变量值都是用set 操作符。而要取变量的值则使用 ${} 来包住一个变量名。另外cmake使用 EXECUTABLE_OUTPUT_PATH 作为可执行程序的输出路径，这里我们设置输出路径为工程目录下的bin目录下面。这里的 PROJECT_SOURCE_DIR 表示的是当前项目的目录指定头文件所在路径这里我们来一个复杂一点的项目作为演示，这个项目的目录结构如下. ├── include │ └── calc.h └── src ├── add.cpp ├── div.cpp ├── main.cpp ├── mul.cpp └── sub.cpp这种工程中，include目录放头文件，src目录放源文件，calc.h 中定义了4个函数分别实现加减乘除四则运算。它们的实现分别在 add.cpp、sub.cpp、mul.cpp、div.cpp 中，而main.cpp主要负责调用这些函数实现。main.cpp 的代码如下#include <stdio.h> #include "calc.h" int main (int argc, char *argv[]) { int a = 30; int b = 10; printf("a + b = %d\n", add(a, b)); printf("a - b = %d\n", sub(a, b)); printf("a * b = %…

从0开始自制解释器——重构代码
type: item
date: 2023-04-18T13:49:00+08:00
description: 在上一篇文章中，完成了对括号的支持，这样整个程序就可以解析普通的算术表达式了。但是在解析两个括号的过程中发现有大量的地方需要进行索引的回退操作，索引的操作应该保证能得到争取的token，这个步骤应该放在词法分析的阶段，如果在语法分析阶段还要考虑下层词法分析的过程，就显得有些复杂了。而且随着后续支持的符号越来越多，可能又得在大量的地方进行这种索引变更的操作，代码将难以理解和维护。因此这里先停下来进行一次代码的重构。基本架构这里的代码我按照教程里面的结构进行组织。将按照程序的逻辑分为3层，最底层负责操作字符串的索引保证下次获取token的时候索引能在正确的位置。第二层是词法分析部分，负责给字符串的每个部分都打上对应的token。第三个部分是语法分析的部分，它负责解析之前设计的BNF范式，并计算对应的结果。详细的代码上面给出模块划分的概要可能没怎么说清楚，下面将通过代码来进行详细的说明。Token 模块为了支持这个设计，首先变更一下全局变量的定义，现在定义的全局变量如下所示extern Token g_currentToken; //当前token extern int g_nPosition; //当前字符索引的位置 extern char g_currentChar; //当前字符串之前通过 get_next_char() 来返回当前指向的token并变更索引的时候发现我们在任何时候想获取当前指向的字符时永远要变更索引，这样就不得不考虑在某些时候要进行索引的回退。比如在解析整数退出的时候，此时当前字符已经指向下一个字符了，但是我们在接下来解析其他符号的时候调用 get_next_char() 导致索引多增加了一个。这种情况经常出现，因此这里使用全局变量保存当前字符，只在需要进行索引增加的时候进行增加。另外我们不希望上层来直接操作这个索引，因此在最底层的Token模块提供一个名为 advance() 的函数用于将索引加一，并获取之后的字符。它的定义如下void advance() { g_nPosition++; // 如果到达字符串尾部，索引不再增加 if (g_nPosition >= strlen(g_pszUserBuf)) { g_currentChar = '\0'; } else { g_currentChar = g_pszUserBuf[g_nPosition]; } }这样在对应需要用到当前字符的位置就不再使用 get_next_char() , 而是改用全局变量 g_currentChar。例如现在的 skip_whitespace 函数现在的定义如下void skip_whitespace() { while (is_space(g_currentChar)) { advance(); } }这样我们在获取下一个token的时候只在必要的时候进行索引的递增。lex 模块由于打标签的工作交个底层的Token模块了，该模块主要用来实现词法分析的功能，也就是给各个部分打上标签，根据之前Token部分提供的接口，需要对 get_next_token 函数进行修改。bool get_next_token() { dyncstring_reset(&g_currentToken.value); while (g_currentChar != '\0') { if (is_digit(g_currentChar)) { g_currentToken.type = CINT; parser_number(&g_currentToken.value); return true; } else if (is_space(g_currentChar)) { skip_whitespace(); } else { switch (g_currentChar) { case '+': g_currentToken.type = PLUS; dyncstring_catch(&g_currentToken.value, '+'); advance(); break; case '-': g_currentToken.type = MINUS; dyncstring_catch(&g_currentToken.value, '-'); advance(); break; case '*': g_currentToken.type = DIV; dyncstring_catch(&g_currentToken.value, '*'); advance(); break; case '/': g_currentToken.type = MUL; dyncstring_catch(&g_currentToken.value, '/'); ad…

从0开始自制解释器——添加对括号的支持
type: item
date: 2023-03-24T17:50:00+08:00
description: 在上一篇我们添加了对乘除法的支持，也介绍了BNF范式，并且针对当前的算术表达式写出了对应的范式，同时根据范式给出相应的代码实现。这篇我们将继续为算数表达式添加对括号的支持。对应的BNF 范式在上一篇我们给出了乘除法对应的范式<expr>::=<term>{(PLUS|MINUS)<term>} <term>::=<factor>{(DIV|MUL)<factor>} <factor>::={(0|1|2|3|4|5|6|7|8|9)}针对乘除法的优先级比加减法高，我们的做法是将乘除法单独作为一个部分，然后在最外层表达式中只处理加减法。基于这种思路，我们来看如何处理括号的问题。例如下面的算数表达式((1+2)*3+4) - (5 - 6 / 3)这里我们直接给出对应的文法，然后再来分析一下该如何由这个文法得到对应的表达式<expr>::=<term>{(PLUS|MINUS)<term>} <term>::=<factor>{(DIV|MUL)<factor>} <factor>::=({(0|1|2|3|4|5|6|7|8|9|)})|LPAREN<expr>RPAREN首先根据表达式，它应该由两个term来组成 expr = term - term接着看看两个term，它们并不是单纯的加法运算，所以两个term应该只有单纯的一个factor，也就是 expr = factor - factor因为最外层都有括号，所以再次展开 expr = (expr1) - (expr2)这时就又到了分析expr的过程了，左侧的expr最外层是一个加法，所以这里可以得到 expr1 = term + term右侧的expr 最外层是一个减法，也就是 expr2 = term - term结合最外层的表达式可以得到 expr = (term1 + term2) - (term3 - term4)term1 部分有一个乘法，所以它可以解析为 term1 = factor * factorterm2 部分就是单独的数字所以可以得到 term2 = factor，并且进一步得到 term2=4term3 部分就是单纯的数字，可以得到 term3 = factor，并且进一步得到 term3=5term4 部分有一个除法，所以它可以解析为 term3 = factor / factor此时整个表达式可以表示为 expr = (factor1 * factor2 + 4) - (5 - factor3 / factor4)factor1 本身也是一个括号，加表达式，所以它可以表示为 factor1 = (expr)factor2 是一个数字，所以它表示为 factor2 = 3factor3 是一个数字，所以它表示为 factor3 = 6factor4 是一个数字，所以它表示为 factor4 = 3此时表达式可以是 expr = ((expr1) * 3 + 4) - (5 - 6 / 3)此时再次分析这个 expr1 可以得到 expr1 = 1+2这个时候，整个表达式就出来了 expr = ((1+2) * 3 + 4) - (5 - 6 / 3)用图来表示大概可以表示如下代码实现有了范式，我们就可以按照范式来组织代码实现。首先我们先在 ETokenType 中添加针对括号的标签typedef enum e_TokenType { CINT = 0, //整数 PLUS, //加法 MINUS, //减法 DIV, //乘法 MUL, //除法 LPAREN, //左括号 RPAREN, //右括号 END_OF_FILE // 字符串末尾结束符号 }ETokenType;然后在 get_next_token 函数中添加对括号进行词法分析并打标签的功能bool get_next_token(LPTOKEN pToken) { char c = get_next_char(); dyncstring_reset(&pToken->value); if (is_digit(c)) { dyncstring_catch(&pToken->value, c); pToken->type = CINT; parser_number(&pToken->value); } else if(is_space(c)) { skip_whitespace(); return get_next_token(pToken); } else { switch (c) { case '+': pToken->type = PLUS; break; case '-': pToken->type = MINUS; break; case '*': pToken->type =…

从0开始自制解释器——添加对乘除法的支持
type: item
date: 2023-03-22T17:56:00+08:00
description: 在上一篇中，我们实现了对减法的支持，并且介绍了语法图。针对简单的语法进行描述，用语法图描述当然是没问题的。但是针对一些复杂的语法进行描述，如果每个部分都通过语法图来描述就显得有些繁琐了。这篇我们先介绍另一种描述语法的方式，并进一步介绍一些关于语法分析的知识。BNF范式与上下文无关文法巴科斯范式 以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法，用来描述语法的一种形式体系，是一种典型的元语言。又称巴科斯-诺尔形式(Backus-Naur form)。它不仅能严格地表示语法规则，而且所描述的语法是与上下文无关的。它以递归方式描述语言中的各种成分，凡遵守其规则的程序就可保证语法上的正确性。它具有语法简单，表示明确，便于语法分析和编译的特点。BNF表示语法规则的方式为：非终结符用尖括号括起。每条规则的左部是一个非终结符，右部是由非终结符和终结符组成的一个符号串，中间一般以“：：=”分开。具有相同左部的规则可以共用一个左部，各右部之间以直竖“|”隔开。所谓非终结符就是语言中某些抽象的概念不能直接出现在语言中的符号，终结符就是可以直接出现在语言中的符号。其实这些都是一些官话，初看起来只觉得拗口和难以理解，但是它的形式非常简单。它主要是用下面几个符号来表达含义使用<>来表示必须包含的部分使用[]来表示可选部分使用{}来表示可以重复0次或者无数次使用|来表示左右两边任选一部分，相当于OR使用::=来表示被定义为现在来给出具体的例子，我们都看过《西游记》，里面的取经4人组包括唐僧、孙悟空、猪八戒和沙僧。使用BNF范式进行定义，可以写成 <取经团队>::=<唐僧><孙悟空><猪八戒><沙僧>。我们再来举一个例子，我们知道一个文章由若干个段落组成、一个段落由若干个句子组成、一个句子由符合一定语法规则的汉字组成并且以句号作为结尾。我们简单的将句子的语法规则定义为主谓宾三个部分。而这里的主谓宾我们简单的用一些名词和动词来定义。因此这里的一系列结构可以定义为如下内容<文章>::={<段落>}<段落>::={<句子>}<句子>::=<主语><谓语><宾语>。<主语>::=人|狗|猫|天<谓语>::=吃|抓|下<宾语>::=饭|雨|肉|鱼根据这个表达式我们很容易的推出类似 人吃饭。、天下雨。、猫抓鱼。 这样的句子。相信到这里小伙伴应该明白BNF范式的一些基本概念和使用方式了。我们再来插入一个题外话，既然这里提到BNF范式是一种上下文无关文法，那什么是上下文、什么是上下文无关。先别着急了解概念，我们仍然通过例子来说明。在上述的句子的定义中，我们一共可以生成 4 * 3 * 4 = 48 种 结果，我们可以获得类似 人吃饭。、猫抓鱼。这种有意义的句子，也可能产生像天吃鱼。、人下雨 这种读起来感觉别扭的非正常语句。但是在上下文无关的语法中，主语宾语和谓语的内容没有相互关联，也就是说谓语和宾语的产生与主语无关。那上下文有关的文法呢？这里为了产生一些有意义的句子，我们给它加上一些限定。例如人后面只能接 吃 抓作为谓语、而当吃作为谓语时只能将 饭、肉、鱼作为宾语。针对这种需求，我们可以进行如下定义<句子>::=<主语><谓语><宾语>。<主语>::=人|狗|猫|天人<谓语>::=人(吃|抓)吃<宾语>::=吃(饭｜肉|鱼)这样我们对这个产生式进行了一些限定，当主语是人的时候，谓语只能产生吃和抓这样的宾语。这种情况下的描述就被称之为上下文有关。上下文无关我自己的理解就是后续表达式的产生不依赖前面已产生的内容。而上下文有关的含义则与之相法。这个上下文就跟我们这么多年阅读理解题里面写的“请根据上下文来理解某个词表达了作者怎样的心情”这里的上下文类似。当然更加规范的说法就是，在应用一个产生式进行推导时，前后已经推导出的部分结果就是上下文。上下文无关就是只要文法的定义里面有一个定义，不管前面的产生串是什么都可以应用相应的产生推导后面的内容。代码编写上面的定义只是开胃菜，希望通过上面的描述，小伙伴能够理解BNF范式的应用，至于上下文无关和上下文有关。这些暂时不用考虑，毕竟我们目前还是在做上下文无关文法相关的内容。这里我们要支持乘法和除法，首先要做的就是在 ETokenType 结构中添加对乘法和除法相关的定义typedef enum e_TokenType { CINT = 0, //整数 PLUS, //加法 MINUS, //减法 DIV, //乘法 MUL, //除法 END_OF_FILE // 字符串末尾结束符号 }ETokenType;接着在 get_next_token和 get_oper() 函数中添加对这两个运算符的支持// get_next_token else if (c == '*') { pToken->type …

从0开始自制解释器——实现多位整数的加减法计算器
type: item
date: 2023-03-08T16:53:00+08:00
description: 上一篇我们实现了一个简单的加法计算器，并且了解了基本的词法分析、词法分析器的概念。本篇我们将要对之前实现的加法计算器进行扩展，我们为它添加以下几个功能计算减法能自动识别并跳过空白字符不再局限于单个整数，而是能计算多位整数提供一些工具函数首先为了支持减法，我们需要重新定义一下TokenType这个类型，也就是需要给 - 定义一个标志。现在我们的TokenType的定义如下typedef enum e_TokenType { CINT = 0, PLUS, MINUS, END_OF_FILE }ETokenType;由于需要支持多个整数，所以我们也不知道最终会有多少个字符，因此我们提供一个END_OF_FILE 表示我们访问到了最后一个字符，此时应该退出词法分析的过程。另外因为整数个数不再确定，我们也就不能按照之前的提供一个固定大小的数组。虽然可以提供一个足够大的空间来作为存储数字的缓冲，但是数字少了会浪费空间。而且考虑到之后要支持自定义变量和函数，采用固定长度缓冲的方式就很难找到合适的大小，太大显得浪费空间，太小有时候无法容纳得下用户定义的变量和函数名。因此这里我们采用动态长度的字符缓冲来保存。我们提供一个DyncString 的结构来保存这些内容#define DEFAULT_BUFFER_SIZE 16 // 动态字符串结构，用于保存任意长度的字符串 typedef struct DyncString { int nLength; // 字符长度 int capacity; //实际分配的空间大小 char* pszBuf; //保存字符串的缓冲 }DyncString, *LPDyncString; // 动态字符串初始化 // str: 被初始化的字符串 // size: 初始化字符串缓冲的大小，如果给0则按照默认大小分配空间 void dyncstring_init(LPDyncString str, int size); // 动态字符串空间释放 void dyncstring_free(LPDyncString str); //重分配动态字符串大小 void dyncstring_resize(LPDyncString str, int newSize); //往动态字符串中添加字符 void dyncstring_catch(LPDyncString str, char c); // 重置动态数组 void dyncstring_reset(LPDyncString str);它们的实现如下/*----------------------------动态数组的操作函数-------------------------------*/ void dyncstring_init(LPDyncString str, int size) { if (NULL == str) return; if (size == 0) str->capacity = DEFAULT_BUFFER_SIZE; else str->capacity = size; str->nLength = 0; str->pszBuf = (char*)malloc(sizeof(char) * str->capacity); if (NULL == str->pszBuf) { error("分配内存失败\n"); } memset(str->pszBuf, 0x00, sizeof(char) * str->capacity); } void dyncstring_free(LPDyncString str) { if (NULL == str) return; str->capacity = 0; str->nLength = 0; if (str->pszBuf == NULL) return; free(str->pszBuf); } void dyncstring_resize(LPDyncString str, int newSize) { int size = str->capacity; for (; size < newSize; size = size * 2); char* pszStr = (char*)realloc(str->pszBuf, size); str->capacity = size; str->pszBuf = pszStr; } void dyncstring_catch(LPDyncString str, char c) { if (str->capacity == str->nLength + 1) { dyncstring_resize(str, str->capacity + 1); } str-…