龙书笔记1 - 模糊概念、杂项知识

编译器可以简单分成分析和综合两个部分

符号表是一种用于存放分析部分收集到的信息的数据结构

一个编译器的结构

  1. 词法分析 lexical analysis
    词法分析器读入源程序的字符流，产生有意义的词素(lexeme)的序列。对于每个词素，产生形式为<token-name,attribute-value>词法单元(token)作为输出

token-name是给语法分析用的抽象符号，第二个分量attribute-value指向符号表中关于这个token的条目。符号表条目的信息被语义分析和代码生成步骤使用

源程序：position=initial+rate*60

position是一个词素，被映射成词法<id,1> id是表示标识符

最终得到的token序列就是<id,1><=><id,2><+><id,3><*><60>，分隔词素的空格会被词法分析器忽略掉

<=><+><*>这样的token不需要属性值，当然也可以使用抽象符号assign

  1. 语法分析 syntax analysis/parsing

语法分析器使用token的第一个分量来创建树形的中间表示，输出词法单元流

  1. 语义分析 semantic analyzer

使用语法树和符号表中的信息来检查源程序是否和定义的语义一致，同时也收集信息放到两者中，为了之后的中间代码生成

  1. 中间代码生成

在语法分析和语义分析完成之后，很多编译器生成一个较低级或类机器语言的中间表示，比如LLVM的IR，不过IR的三种表现形式更灵活了就是说

  1. 代码优化

没什么好说的，太抽象了，没有经验撑得起来

  1. 代码生成

同上，个人对存储和寄存器的知识储备为0

  1. 符号表管理

记录使用的变量的名字，并收集和每个名字的各种属性有关的信息，这些属性提供一个名字的存储分配、类型、作用域…

  1. 将多个步骤组合成pass

每个pass读入一个文件，产生一个输出文件

  1. 编译器构造工具

  2. 语法分析器的生成器 根据一门语言的语法描述自动生成语法分析器

  3. 扫描器/词法分析器的生成器 根据一门语言的token的正则表达式描述生成词法分析器

  4. 语法制导的翻译引擎 生成一组用于遍历分析树并生成中间代码的例程

  5. 代码生成器的生成器 依据一组将中间语言的每个运算翻译成目标机上的机器语言的规则，生成一个代码生成器

  6. 数据流分析引擎

  7. 编译器构造工具集 提供可用于构造编译器不同阶段的例程的完整集合

静态与动态

  • 静态策略：编译期决定
  • 动态策略：运行期决定

环境是名字到内存位置的映射，状态是内存到值的映射

这两个映射都有动态绑定和静态绑定，动态绑定不用说，静态绑定就如设定一个全局变量时，变量的内存位置可以固定，设定一个常量时，内存对应的值可以固定

静态作用域和块结构

看到这个我人傻了，以前单知道一个作用域，但是没想到还能这么写

C++的compiler到底是有多逆天，这都能分析

int a = 1;
int b = 1;
{
  int b = 2;
  {
    int a = 3;
    cout << a << ' ' <<  b << '\n';
  }
  {
    int b = 4;
    cout << a << ' ' <<  b << '\n';
  }
  cout << a << ' ' <<  b << '\n';
}
cout << a << ' ' <<  b << '\n';

推荐阅读

Codeforces Round 864

越来越感觉前面几题浪费时间了 （对想题能力没有什么提升 实现和具体的考虑则需要更专注一点）

这两天看老番 佐贺偶像是传奇 感觉很好看 很鲜活有感染力 然而今天不怎么在状态 人有点消沉 不知道是不是熬夜的缘故

Read More

值类别和引用浅析

本文使用的Clang/LLVM环境：

Homebrew clang version 17.0.6
Target: arm64-apple-darwin23.0.0
Thread model: posix

此文中对象的概念沿用primer的说法，即认为对象是具有某种数据类型的内存空间

Read More

后缀数组(SA) 学习笔记

天梯赛校赛碰到的 本以为切个水题 没想到捅了老挝

甚至还有n,q=10w的区间众数 2333 就是数据比较水 感觉严一点分块都不一定能过

原题貌似是这个 但是他妈的校赛n改到了2w

一开始感觉是差分+lcs或kmp之类的 然后感觉不太对劲…

还是需要一些处理字符串的手段 于是学一下SA和SAM 已经拖了挺久了…

Read More

Windows 配置 WSL2

挺多人搁那儿吹捧，怎么说呢…. 有总比没有好吧

但是还是存在很多问题的，比如opengauss在openEuler的WSL上，重启WSL后开启服务是个薛定谔的状态，在尝试的4台电脑上有两台可以，有两台wsl –shutdown之后重启openGauss就开不起来了，也不清楚是哪一方的锅，还有很多的锅。

Read More