rt

#tool #recommended #scheme
https://www.biwascheme.org/test/tracer.html

https://github.com/duangsuse/BisonFlexCalc
#project 我试了整整一个上午才基本能正常开发的计算器啊...

Yacc 的文档很难理解，我看 GitHub 上 Yacc 语言的代码，勉强弄明白是怎么回事了... 差点连 PG 基础终结符和非终结符都搞混

... 理想到现实还是有区别的

BNF 到 Yacc 还是有区别的

https://github.com/ice1000/Ruiko.kt

这里也有个组合子，F# 的看不懂于是看这个.. 大概能看 #PL #CS

改天我打算拿 Kotlin 重写一遍这个（没错，当自己的了）（跑）

毕竟 RegularPP 有时候可能用得到（类似 [s:string] (<$> | <+>)? ）
虽然之前说可以使用 LALR，但现在也是搞不清楚他们都有何关系...

（现在左递归和 Monad 都搞不懂的话有点牵强了，不过还请允许我继续 Naive 的广播 🙈

Parser Combinator 在语法解析的当中处于怎样的位置? - 陈甫鸼的回答 - 知乎
https://www.zhihu.com/question/35778359/answer/64769298 #PL #CS

读后感（这次的其实就是摘录，因为我也没看完）

parser combinator 其实就是自顶向下分析算法的一种。所谓 parser combinator 和 parser generator 的区别，实际上就是将算法的状态表示为一个整数（Yacc/Bison 的做法）和一个类（ANTLR 的做法）的分别，看上去写法完全不同，然而写法并不决定表达能力

从算法角度上看，parser combinator 不牛，一点都不。从工程角度看，它有一些优点。

从算法上说，语法分析的思路分为自顶向下和自底向上两类。两者对输入文本的分类是类似的：它们都将输入划分为终结符和产生式（或者说，表达式），而区别在于遍历的方法：自顶向下方法通过获取向前数第 k 个终结符猜测整句表达式究竟属于哪个产生式并将后续展开进行后续计算；而自底向上方法通过不停地遍历终结符（所谓移进，shift），直到发现已经获取的终结符序列满足某一个已知的产生式，从而将已知的终结符序列合并成产生式（即所谓规约，reduce）。所以自顶向下文法的一个特征就是，它不能很好地支持左递归文法，因为自顶向下方法要求所有能够被它解析的文法，总是必须在前若干个终结符上看出区别，这也是所谓 ANTLR 的 LL(k) 文法中的 k 的含义。自底向上方法不受这个限制，相反地，为了能够处理二义文法，自底向上算法需要决定可以规约时应该继续看下一个终结符，还是选择直接合并产生式，这也就是 Yacc/Bison 里用的 LALR 算法著名的移进/规约冲突和规约/规约冲突

那么，parser combinator 是不是跳出两者之外的第三种方法？我们可以拿一个典型的 parser combinator 来做例子，即 Haskell 的 parsec。我不知道这里的朋友有多少熟悉这个库，只说一点。Parsec 的 <|> 操作符——它的右端要求必须是在左端出错并且没有接收任何输入的前提下，才会转入右端。这实际上就是说，它的左端和右端不能有公共左因子，而这一点，正是它支持递归下降文法的典型特征

我猜看到这里，熟悉 parsec 的朋友可能要拿 Try 算符来反驳我。然而 Try 算符的存在，恰恰说明 parsec 并不是以一致的方式处置语法规则的
Parsec 的 Try 和 Optional，它们都是通过在递归过程中增加一些回溯的操作来允许一定程度的回溯，从而获得更强的表达能力
由于 Haskell 运行时大量使用惰性求值和图规约技术，递归操作是相对低代价的，所以 Haskell 更能容忍深度的递归调用
但这是实现细节，而非算法差异。与之对比，Yacc/Bison 允许程序员自由书写左递归文法而不需要任何显式标注，这是它在算法层面处理能力更强的明证。

前面还有轮子哥的回答（大意）

Parser Combinator 是一种实现技巧，在讲理论的东西里当然不会提到它
正如同面向对象理论里面不会有《深入理解 C++ 对象模型》的东西一样

话说，最近我有好多天都没有写过 Java/Kotlin 了呢 😶

#media #cs 从零开始的简单光线追踪示例 - IceDust的文章 - 知乎
https://zhuanlan.zhihu.com/p/45335463

#recommended #China #school #PL #CS
浅谈国内高校编程语言教育 - 啥玩应啊的文章 - 知乎
https://zhuanlan.zhihu.com/p/43914842

#CS #media #backend 有哪些让你目瞪口呆的 bug？ - 叛逆者的回答 - 知乎
https://www.zhihu.com/question/21747929/answer/498345137

"dirty region"

CSAPP第六章矩阵乘法缓存友好案例的实际测试疑问？ - 彭飞的回答 - 知乎
https://www.zhihu.com/question/295567230/answer/496041685

因为题主用错了profiler 工具。你用的是tracing profiler，它的用途是准确分析大型复杂程序的函数调用，但缺点是会拖慢程序（甚至修改程序代码）。对于这种小程序，没什么复杂的函数调用关系，且性能差异来自缓存的程序，应该使用hardware sampling profiler，最常用的是Intel VTune

树状数组的原理是什么？ - 后缀自动机·张的回答 - 知乎
https://www.zhihu.com/question/54404092/answer/139192487

非常抱歉每次都这样几乎是全文转载别人的知识，我知道这可能不好，但还请包容一下
如果以后 Stiack Note 成功做出来，这些就不会发在频道上了

我假设你知道啥是 lowbit

大前提：设节点编号为 x ，那么该节点维护的值是 (x - lowbit(x), x] 这个区间的和

现在我们分两步来分析

1. 查询
因为查询比较简单所以我就先讲查询为什么 work
先上 query 的代码

int query(s, usize index) {
  int ans = 0;
  while (index != 0) {
    ans += s[index];
    index -= lowbit(index);
  }
  return ans;
}

注意到某个点后面的值是肯定不会影响树状数组上这个点的 sum 的，那么因为我们每次取的是一段后缀，然后每次取的节点所覆盖的区域是是不重合的，所以正确性是显然的。

复杂度的话，可以发现我们每次取的lowbit是逐渐变大的，因为一个数二进制下只有 log 位，所以复杂度是 O(log(n)) 的

2. 更新
设我们更新的点的编号是 x
首先对于一种 lowbit，最多只有一个点可以覆盖 x（证明留作练习
因为一共只有 log(n) 种lowbit，所以我们可以枚举 lowbit
设 lowbit = 2^{k}

如果存在某个位置的lowbit = 2^{k}，而且他可以覆盖x的话，那么他的形式肯定是

000……0001aaaaaa

即前面是k-1个0，第k位是1，第k位之后必定每一位都和x相同（想想为什么）

现在我们分情况讨论：

2^k < lowbit(x)，显然不可能，因为这种情况覆盖不到x
2^k = lowbit(x)，这个肯定是可以的
2^k > lowbit(x)，这里有两种情况

x的第k位为0
那么根据我们上面构造的编号，他本身肯定比x大，但是他减去2^k会比x小（因为低位全部置零，而且这一位大于lowbit(x)，所以减去2^k之后在lowbit(x)这位小于x，所以这种case构造出来的编号是合法的

x的第k位不为0
那么构造出来的编号比x小（想想为什么

void update(s, usize index, int value) {
  while (a <= INT_MAX) {
    s[index] += value;
    index += lowbit(index);
  }
}

仔细观察可以发现，这个函数的作用就是每次求出下一个lowbit并且把之前的位都清零，并且保持了后缀不变嘛

每次加 lowbit 相当于清掉了若干个 1，并把碰到的第一个 0 的位置为 1（这就是进位的过程）

#book 《Streaming System》 （分布式流系统）《High Performance Spark》（大数据平台）

在游戏的发展历史中，出现过哪些有意思的加密反盗版机制和破解机制？ - Zign的回答 - 知乎
https://www.zhihu.com/question/46773069/answer/463741166

#Haha #recommended #tech #old #reveng #backend

+ 软盘激光加密
+ Int3争夺战
+ PSP的GTA破解
+ PSP的电池破解
+ Wii的破解