【C/C++理论实战技术】编译原理与语法详解

一、编译流程全景

C/C++ 从源码到可执行文件，经历四个阶段：预处理（Preprocessing）→ 编译（Compilation）→ 汇编（Assembly）→ 链接（Linking）。理解每个阶段的工作原理，是掌握构建系统、调试编译错误、实现字节码插桩、编写编译器插件的基础。

source.c → [预处理器 cpp] → source.i → [编译器 cc1] → source.s → [汇编器 as] → source.o → [链接器 ld] → a.out

对于 Android NDK，工具链位于 $NDK/toolchains/llvm/prebuilt/linux-x86_64/bin/，使用以 aarch64-linux-android21- 为前缀的 clang 作为编译驱动。

1.1 预处理（Preprocessing）

预处理器是一个文本替换引擎。它不关心 C 语义——只做文本级别的宏替换、文件包含、条件编译。

#include 的处理机制

#include 与 #include "..." 的区别在于头文件查找路径：

• #include <stdio.h>：按 -I 指定的目录和系统 include 路径顺序搜索
• #include "myheader.h"：先在当前源文件所在目录搜索，再按 <...> 方式搜索

编译器通过 -I 参数追加搜索路径：

gcc -I./include -I/usr/local/include main.c

对于 NDK，sysroot 的 include 路径在 $NDK/toolchains/llvm/prebuilt/linux-x86_64/sysroot/usr/include/。

宏展开的陷阱

宏是纯文本替换，不涉及类型检查。经典错误：

#define SQUARE(x) x * x
SQUARE(1 + 2)  // 展开为 1 + 2 * 1 + 2 = 1 + 2 + 2 = 5，而非期望的 (1+2)*(1+2)=9

修复方法：为宏的每个参数和使用处加括号。

#define SQUARE(x) ((x) * (x))

宏的两个特殊操作符：

• #（stringification）：将宏参数转为字符串字面量。#define STR(x) #x → STR(hello) 展开为 "hello"
• ##（token pasting）：将两个 token 合并为一个。#define CONCAT(a, b) a##b → CONCAT(my, Var) 展开为 myVar

条件编译

#if defined(__arm__) && defined(__aarch64__)
// ARM64 NEON 路径
#elif defined(__i386__) || defined(__x86_64__)
// x86 SSE 路径
#else
#error "unsupported architecture"
#endif

#ifdef DEBUG
#define LOG(msg) __android_log_print(ANDROID_LOG_DEBUG, "native", "%s", msg)
#else
#define LOG(msg) ((void)0)
#endif

#pragma once vs include guards：两者都防止重复包含，#pragma once 由编译器实现，效率更高（不需要读取完整个头文件），但不是 C 标准的一部分——所有主流编译器都支持，严格可移植代码仍用 include guards。

1.2 编译（Compilation）——核心阶段

编译阶段将预处理后的 .i 文件转换为汇编代码 .s，内部可细分为前端和后端。

词法分析（Lexical Analysis）

词法分析器将字符流分解为 token 序列。每个 token 包含类型和可选的属性值。

以 int sum = a + 10; 为例，词法分析输出：

Token: KW_INT     "int"
Token: IDENTIFIER "sum"
Token: OPERATOR   "="
Token: IDENTIFIER "a"
Token: OPERATOR   "+"
Token: INT_LITERAL "10"
Token: SEMICOLON  ";"

词法分析器通常基于有限自动机实现。正则表达式描述 token 模式，然后转换为 NFA（非确定性有限自动机），再通过子集构造法转为 DFA（确定性有限自动机）。DFA 每个输入字符只需一次状态转移，O(n) 的时间内完成扫描。

flex（Lex 的 GNU 实现）是经典的词法分析器生成器：

%%
[0-9]+          { yylval = atoi(yytext); return INT_LITERAL; }
[a-zA-Z_][a-zA-Z0-9_]*  { return IDENTIFIER; }
"+"             { return PLUS; }
"int"           { return KW_INT; }

语法分析（Syntax Analysis）

语法分析器接收 token 流，按文法产生式构建抽象语法树。C 语言的文法属于上下文无关文法。

关键概念——推导与归约。自顶向下（Top-Down）从起始符号出发推导出 token 序列；自底向上（Bottom-Up）从 token 序列归约到起始符号。

LL(k) 分析法是自顶向下的代表。第一个 L 表示从左到右扫描输入（Left-to-right），第二个 L 表示使用最左推导（Leftmost derivation），k 为前瞻符号数。LL(1) 每步只需看一个 token 即可无歧义地选择产生式。LL(1) 文法要求每个非终结符的各候选式的 FIRST 集互不相交。递归下降分析器就是手写的 LL(1) 分析器。GCC 早期使用手写的递归下降，Clang 也使用递归下降。

LR 分析法是自底向上的代表，能处理比 LL 更广的文法类。L 表示从左到右扫描，R 表示最右推导的逆过程（Rightmost derivation in reverse）。LR 分析器维护一个状态栈和一个符号栈，根据当前状态和输入符号查 ACTION 表决定移进（shift）或归约（reduce），查 GOTO 表决定归约后的状态跳转。

四种 LR 变体按表达能力排序：LR(1) > LALR(1) > SLR(1) > LR(0)。LALR(1) 是 LR(1) 的实用近似——将具有相同核心（core）的 LR(1) 状态合并，在保持几乎全部 LR(1) 表达能力的同时将状态数减少到与 SLR(1) 相当。YACC/Bison 使用 LALR(1)。

移进-归约冲突（shift-reduce conflict）：当前既可以移进也可以归约，如经典的悬空 else 问题。

if (a) if (b) f(); else g();
// else 与哪个 if 配对？shift（与外层 if 配对）vs reduce（与内层 if 配对）

解决方式：Bison 中通过 %prec 声明优先级与结合性，或采用”最近未匹配的 if”规则（shift 优先）。

语义分析（Semantic Analysis）

语义分析检查程序的语义正确性。核心工作包括：

类型检查是语义分析的核心。编译器维护一个类型系统，对每个表达式节点推断类型并检查操作数类型是否兼容。C 语言的隐式类型转换规则（usual arithmetic conversions）：向更宽的类型提升，整数提升（integer promotion），浮点提升。

符号表管理：符号表是编译器的心脏，记录每个标识符的名称、类型、作用域、存储类别（static/extern/auto/register）等信息。作用域可以通过”栈式符号表”实现——进入新作用域时 push 新表，离开时 pop。C 语言的块作用域对应一对花括号。处理得当，名称查找从内层向外层逐级搜索，内层声明遮蔽外层同名声明。

中间代码生成与优化

现代编译器（LLVM、GCC）在 AST 之后构建与平台无关的中间表示（IR），在 IR 上进行优化，最后将优化后的 IR 翻译为目标平台代码。这种三段式架构的优点：前端只负责语言解析，后端只负责目标代码生成，增加新语言只需新增前端，增加新平台只需新后端。

LLVM IR 是 SSA（Static Single Assignment）形式——每个变量只被赋值一次。新值通过创建新版本表示：

; 原始代码: a = a + 1
; SSA形式:
%a.1 = add i32 %a.0, 1

SSA 使数据流分析变得极其高效——use-def 链直接编码在变量名中，不需要额外的数据流分析就能确定每个值的使用点和定义点。

关键优化遍（passes）：

死代码消除（DCE, Dead Code Elimination）：删除结果不产生任何副作用且不被任何后续代码使用的指令。以 SSA 形式表示的 LLVM IR 中，检查一条指令的所有使用（use）是否为空即可判断是否为死代码。

常量折叠与传播（Constant Folding & Propagation）：编译期计算常量表达式。在 SSA 形式中，如果某个值的定义是常量操作，则将该常量值替换到所有使用点。

int x = 5 * 3600;  // 编译期计算为 18000

循环不变量外提（LICM, Loop Invariant Code Motion）：将循环内计算结果不变的表达式移到循环外部。

for (int i = 0; i < n; i++) {
    double d = sqrt(2.0);  // 每次迭代都计算，但结果不变 → 提到循环外
    arr[i] *= d;
}

内联（Inlining）：将被调用函数的函数体嵌入调用处，消除调用开销（栈帧建立、参数传递、跳转指令），同时为后续优化创造上下文——内联后的代码可以与其他代码一起被优化。但内联增大代码体积，可能降低指令缓存命中率。编译器通过启发式算法决定是否内联：函数体小（如 < 50 条指令）、调用次数少、包含常量参数利于常量传播时倾向于内联。

1.3 汇编（Assembly）

汇编器将汇编代码（.s）翻译为目标文件（.o）中的机器指令。每条汇编指令对应一条机器指令（CISC 架构可以一对多）。

目标文件（ELF 格式）的组织：

• .text section：可执行代码
• .rodata section：只读数据（字符串字面量等）
• .data section：已初始化的全局变量和静态变量
• .bss section：未初始化的全局变量（文件占 0 字节，加载时清零）
• 符号表 .symtab：函数和全局变量的名称及地址
• 重定位表 .rela.text / .rela.dyn：链接时需要修正的地址引用

1.4 链接（Linking）

链接器将一个或多个目标文件与库合并为最终的可执行文件或共享库。

链接的两大任务：

符号解析：每个目标文件引用外部符号（未定义符号，UND），链接器在为所有输入目标文件找到每个引用符号的定义。如果找不到定义（或找到多个定义），则报错——“undefined reference to” 或 “multiple definition of”。

重定位：编译时目标文件的代码段和数据段地址从 0 开始。链接器将所有目标文件的 section 合并到同一个地址空间，为每个 section 分配最终的运行时地址，然后修改代码中所有地址引用。重定位有两种：

• 绝对重定位：将绝对地址修正为最终地址。如 R_AARCH64_ABS64 将 64 位地址字段填充为符号的运行时地址。
• 相对重定位：将相对偏移修正。如 R_AARCH64_CALL26 修改 B/BL 指令的 26 位偏移域——这在动态链接 PLT 中频繁使用。

1.5 静态库 vs 动态库

维度	静态库 .a	动态库 .so
链接时机	编译时	运行时（由 linker 加载）
可执行文件体积	较大（库代码嵌入）	较小（只引用，不嵌入）
内存效率	每个进程一份副本	所有进程共享同一份物理内存（通过 mmap）
更新部署	需重新编译所有依赖者	二进制兼容时替换 so 即可，不需要重编
符号冲突	链接时报错	运行时通过符号版本化隔离

# 静态库
gcc -c foo.c -o foo.o
ar rcs libfoo.a foo.o

# 动态库
gcc -shared -fPIC -o libfoo.so foo.c

关键参数：

• -fPIC：生成位置无关代码（Position-Independent Code）。共享库加载地址在每次加载时可能不同（ASLR 随机化），PIC 代码使用 PC 相对寻址访问数据——代码中的地址是相对于当前 PC 值的偏移，不依赖绝对地址。这样多个进程可以加载同一份 .so 到不同虚拟地址，物理内存只占用一份。
• -Wl,-rpath：向可执行文件写入一个搜索路径告诉 linker 去哪里找 .so
• -Wl,-soname：设置 .so 的 SONAME（逻辑名称），用于运行时身份验证
• -Wl,--version-script：控制导出符号集——隐藏内部实现细节，只导出公开 API

1.6 链接与 Android NDK

Android 的动态链接器是 /system/bin/linker（32 位）和 /system/bin/linker64（64 位）。与 GNU/Linux 的 ld-linux.so 类似，但有以下差异：

Android 7.0+ 实施 namespace 隔离——应用不能直接链接到非 NDK 公开 API 的系统库符号。NDK 公开 API 列表在 $NDK/meta/platforms.json 中声明。

Android 自 API 21 统一使用 ET_DYN 类型的 ELF（Position Independent Executable）。所有可执行文件与共享库使用相同的 ELF 类型，区别在于可执行文件有 INTERP program header（指定 linker 路径）。

---

二、Makefile 语法详解

Make 是最基础的构建工具——没有 Make，就不会有对构建过程的理解，也就难以理解更高级的 CMake、Soong（Android.bp）、Bazel。

2.1 Makefile 的基本规则

Makefile 的核心是规则：

target ... : prerequisites ...
    recipe

• target：通常是一个文件名（可执行文件或目标文件），也可以是一个标签（label），如 clean
• prerequisites：生成 target 所依赖的文件或其它 target
• recipe：shell 命令。必须以 TAB 开头，不能用空格。这是 Makefile 最常见的错误源

Make 如何决定是否需要重新构建 target：检查 prerequisites 的修改时间（mtime，modification time）。如果任一 prerequisite 的 mtime 比 target 的 mtime 新，则认为 target 过期，执行 recipe 重新生成。

2.2 自动变量

Make 提供自动变量简化规则书写：

变量	含义	示例
$@	当前规则的目标文件名	target
$<	第一个 prerequisite 的名称	第一个依赖
$^	所有 prerequisite 的名称，去重	所有依赖
$?	所有比 target 更新的 prerequisite	发生变化的依赖
$*	目标文件名去除后缀的部分（stem）	模式匹配时的 stem

%.o: %.c
    $(CC) -c $(CFLAGS) $< -o $@
# 等价于: gcc -c -O2 main.c -o main.o

此处 % 是通配符，匹配任意非空字符串——相同 stem 的值在 target 和 prerequisite 中保持一致。$< 展开为 main.c，$@ 展开为 main.o。

2.3 伪目标（Phony Target）

有些 target 不对应文件名，如 clean。使用 .PHONY 声明：

.PHONY: clean all install

clean:
    rm -rf *.o $(TARGET)

如果不声明 .PHONY，且目录中恰好存在一个文件名为 clean，由于 clean 没有 prerequisites 且 target 文件已存在（mtime 检查认为它是最新的），make 会认为 clean 已经是最新的而不执行 recipe。.PHONY 告诉 make：不管有没有同名文件存在，每次都要执行。

2.4 条件判断

ifeq ($(DEBUG), 1)
    CFLAGS += -g -DDEBUG
else
    CFLAGS += -O2 -DNDEBUG
endif

ifdef ANDROID_NDK
    CC := $(ANDROID_NDK)/toolchains/llvm/prebuilt/linux-x86_64/bin/aarch64-linux-android21-clang
endif

条件判断在 Makefile 解析阶段求值——不在 recipe 执行时。这与 shell 的 if 语句不在同一层次。条件判断决定哪些 Makefile 规则生效，不决定 shell 命令的控制流。

2.5 常用函数

Make 内置大量函数用于字符串和文件名操作：

SRCS = $(wildcard src/*.c)          # glob匹配: src/main.c src/util.c
OBJS = $(patsubst src/%.c, obj/%.o, $(SRCS))  # 模式替换: obj/main.o obj/util.o
DIRS = $(sort /usr/local /usr /usr/local)      # 排序去重: /usr /usr/local
FILES = $(notdir src/main.c)                   # 取文件名: main.c

2.6 完整的 Android NDK Makefile 示例

# Android.mk
LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

LOCAL_MODULE    := native-lib
LOCAL_SRC_FILES := main.c util.c crypto.c
LOCAL_C_INCLUDES := $(LOCAL_PATH)/include
LOCAL_CFLAGS    := -O2 -Wall -Wextra -fvisibility=hidden
LOCAL_LDLIBS    := -llog -landroid -ldl
LOCAL_STATIC_LIBRARIES := libssl_static

include $(BUILD_SHARED_LIBRARY)

---

三、CMake 详解

CMake 是 Android 官方推荐的 NDK 构建系统（自 Android Studio 2.2 起）。它本质上是一个构建系统生成器——不直接调用编译器，而是生成 Makefile（或 Ninja 文件），再由 Make/Ninja 执行具体构建。

3.1 CMakeLists.txt 基本结构

cmake_minimum_required(VERSION 3.18.1)
project("nativeapp" LANGUAGES C CXX)

# 创建库
add_library(native-lib SHARED
    src/main/cpp/native-lib.cpp
    src/main/cpp/crypto.cpp
)

# 查找依赖
find_library(log-lib log)

# 头文件搜索路径
target_include_directories(native-lib PRIVATE
    ${CMAKE_CURRENT_SOURCE_DIR}/include
)

# 链接依赖
target_link_libraries(native-lib
    ${log-lib}
    android
)

PRIVATE、PUBLIC、INTERFACE 的含义：

• PRIVATE：仅当前 target 使用
• PUBLIC：当前 target 及依赖它的 target 都使用
• INTERFACE：仅依赖当前 target 的 target 使用

这是 CMake 传播性依赖（transitive dependency）控制的核心——选择错误的作用域，要么暴露不需要的内部头文件，要么缺少必要的公开头文件。

3.2 常用 CMake 命令

# 设置 C++ 标准
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

# 条件判断
if(${ANDROID_ABI} STREQUAL "arm64-v8a")
    add_definitions(-DARCH_ARM64)
elseif(${ANDROID_ABI} STREQUAL "armeabi-v7a")
    add_definitions(-DARCH_ARM32)
endif()

# 查找预编译库
add_library(avcodec SHARED IMPORTED)
set_target_properties(avcodec PROPERTIES
    IMPORTED_LOCATION ${CMAKE_SOURCE_DIR}/libs/${ANDROID_ABI}/libavcodec.so
)

# 自定义构建命令
add_custom_command(
    OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/generated.h
    COMMAND python3 ${CMAKE_CURRENT_SOURCE_DIR}/gen_header.py
    DEPENDS ${CMAKE_CURRENT_SOURCE_DIR}/gen_header.py
)

3.3 CMake vs Android.mk vs Bazel

维度	Android.mk (ndk-build)	CMake	Bazel (Soong)
定位	NDK 专用，Google 已停止新功能开发	跨平台，官方推荐	AOSP 构建系统，Android 平台级使用
IDE 集成	差	Android Studio 原生支持	不在应用开发中使用
语言	Makefile 语法	自定义脚本语言	Starlark（Python 子集）
学习曲线	中	中	较高
推荐场景	遗留项目	新项目首选	AOSP 平台开发

结论：Android 应用开发中，所有新 NDK 项目优先选择 CMake。只有维护遗留的 Android.mk 项目才接触 ndk-build。

---

四、GCC vs Clang/LLVM

Android NDK 自 r13（2016 年）起将 Clang 设为默认编译器。自 NDK r18（2018 年）起完全移除 GCC——所有 Android 平台的 C/C++ 编译全部由 Clang 完成。

4.1 架构差异

GCC 是”一体化”编译器——词法分析、语法分析、语义分析、优化、代码生成在同一个可执行文件 cc1 中完成，内部模块耦合紧密。新增语言支持需要修改大量内部代码。

Clang/LLVM 是”三段式”编译器：

Clang (C/C++/ObjC Frontend)
   ↓ AST
LLVM IR (平台无关中间表示)
   ↓ Optimizations
LLVM IR (优化后)
   ↓ Code Generation
Target Machine Code

三段式的核心优势：

• 增加新语言只需要写新的前端（如 Rust 的 rustc 也计划使用 LLVM 后端）
• 增加新平台只需要写新的后端（Android 的 AArch64、RISC-V 等）
• 工具复用：Clang 的静态分析器（clang-tidy）、代码格式化（clang-format）、LSP 服务器（clangd）全部共享同一个 AST 解析器
• 链接时优化（LTO, Link-Time Optimization）：各个编译单元生成为 LLVM bitcode（而非目标平台的机器码），链接时将 bitcode 合并到一个模块中，对这个整体模块进行跨编译单元的过程间优化，再生成最终机器码

4.2 Clang 的优势

错误信息质量：Clang 的错误信息精确指向出错位置并给出修复建议。这是 Clang 最初设计时最优先考虑的用户体验目标之一。

编译速度：对于大多数 C/C++ 代码，Clang 的编译速度快于 GCC。原因包括手写递归下降分析器（跳过了解析表生成和查找）、更高效的 AST 内存分配（BumpPtrAllocator——大块分配，批量释放）、增量编译支持更好。

工具链生态：基于 Clang 构建的工具远比 GCC 丰富。clang-format（代码格式化）、clang-tidy（lint 与自动修复）、clangd（LSP 语言服务器）、AddressSanitizer/MemorySanitizer/UndefinedBehaviorSanitizer（运行时错误检测器）在现代工程中不可或缺。

4.3 GCC 仍然存在的场景

• Linux 内核编译（内核高度依赖 GCC 扩展，尽管 Clang 内核构建也在推进）
• 需要特定 GCC 扩展的项目（嵌套函数、computed goto 的特定语义等）
• 某些性能场景下 GCC 生成的代码略优于 LLVM（虽然差距在缩小）

对于 Android NDK 开发，唯一选择的编译器是 Clang。

---

面试常考问题

Q1：编译的四个阶段各做什么？预处理、编译、汇编、链接之间的关系是什么？

预处理做文本替换（宏、include、条件编译），输出 .i。编译做词法分析→语法分析→语义分析→中间代码生成→优化→汇编代码生成，输出 .s。汇编将汇编指令一一翻译为机器码，输出 .o 目标文件。链接将多个 .o 和库合并，进行符号解析和重定位，输出可执行文件或 .so。各阶段通过中间文件串联；GCC/Clang 的 -E、-S、-c 参数分别停在对应阶段。

Q2：LL 和 LR 分析法的核心区别？为什么 GCC 用递归下降（LL），而 YACC/Bison 用 LALR(1)？

LL 自顶向下推导（从文法开始符号推导到 token 序列），LR 自底向上归约（从 token 序列归约到开始符号）。LL 分析表简单，手写直观；LR 能处理更广的文法类（所有 LL 文法都是 LR 文法，但反之不成立）。手写的递归下降分析器可以给每个产生式添加自定义错误恢复和诊断，产生最好的错误信息——这对编译器尤为重要。Bison 的 LALR(1) 适合”先用现成工具迭代，以后再手写”的项目。

Q3：静态库和动态库的区别？在 Android 上为什么系统库都是动态链接的？

静态库在编译时嵌入可执行文件；动态库在运行时由 linker 加载。Android 上，系统库（libc、libm、libdl 等）以动态库形式存在的主要原因：(1) 共享同一个物理内存副本——所有应用进程通过 mmap 共享 libc.so 的代码段，极大节省 RAM；(2) 安全更新只需替换 .so 文件，不需重编译所有依赖它的应用；(3) ASLR 要求库代码是位置无关的（PIC），这天然适合动态库。

Q4：CMake 中 target_include_directories 的 PRIVATE、PUBLIC、INTERFACE 分别对应什么场景？

PRIVATE：头文件只用于当前 target 内部实现，不暴露给依赖者。PUBLIC：头文件是当前 target 公开 API 的一部分，依赖者需要使用。INTERFACE：当前 target 是一个纯头文件库（header-only library），实际编译不需要这些头文件，但依赖者需要。正确使用传播性依赖控制可以显著减少不必要的重编译——如果只修改了 PRIVATE 依赖的头文件，依赖者的目标文件不需要重编译。

Q5：LLVM IR 为什么使用 SSA 形式？

SSA 要求每个变量只被赋值一次。这极大地简化了数据流分析：use-def 链直接编码在变量名中，优化遍不需要额外维护数据流信息。例如死代码消除只需检查变量的 use list 是否为空；常量传播只需检查定义指令是否为常量操作。代价是需要引入 φ（phi）函数在控制流汇合点合并多个定义——这增加了 SSA 构造的复杂度，但对于后续所有的分析和优化都是净收益。

---

参考

• AOSP: prebuilts/clang/host/linux-x86/ — Android NDK Clang 预编译工具链
• AOSP: prebuilts/build-tools/ — Make, Ninja 等构建工具
• CMake 官方文档: https://cmake.org/documentation/
• LLVM 文档: https://llvm.org/docs/
• GCC Internals Manual: https://gcc.gnu.org/onlinedocs/gccint/
• 《Compilers: Principles, Techniques, and Tools》(Dragon Book) — 第2-4章：词法/语法分析
• 《Engineering a Compiler》(Cooper & Torczon) — 第8-13章：优化与代码生成
• NDK 构建指南: https://developer.android.com/ndk/guides/build