@FYFX 词法分析有上下文相关的吗？

@lmshl
@ericmzhu
@ysc3839
@FYFX

编译原理新手求问，你们咋写词法和语法分析呢？


比如下面这条，你们词法分析结果是啥呢？

{options:1:yes:tag-info,2:no:tag-danger}


这样吗？

<{,左括号><options,关键字><:,冒号><1,数字><:,冒号><yes,字符串>……<},右括号>


那你们文法咋写呢？

1. 键值对 ::= 关键字 ":" 『？？？』

2. 多个键值对 ::= 键值对 | 键值对 "," 多个键值对

3. 对象 ::= "{" 多个键值对 "}"

@sutra 我看 regex101 说，golang 的正则不支持断言，条件子组也不支持。你这是用了第三方库是嘛

每匹配一个字前，都要看看后面的是否是一个关键字，我总觉得性能消耗会大一点

另外，我老怀疑你『?!:』写错了……

@morri 你试试这个：

\s*"?(options)"?\s*:\s*"?((?:[^,]*?:[^,]*?:[^,]*?,?)*)"?\s*([,}])|\s*"?(\w+)"?\s*:\s*"?(.*?)"?\s*([,}])

『要求』

1. options 键的值，为若干个以『,』分隔的 value:label:class （每个字段都不包含『,』）

2. 其他键的值不包含『,』『}』

3. 头尾裹上『"』后（若已有则不裹）仍符合 json 字符串规范

@morri 那你要给出各字段值的特点才行啊

否则产生的歧义，怕是连人工都分不清：

{options:1:yes:tag-info,2:no:tag-danger,label:用户 id,searchType:1,hide:1,disabled:1,required:1}

也可以认为是：

{"options": "1:yes:tag-info,2:no:tag-danger,label:用户 id,searchType:1,hide:1,disabled:1,required:1"}

@ranxi 描述改个不停。。不如放几行数据出来

我还是觉得 sqlite 足够你用，几行的事

下载个 sqlite3.exe （ 1~2MB ）就能用，也不用管理员权限，内存占用也随你设，1MB ，1GB ，都行

xml 也很好解决，xmlstarlet

@morri 临时学了下 golang ，看起来运行没问题

『源码』

package main

import (
　　"fmt"
　　"regexp"
)

func main() {
　　 str := `{
　　　　"label" : {label} ,
　　　　 searchType : "hide_222" ,
　　　　"hide" : 333 disabled ,
　　　　 disabled : "required" ,
　　　　"required" : "options" ,
　　　　 options:1:yes:tag-info,2:no:tag-danger
　　}`
　　 re := regexp.MustCompile(`\s*"?(options)"?\s*:\s*"?(.*?)"?\s*(})|\s*"?(\w+)"?\s*:\s*"?(.*?)"?\s*(,)`)
　　 fmt.Println(re.ReplaceAllString(str, `"$1$4":"$2$5"$3$6`))
}


『输出』

{"label":"{label}","searchType":"hide_222","hide":"333 disabled","disabled":"required","required":"options","options":"1:yes:tag-info,2:no:tag-danger"}

#1 说这是 golang ？在 regex101 看了下，支持的正则特性有点少。。

反正不要求通用方案，那就随便写咯


『模式匹配』

\s*"?(options)"?\s*:\s*"?(.*?)"?\s*(})|\s*"?(\w+)"?\s*:\s*"?(.*?)"?\s*(,)


『全部替换为』

\"$1$4\":\"$2$5\"$3$6


『要求』

1. 除了 options 外，其他键的值不包含『,』（锚定键值对结束）

2. options 键在最后一位，其值不包含『}』（锚定键值对结束）

3. 头尾裹上『"』后（若已有则不裹）仍符合 json 字符串规范

　（如：『 key: 他说"xxx"，我不以为然』变成『"key": "他说"xxx"，我不以为然"』会出问题）


『例子』

原文：

{
　　"label" : 用户 id ,
　　 searchType : "1" ,
　　"hide" : 1 ,
　　 disabled : "1" ,
　　"required" : "1" ,
　　 options:1:yes:tag-info,2:no:tag-danger
}

替换后：

{"label":"用户 id","searchType":"1","hide":"1","disabled":"1","required":"1","options":"1:yes:tag-info,2:no:tag-danger"}

噢，还有个操作二

$ jq '[.data[] | select(.age | tonumber > 1)][0]' test.json

{
　"name": "name2",
　"age": "2"
}

用过 jq ，语法是有点绕，功能还算凑合。好像是没有交互，自然也没有补全


$ jq '.data[].name' test.json

"name1"
"name2"
"name3"


$ jq -r '[.data[].name]' test.json

[
　"name1",
　"name2",
　"name3"
]

@krixaar 不知为何不考虑数据库，权限不足？不熟悉？

连 1MB 、无需额外进程 的 SQLite 也要排除。。

那上面提到的大数据平台就更离谱了


眼拙，丝毫没看出原来是在讽刺

其他做得好的类似软件，是如何存储这些小文件的？数据库？

SQLite 确实提到过，数据库中存储小文件，可比文件系统快 35%，减少 20% 磁盘占用

https://sqlite.org/fasterthanfs.html

@krixaar 这个开销有点大噢

比如 Linux ext4 ，每个文件所需的一个 inode 要 256 字节（存各种属主、权限、时间信息，还有数据分布在哪儿等），

且不说应该不会预留几亿个 inode 可用，光是建一亿个文件就要 23.8 GB 的 inode ，还没算目录……

以及长文件名、特殊符号等其他问题

那还不如用数据库呢，MySQL 的 innodb 下，一行数据仅额外需要至少 18 字节（存事务、回滚信息等），SQLite 更少

若这个表的 B+树 3~4 层高，前两层容易缓存至内存，那么翻译一行数据一般只需额外读取 1~2 次硬盘，绝对比文件系统开销小

@ranxi 可以试试用 sqlite ，几行搞定 导入+翻译+输出，感觉速度应该也不慢


1. 生成 O2.txt （从小写字母，映射至大写字母，共 26 行）

printf "%s\n" {a..z} | sed 's/^.*$/&\t\U&/' | tee O2.txt

『输出』
a 　　 A
b 　　 B
…　　…
z 　　 Z


2. 生成 O1.txt （也是 26 行，字段内容是：主键 ID 、预期转换成啥样、待转换内容）

printf "%s\n" {a..z} | awk -v OFS=$'\t' '{print NR, toupper($0), $0}' | tee O1.txt

『输出』
1 　　 A 　　 a
2 　　 B 　　 b
…　　…　　…
26 　　 Z 　　 z


3. 导入映射表至数据库

sqlite3 -tabs O2.db 'CREATE TABLE O2 (key PRIMARY KEY, value) WITHOUT ROWID' '.import O2.txt O2'


4. 逐行查数据库进行翻译

4.1 为 SQLite 启用 csv 扩展

①下载 csv.c： https://www.sqlite.org/src/file?name=ext/misc/csv.c&ci=tip
②编译扩展：参考 https://sqlite.org/loadext.html

4.2 翻译

SQLITE_CSV_LIB_PATH='./csv' # 编译好的 CSV 模块库路径（可省略后缀）
SQLITE_CACHE_SIZE_MB=512 # 数据库最大缓存页面大小（单位：MB ）

# sed -E 's/"/""/g; s/^|$/"/g; s/\t/","/g' O1.txt |
tr '\t' ',' < O1.txt | # 制表符 转成 逗号（要求 O1.txt 每列内容，都不包含『"』『,』，否则用上面那行）

sqlite3 -tabs O2.db \
　　".load $SQLITE_CSV_LIB_PATH" \
　　"PRAGMA cache_size = -$((SQLITE_CACHE_SIZE_MB << 10))" \
　　'CREATE VIRTUAL TABLE TEMP.O1 USING csv(filename="/dev/stdin", columns=3)' \
　　'SELECT O1.c0 id, O1.c1 expect, O2.value replaced FROM O1 LEFT JOIN O2 ON O1.c2 = O2.key'

『输出』
id 　 expect 　 replaced
1 　　 A 　　 A
2 　　 B 　　 B
…　　…　　…
26 　　 Z 　　 Z

再来个 json 版的：

jq -r '
　　 def work($obj; $path):
　　　　 if ($obj | type) == "object" then
　　　　　　$obj | to_entries[] | (
　　　　　　　　$path + .key + "/",
　　　　　　　　 work(.value; $path + .key + "/")
　　　　　　)
　　　　 elif ($obj | type) == "array" then
　　　　　　($obj[] | work(.; $path))
　　　　 else
　　　　　　($path + $obj + "/")
　　　　 end;

　　 work(.; "./")
' <<< '
{
　　"考研资料": ["数学", "英语", "电影"],
　　"音乐": {
　　　　"华语": ["周杰伦", [[["张震岳"]]]],
　　　　"粤语": "Beyond"
　　}
}' | tee /dev/stderr | xargs -d $'\n' mkdir

输出并创建：

./考研资料 /
./考研资料 /数学 /
./考研资料 /英语 /
./考研资料 /电影 /
./音乐 /
./音乐 /华语 /
./音乐 /华语 /周杰伦 /
./音乐 /华语 /张震岳 /
./音乐 /粤语 /
./音乐 /粤语 /Beyond/

仅捕获想要的字符串：

[^.]*$

$ sed 's/^.*\.//' <<<'dkfj.wer.dkfjj.sldkf'

输出：
sldkf

@ranxi 按理说你都能用 python 了，sqlite 是内置的标准库，应该是用得了的

# 根据 O2 构造 hash 表（字典）
with open(r'O2.txt', encoding='utf-8') as fp:
　　 table = dict((row.split('\t') for row in fp))

# O1 逐行替换并输出
with open(r'O1.txt', encoding='utf-8') as in_fp, open(r'out.txt', 'w', encoding='utf-8') as out_fp:
　　 for row in in_fp:
　　　　 cols = row.split('\t')
　　　　 cols[2] = table[cols[2].rstrip('\n')]
　　　　 out_fp.write('\t'.join(cols))

内存若不够，考虑构造 hash 表时，仅将 hash(str) 作为键名，然后 cols[2] = table[hash(cols[2].rstrip('\n'))] ？

有意思，也来写个 bash 版的

1. 默认去除前面的 1.1.2 、doc.math 之类的键名
2. 允许不按顺序指定目录，如此顺序可打乱：1 、1.1 、1.2 、1.2.1 、1.2.2
3. 父目录不存在，会在另一指定地方创建：1 、1.2.1 （不存在 1.2 ，所以 1.2.1 不会在 1 之下）

#!/bin/bash

declare -a SEP=('.' ' ')
declare -r WORK_DIR='./'
declare -r DANG_DIR='./dangling/'
declare -r EXCLUDE_KEY=yes # 若要包含 1.1.2 之类的键名，设为空字符串

declare -A dict=([${SEP[0]}]=$WORK_DIR)

sed '/^$/d' <<EOF | sort |
doc.eng 英语
doc 考研资料
doc.math 数学
doc.movie 电影

2.3.1 ？？？
2.3.1.1 ！！！
2.2.1 Beyond
2 音乐
2.2 粤语
2.1.2 张震岳
2.1.1 周杰伦
2.1 华语
EOF
while read -r path; do
　　 key=${SEP[0]}${path%%"${SEP[1]}"*}
　　 parent=${key%"${SEP[0]}"*}
　　 dict[$key]=${dict[${parent:-${SEP[0]}}]:-$DANG_DIR}${path#${EXCLUDE_KEY:+*${SEP[1]}}}/
　　 echo "${dict[$key]}"
done | tee /dev/stderr | xargs -d $'\n' mkdir

输出并创建：

./音乐 /
./音乐 /华语 /
./音乐 /华语 /周杰伦 /
./音乐 /华语 /张震岳 /
./音乐 /粤语 /
./音乐 /粤语 /Beyond/
./dangling/？？？/
./dangling/？？？/！！！/
./考研资料 /
./考研资料 /英语 /
./考研资料 /数学 /
./考研资料 /电影 /

@iamhrh2 放多点“有些数字和英文一起的不是单位，不需要空软空格”的例子出来呗？