用类似js的语法查询map
// 返回true
mapq.QueryMap(map[string]interface{}{"a": 1, "b": 2, "c": map[string]interface{}{"d": 3}}, "a == 1 && b == 2 && c.d*(a+b) == 9")
在实验1中,你需要构建一个词法分析器,以便之后的语法分析使用。
词法分析器在接受一段源码输入之后,可以根据需求将源码分割成一个个的词,每个词都有一个类型,比如数字、字符串、标识符等等。
词法分析器的主要被使用的接口是ScanType
和Scan
,后者扫描下一个可以被识别的“词”,返回它的类型和值,后者
会接受一个类型码,当且仅当下一个“词”是该类型时它才返回对应的类型和值,否则会返回一个错误并且恢复lexer到调用前的状态。
提示:
- 字符串是单引号
在实验2中,你需要构建一个语法分析器。语法分析器的Parse方法会生成一个语法书,语法书的每个节点都有Eval方法,可以用来进行查询。
基础部分的测试覆盖以下功能:
- 支持所有的双目运算符
- 支持对逻辑运算符的小括号
- 支持单目运算符中的
!
- 支持嵌套搜索(例如
a.b==1
)
提示:
- 基础测试中有一部分较难的内容可能比进阶测试的一些内容(null,字符串)更难,为得分可以先跳过
- 如果基础测试不通过,基本上无法正常运行性能测试,也就无法获得加分
- 实验中所有的数字都应该转换成float64处理
在实验3中,你需要完善你在Lab 2中构建的语法分析器。
进阶测试覆盖以下功能:
- 支持所有单目运算符
- 支持null
- 支持字符串
- 支持四则运算
- 支持用括号改变四则运算优先级
提示:
- 不需要通过进阶测试也可以获得加分
- 四则运算部分可能显著难于其他的测例,请科学安排时间
- 四则运算的括号处理逻辑可能不能沿用Lab 2中的逻辑运算括号逻辑
在实验4中,你需要优化你在Lab 3中构建的语法分析器,以尽量获得更高的性能
提示:
- 使用ast的分析器相比不使用的在这一步有优势
- 性能测试的例子中隐藏了优化的方式
- 对于Parser的性能测试,语法是主要影响因素
本题分为基本分和加分两部分
基本分满分130分,评分标准如下:
在项目根目录运行
go test -bench ./... -v
这个命令会运行单元测试文件中的30个测试,并计算你的查询函数的性能。
lexer相关测试共10个,总分30分,每个测试3分
parser相关测试共20个,总分100分,每个5分,分为基础和高级功能测试两部分,只有基础功能测试满分者才有资格获取附加分
有资格获取附加分的人,其附加分按照性能测试结果得分。
对于Parse测试和Query测试,从有资格测试的最后一名起,每名的加分分别递增3分和2分
- 递归下降分析法
- 编译原理
- 抽象语法树(AST)(完成此任务不一定需要抽象语法树)
- bool
- string(单引号)
- number(float64)
- null
- -
- +
- !
- ==
- !=
- >
- <
- >=
- <=
- +
- -
- *
- /
- ||
- &&
- 小括号:改变运算优先级
- 嵌套map查询