Posted Updated 35 minutes read (About 5250 words)

Clang static analyzer Checker 初探

这里只是我刚开始学习静态分析时的一些粗浅的理解和经验之谈，以及相关资料整理，并不能确保正确，还请多多补充指正

1. 关于 Clang static analyzer

这是 naive systems 的一个静态分析工具： https://www.naivesystems.com/ 其中一些对于 MISRA C 的检查器就是基于 Clang static analyzer 构建的。

1.1. Clang static analyzer

Clang 是 LLVM 的一个“前端”，意思是底层依赖于 LLVM 架构。Xcode 使用 Clang 。

LLVM 不是一个缩写，它是一个工具集，用于构建编译器、优化器、运行时环境。Clang 只是在其基础上建立的 C语系（C/C++/Objective C）编译器，该计划最初设想提供一种基于SSA编译策略的，支持任意编程语言的静态和动态编译，现今该计划已经发展出多个模块化的子项目，成为编译器和相关工具链的合集。

Clang Static Analyzer 是 Clang 项目的一部分，在 Clang 基础上构建，静态分析引擎被实现为可重用的C++库，可以在多种环境下使用（Xcode、命令行、接口调用等）。静态分析会自动检查源代码中的隐含bug，并产生编译器警告。随着静态分析技术的发展，其已经从简单的语法检查，步进到深层的代码语义分析。要注意到，由于使用最新的技术深入分析代码，因此静态分析可能比编译慢得多（即使启用编译优化），查找错误所需的某些算法在最坏的情况下需要指数时间。静态分析还可能会存在假阳性问题（False Positives）。如果需要更多 Checker 来让静态分析引擎执行特定检查，需要在源码中实现

1.2. How it works

静态分析最初由一些基础研究论文启发。

简而言之，分析器是一个源码的模拟器，追踪其可能的执行路径。程序状态（变量和表达式的值）被封装为 ProgramState 。程序中的位置被叫做 ProgramPoint 。state 和 program point 的组合是 ExplodedGraph 中的节点。术语“exploded”来自控制流图（control-flow graph，CFG）中爆炸式增长的控制流连边。

概念上讲，分析器会沿着 ExplodedGraph 执行可达性分析（reachability analysis）。从具有 entry program point 和 initial state 的根节点开始，分析模拟每个单独表达式的转移。表达式分析会产生状态改变，使用更新后的 program point 和 state 创建新节点。当满足某些 bug 条件时（违反检测不变量，checking invariant），就认为发现了 bug 。

分析器通过推理分支（branches）追踪多条路径（paths），分叉状态：在 true 分支上认为分支条件为 true，在 false 分支上认为分支条件为 false 。这种“假设”创建了程序中的值的约束（constraints），这些约束被记录在 ProgramState 对象（通过 ConstraintManager 修改）。如果假设分支条件会导致不能满足约束，这条分支就被认为不可行，路径也不会被选取。这就是我们实现路径敏感（path-sensitivity）的方式。我们降低了缓存节点的指数爆炸。如果和已存在节点含相同 state 和 program point 的新节点将被生成，路径会“出缓存”（caches out），我们只简单重用已有节点。因此 ExplodedGraph 不是有向无环图（DAG），它可以包含圈（cycles），当路径相互循环，以及出缓存。

ProgramState 和 ExploledNodes 在创建后基本上是不可变的。当产生新状态时，需要创建一个新的 ProgramState 。这种不变性是必要的，因为 ExplodedGraph 表示了从入口点开始分析的程序的行为。为了高效表达，我们使用了函数式数据结构（比如 ImmutableMaps ）在实例间共享数据。

最终，每个单独检查器（Checkers）也通过操作分析状态来工作。分析引擎通过访问者接口（visitor interface）与之沟通。比如，PreVisitCallExpr() 方法被 GRExprEngine 调用，来告诉 Checker 我们将要分析一个 CallExpr ，然后这个检查器被请求检查任意前置条件，这些条件可能不会被满足。检查器不会做除此之外的任何事情：生成一个新的 ProgramState 和包含更新后的检查器状态的 ExplodedNode 。如果它发现了一个 bug ，它会把错误告诉 BugReporter 对象，提供引发该问题的路径上的最后一个 ExplodedNode 节点。

2. 如何添加一个最简单的 Checker

以一个最简单的 checker ，禁用 malloc 为例:

2.1. Hello World

在 clang/lib/StaticAnalyzer/Checkers/ ，新建 MyChecker.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"

using namespace clang;
using namespace ento;

namespace {
class MyChecker : public Checker< check::PreCall > {
  mutable std::unique_ptr<BuiltinBug> BT;
  void reportBug(const char *Msg, const CallEvent &Call, CheckerContext &C) const;

public:
  // process malloc(0)
  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
};
} // end anonymous namespace

void MyChecker::reportBug(const char *Msg, const CallEvent &Call, ProgramStateRef StateZero, CheckerContext &C) const 
{
  if (ExplodedNode *N = C.generateErrorNode(StateZero)) {
    if (!BT)
      BT.reset(new BuiltinBug(this, "call to malloc"));

    auto R = std::make_unique<PathSensitiveBugReport>(*BT, Msg, N);
    R->addRange(Call.getSourceRange());
    C.emitReport(std::move(R));
  }
}

void MyChecker::checkPreCall(const CallEvent &Call, CheckerContext &C) const 
{
  if (!Call.isGlobalCFunction("malloc"))
    return;

    reportBug("V: Allocation of zero bytes", Call, C);    
    return;
}

void ento::registerMyChecker(CheckerManager &mgr) {
  mgr.registerChecker<MyChecker>();
}

bool ento::shouldRegisterMyChecker(const CheckerManager &mgr) {
  return true;
}

2.2. 注册编译

在 clang/include/clang/StaticAnalyzer/Checkers/Checkers.td 文件中，把新建的 MyChecker 放入待注册列表:

1
2
3
4
5
6
7
let ParentPackage = Core in {
// ...
def MyChecker : Checker<"MyChecker">,
  HelpText<"Check for zero malloc">,
  Documentation<HasDocumentation>;
// ...
} // end "core"

之后，需要把 MyChecker.cpp 添加进 clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt 检查器构建列表。

1
2
3
4
add_clang_library(clangStaticAnalyzerCheckers
  MyChecker.cpp
  ...
  )

3. 教程：进行不同类型的检查

举几个例子：

（TODO: 待完善）

3.1. PointerSubChecker.cpp

检查程序某个特定的节点中，两个指针是否指向了同一个内存区域：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

using namespace clang;
using namespace ento;

namespace {
class PointerSubChecker
  : public Checker< check::PreStmt<BinaryOperator> > {
  mutable std::unique_ptr<BuiltinBug> BT;

public:
  void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
};
}

void PointerSubChecker::checkPreStmt(const BinaryOperator *B,
                                     CheckerContext &C) const {
  // When doing pointer subtraction, if the two pointers do not point to the
  // same memory chunk, emit a warning.
  if (B->getOpcode() != BO_Sub)
    return;

  SVal LV = C.getSVal(B->getLHS());
  SVal RV = C.getSVal(B->getRHS());

  const MemRegion *LR = LV.getAsRegion();
  const MemRegion *RR = RV.getAsRegion();

  if (!(LR && RR))
    return;

  const MemRegion *BaseLR = LR->getBaseRegion();
  const MemRegion *BaseRR = RR->getBaseRegion();

  if (BaseLR == BaseRR)
    return;

  // Allow arithmetic on different symbolic regions.
  if (isa<SymbolicRegion>(BaseLR) || isa<SymbolicRegion>(BaseRR))
    return;

  if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
    if (!BT)
      BT.reset(
          new BuiltinBug(this, "Pointer subtraction",
                         "Subtraction of two pointers that do not point to "
                         "the same memory chunk may cause incorrect result."));
    auto R =
        std::make_unique<PathSensitiveBugReport>(*BT, BT->getDescription(), N);
    R->addRange(B->getSourceRange());
    C.emitReport(std::move(R));
  }
}

void ento::registerPointerSubChecker(CheckerManager &mgr) {
  mgr.registerChecker<PointerSubChecker>();
}

bool ento::shouldRegisterPointerSubChecker(const CheckerManager &mgr) {
  return true;
}

（TODO: 待完善）

3.2. SimpleStreamChecker.cpp

跟踪状态传递：[SimpleStreamChecker.cpp]https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/SimpleStreamChecker.cpp)

Defines a checker for proper use of fopen/fclose APIs.

  • If a file has been closed with fclose, it should not be accessed again.
    Accessing a closed file results in undefined behavior.
  • If a file was opened with fopen, it must be closed with fclose before
    the execution ends. Failing to do so results in a resource leak.

（TODO: 待完善）

3.3. Taint.cpp

Defines basic, non-domain-specific mechanisms for tracking tainted values.

https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/Taint.cpp

（TODO: 待完善）

3.4. 其他一些常用的检查实现

https://b.corp.naive.systems:9443/projects/misra-c-2012/wiki/一些简单的可供参考的代码片段

4. 如何写一个更好的检查器

部分翻译和整理自 https://clang-analyzer.llvm.org/checker_dev_manual.html：Making Your Checker Better，也有一部分是经验总结。这部分值得好好阅读，我们在这上面栽过不少坑

4.0.1. 良好的编码习惯

  • 警告和注意信息应该清晰易懂，即使有点长。
    • 消息应以大写字母开头（与 Clang 警告不同！）且不应以 .. 结尾
    • 引入 BugReporterVisitor 以发出额外的注释，更好地向用户解释警告。有一些现有的访问者可能对您的检查有用，例如 trackNullOrUndefValue 。例如， SimpleStreamChecker 应该在报告文件描述符泄漏时突出显示打开文件的事件。
  • 如果 checker 跟踪程序状态中的任何内容，则需要实现 checkDeadSymbols回调来清理状态。
  • 当跟踪的未知符号被传递给 checker 时，检查应该保守地假设程序是正确的。 checkPointerEscape 回调可以帮助您处理这种情况。
  • 使用安全便捷的 API！
    • 始终使用 CheckerContext::generateErrorNode 和 CheckerContext::generateNonFatalErrorNode 来发出错误报告。最重要的是，永远不要针对 CheckerContext::getPredecessor 发出报告。
    • Prefer checkPreCall and checkPostCall to checkPreStmt<CallExpr> and checkPostStmt<CallExpr>.
    • 使用 CallDescription 检测程序中的硬编码 API 调用。
    • 将 C.getState ()->getSVal(E, C.getLocationContext()) 简化为 C.getSVal(E)。

4.0.2. 常见的崩溃来源

  • CallEvent::getOriginExpr 可以为空 - 例如，它为变量的自动析构函数返回 null。这同样适用于模拟调用时生成的一些值，例如， SymbolConjured::getStmt 可以为空。
  • CallEvent::getDecl 可以为空 - 例如，它为调用符号函数指针返回 null。
  • addTransition generateSink generateNonFatalErrorNode generateErrorNode 可以为空，因为您可以转换到您已经访问过的节点。
  • 当参数越界时，返回参数的 CallExpr/FunctionDecl/CallEvent 方法会崩溃。如果您检查了函数名称，这并不意味着该函数具有预期的参数数量！这就是您应该使用CallDescription的原因。
  • 不同种类的符号和区域中不同实体的可空性通常通过其构造函数中的断言来记录。
  • 如果声明的名称不是单个标记，例如对于析构函数，NamedDecl::getName 将失败。对于这些情况，您可以使用 NamedDecl::getNameAsString 。请注意，此方法要慢得多，应谨慎使用，例如仅在生成报告时而不是在分析期间使用。
  • -analyzer -checker=core 是否包含在所有测试RUN:行中？从未支持在禁用核心检查的情况下运行分析器。它可能会导致意外行为和崩溃。您应该在启用核心检查的情况下进行所有测试。

除了上述 CSA 中常见的 崩溃可能性，还应当注意 llvm 中的类型转换和空指针检查。

4.0.3. 即使在技术上没有错误，您也应该避免的模式

  • BugReporterVisitor 很可能与当前程序点的 AST 不匹配，以决定何时发出注释。通过观察 program state 的变化来确定这一点要容易得多。
  • 在 State->getSVal(Region) 中，如果 Region 不是 TypedValueRegion 并且未指定可选类型参数，则检查器可能会意外尝试取消引用 void 指针。
  • 检查器逻辑不应依赖于某个值是 Loc 还是 NonLoc 。根据正在检查的 AST， SVal 是 Loc 还是 NonLoc 应该立即显而易见。检查一个值是 Loc 还是 Unknown/Undefined 或者该值是 NonLoc 还是 Unknown/Undefined 完全没问题。
  • 不应通过直接调用 SymbolManager 在检查器中构造新符号，除非它们属于检查器标记的 SymbolMetadata 类，或者它们代表新创建的值，例如 evalCall 中的返回值。对于模拟算术/按位/比较操作，应使用 SValBuilder 。
  • 不应在检查器中创建自定义 ProgramPointTag 。检查器通常没有充分的理由将多个节点链接在一起，因为检查器不是 worklists 算法。
  • 鼓励检查者通过与分析器的其余部分分享他们关于程序状态的知识来积极参与分析，但他们不应不必要地破坏分析：
  • 如果检查器拆分程序状态，这必须基于新出现的分支绝对是可能的并且值得从用户的角度探索的知识。否则，状态拆分应该延迟，直到有迹象表明采取了其中一条路径，或者需要完全删除其中一条路径。例如，只要x在每条路径上受到相应的约束，就可以在建模isalpha(x)时急切地分割路径。同时，在为调用建模时，在printf()的返回值上分割路径并不是一个好主意，因为没有人检查printf中的错误；充其量，它只会使剩余的分析时间增加一倍。
  • 使用 CheckerContext::generateNonFatalErrorNode 时建议小心， 因为它会生成一个独立的转换，很像 addTransition 。使用时很容易意外拆分路径。理想情况下，尝试对代码进行结构化，以便每个 addTransition 或 generateNonFatalErrorNode （或如果要拆分的情况下的序列）之后立即从检查器回调返回。
  • 不同检查器中 evalCall 的多个实现不应冲突。
  • 实现 evalAssume 时，检查器应始终为真假设或假假设（或两者）返回非空状态。
  • 检查器不得改变表达式的值，即使用 ProgramState::BindExpr API，除非它们完全负责计算值。在任何情况下，他们都不应更改表达式的非未知值。目前，此 API 在检查器中的唯一有效用例是在 evalCall 回调中对返回值进行建模。如果表达式值不正确，则需要修复 ExprEngine 。

5. 有哪些资料可以进一步参考？

5.1. llvm 官方文档和论坛

一切以官方文档为准。

5.2. 代码

这一部分是在 llvm-project 代码库中可见的一些参考资料：

  • README

    一个简要介绍 CSA 的 README 文件，包含了库结构，工作原理等。

  • documentation

    This checker lists all the checker callbacks and provides documentation for checker writers. 提供了所有的回调钩子的文档。

5.3. 论文/主要文档

5.4. 博客

5.4.1. 某个 clang static analyzer 源码分析博客：dashuniuniu

这一部分主要是关于 clang static analyzer 的工作原理分析，虽然稍微有点老旧（约2017年），不过应该大体上还是没有太多变化的；相关系列从源码入手详细分析了 clang static analyzer 的一些基本概念和工作模式，值得一看。

同一个人在知乎上也有相关文章，讨论 CSA 相关内存模型：

其他部分还可以自行访问其 csdn 和 zhihu 账号。

5.4.2. 知乎：VVKoishi

这一系列文章关注于实现一个简单的 memory.ZeroAlloc Checker，让 Analyzer 引擎提供自定义的静态检查支持；并且也涉及到了一些简单的代码分析，如果你是在 MacOS 下工作的话，这是一个很好的入门文档，写于 2021 年。

Part 1 介绍 Clang Static Analyzer ，以及源码构建 Clang 。

Part 2 关注引擎底层实现，包含 Checker 相关源码解读，举例 DivZeroChecker 。

Part 3 关注如何添加一个 Checker 。

5.4.3. 其他

关于 Live Variables analysis 的源码分析：

Posted Updated 11 minutes read (About 1635 words)

用 rust 实现可持久化 AVL 树：ImmutableMap

这几篇想简单谈谈一下自己在写代码时遇见的，或者阅读 llvm 相关代码时见到的数据结构实现。

本文源代码：https://github.com/yunwei37/immutable-map-rs

关于 ImmutableMap

ImmutableMap 是一种可持久化数据结构，在进行插入或删除操作时并不对原先的数据结构进行改动，而是创建一个新的拷贝。关于可持久化数据结构，可以参考维基百科[1]：Persistent_data_structure

这里参考的是 llvm 中的 ImmutableMap/ImmutableSet 实现，采用一个平衡因子为 2 的 AVL 树[2]:

Read more
Posted Updated 12 minutes read (About 1792 words)

llvm 源码中的数据结构：ImmutableList

这几篇想简单谈谈一下自己在写代码时遇见的，或者阅读 llvm 相关代码时见到的数据结构实现。

关于 ImmutableList

ImmutableList 顾名思义，即不可变链表。它是一种可持久化数据结构，在进行插入或删除操作时并不对原先的数据结构进行改动，而是创建一个新的拷贝。关于可持久化数据结构，可以参考维基百科：Persistent_data_structure

在计算中，持久数据结构或非临时数据结构是一种在修改时始终保留其先前版本的数据结构。这样的数据结构实际上是不可变的，因为它们的操作不会（明显地）就地更新结构，而是总是产生一个新的更新结构。该术语是在 Driscoll、Sarnak、Sleator 和 Tarjans 1986 年的文章中引入的。[1]这些类型的数据结构在逻辑和函数式编程中特别常见，[2]因为这些范式中的语言不鼓励（或完全禁止）使用可变数据。

Read more
Posted Updated 2 minutes read (About 316 words)

2022 一个新的开始

一点没啥意义的话

去年因为某些原因站点挂了，也没来得及备份…（好像是我躺在医院的床上晕晕乎乎的那段时间？）虽然大多数文章都散落在各个仓库或者网站上存着，倒也没损失什么。

无论如何，2022年都算是一个全新的开始吧。虽然日常已经是摆的不能再摆了，但总归还是有很多想要去追寻的东西。既然旧的事情离开的了无痕迹，那也没有更多需要回首的意义了。

但行好事，莫问前程。

Read more
Posted Updated 8 minutes read (About 1198 words)

c++20 协程与 io_uring 初探：一个最简单的 echo server

写这篇的初衷是想动手实践一下 io_uring 和 c++20 协程。

这个版本的代码由 github.com/frevib/io_uring-echo-server 改造而来，是希望通过在 io_uring 的基础上，尝试实现最基本的协程 IO 模式，然后进行性能对比。之前的版本使用了一个 event loop 的模式，并通过 io_uring 的 IORING_OP_PROVIDE_BUFFERS 参数和 IORING_FEAT_FAST_POLL 参数，实现了零拷贝和内核线程的 polling，不需要额外的系统调用开销。

本文在 io_uring-echo-server 的基础上增添了一个简易的协程实现，完整的 demo 代码实现在这里：github.com/yunwei37/co-uring-WebServer/blob/master/demo/io_uring_coroutine_echo_server.cpp

Read more
Posted Updated 9 minutes read (About 1297 words)

c语言手搓一个500+行的类c语言解释器（1）- 目标和前言

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程（1）- 目标和前言

项目github地址及源码：
https://github.com/yunwei37/tryC

一个小目标

这一系列教程希望面向初学者，使用c语言手工实现一个简单的解释器来玩，不需要您掌握除了c语言以外的其他前置知识，也不需要您学习过编译原理的相关知识（当然如果能对简单的数据结构有所了解的话会更好，比如树、栈等）。

写一个能执行代码的解释器不仅是一件很有（zhuang）趣（bi）的事情，大概也可以作为刚学习完c语言的一个练手的小项目啦

不同于大部分常见的其他只支持四则运算的所谓”手工解释器“教程，我们希望在代码结构尽量清晰的600行代码中，手工（不借助lex/yacc等工具）完成一个脚本语言“try”，实现以下功能：

  • 选择和循环的流程控制语句
  • 支持的数据类型：双精度浮点数、字符型、字符串、浮点数数组
  • 支持函数和变量的定义、函数的递归调用、嵌套作用域

（如果看不懂下面这段也没关系，可以略过啦）

这个小玩意采用递归下降法进行语法分析，同时不显式构建语法树，不生成中间代码或目标代码，在语法分析的同时进行解释执行；

解释器可运行的代码示例

递归计算文波那契数列 1 - 15，将结果存入数组中，并打印：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Fibonacci sequence
func fun{ 
	if(x <= 2){  
		return(1);  
	}
	y = 0;
	x = x - 1;
	y = fun(x);
	x = x - 1;
	return(y + fun(x));
};

# save the Fibonacci sequence of 1 to 15 in an array 
array arr(15);	
x = 1;
while( x <= 15 ){
	arr[x - 1] = fun(x);
	x = x + 1;
}

puts("Fibonacci sequence:");
# print the Fibonacci sequence of 1 to 15
i = 0;
while(i < 15){			
	print(arr[i]);
	i=i+1;
}

（起名困难x）这个小玩意我们就随便叫它tryC吧，当做是一个小的尝试。

本人水平有限，如有疏漏之处，还请多多指教。

部分语言规则：

  • 注释在一行内，以‘#’开头；

  • 语句以‘;’结尾

  • 赋值语句类型：

    1
    2
    3
    x = 123.4;
    x = 'c';
    x = "hello world!";

  • 循环语句：

    1
    2
    3
    while( bool ){
     statements
    }

  • 选择语句：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    if( bool ){
     statements
    }

    if( bool ){
     statements
    }else{
        statements
    }

  • 定义函数：函数参数在定义中不出现，在调用中获取；返回值为double

    1
    2
    3
    4
    5
    func function_name{
        ...
        return(expression);
    }

  • 定义数组：

    1
    2
    array array_name(array_length);

  • 输入输出：

    1
    2
    3
    puts(string);
    print(num);
    read(num);

写在前面

关于写这玩意的缘由（写的很乱可以不看系列）

之前大一学c语言的时候，老师要求实现一个四则运算的计算器，于是我想…要是能给计算器加上函数和变量的定义就好啦…那大概能算一个简单的解释器？我应该怎样去实现它呢？就去查了不少资料七拼八凑加上自己脑补搓了一个出来…虽然能跑起来但是代码混乱不堪一塌糊涂，不过也挺好玩的。

这里的部分是过了一年之后大二学编译原理的时候，把当时的代码用相对比较规范完善的方式重写了一遍，也因此希望把它整理成一个简单的教程，让c语言的初学者也可以愉快地搓一个解释器玩；或者让学过编译原理的同学，能够把理论和实践联系起来，（不要像我一样被一大堆的理论迷惑住或吓跑），对于如何构造一个解释器有个直观感性的认识，并且发现它并不像想象的那么困难。

需要了解的前置知识

  • c语言的指针、函数指针、结构体等
  • 递归的思想

心理准备

  • 写一个600行的解释器虽然不算什么大工程，但相关的原理还是稍微有些复杂的，可能需要多花一些时间理解程序的运行过程；

  • 代码可能难以调试，尤其在没有生成中间代码的情况下；

参考资料

Posted Updated 11 minutes read (About 1603 words)

c语言手搓一个500+行的类c语言解释器（2）- 简介和设计

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程（2）- 简介和设计

项目github地址及源码：
https://github.com/yunwei37/tryC

需要了解的一些基本概念

编译器和解释器的区别不同

通常我们说的 “编译器” 是一种计算机程序，负责把一种编程语言编写的源码转换成另外一种计算机代码，后者往往是以二进制的形式被称为目标代码(object code)。这个转换的过程通常的目的是生成可执行的程序。

而解释器是一种计算机程序，它直接执行由编程语言或脚本语言编写的代码，它并不会把源代码预编译成机器码，而是一行一行地分析源代码并且直接执行，相对编译器而言可能效率较为低下，但实现也相对简单，并且容易在不同的机器上进行移植（比如x86和mips指令集的机器）。

先来看看通常的编译器是如何实现的：

编译器从源码翻译为目标代码大致需要这样几个步骤，每个步骤都依赖于上一个步骤的结果：

  1. 词法分析：

    编译器对源程序进行阅读，并将字符序列，也就是源代码中一个个符号收集到称作记号（token）的单元中；比如:

    1
    num = 123.4;

    这样个赋值语句中，变量num算是一个token，“=”符号算是一个token，“123.4”算是一个token；每个token有自己的类别和属性，比如“123.4”的类别是数字，属性（值）是123.4

  2. 语法分析：

    语法分析指将词法分析得到的标记流（token）进行分析，组成事先定义好的有意义的语句，这与自然语言中句子的语法分析类似。通常可以用抽象语法树表示语法分析的结果，比如赋值语句：

    1
    num = 123.4 * 3;

    可以用这样一个抽象语法树来表示:

    1
    2
    3
    4
    5
    graph TD
    = --> num
    = --> *
    * --> 123.4
    * --> 3

  3. 语义分析：
    程序的语义就是它的“意思”，程序的语义确定程序的运行方式。语义分析阶段通常包括声明和类型检查、计算需要的一些属性值等等。编译器在这个阶段中通常会维护一个叫做“符号表”的东西，保存变量的值、属性和名称。同样以

    1
    num = 123.4 * 3;

    为例，假如我们是第一次在这里遇见“num”，就将num的名称字符串“num” 和当前计算出来的初始值370.2插入符号表中，当下次再遇见num时。我们就知道它是一个数字，已经初始化完毕，并且当前值是370.2；

  4. 目标代码生成：
    在语义分析之后，我们就可以将语法分析和语义分析的结果（通常是抽象语法树）转换成可执行的目标代码。

解释器与编译器仅在代码生成阶段有区别，而在前三个阶段如词法分析、语法分析、语义分析基本是一样的。

当然，已经有许多工具可以帮助我们处理阶段1和2，如 flex 用于词法分析，bison 用于语法分析；但它们的功能都过于强大，屏蔽了许多实现上的细节，对于学习构建编译器帮助不大，所以我们要完全手写这些功能。

（实际上完成一个可以跑起来的解释器并不难，而且还是一件很有成就感的事，不是嘛？）

tryC编译器的设计：

从上面可以看出，我们的tryC解释器需要这三个模块：

  1. 词法分析
  2. 语法分析
  3. 语义分析和解释执行

需要这两个数据结构（用来在阶段之间保存或传递值）：

  1. token，用来在词法分析和语法分析之间传递标记；
  2. 符号表，保存语义分析阶段遇见的变量值，使用一个数组存储；

在了解过这些之后，我们先来大概看看代码的基本结构：

（从上往下在代码中依次对应，“…”表示省略的相关代码，在后续文章中会详细讲解）

  • 数据结构的声明部分：token类型、符号表结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
...

typedef struct symStruct {  
    int type;                
    char name[MAXNAMESIZE];    
    double value;             
    ..........
} symbol;
symbol symtab[SYMTABSIZE];          // 符号表
int symPointer = 0;             

char* src, * old_src;               // 当前分析的源代码位置指针

// tokens 的枚举类型
enum {
    Num = 128, Char, Str, Array, Func,
    ........
};

// token 的表示形式
int token;                      // current token type
union tokenValue {
    symbol* ptr;               
    double val;                 
} token_val;

  • 词法分析的两个函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 获取输入流中的下一个记号：
void next() {
    char* last_pos;

    while (token = *src) {
        ++src;
        if(token == AAA ){
            .....
        }else if(token == BBB ){
            .....
        }
    }
}

// 匹配一个记号，并获取下一个token：
void match(int tk) {
    if (token == tk) {
        next();
    }
    else {          // 遇到了一个错误
        exit(-1);
    }
}

  • 语法分析和语义分析，以及执行阶段：使用递归下降法实现（后面会再提到什么是递归下降法啦）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 计算表达式的值：
double expression(){}
double factor(){}
double term(){}

// 计算布尔表达式的值：
int boolOR();
int boolAND();
int boolexp();

// 执行一个语句；
double statement();

// 执行一个函数：
double function();

  • main() 函数，代码的入口，并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int main(int argc, char** argv)
{   
    // 往符号表里面添加关键词
    int i, fd;
    src = "array func else if return while print puts read";
    for (i = Array; i <= Read; ++i) {
        next();
        symtab[symPointer -1].type = i;
    }

    src = old_src = (char*)malloc(POOLSIZE); // 分配空间

    ....

    fd = open(*argv, 0);        // 打开读取文件

    read(fd, src, POOLSIZE - 1);

    src[i] = 0; 
    close(fd);
    next();
    while (token != 0) {        // 一条一条语句执行
        statement();
    }
    return 0;
}

重要概念

  • 编译器/解释器
  • 词法分析
  • 语法分析
  • 语义分析
  • token
  • 符号表

可参照github源码查看（如果觉得写得还行麻烦您帮我点个star哦）
https://github.com/yunwei37/tryC

Posted Updated 7 minutes read (About 1029 words)

c语言手搓一个500+行的类c语言解释器（5）- 语法分析2 tryC的语法分析实现

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程（5）- 语法分析2: tryC的语法分析实现

项目github地址及源码：
https://github.com/yunwei37/tryC

tryC的语法分析

完整的tryC文法：

(这里我们用单引号包裹那些在BCNF文法定义中出现但又作为终结符出现的字符)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
exp -> term { addop term }
term -> factor { mulop factor }
factor -> number | ( exp ) | Sym | array_name '[' exp ']' | function        // 处理数组单元、函数、变量等
addop -> + | -
mulop -> * | /

boolOR = boolAND { '||' boolAND }
boolAND = boolexp { '||' boolexp }
boolexp -> exp boolop exp | ( boolOR ) | !boolexp
boolop -> > | < | >= | <= | ==

statement -> '{' { statement } '}'                                  |       // 语句块
            if-stmt -> if ( exp ) statement [ else statement ]      |       // 选择语句
            while-stmt -> while ( exp ) statement                   |       // 循环语句
            Sym = exp;                                               |       // 赋值语句
            print ( exp );                                           |       // 输入输出语句
            puts ( Str );                                            |
            read ( Sym );                                            |
            return ( exp );                                          |       // 函数的返回语句
            func func_name statement;                                |       // 函数定义    
            array array_name length;                                 |       // 数组定义

statement的代码实现

布尔表达式和算术表达式的代码之前已经讲过了，这里看看statement的实现，以及如何在语法分析的同时解释执行：

这里使用的方法是，对于流程控制语句，在语法分析的时候就进行条件判断，如果if判断失败或者while不进入循环块，就跳过该语句块不进行语法分析、解释执行；

其中RETURNFLAG用来表示在函数中返回，跳过剩余的语句；statement默认返回0，当有return语句在其中出现时才需要使用返回值。

代码块：

在一个statement中通过花括号包含多个语句

1
2
3
4
5
6
7
8
9
10
double statement() {
    if (token == '{') {
        match('{');
        while (token != '}') {
            if (RETURNFLAG == statement()) 
                return RETURNFLAG;
        }
        match('}');
    }
    ....

if语句

由于tryC解释器是边进行语法分析，边解释执行的，因此如果不需要解释执行执行某一个语句块，就调用函数

1
skipStatments()

跳过该语句块，不对其进行语法分析，不解释执行；（在if语句和while语句中使用）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
    else if (token == If) {
        match(If);
        match('(');
        int boolresult = boolOR();
        match(')');
        if (boolresult) {
            if (RETURNFLAG == statement()) 
                return RETURNFLAG;
        }
        else skipStatments();
        if (token == Else) {
            match('Else');
            if (!boolresult) {
                if (RETURNFLAG == statement())
                    return RETURNFLAG;
            }
            else skipStatments();
        }
    }
...

其中skipStatments()的实现如下：

1
2
3
4
5
6
7
8
9
10
11
void skipStatments() {
    if(token == '{')
        token = *src++;
    int count = 0;
    while (token && !(token == '}' && count == 0)) {
        if (token == '}') count++;
        if (token == '{') count--;
        token = *src++;
    }
    match('}');
}

while语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
    else if (token == While) {
        match(While);
        char* whileStartPos = src;
        char* whileStartOldPos = old_src;
        int boolresult;
        do {
            src = whileStartPos;
            old_src = whileStartOldPos;
            token = '(';
            match('(');
            boolresult = boolOR();
            match(')');
            if (boolresult) {
                if (RETURNFLAG == statement()) 
                    return RETURNFLAG;
            }
            else skipStatments();
        }while (boolresult);
    }
...

赋值语句

赋值语句的左边可以是数组中间的一个单元，也可以是一个变量，右边是字符串或表达式、字符。

(在下一篇文章中还会提及具体变量赋值的实现)

数组需要先定义才能进行赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
    else if (token == Sym || token == ArraySym) {
        symbol* s = token_val.ptr;
        int tktype = token;
        int index;
        match(tktype);
        if (tktype == ArraySym) {
            match('[');
            index = expression();
            match(']');
            match('=');
            if (index >= 0 && index < s->value) {
                s->pointer.list[index].value = expression();
            }
        }
        else {
            match('=');
            if (token == Str) {
                s->pointer.funcp = (char*)token_val.ptr;
                s->type = Str;
                match(Str);
            }
            else if (token == Char) {
                s->value = token_val.val;
                s->type = Char;
                match(Char);
            }
            else {
                s->value = expression();
                s->type = Num;
            }
        }
        match(';');
    }
...

定义函数语句

定义函数的时候并不执行函数体，所以同样跳过语句块；

1
2
3
4
5
6
7
8
9
10
11
12
13
...
    else if (token == Func) {
        match(Func);
        symbol* s = token_val.ptr;
        s->type = FuncSym;
        match(Sym);
        s->pointer.funcp = src;
        s->value = token;
        skipStatments();
        match(';');
    }
...

定义数组语句

定义数组并分配空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
...
    else if (token == Array) {
        match(Array);
        symbol* s = token_val.ptr;
        match(Sym);
        match('(');
        int length = (int)expression();
        match(')');
        s->pointer.list = (double*)malloc(sizeof(struct symStruct) * length + 1);
        for (int i = 0; i < length; ++i)
            s->pointer.list[i].type = Num;
        s->value = length;
        s->type = ArraySym;
        match(';');
    }
...

返回语句

返回RETURNFLAG作为标志；

1
2
3
4
5
6
7
8
9
10
11
...
    else if (token == Return) {
        match(Return);
        match('(');
        return_val = expression();
        match(')');
        match(';');
        return RETURNFLAG;
    }
...

输入输出语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
    else if (token == Print || token == Read || token == Puts) {
        int func = token;
        double temp;
        match(func);
        match('(');
        switch (func) {
        case Print: 
            temp = expression();
            printf("%lf\n", temp);
            break;
        case Puts: 
            printf("%s\n", (char*)token_val.ptr);
            match(Str);
            break;
        case Read:
            scanf("%lf", &token_val.ptr->value);
            token_val.ptr->type = Num;
            match(Sym);
        }
        match(')');
        match(';');
    }
    return 0;
}

可对照源码查看（如果觉得写得还行麻烦您帮我点个star哦）
https://github.com/yunwei37/tryC

Posted Updated 13 minutes read (About 1928 words)

c语言手搓一个500+行的类c语言解释器（3）- 词法分析

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程（3）- 词法分析

项目github地址及源码：
https://github.com/yunwei37/tryC

这一篇讲讲在tryC中词法分析器是怎样构建的

词法分析器是什么玩意

回想一下上一篇我们说的词法分析阶段，编译器做了这样一件事：

对源程序进行阅读，并将字符序列，也就是源代码中一个个符号收集到称作记号（token）的单元中

帮编译器执行词法分析阶段的模块，就叫词法分析器啦。词法分析器能够对源码字符串做预处理，以减少语法分析器的复杂程度。

词法分析器以源码字符串为输入，输出为标记流（token stream），即一连串的标记，比如对于源代码中间:

1
num = 123.4;

这样一个赋值语句中，变量num算是一个token，“=”符号算是一个token，“123.4”算是一个token；每个token有自己的类别和属性，比如“123.4”的类别是数字，属性（值）是123.4；每个token可以用这一对儿表示：{token, token value}，就像“123.4”可以表示为{Num, 123.4}

词法分析器输入上面那句话，就得到这样一个标记流：

1
{Sym, num}, {'=', assign}, {Num, 123.4}

词法分析器的具体实现

由于词法分析器对于各个语言基本都是大同小异，在其他地方也有很多用途，并且手工构造的话实际上是一个很枯燥又容易出错的活计，因此其实已经有了不少现成的实现，比如 lex/flex 。

通常词法分析器的实现会涉及到正则表达式、状态机的一些相关知识，或者通过正则表达式用上面那些工具来生成。但对于我们这样一个简单的解释器来说，手工构造词法分析器，并且完全不涉及到正则表达式的知识，理解起来也并不是很困难啦。

先来看看token是怎样写的

token的数据结构如下：

1
2
3
4
5
6

int token;                      // current token type
union tokenValue {              // token value
    symbol* ptr;               
    double val;                 
} token_val;
  • 用一个整型变量 token 来表示当前的 token 是什么类型的；
  • 用一个联合体来表示附加的token属性，ptr可以附加指针类型的值，val可以附加数值。

token 的类型采用枚举表示定义：

1
2
3
4
5
6
7
/* tokens and classes (operators last and in precedence order) */
enum {
    Num = 128, Char, Str, Array, Func,
    Else, If, Return, While, Print, Puts, Read,
    Assign, OR, AND, Equal, Sym, FuncSym, ArraySym, Void,
    Nequal, LessEqual, GreatEqual, Inc, Dec
};

比如我们会将“==”标记为Equal，将Num标记为Sym等等。从这里也可以看出，一个标记（token）可能包含多个字符；而词法分析器能减小语法分析复杂度的原因，正是因为它相当于通过一定的编码（采用标记来表示一定的字符串）来压缩和规范化了源码。

另外，一些单个字符我们直接作为token返回，比如：

1
'}' '{' '(' ')' ';' '[' ']' .....

词法分析器真正干活的函数们

首先需要说明一下，源码字符串为输入，输出为标记流（token stream），这里的标记流并不是一次性将所有的源代码翻译成长长的一串标记串，而是需要一个标记的时候再转换一个标记，原因如下：

  1. 字符串转换成标记流有时是有状态的，即与代码的上下文是有关系的。
  2. 保存所有的标记流没有意义且浪费空间。

所以通常的实现是提供一个函数，每次调用该函数则返回下一个标记。这里说的函数就是 next() 。

这是next()的基本框架：其中“AAA””BBB”是token类型；

1
2
3
4
5
6
7
8
9
10
void next() {
    while (token = *src) {
        ++src;
        if(token == AAA ){
            .....
        }else if(token == BBB ){
            .....
        }
    }
}

用while循环的原因有以下几个：

  • 处理错误：
    如果碰到了一个我们不认识的字符，可以指出错误发生的位置，然后用while循环跳过当前错误，获取下一个token并继续编译；

  • 跳过空白字符；
    在我们实现的tryC语言中，空格是用来作为分隔用的，并不作为语法的一部分。因此在实现中我们将它作为“不识别”的字符进行跳过。

现在来看看AAA、BBB具体是怎样判断的：

换行符和空白符

1
2
3
4
5
6
7
...
if (token == '\n') {
    old_src = src;              // 记录当前行，并跳过；
}
else if (token == ' ' || token == '\t') {        }
...

注释

1
2
3
4
5
6
7
8
...
else if (token == '#') {            // skip comments
    while (*src != 0 && *src != '\n') {
                src++;
    }
}
...

单个字符

1
2
3
4
5
6
7
8
...
else if ( token == '*' || token == '/'  || token == ';' ||  token == ',' ||
token == '(' || token == ')' || token == '{' || token == '}' ||  token == '[' || token == ']') {
    return;
}

...

数字

token 为Num；
token_val.val为值；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
else if (token >= '0' && token <= '9') {        // process numbers
    token_val.val = (double)token - '0';
    while (*src >= '0' && *src <= '9') {
        token_val.val = token_val.val * 10.0 + *src++ - '0';
    }
    if (*src == '.') {
        src++;
        int countDig = 1;
        while (*src >= '0' && *src <= '9') {
            token_val.val = token_val.val + ((double)(*src++) - '0')/(10.0 * countDig++);
        }
    }
    token = Num;
    return;
}

...

字符串

token 为Str；
token_val.ptr保存字符串指针；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
        else if (token == '"' ) {               // parse string
            last_pos = src;
            char tval;
            int numCount = 0;
            while (*src != 0 && *src != token) {
                src++;
                numCount++;          
            }
            if (*src) {
                *src = 0;
                token_val.ptr = malloc(sizeof(char) * numCount + 8);
                strcpy(token_val.ptr, last_pos);
                *src = token;
                src++;
            }
            token = Str;
            return;
        }

...

字符

token 为Char；
token_val.val为值；

1
2
3
4
5
6
7
8
9
10
...
        else if (token == '\'') {               // parse char
            token_val.val = *src++;
            token = Char;
            src++;
            return;
        }

...

变量：这是最复杂的一部分

对变量的处理需要以下几个步骤：

  1. 获取完整的变量名：
  2. 在符号表中查找变量：
  3. 如果在符号表中找到了变量，根据变量不同的类型，返回不同的token值；
  4. 如果没有找到，在符号表中间插入新的变量

关于符号表具体的内容，会独立出一篇文章来解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
...
        else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) {
            last_pos = src - 1;             // process symbols
            char nameBuffer[MAXNAMESIZE];
            nameBuffer[0] = token;
            while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) {
                nameBuffer[src - last_pos] = *src;
                src++;
            }
            nameBuffer[src - last_pos] = 0;                 // get symbol name
            int i;
            for (i = symPointer-1; i >= 0; --i) {           // search symbol in symbol table 
                if (strcmp(nameBuffer, symtab[i].name) == 0) {      // if find symbol: return the token according to symbol type
                    if (symtab[i].type == Num || symtab[i].type == Char) {
                        token_val.ptr = &symtab[i];
                        token = Sym;
                    }
                    else if (symtab[i].type == FuncSym) {
                        token_val.ptr = &symtab[i];
                        token = symtab[i].type;
                    }
                    else if (symtab[i].type == ArraySym) {
                        token_val.ptr = &symtab[i];
                        token = symtab[i].type;
                    }
                    else {
                        if (symtab[i].type == Void) {
                            token = Sym;
                            token_val.ptr = &symtab[i];
                        }
                        else token = symtab[i].type;
                    }
                    return;
                }
            }
            strcpy(symtab[symPointer].name, nameBuffer);        // if symbol not found, create a new one 
            symtab[symPointer].levelNum = currentlevel;
            symtab[symPointer].type = Void;
            token_val.ptr = &symtab[symPointer];
            symPointer++;
            token = Sym;
            return;
        }
...

其他的一些符号，可能需要再多读取一个字符才能确定具体token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
...
        else if (token == '=') {            // parse '==' and '='
            if (*src == '=') {
                src++;
                token = Equal;
            }
            return;
        }
        else if (token == '+') {            // parse '+' and '++'
            if (*src == '+') {
                src++;
                token = Inc;
            }
            return;
        }
        else if (token == '-') {            // parse '-' and '--'
            if (*src == '-') {
                src++;
                token = Dec;
            }
            return;
        }
        else if (token == '!') {               // parse '!='
            if (*src == '=') {
                src++;
                token = Nequal;
            }
            return;
        }
        else if (token == '<') {               // parse '<=',  or '<'
            if (*src == '=') {
                src++;
                token = LessEqual;
            }
            return;
        }
        else if (token == '>') {                // parse '>=',  or '>'
            if (*src == '=') {
                src++;
                token = GreatEqual;
            }
            return;
        }
        else if (token == '|') {                // parse  '||'
            if (*src == '|') {
                src++;
                token = OR;
            }
            return;
        }
        else if (token == '&') {                // parse  '&&'
            if (*src == '&') {
                src++;
                token = AND;
            }
            return;
        }

...

错误处理

1
2
3
4
5
6
7
...
        else {
            printf("unexpected token: %d\n", token);
        }

...

match函数：用于匹配当前token并获取下一个token

1
2
3
4
5
6
7
8
9
10
// 匹配一个记号，并获取下一个token：
void match(int tk) {
    if (token == tk) {
        next();
    }
    else {          // 遇到了一个错误
        exit(-1);
    }
}

可对照源码查看（如果觉得写得还行麻烦您帮我点个star哦）
https://github.com/yunwei37/tryC

Posted Updated 14 minutes read (About 2074 words)

c语言手搓一个500+行的类c语言解释器（6）- 语义分析：符号表和变量、函数

用c语言手搓一个500+行的类c语言解释器: 给编程初学者的解释器教程（6）- 语义分析：符号表和变量、函数

项目github地址及源码：
https://github.com/yunwei37/tryC

这一部分，我们再回过头来看看变量、函数是怎样存储和处理的、以及符号表是怎样构建的。

符号表

我们先来回顾一下符号表的定义：

符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。

简单来说就是，我们在符号表中存储对应的变量的各种信息，在定义的时候对符号表进行插入，以便下次碰见它的时候可以知道这个变量的具体信息。

我们可以在符号表中保存五种变量：Num（数值）, Char（字符）, Str（字符串）, Array（数组）, Func（函数）

tryC符号表的完整定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* this structure represent a symbol store in a symbol table */
typedef struct symStruct {  
    int type;                  // 符号的类型:  Num, Char, Str, Array, Func
    char name[MAXNAMESIZE];    // 符号名称
    double value;              // 如果是数值变量，记录它的值; 如果是数组或者字符串，记录它的长度
    union {
        char* funcp;            // 指向函数定义在源代码中位置的字符指针
        struct symStruct* list; // 指向数组列表
    } pointer;
    int levelNum;               // 作用域层
} symbol;
symbol symtab[SYMTABSIZE];      // 用数组定义符号表
int symPointer = 0;             // 符号表数组当前使用的最大下标的指针+1（栈顶 + 1）
int currentlevel = 0;           // 当前作用域层

作用域

作用域就是程序中定义的变量所存在的区域，超过该区域变量就不能被访问。

（这里就不具体举例介绍了）

作用域可以相互嵌套；当内层作用域和外层作用域存在同名变量时，在内层的程序访问的应当是内层的变量，在外层的程序访问的应当是外层的变量；在函数中的变量，只有在所在函数被调用时才动态地为变量分配存储单元，并在调用结束时回收。

作用域可以是块作用域、函数作用域等，tryC中只实现了函数作用域。

我们可以用currentlevel这个变量记录当前的嵌套深度；

1
int currentlevel = 0;

对于函数作用域我们可以这样处理：在函数调用时加深作用域层，并把需要传入的参数插入符号表；并在函数退出的时候，删除该作用域层的所有变量，并减少作用域层，对应代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
double function() {
    currentlevel++;
    return_val = 0;

    .....

    while (symtab[symPointer - 1].levelNum == currentlevel) {
        symPointer--;
    }
    currentlevel--;
    return return_val;
}

由于插入的变量肯定在符号表数组的最上面，因此只要减少符号表数组最大值的指针就可以表示删除啦。

变量

对变量的处理主要分为几个部分：

  • 词法分析阶段，当我们遇见一个标识符名称时，需要返回对应的token；
  • 在表达式中，当遇见一个变量时，我们需要获取它的值；
  • 在定义语句中，对变量进行定义和在符号表中插入相关信息；

词法分析阶段

当我们在词法分析的时候，对变量的处理需要以下几个步骤：

  1. 获取完整的变量名：
  2. 在符号表中查找变量，从上往下查找，这样返回的一定是最近作用域的那个变量：
  3. 如果在符号表中找到了变量，根据变量不同的类型，返回不同的token值；
  4. 如果没有找到，在符号表中间插入新的变量，返回的token值为void；这时应该对应赋值语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
...
        else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) {
            last_pos = src - 1;             // process symbols
            char nameBuffer[MAXNAMESIZE];
            nameBuffer[0] = token;
            while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) {
                nameBuffer[src - last_pos] = *src;
                src++;
            }
            nameBuffer[src - last_pos] = 0;                 // get symbol name
            int i;
            for (i = symPointer-1; i >= 0; --i) {           // search symbol in symbol table 
                if (strcmp(nameBuffer, symtab[i].name) == 0) {      // if find symbol: return the token according to symbol type
                    if (symtab[i].type == Num || symtab[i].type == Char) {
                        token_val.ptr = &symtab[i];
                        token = Sym;
                    }
                    else if (symtab[i].type == FuncSym) {
                        token_val.ptr = &symtab[i];
                        token = symtab[i].type;
                    }
                    else if (symtab[i].type == ArraySym) {
                        token_val.ptr = &symtab[i];
                        token = symtab[i].type;
                    }
                    else {
                        if (symtab[i].type == Void) {
                            token = Sym;
                            token_val.ptr = &symtab[i];
                        }
                        else token = symtab[i].type;
                    }
                    return;
                }
            }
            strcpy(symtab[symPointer].name, nameBuffer);        // if symbol not found, create a new one 
            symtab[symPointer].levelNum = currentlevel;
            symtab[symPointer].type = Void;
            token_val.ptr = &symtab[symPointer];
            symPointer++;
            token = Sym;
            return;
        }
...

在表达式中对变量的处理：

在表达式中遇到的标识符可能是三种形式：

  1. 普通变量：Char或Num，token_val传递数值类型；
  2. 函数变量：进行调用函数操作；
  3. 数组变量：获取token_val传递的数组指针，获取下标，进行边界检查，获取元素；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double factor() {
    double temp = 0;
    .....
    else if (token == Sym) {                // 普通变量
        temp = token_val.ptr->value;
        match(Sym);
    }
    else if (token == FuncSym) {            // 函数变量
        return function();
    }
    else if (token == ArraySym) {           // 数组变量
        symbol* ptr = token_val.ptr;
        match(ArraySym);
        match('[');
        int index = (int)expression();
        if (index >= 0 && index < ptr->value) {
            temp = ptr->pointer.list[index].value;
        }
        match(']');
    }
    return temp;
}

在变量定义语句中对变量的处理

由于是动态类型语言，我们对变量的定义语句也是变量的赋值语句；根据赋值的类型确定变量的类型。进入赋值语句时，传递过来的token_val包含的是一个指向当前变量结构体的指针，赋值就是对其进行操作：

赋值语句的左边可以是数组中间的一个单元，也可以是一个变量，右边是字符串或表达式、字符。

数组需要先定义才能进行赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
    else if (token == Sym || token == ArraySym) {
        symbol* s = token_val.ptr;
        int tktype = token;
        int index;
        match(tktype);
        if (tktype == ArraySym) {                   // 对数组进行特殊判断：获取要赋值的数组单元；
            match('[');
            index = expression();
            match(']');
            match('=');
            if (index >= 0 && index < s->value) {
                s->pointer.list[index].value = expression();
            }
        }
        else {
            match('=');
            if (token == Str) {                     // 根据赋值类型进行不同的操作
                s->pointer.funcp = (char*)token_val.ptr;
                s->type = Str;
                match(Str);
            }
            else if (token == Char) {
                s->value = token_val.val;
                s->type = Char;
                match(Char);
            }
            else {
                s->value = expression();
                s->type = Num;
            }
        }
        match(';');
    }
...

函数

tryC的函数实现完整代码：这个函数做了以下几件事：

  1. 对变量的作用域进行控制；
  2. 将函数参数中的变量直接插入作用域；
  3. 保存当前词法分析的源代码位置和token，并跳转到函数定义时的源代码位置和token；
  4. 语法分析和执行定义时的函数体，如果碰到返回语句，就将返回值存入return_val；
  5. 恢复保存的当前源代码位置和token；
  6. 返回值从全局变量return_val中获取；

由于function()函数本身是递归的，且变量作用域等可以得到控制，因此可以实现函数的递归调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
double function() {
    currentlevel++;
    return_val = 0;             // 对变量的作用域进行控制；

    symbol* s = token_val.ptr;  // 将函数参数中的变量直接插入作用域；
    match(FuncSym);
    match('(');
    while (token != ')') {
        symtab[symPointer] = *token_val.ptr;
        strcpy(symtab[symPointer].name, token_val.ptr->name);
        symtab[symPointer].levelNum = currentlevel;
        symPointer++;
        match(Sym);
        if (token == ',')
            match(',');
    }
    match(')');
    char* startPos = src;                   // 保存当前词法分析的源代码位置和token
    char* startOldPos = old_src;
    int startToken = token;
    old_src = src = s->pointer.funcp;       // 跳转到函数定义时的源代码位置和token；
    token = (int)s->value;
    statement();                            // 语法分析和执行定义时的函数体
    src = startPos;
    old_src = startOldPos;
    token = startToken;                     // 恢复保存的当前源代码位置和token；

    while (symtab[symPointer - 1].levelNum == currentlevel) {
        symPointer--;
    }
    currentlevel--;
    return return_val;
}

可对照源码查看（如果觉得写得还行麻烦您帮我点个star哦）
https://github.com/yunwei37/tryC

Follow

Links

Recents

Archives

Tags

Notes1
WebAssembly1
WebAssembly GIS1
ebpf tutorial1
notes14
notes WebAssembly1
notes ai1
notes ebpf2
notes gpt ai10
others4
tutorial6

Subscribe for updates

Advertisement

×