Graphorall

Back
/ Update
en

compile

Transformed from Logseq page

compile

  • Intro

    • Syntax

      • context-free syntax -> readability

    • semantics -> ambigurous

    • Fortran -> COBOL -> lisp

Linked References (31)

代码生成 #compile

  • 寄存器与内存空间的分与合 #ideas

    • 将寄存器作为地址空间的低位？

    • 通用寄存器的个数？

Advanced Compile Intro #compile

  • 中端

    • 控制流

    • SSA与LLVM IR

      • single static assignment

    • 数据流分析

    • 指针分析

      • P -> {O}

        • flow sensitive

        • context sensitive

        • path sensitive

    • 过程间控制流

  • 后端？

    • codegen

      • 指令选择

      • 寄存器分配

      • 指令调度

  • else

    • 实验用Clang与LLVM

      • 本身的编译速度

      • commands

        • llvm-dis test.bc

        • opt -view-cfg test.bc

        • opt -mem2reg test.bc -o test.opt => SSA code

        • llc test.c => asm

        • clang/gcc as linker

      • authentication, authorization, accounting

        • MPC(missing permission check vulnerabilities) #security

          • detect: not all are guarded

          • verify: whether guarded in path?

          • 复杂系统中，check可能也并不正确 #ideas

      • 缺陷表述语言 APISpell

        • SmPL: semantic patch lang

          • pattern based code matching & transforming

马云离开的第四年，19000多人被阿里裁掉，释放出什么信号？ - 知乎 ↗ #PL #compile

  • 关于PL人是怎么看编译器业界的人的

  • 这才是正确的教育方法，因为它给予学生合理的反馈，让他们清晰的知道自己的表现是否符合预期，主动进步，而不是拿一些学生事先不知道的标准在那里瞎坑人，光是给人打分。

    • ACM赛制好！OI赛制什么坑货，不敢给人hack只能说测例本身水的一批

  • 编译器领域最重要的教材，龙书和虎书，在我看来也有很多一知半解，作者自己都稀里糊涂的内容。而且花了大量篇幅讲parser这种看似高深，实则肤浅的话题，浪费读者太多时间，误导他们认为 parser 是至关重要的技术。以至于很多人上完编译器课程，只学会了写 parser，对真正关键的部分没能理解。

    • 回想起来确实如此，主要的focus还是太关注parser了，虽然parser很重要但它只是编译器前中后端里的一部分，而且是非常模块化的一部分，不从事该领域研究的人可以直接当做黑盒调用

    • 相比起来，更generic的是parser的复杂度、能力与语言设计之间的制约关系

最后一次课了 #compile

  • json2xml

    S'-> {I}	
I->I,I	$$=$1+$2
I->C	$$=$1
C->i:E	$$=<i><E></i>
E->i	$$=$1
|S		$$=$1
    plaintext
  • E->L	$$=$1
|a		$$=a.lexval
L->(S)	$$=S.head(S.others)
S->SS	$$.head=$1.head,$$.others=$1.others+$2.all
|E		

(a(b(c)))(d,e(f,g(h)))
    plaintext

课堂小计 #compile

  • 为什么反向压栈

    • callee只具有当前栈顶指针而不具有关于caller栈帧的其他假定，为了实现可变参数，ABI就规定把前面那些固定的参数保存在栈顶，从而能据此对变长参数进行处理

  • 代码优化！好东西

    • size and speed tradeoff

    • 一系列heuristic rules

  • 还准备讲点构建工具，好东西

  • 一些题，都是C+x86的奇葩

    • C竟然可以定义int foo(int)调用foo(x,y,z)

课堂小记 #compile

  • 栈和堆空间的运行时动态调整？

    • 用类似sbrk的syscall应该能动态加分页映射呀，虽然不知为啥栈那端确实没有

    • 哦，只要使用mmap出来的空间就行

  • 反复提及Ruby，是粉丝罢

今日小记 #compile

  • quiz力

    not(a<b and(c<d or not (e<f))) = not ab or not(cd or not ef)=not ab or not cd and ef
ifnot(ab) goto L2
if(cd) goto L3
ifnot(ef) goto L3
x=x+1
if(x=0)goto L0
ifnot(x=2)goto L1
    plaintext

  • quiz2

    ef and (not gh or not ik)
if(a>b)goto L0
if(c>d)goto L1
#if(e>f)goto L1
  ifnot(e>f)goto L0
ifnot(g>h)goto L1
if(i>k)goto L0
    plaintext

课题小记 #compile

  • 静态性质、动态性质

    • 插桩 instrumentation

  • semantic analysis是前端最后一步，进行symbol table维护和type check

  • 数据库的合同一般都签50年

    即使人类寄了数据库还在（

  • boxing,unboxing

    • 强制使用boxing，避免UB：int x;Integer y=null;x=y;

  • 类型等价：名称等价（实际采用）、结构等价

  • 有学生在做这个（☞ scala ）

DONE 编译作业 #compile #homework DEADLINE: <2023-04-27 Thu 22:30> :LOGBOOK: CLOCK: [2023-04-27 Thu 11:17:07]—[2023-04-27 Thu 23:33:20] => 12:16:13 :END:

  • TODO 一个问题，S'->S·这种还有归约项吗？比如Follow(S)={'}',','}

    • image.png 很有意思，似乎是根据左结合规定了冲突的情况优先reduce？

今日课堂小计 #compile

  • 空间换时间

  • 语法树AST

    • 分析树的浓缩表示

    • multi-level isolation

  • Syntax-Directed Translation

    • 举例：公式排版？

继续 {{embed (((64417248-0c7a-45a3-9d61-8a309e6e0ea0)) }} #compile

  • 都能通过传值实现？

    • 编译器常量优化，通过传值实现？

    • 泛型参数可能无法编译期确定

      • 涉及linker，off-the-shelf object

  • 杂谈

    • synthesis是拉丁语，etc./et al.这一对也是

    • 楽，enumeration到底读啥哈，[əˌno͞oməˈrāSHən]还是i-ˌn(y)ü-mə-ˈrā-shən

    • IDE真不是相当程度的调用编译器、保持一致性吗，例：编译器会识别1/(1-3+2)，IDE可能不会，因为IDE识别的规则不完善？

  • 综合属性

  • 继承属性

    • 适合处理上下文信息

    • 例：int a,b,c如何传递类型

      • D->TL : L.type=T.type
T->int|real : T.type=x
L->L1,id|id : id.type=L.type|addtype(id.entry,L.type)//可能顺便检查是否冲突,L1.type=L.type
        plaintext

      • 若为自上而下则可直接赋值，若为自下而上顺序不一致？

      • 输入串->语法树->依赖图->计算属性

      • 以语法树节点作为element，要是有环路怎么办？以值为element

      • 真有值环路就不是良定义的（well-defined/ill-defined），检测或者超时报错

        • 例：#include循环依赖（好像也不太恰当）

讲到语义分析了 #compile

  • Syntax-Directed Definition/Translation

  • 杂谈 出书的图灵奖得主

    • 人月神话 Peopleware

      • 陷坑，加钱只会打水漂

  • 属性文法

继续 (((643215ec-059d-4848-ad39-a00a7b8f8dd1)) #compile

  • handle -> O(n) to O(1)

  • stack 和queue都行

    • stack实现上开销的常数更小

  • 拓广文法 增加S′→SS' \to S

    • 因为S可能在产生式中作为叶节点，则自底向上过程中无法知道是否到了根

  • 求闭包的时候，经常会碰到已求解过的集合

整一下作业 #compile

  • 消除左递归怎么推的来着？

  • 真nm离谱啊，手动消CFG里的左递归、左公因子还得递归进行，全写废了 这么复杂的玩意根本没讲过好吧，到底是先消左递归还是先消左公因子？

  • image.png

  • image.png

  • image.png

自底向上解析 #compile

  • 自顶向下问题：无法准确定位错位置

  • derivation reduction

  • LR: l2r reduction and rightmost derivation?

课堂笔记 #compile

  • 继续 (((6419566f-0e91-4462-8da6-f651821ad9bf))

    • 左句型、右句型

    • a=b=c计算顺序？= assignment operator 是right-associative滴

    • 二义性：推导过程，i.e.语法树

    • ab数量相同的串

      • 由子串构建

        • 考虑aabbbbaa？若有S→SSS\to SS就可以。第一个例子枚举a,b,Sa,b,S的组合，不行

      • 少的不一定好，考虑可读性

    • CFG=<T,N,S,{P→Q}><T,N,S,\{P\to Q\}>

  • Top-Down Approach 自顶向下

    • Left-Recursion: A→Aα∣βA\to A\alpha|\beta

      • 消除左递归：L=βαn∴L≡A→βA′;A′→αA′∣ϵL=\beta \alpha^n\therefore L\equiv A\to \beta A'; A' \to \alpha A'|\epsilon

      • e.g.

        expr->expr+term|term
expr->term expr'
expr'->+term expr'|epsilon
        plaintext

      • pram?首领？“ ’ ”？

    • 间接左递归

    • Left-Factoring: A→aB∣aCA\to aB|aC

      • 等价变换为A→aD;D→B∣CA\to aD; D\to B|C

  • 发作业了，他批作业竟然还给我举反例😭

谈正事儿了 #compile

  • L(RE)=L(NFA)=L(DFA), L∈L(RE)→Σ∗−L∈L(RE)\mathscr L(RE)=\mathscr L(NFA)=\mathscr L(DFA),\ L\in\mathscr L(RE)\rightarrow \Sigma^* -L\in \mathscr L(RE)

  • 又杂谈了：大型程序编译中间卡住，提前判断？

  • CFG(Context Free Grammar): rewriting

DONE Compile HW1 ↗ #compile #homework DEADLINE: <2023-03-21 Tue> :LOGBOOK: CLOCK: [2023-03-17 Fri 08:31:17] CLOCK: [2023-03-17 Fri 08:31:29]—[2023-03-21 Tue 14:12:26] => 101:40:57 :END:

NFA2DFA #compile

  • 任意状态从s0抵达的路径都是等价的？即是否满足无记忆性？

    • NFA不满足

  • 枚举可达状态？有穷？

    • 至可达状态不再增长终止

    • 由于任意s的{s}ˉ\bar{\{s\}}有穷，而s∈PNFAs\in \mathscr P_{NFA}有限

  • DFA简化

    • a,b可区别 iff 从a,b出发的可达路径集不同

      • PPT写的是(A,a,C)(B,a,D)a∈Σ∗(A,a,C)(B,a,D) a\in \Sigma^*且CD中只有一个可达。。

    • ∀a∈Σ,(A,a,x)(B,a,y),x=y\forall a\in \Sigma, (A,a,x) (B,a,y), x=y则AB状态相同（？）

奇怪的杂谈 #compile

  • runtime environment

    • var, mem loc

  • 黑龙江，20年前，高中应该人均学过映射吧？

  • 问：如何从regex串转化为NFA状转表？

    • 这不就是编译吗。。

    • 好家伙藏这儿呢，跳到算术式优先级了

正则表达式的局限性 #compile

  • {anbn∣n∈N}\{a^nb^n|n\in \N\}

  • 常见场景，如括号匹配

怎么串到离散数学的 #compile

  • 幺半群、代数系统

  • G△G=GG\triangle G=G 建立在图的幺半群上，数据结构的原理？

compile course 杂谈

  • 99 bottles of bears

  • Java GC refinement

  • GCD的更相减损、辗转相除、欧几里得算法

  • perl其实现在还有很多历史悠久的项目在用，比如postgresql里脚本生成对象化的C代码😋

  • shell类语言会guess缺失引号，潜在风险

  • imperative vs. declarative

#compile #tips

  • 泰勒展开：连续转离散

    • e.g. sin(x)sin(x)

  • #readings

    • Advanced Compiler Design Implementation（鲸书）
    • 龙书

DONE 作业二 ↗ #compile #homework DEADLINE: <2023-03-30 Thu> :LOGBOOK: CLOCK: [2023-03-25 Sat 22:03:32] CLOCK: [2023-03-30 Thu 10:34:21]—[2023-03-30 Thu 10:34:21] => 00:00:00 CLOCK: [2023-03-30 Thu 10:34:23]—[2023-04-04 Tue 19:27:22] => 128:52:59 :END:

https://github.com/dtcxzyw/cmmc/blob/main/docs/Compilers%20Three%20Easy%20Pieces.pdf ↗ #compile

  • 强烈推荐，绝佳教材，应该达到了研究生课程水平

MLIR as a Rewritable Graph Database ↗ 作者总结了为什么mlir当前无法直接用于db #DB #compile

compile
https://blog.graphorall.top/blog/compile
Author rubbishzyc
Published at December 8, 2024
Copyright CC BY-NC-SA 4.0
Buy me a cup of coffee ☕.

Jan 11th, 2026

contents