l**h
发帖数: 893 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: babyfacenan (黑土), 信区: JobHunting
标 题: 实现一个parser可以解析给定的几种sql语句，怎么做？
发信站: BBS 未名空间站 (Wed Sep 23 02:44:52 2015, 美东)
需要写现场可以运行的代码
求思路
用什么数据结构
比如说有下面的数据 和 sql query, 让输出结果
String[][] data = {
{ "id", "gender", "age", "job" },
{ "1", "male", "10", "yes" },
{ "2", "female", "20", "no" },
{ "3", "male", "30", "yes" }, };
String query = "select id, gender, age from table where gender = male"; | n*****t
发帖数: 22014 | 2 yacc/lex
【在 l**h 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: babyfacenan (黑土), 信区: JobHunting
: 标 题: 实现一个parser可以解析给定的几种sql语句，怎么做？
: 发信站: BBS 未名空间站 (Wed Sep 23 02:44:52 2015, 美东)
: 需要写现场可以运行的代码
: 求思路
: 用什么数据结构
: 比如说有下面的数据 和 sql query, 让输出结果
: String[][] data = {
: { "id", "gender", "age", "job" },
| l*********s
发帖数: 5409 | | w***g
发帖数: 5958 | 4 轮子的话用这个https://github.com/uwescience/raco
带优化的关系代数编译器。
现在真是啥轮子都有。
【在 l**h 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: babyfacenan (黑土), 信区: JobHunting
: 标 题: 实现一个parser可以解析给定的几种sql语句，怎么做？
: 发信站: BBS 未名空间站 (Wed Sep 23 02:44:52 2015, 美东)
: 需要写现场可以运行的代码
: 求思路
: 用什么数据结构
: 比如说有下面的数据 和 sql query, 让输出结果
: String[][] data = {
: { "id", "gender", "age", "job" },
| k******t
发帖数: 1498 | 5 如果没有轮子的话我这种二把刀也就搞不出来可以商用的系统了。
【在 w***g 的大作中提到】
: 轮子的话用这个https://github.com/uwescience/raco
: 带优化的关系代数编译器。
: 现在真是啥轮子都有。
| N********n
发帖数: 8363 | 6 You need a tokenizer and then construct an evaluation TREE based on
syntax of SELECT statement and input tokens. Once you have the eval
tree you can traverse it to get the result.
To write it all out during an interview they will have to simplify
it a lot, for example no SELECT ... FROM (SELECT ...). Basically a
lot of TREE operations and recursions. | l**h
发帖数: 893 | 7 如果只是最基本的Select from where,好像不难，比如
String query = "select id, gender, age from table where gender = male";
只要parse出来Target (id, gender, age) 和condition (gender='male').
就和Data的第一行比较，拿到index, 然后顺序scanData二维数组，
打印出结果。
【在 N********n 的大作中提到】
: You need a tokenizer and then construct an evaluation TREE based on
: syntax of SELECT statement and input tokens. Once you have the eval
: tree you can traverse it to get the result.
: To write it all out during an interview they will have to simplify
: it a lot, for example no SELECT ... FROM (SELECT ...). Basically a
: lot of TREE operations and recursions.
| n*****t
发帖数: 22014 | 8 var input = "select id, gender, age from table where gender=male";
function parser(input) {
var select_sentence = /select\s+(.+)\s+from\s+(\w+)\s+where\s+(.+)/i;
var match = select_sentence.exec(input);
if (match)
return parse_select({
fields : match[1],
table_name : match[2],
condition : match[3]
});
} | N********n
发帖数: 8363 | 9
光"WHERE"就够折腾一阵的。这里可以是非常复杂的条件表达式，有AND、OR和
NOT，再加上括号优先级，另外还有>, <, !=等各种运算。这个表达式本身就
要来个TREE。除非原题条件就是简单的一个等号比较。
【在 l**h 的大作中提到】
: 如果只是最基本的Select from where,好像不难，比如
: String query = "select id, gender, age from table where gender = male";
: 只要parse出来Target (id, gender, age) 和condition (gender='male').
: 就和Data的第一行比较，拿到index, 然后顺序scanData二维数组，
: 打印出结果。
| g*****g
发帖数: 34805 | 10 面试的话写个最简单的估计就能过。不用考虑太复杂的情况。 | | | n*****t
发帖数: 22014 | 11 递归吧，按优先级拆。解析不难
【在 N********n 的大作中提到】
:
: 光"WHERE"就够折腾一阵的。这里可以是非常复杂的条件表达式，有AND、OR和
: NOT，再加上括号优先级，另外还有>, <, !=等各种运算。这个表达式本身就
: 要来个TREE。除非原题条件就是简单的一个等号比较。
| c*****t
发帖数: 1879 | 12 It is actually far simpler than what you think.
For example, using Java 1.8 stream api,
You basically
1. Create a Stream of rows (which are key/value pairs)
2. Create a Predicate which is based on the predicate to filter the stream.
3. Create a Consumer that does the projection.
And then just collect() the result. You can optionally do the sort()
(if there is an order by). Aggregation is just map / reduce of the
stream.
Other than join, basically any single table SQL operation can be easily
done by supplying the necessary functors to the stream api.
The interpretation part is trivial. One you construct an AST, you can
easily write an interpreter in minutes. If you are lazy, you can just
have an eval function as part of AST node that each node need to implement.
Constant folding is trivial. If you are even lazier, just convert the
entire expression to JavaScript or some script language, and call the
appropriate script engine to do the evaluation.
As for AST construction, if you use any tools lex + yacc, it is trivial.
Even hand writing these stuff using LL(1) is not difficult at all.
Of course, none of these makes sense to people who have no experiences
in text processing. It is very easy to people who do it a lot.
【在 N********n 的大作中提到】
:
: 光"WHERE"就够折腾一阵的。这里可以是非常复杂的条件表达式，有AND、OR和
: NOT，再加上括号优先级，另外还有>, <, !=等各种运算。这个表达式本身就
: 要来个TREE。除非原题条件就是简单的一个等号比较。
| N********n
发帖数: 8363 | 13
看考官奔着啥去的。如果就是要考编译原理基础这里的名堂多了。如果只是来个
简单正则表达式拆分然后糙快猛解析，你楼上那个可能就差不多了。
【在 n*****t 的大作中提到】
: 递归吧，按优先级拆。解析不难
:
:
| N********n
发帖数: 8363 | 14
People w/o text processing experience probably don't even know
what LL(1) / LR(1) is. They probably fail to realize you need to
look 1 operator ahead b4 constructing the AST since different
operators have different precedence.
【在 c*****t 的大作中提到】
: It is actually far simpler than what you think.
: For example, using Java 1.8 stream api,
: You basically
: 1. Create a Stream of rows (which are key/value pairs)
: 2. Create a Predicate which is based on the predicate to filter the stream.
: 3. Create a Consumer that does the projection.
: And then just collect() the result. You can optionally do the sort()
: (if there is an order by). Aggregation is just map / reduce of the
: stream.
: Other than join, basically any single table SQL operation can be easily
| l**h
发帖数: 893 | 15 面试的时候Construct AST不现实吧
有没有什么快猛糙的办法应付面试的
【在 c*****t 的大作中提到】
: It is actually far simpler than what you think.
: For example, using Java 1.8 stream api,
: You basically
: 1. Create a Stream of rows (which are key/value pairs)
: 2. Create a Predicate which is based on the predicate to filter the stream.
: 3. Create a Consumer that does the projection.
: And then just collect() the result. You can optionally do the sort()
: (if there is an order by). Aggregation is just map / reduce of the
: stream.
: Other than join, basically any single table SQL operation can be easily
| c*****t
发帖数: 1879 | 16 AST is nothing. You can easily create one by hand.
For example, for the following simple calculator code:
print 2 * 3 + 5 * 7;
x = 1;
while (x < 10) {
if (x < 5)
print x * x;
else
print x + x;
x = x + 1;
}
The entire code for it, include AST classes, interpreter, lexer + parser
in CookCC (which generates Java) is 310 lines.
https://code.google.com/p/cookcc/source/browse/trunk/tests/java/parser/calc/
calc.xcc
Like I said, it is trivial if you know this area.
【在 l**h 的大作中提到】
: 面试的时候Construct AST不现实吧
: 有没有什么快猛糙的办法应付面试的
| c*********e
发帖数: 16335 | 17 sql的关键字就那么几个，select,create, update,set,insert,delete,from,where,
order by,asc,desc,=,like,%,!=, in, not in, is null, >,<
首先找到关键字，然后
switch()
case 'select':
case 'insert':
case 'update':
case 'delete':
case 'create':
default:
【在 l**h 的大作中提到】
: 面试的时候Construct AST不现实吧
: 有没有什么快猛糙的办法应付面试的
| b*******s
发帖数: 5216 | 18 可以用类厂实现，写个几千种估计够了，每次系统崩溃发现新语句了就加一个新类，在
别人写parser时，你的bug都改了几百个了 | N********n
发帖数: 8363 | 19 首先要一个像样的TOKENIZER能够区分真假关键字。比如这个SQL里的WHERE就是
假的需要过滤掉。 " SELECT * FROM table /* WHERE age > 20 */ "
先搞TOKENIZER，然后SYNTAX分析。THAT ORDER。
【在 c*********e 的大作中提到】
: sql的关键字就那么几个，select,create, update,set,insert,delete,from,where,
: order by,asc,desc,=,like,%,!=, in, not in, is null, >,<
: 首先找到关键字，然后
: switch()
: case 'select':
: case 'insert':
: case 'update':
: case 'delete':
: case 'create':
: default:
| c*********e
发帖数: 16335 | 20 /*也是一個关键字。
首先要一个像样的TOKENIZER能够区分真假关键字。比如这个SQL里的WHERE就是
假的需要过滤掉。 " SELECT * FROM table /* WHERE age > 20 */ "
先搞TOKENIZER，然后SYNTAX分析。THAT ORDER。
【在 N********n 的大作中提到】
: 首先要一个像样的TOKENIZER能够区分真假关键字。比如这个SQL里的WHERE就是
: 假的需要过滤掉。 " SELECT * FROM table /* WHERE age > 20 */ "
: 先搞TOKENIZER，然后SYNTAX分析。THAT ORDER。
|
|
