作者： 956237586

20221015新nas&私有云实验环境规划

背景

因原群晖已经试用了3年并且是单盘，考虑到数据风险决定对它做升级。本来在B站无情开评看到的FusionCube 500完美满足我的需求，但询问售价后果断放弃hhhhh根本不是个人用户能玩得起的设备。但也是因此机缘巧合发现无情开评居然承接个人业务需求，他们负责硬件组装和虚拟化平台配置，服务周到省心省力，欢迎有兴趣但懒得自己折腾的同学联系他们帮忙，比自己折腾要方便的多。就这样我又多了一台服务器，在到货之前提前设计下网络结构和软件结构

目标

1.保证家里其他人的IPTV、无线设备的正常使用，即使服务器挂掉也不应该影响原有网络结构

2.加强nas上数据的安全性，重要数据利用nas自带功能备份一份到新的服务器上

3.创建新子网3和4，子网3与光猫相连赋予公网访问权，子网4和公网隔离但能通过子网2访问，虚拟化一个软路由方便控制子网3和4下虚机

4.剩余资源搭建一个分布式的私有实验环境放到子网4，满足我对开源软件和分布式软件开发和测试的需求，解放我的台式机。后面也许就有机会做各种实验了

5.基础网络安全防护，内网随意折腾但从公网无法轻易穿透到内网

 

网络结构设计

现网络结构

相关设备如下，为了网络安全不暴露具体设备型号信息

1.光猫

2.无线路由器

3.群晖nas

4.iptv

5.手机、电脑、平板等无线客户端

目前nas上和一个台式机上运行着tailscale，配合ipv6可以让我随时从公网穿透回子网2做操作，虽然麻烦了点但足够安全。

其余需要对外暴露的端口均通过光猫和无线路由器人工配置端口和协议范围，可以满足公网上手机和电脑对nas的访问需求

新网络结构

看了下服务器文档，有4个千兆口/可选两个万兆口，如果实际到货有2个以上接口的话，可以考虑把nas改为接到服务器下面，剩下的接光猫使用，（为了nas稳定使用还是算了，等服务器运行稳定了再考虑把nas挂到服务器下面用软路由精细控制流量）

nas本身的加强因预留了足够的磁盘空间，并且无情开评会帮忙配置好磁盘阵列，因此我只需要划一部分空间给nas就行了。这部分既可以开个linux，也可以到时候优先看看能不能直接在ESXI里通过iSCSI搞定。这样还可以继续使用群晖正版系统，虽然理论上可以把我的白群转到虚拟化里做”黑”群，但我懒得折腾还是算了，等nas的磁盘坏了再考虑

个人电脑都在子网2下操作子网4的路径待设计，想避免出现网络故障还要满足子网4一定的隔离和访问需求，不是网工专业的我设计这玩意真的头疼= = 实在搞不定到时候再问问同学吧hhh

服务器的管理口和esxi的管理口都放到子网2下

服务器软件集群设计

TODO

群晖扩容

远程磁盘创建

TODO in ESXI

远程磁盘挂载

群晖本身的DSM只看到了FTP SFTP WebDav CIFS NFS这几种协议来远程挂载，没看到能把DSM当作iscsi的客户端的，网上能找到的资料都是把DSM当作iscsi服务器来使用。之所以选择iscsi是因为不想再创建一个虚拟机来提供FTP SFTP WebDav CIFS NFS这些协议转换，尽可能使用ESXI本身的虚拟化能力，减少后期维护成本

但尝试登陆群晖命令行后执行iscsiadm 是可以的，因此将尝试直接用命令行挂载

TODO

 

20220908编译原理读书笔记

 

 

 

20220908编译原理读书笔记
前言

为啥我今天又开始读书了呢？是因为昨天拔牙之后持续的疼痛让我无法集中注意力工作，但睡觉也是有限度的，否则结果就是3点多还睡不着，依然煎熬。这种疼痛不剧烈但持久，让又人无法忽视。。。。简直是煎熬
还是找点事情分散下注意力吧，某博建议刷114514的题并没有找到这个题号（逃
还是读书吧，也许在我全神贯注的打字时可以让编译原理的复杂性来减轻我的精神负担

4. 自顶向下语法分析方法

语法分析分为自顶向下和自底向上的语法分析，还可以分为确定分析和不确定分析
本篇为确定的自顶向下分析
这种分析也成为面向目标的分析方法

4.1. 思路

从开始符号，根据当前的输入符号，寻找唯一确定的产生式，替换非终结符
如果输入的符号在满足<使用某个生成式的条件>，则就使用这个生成式
简易想法是，给每个生成式生成互不相交的符号集合，根据当前输入在哪个集合里就选取哪个生成式
这个想法贯穿到最终的SELECT集合定义，书本没说，这里提前提出方便理解FIRST集和FOLLOW集的由来
注意，这里的符号不再是单一字母，而是经过词法分析输出的token串，英文为symbol

例1 文法G1[S]：
S->pA|qB
A->cAd|a
B->dB|b
给定输入串W=pccadd，注：教科书这里其实是为了简化，所以用的都是单字母，实际一个字母对应一个symbol

推导过程显然为S->pA->pcAd->pccAdd->pccadd

例2 文法G2[S]：
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
给定输入串W=ccap

推导过程为S->Ap->cAp->ccAp->ccap
第一步选择S->Ap的原因为A->cA的右侧存在c开头的非终结符
人肉还可以比较容易的看到，但对机器来说不那么容易，需要总结规则
因此如果能知道S->Ap的第一个非终结符是什么就好了
因此定义FIRST集合如下：
设G=(Vt,Vn,P,S)是上下文无关文法
FIRST(t)={t|t=>* aq, t ∈ Vt, t,q ∈ V*}
称FIRST(t)为t的开始符号集或首符号集

给定文法G[S]：
S->aA
S->d
A->bAS
A->NULL
给定输入串W=abd
S->aA->abAS->abNULLS->abNULLd
当面临输入d时，因A的FIRST集里只有b和NULL，不包含d，因此只能认为d的匹配依赖于A后面的符号，因此选择A->NULL
同理找规律，如果我们可以直接知道d可以是A后面首个终结符，那是不是就可以直接选取确定的一个生成式了？
FOLLOW集定义也就是这样，数学表达比较抽象，懒得打了
结合FIRST和FOLLOW集合即可定义SELECT集合，前面的数学证明可保证生成的SELECT集合互不相交

设G=(Vt,Vn,P,S)是上下文无关文法
给定产生式A->t,A是终结符，t属于V的*闭包
若t无法推出空NULL，则SELECT(A->t) = FIRST(t)
显然嘛，没有空的干扰，就直接是第一个非终结符
若t可以推出空NULL，则SELECT(A->t) = (FIRST(t) – {NULL}) ∪ FOLLOW(A)
这个也好理解，排除掉NULL的干扰后，再继续往后寻找A后面的第一个非终结符就行了

LL1文法指的是，从左L到右扫描使用最左L推导，每次往后看1个符号
条件是，对于相同非终结符的两个产生式A->t A->q, 满足SELECT(A->t)∩SELECT(A->q) = {空集}

对于FIRST FOLLOW SELECT集合的生成，纯粹就是力气活了。。。细节不再赘述，相信编程能力过关的同学都能正确实现，这里说思路。可能需要多次扫描才能完成
1.求出能推出NULL的非终结符
2.计算FIRST集合，这里可以根据定义计算，使用迭代法使得每个FIRST集合不再增大即可结束
也可以使用图论的算法计算，思路类似，在图上使用增广做标记即可
3.计算FOLLOW集合，同理也是根据定义计算，使用迭代法使得每个FOLLOW集合不再增大即可结束
也可以使用图论的算法计算，思路类似，在图上使用增广做标记即可
4.计算SELECE集合，根据前面的计算结果合并生成

4.3 非LL1文法到LL1文法的等价变换

4.3.1.提取左公因子

4.3.2.消除左递归

4.4 不确定性的自顶向下分析

略
mark
当前86页

 

国内运行coder的坑

https://github.com/coder/coder

git clone && cd coder

在docker-compose.yaml中给postgres增加privileged: true，防止数据库出错

export CODER_ACCESS_URL=http://YOUR_IP:7080

docker-compose up

启动后注册

找个客户端安装coder的cli后按https://coder.com/docs/coder-oss/latest/templates创建模板

先用bare测试，执行coder template create后会报错

bare的模板上传后会报错，进容器

ps aux 可以看到执行了 /tmp/coder-cache/terraform init -no-color -input=false

通过ps aux获取PID后执行 ls -hal $PID/cwd

可以看到在provisionerd开头的文件夹下有客户端上传的文件，趁着失败之前复制走好手动测试

可以看到国内的网络执行terraform init一定会卡，fuck

参考这些尝试中

https://cloud.tencent.com/developer/article/1987762

https://developer.aliyun.com/article/713099

https://developer.aliyun.com/article/723935

 

coder实现了terraform的provider，来管理自己的资源

https://github.com/coder/terraform-provider-coder

20220731lamda表达式中的方法调用识别

psi过滤直接用JavaRecursiveElementVisitor过滤PsiMethodCallExpression会发现只识别到了collect的调用

因为JavaRecursiveElementVisitor的逻辑是当一个节点满足要求后，下一个继续的节点是nextSibing

因此需要增加特殊逻辑，当第一层PsiMethodCallExpression被匹配到后，需要递归在PsiReferenceExpression继续寻找，需要把PsiReferenceExpression+PsiReferenceParameterList中的lamda表达式以及其中的方法调用和方法引用都找出来，这里只写方法调用，方法引用也是一样的套路

 

不知道jetbrains有没有类似的工具类做这种深度搜索，代码太多了懒得看，就先这么写着，附语义树如下

完整代码，更新中

20220721数据库基础-谓词逻辑转写sql

20220721数据库原理
同事在学数据库，问我这个题，重新总结下我上学时候的经典套路
这个套路针对任意存在性和任意性判定的sql编写或集合运算，当时数据库老师疯狂改题目条件，导致sql毫无规律且从字面含义上难以正向理解运算逻辑。为了考试以不变应万变总结了这个套路，核心思想是不要纠结于最终sql的语法表达，而是通过逻辑化简来确保集合元素的正确性，化简后再转写成sql
主要运用集合论、关系代数基础以及离散数学的谓词逻辑，这些应该是我要做sql自动生成和优化的理论基础
题目经典的三张表如下
学生表s(sid,sname)
课程表c(cid,cname)
选课关系表sc(scid,sid,cid)
求至少学过lz同学学过所有课程的同学的学号
编写过程如下
首先做形式化表达和逻辑化简,原则：逻辑取反极可能少，尽可能使用存在性判断
谓词逻辑定义f(x,y) = 学生x选择了课程y
{x|对任意y,f(lz,y)->f(x,y)}
–逆否命题
{x|!(存在y,!(f(lz,y) -> f(x,y)))}
–蕴含等值 p->q === !p||q
{x|!(存在y,!(!f(lz,y) || f(x,y)))}
{x|对任意x,!(存在y,!(!f(lz,y) || f(x,y)))}
–等价替换
{x|!(存在y,(f(lz,y) && !f(x,y)))}
{x|对任意x,!(存在y,(f(lz,y) && !f(x,y)))}
–对任意x
select sc.sid from sc where 1=1
— f(x,y)
exists (
    select * from sc where sc.sid = x and sc.cid = y
)
— f(lz,y)
exists (
    select * from sc where sc.sid = ‘lz’ and sc.cid = y
)
— 存在y, (f(lz,y) && !f(x,y))
exists (– 存在y, 取y = sc1.cid  看作是定值，但要注意给表加别名
    select sc1.cid from sc sc1 where exists (
        select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid –f(lz,y)
    )
    and not exists ( –!f(x,y)
        select * from sc sc3 where sc3.sid = x and sc3.cid = sc1.cid
    )
)
— 对任意x, 取x = sc0.sid
select * from sc sc0 where not exists (
    select sc1.cid from sc sc1 where exists (
        select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid
    )
    and not exists (
        select * from sc sc3 where sc3.sid = sc0.sid and sc3.cid = sc1.cid
    )
)
— 从来没有人告诉我存在这样一个化简的过程，这个方法多年间也未曾见到有人和我讲过，以上中间过程我翻遍了互联网也没找到。这是我上学时候应对考试用的通解套路，工作后好久没这么详细的写过sql转写了，简单的业务都是直接写sql结果而快忘却了正确的通解解法
— 在exists内select sc1.cid和select *是一样的，判定结果只看行数，但语义完全不一样，如果是从谓词逻辑转来的不应该都是*
— 另外，从exists子句转为where子句是容易的，反过来理论上也一样，但网上的所谓教程根本不会讲这个是怎么来的
— 因子句存在永真式sc1.cid = sc1.cid 且 存在性判定可由where条件代替一次子查询
— 所以接下来才是你在网上轻易看到的答案格式，也就是课本或老师PPT给的的答案
exists (– y sc1.cid
    select sc1.cid from sc sc1 where sc1.sid = ‘lz’ and sc1.cid = sc1.cid –f(lz,y)
    and not exists ( — !f(x,y)
        select * from sc sc2 where sc2.sid = x and sc2.cid = sc1.cid
    )
)
–投影输出结果
select sc0.sid from sc sc0 where not exists (
     select sc1.cid from sc sc1 where sc1.sid = ‘lz’ and not exists (
        select * from sc sc2 where sc2.cid = sc1.cid and sc0.sid = sc2.sid
    )
)
–等价答案
— {x|对任意x,!(存在y,!(!f(lz,y) || f(x,y)))}
exists (– 存在y, 取y = sc1.cid  看作是定值，但要注意给表加别名
    select sc1.cid from sc sc1 where not(
        not exists (
            select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid –f(lz,y)
        )
        or
        exists ( –f(x,y)
            select * from sc sc3 where sc3.sid = x and sc3.cid = sc1.cid
        )
    )
)
— 对任意x, 取x = sc0.sid
select * from sc sc0 where not (
    exists (– 存在y, 取y = sc1.cid  看作是定值，但要注意给表加别名
        select sc1.cid from sc sc1 where not (
            not exists (
                select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid — f(lz,y)
            )
            or
            exists ( — f(x,y)
                select * from sc sc3 where sc3.sid = sc0.sid and sc3.cid = sc1.cid
            )
        )
    )
)
— 投影输出略
— 语义分析
sc0.sid = sc2.sid的子查询条件字面意义上是扫描了sc的每一行来分别做两次集合的存在性判定
第1行数据执行
id sid cid
sc0 1 lz 1
select sc0.sid from sc sc0 where not exists (
    select * from sc sc1 where sc1.sid = ‘lz’ and not exists (
        select * from sc sc2 where sc2.cid = 1 and ‘lz’ = sc2.sid
    )
)
select sc0.sid from sc sc0 where not exists (
    select * from sc sc1 where sc1.sid = ‘lz’ and not true
)
select sc0.sid from sc sc0 where not exists (
    empty
)
select sc0.sid from sc sc0 where true
1 lz 1输出
CREATE DATABASE test;
use test;
CREATE TABLE sc (
    id int(11) PRIMARY KEY NOT NULL AUTO_INCREMENT,
    sid varchar(255),
    cid varchar(255)
);
INSERT INTO sc(sid,cid) VALUES
('lz', '1'),
('lz', '2'),
('a', '1'),
('b', '2'),
('c', '1'),
('c', '2'),
('c', '3')
;
SELECT * FROM sc;
+----+------+------+
| id | sid  | cid  |
+----+------+------+
|  1 | lz   | 1    |
|  2 | lz   | 2    |
|  3 | a    | 1    |
|  4 | b    | 2    |
|  5 | c    | 1    |
|  6 | c    | 2    |
|  7 | c    | 3    |
+----+------+------+
7 rows in set (0.00 sec)

20220628编译原理读书笔记

 

 

 

 

20220628编译原理读书笔记

2.5 上下文无关文法及其语法树

给定文法G=(Vn,Vt,P,S)
语法树又称推导树，定义：
1.每个节点都有一个标记属于V
2.根节点是S
3.若一个节点n至少有一个它自己除外的子孙A，则A肯定属于Vn
4.若节点n的直接子孙从左到右为n1,n2,…n，则n=>n1,n2,…n是P中的产生式

推导过程不唯一
若每一步都是对左部最左的Vn替换则称为最左推导，反之是最右推导
形式语言中最右推导被叫做规范推导，所得句型叫规范句型或最右句型

若一个文法存在多个语法树，则称这个文法是二义的
判定给定的上下文无关文法是否是二义的，或它是否产生一个先天二义的语言，这两个问题递归不可解

2.6 句型分析

自顶向下、自底向上

3 词法分析

虽然词法和语法可以同时放到文法描述里，但一半实现时候都是独立做词法分析

常见分类
标识符、字母数字、整数、运算符、等号、界符

正则表达式可以方便的描述词法规则，且正则表达式和正规文法都能定义语言，且有时候表达更加方便

如
A->xB,B->y => A = xy
A->xA|y => A = x*y
A->x, A->y => A = x|y

3.4 有穷自动机

确定的有穷自动机DFA,不确定的有穷自动机NFA
M=(K,M,f,S,Z)
K:有穷状态集
M:有穷字母表
f:转换函数，是K和M的笛卡尔积到K上的映像，用来定义状态转换条件
S:唯一的初态
Z:终态集合，是K的真子集

这里歪个楼，画状态转换图一定要有这几个元素，工作这么久很少见有人完全画对。初始要有一个箭头指向S，Z上的元素要有双层圈标记，每个线段代表转换规则，线上要有M元素的标记

NFA区别就是转换函数在特定状态上可以不唯一
NFA有算法可以转DFA，核心思想是构造确定性的子集

DFA化简，计算入度为0的状态可删除、计算等价状态合并多余的状态

3.5 正则表达式和有穷自动机的等价性

结论是等价，证明略，因此用正则表达式可以直接描述状态机，状态机的实现可由特定算法自动生成结构完整

3.6 正规文法和有穷自动机的等价性

结论是等价的，证明略，经过前面的铺垫，为自动化打下了良好的理论基础

3.7 词法分析器的自动构造工具

这可能是正常途径下接触到的第一个元编程吧。。。。
由前面的铺垫可知，既然等价，那就可以直接用程序生成程序，人工提供规则即可

这里歪个楼介绍下正则表达式基础，其实如果你手写练习过一些正规文法的生成式，就知道正则表达式多简洁了。因为这个概念是数学集合论的，因此正则表达式的写法也和集合闭包几乎一样，掌握基础并不困难

r* 匹配r的星闭包，r出现0次到多次
r+ 匹配r的正闭包，r出现1次到多次
r? 匹配r的任选，r出现0次或1次
r{n} 匹配r的n次幂，r出现n次
r{m,n} 匹配r的m到n次幂，r出现m次到n次闭区间
r{m,} 匹配r的m次幂以上，r出现m次以上闭区间
rs 匹配r和s的连接
r|s 匹配r和s的并集
其余写法均为简写，常见的就这几个

借助lex描述文件可以目标结构的c语言代码，完成词法分析器的自动生成
类似的工具不唯一，可以看看antlr

第4章到第6章都是语法分析的各种方法，有点懒得看了，总之结果是个语法树
我关心的是第7章语法制导的语义计算
也许是明天继续？
mark当前68页

 

20220622编译原理读书笔记

 

 

 

20220622编译原理读书笔记

1.引论

基础知识和概念，不细说
编译程序的定义：语言翻译程序
编译程序的功能：源语言程序翻译为目标语言的等价程序的程序（按这个定义是不是能算元程序了hhhh生成程序的程序）

编译过程：
词法分析：源程序->单词（符号、单词符号、token）序列
语法分析：token序列->语法树
语义分析：语法树->语义树、图 这个阶段才有类型检查
中间代码生成：就是字面意思
代码优化：无效代码删除、优化
目标代码生成：翻译到目标语言

前端：到中间代码之前的部分，与目标语言和平台无关
后端：中间代码到目标代码的部分，与源语言和平台无关
编译过程可以是一遍或多遍扫描源码完成

解释执行和编译执行
解释执行不需要完整的源码，编译执行需要完整编译后才能运行

EBNF：扩展的巴克斯范式

练习题
else没有匹配的if，语法分析阶段检查
数组下标越界，语义分析阶段检查或代码生成阶段，甚至运行时才知道
使用的函数没有定义，语义分析阶段检查
数中出现非数字字符，词法分析阶段检查

2.文法和语言

程序设计语言是记号系统，完整定义包含语法和语义

语法只定义怎么写，不管含义例如a=b+c是合法的表达式，但如果c未定义，语法检查是检查不出来的
语义分为
静态语义：类型匹配检查，在满足语法限定的情况下，什么样的写法是合法的
动态语义：变量作用域检查，表明程序要做什么

文法：用来定义语法的工具
语义：目前（书上说没有，实际不知道）没有公认的形式系统可以用来自动构造正确的编译系统
形式语义学：这个可以再查查资料，对这个比较好奇，这本书居然不讲

文法：用有穷规则集合表示句子的无穷集合，描述语言的语言，所以也叫元语言
规则：左侧符号=>右侧符号序列，=>表示使用左侧符号可以产生右侧符号

字母表：符号组成的集合，所以也叫符号集，这里的符号层次就是字母、数字、标点之类的类型，不是token.符号这个词的含义在不同语境下会容易混淆，因此尽量避免，一般意思是token
符号串：有穷的符号序列，允许为空

表示法
若符号串x中有m个符号，则|x|=m
连接，x=臻臻,y=真厉害,xy=臻臻真厉害
方幂，x=臻ab,x^0=空,x^2=臻ab臻ab
符号串集合:乘积定义为两个集合元素的连接运算，区分先
对字母表C，C的闭包表示C上有穷长串的集合，也就是C^0∪C^1...C^n
排除C^0后的集合称为正闭包

2.3 形式定义

规则又称重写规则、产生式、生成式
写作A::=B或A=>B，A是左部，B是右部

文法G定义为(Vn,Vt,P,S)
Vn:非终结符(语法实体、变量)集合, 这里的符说的是抽象定义，也就是终结符有限集的划分
Vt:终结符集合，注意这里的符是字母那个层次的
P:规则集
S:识别符、开始符

因此这里的文法主要是词法分析使用，最终Vn的闭包将作为产物给语法分析（上学时候就糊涂，希望这次没说错

2.4 文法类型

文法G定义为(Vn,Vt,P,S), 产生式为a=>b
0型:a和b均属于V=Vn∪Vt的闭包 且a至少含有一个非终结符
特性：递归可枚举、能力等价于图灵机
1型：上下文有关，除S->空以外，|b|>=|a|。
另一种描述 aBc=>aDc(D不为空)，更能描述上下文，仅B出现在ac这种上下文时才能替换成D
2型：上下文无关，a是非终结符，b属于V的闭包
另一种描述 A=>B,A属于Vn，也就是取代A的时候无需关心A的上下文
3型：正规文法，产生式形如A=>aB或A=>a，A,B属于Vn，a属于Vt的闭包

定义限制是逐层增加的，因此满足3型的一定满足2、1、0
上下文无关说的是生成式看起来上下文无关，所以实际上上下文无关文法都是上下文有关的hhhh

例如C → a b 这条规则将一个单独的非终端符 C 变换为两个连续的终端符 “a b”
“a b” 这个序列能出现在什么位置是由右部出现 C 的其他规则决定的，只能出现在特定的上下文中，因此是上下文有关的。

明天继续2.5语法树
往后翻了翻终于知道为啥上学的时候糊涂了，第二章讲完了文法，第三章退回到词法了，所以概念理解上很容易乱
mark当前26页