当前位置：网站首页>Lex & yacc of Pisa proxy SQL parsing
Lex & yacc of Pisa proxy SQL parsing
2022-07-07 17:19:00 【InfoQ】
One 、 Preface
1.1 The authors introduce
Wang Bo ,SphereEx MeshLab R & D Engineer , Focus on Database Mesh,Cloud Native The development of .Linux,llvm,yacc,ebpf user. Gopher & Rustacean and c bug hunter.
GitHub:
https://xie.infoq.cn/article/d59e47a90edaf763df760ac2d
1.2 background
In the last article 《
Pisa-Proxy And SQL Analytical practice
》 This paper introduces the in Pisa-Proxy One of the core modules of SQL Parser related content . stay MySQL and PostgreSQL in
SQL analysis
It's through Yacc Realized , Again Pisa- Proxy Of SQL The parser is composed of Yacc Such tools realize , So this article will focus on SQL The parser introduces some compilation principles and Lex & Yacc Use , It will also show readers how to pass Lex & Yacc Implement a simple one SQL Parser . So as to help you better understand Pisa-Proxy in SQL How the parser works .
Two 、 Compiler exploration
A programming language, no matter what we often use Java,Golang Or is it SQL It is essentially a notation system , Like natural language , Its complete definition should include both syntax and semantics . The grammar of a language is actually a corresponding set of rules , It can be used to form and produce a suitable program . Currently, the most widely used method is context free grammar , Context free grammar is used as a tool to describe the syntax of programming language . Grammar just defines what kind of symbol sequence is legal , It has nothing to do with the meaning of these symbols . However, there are two categories in semantics ： Static semantics and dynamic semantics . Static semantics refers to a series of qualification rules , And determine which syntax is appropriate for the program ; Dynamic semantics is also called running semantics or execution semantics , Specify what the program will calculate .
2.1 Compiler workflow
Pictured 2.1.1 As shown in , Generally, the compiler compiles the source code into executable files in the following steps ：
- Scan the source file , Split the character stream of the source file into words （token）, This is lexical analysis
- According to the grammar rules, these marks are constructed into a grammar tree , This is syntax analysis
- Check the relationship between the nodes of the syntax tree , Check whether semantic rules are violated , At the same time, the syntax tree is optimized as necessary , This is semantic analysis
- Traverse the nodes of the syntax tree , Convert each node into intermediate code , And put them together in a specific order , This is intermediate code generation
- Optimize the intermediate code
- Convert intermediate code into object code
- Optimize the object code , Generate the final target program
chart 2.1.1
about SQL Analytically speaking , The steps in the above figure can be simplified as shown in the figure 2.1.2 In the form of , Source code input （SQL sentence ）, take SQL Sentence for lexical analysis , Generate SQL In the specific token Sign flow . Then get the token stream and parse it to generate the final SQL AST.
chart 2.1.2
2.2 Lexical analysis
As mentioned above , Whether compiler or SQL A key step of the parser is to do lexical analysis on the source file , Lexical analysis can be understood as right SQL The sentence itself is processed by word segmentation . So at this stage ,SQL What the parser needs to do is scan the source file from left to right , take SQL Statements are divided into one by one token, here token Refer to SQL A string of characters that cannot be further divided in . For example, figure 2.1.2 Medium SQL sentence , After lexical analysis , Generated token by ：
SELECT、
*、
FROM、
pisa_proxy wait .
stay SQL What can be used in the sentence token Categories are also limited , For example, reserved words
SELECT、
INSERT、
DELETE wait . And operators , such as ： arithmetic operator 、 Comparison operator . And identifiers , such as ： Built in function name and so on . At this stage, each scan token Will be maintained in a data structure , Then in the next phase, the parsing phase uses . Generally speaking , Lexical analysis has direct scanning , Regular matching scanning mode .
2.2.1 Direct scanning method
The logic of direct scanning method is very clear , Each scan determines which type it belongs to according to the first character token, Then take different strategies to scan out a complete token, Then proceed to the next scan . stay Pisa-Proxy Medium SQL Parsing , Lexical analysis adopts this implementation , use Python Show how to implement a simple SQL Lexical analyzer pair SQL scan , The code is as follows ：
# -*- coding: utf-8 -*-
single_char_operators_typeA = {
";", ",", "(", ")","/", "+", "-", "*", "%", ".",
}
single_char_operators_typeB = {
"<", ">", "=", "!"
}
double_char_operators = {
">=", "<=", "==", "~="
}
reservedWords = {
"select", "insert", "update", "delete", "show",
"create", "set", "grant", "from", "where"
}
class Token:
def __init__(self, _type, _val = None):
if _val is None:
self.type = "T_" + _type;
self.val = _type;
else:
self.type, self.val = _type, _val
def __str__(self):
return "%-20s%s" % (self.type, self.val)
class NoneTerminateQuoteError(Exception):
pass
def isWhiteSpace(ch):
return ch in " \t\r\a\n"
def isDigit(ch):
return ch in "0123456789"
def isLetter(ch):
return ch in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def scan(s):
n, i = len(s), 0
while i < n:
ch, i = s[i], i + 1
if isWhiteSpace(ch):
continue
if ch == "#":
return
if ch in single_char_operators_typeA:
yield Token(ch)
elif ch in single_char_operators_typeB:
if i < n and s[i] == "=":
yield Token(ch + "=")
else:
yield Token(ch)
elif isLetter(ch) or ch == "_":
begin = i - 1
while i < n and (isLetter(s[i]) or isDigit(s[i]) or s[i] == "_"):
i += 1
word = s[begin:i]
if word in reservedWords:
yield Token(word)
else:
yield Token("T_identifier", word)
elif isDigit(ch):
begin = i - 1
aDot = False
while i < n:
if s[i] == ".":
if aDot:
raise Exception("Too many dot in a number!\n\tline:"+line)
aDot = True
elif not isDigit(s[i]):
break
i += 1
yield Token("T_double" if aDot else "T_integer", s[begin:i])
elif ord(ch) == 34: # 34 means '"'
begin = i
while i < n and ord(s[i]) != 34:
i += 1
if i == n:
raise Exception("Non-terminated string quote!\n\tline:"+line)
yield Token("T_string", chr(34) + s[begin:i] + chr(34))
i += 1
else:
raise Exception("Unknown symbol!\n\tline:"+line+"\n\tchar:"+ch)
if __name__ == "__main__":
print "%-20s%s" % ("TOKEN TYPE", "TOKEN VALUE")
print "-" * 50
sql = "select * from pisa_proxy where id = 1;"
for token in scan(sql):
print token
The final output is as follows ：
TOKEN TYPE TOKEN VALUE
--------------------------------------------------
T_select select
T_* *
T_from from
T_identifier pisa_proxy
T_where where
T_identifier id
T_= =
T_integer 1
T_; ;
We can see from the above code , At the beginning, we defined several token type , for example ：
reservedWords Array is maintained SQL Reserved word in , also SQL Operator in
single_char_operators_typeA. We can see the final implementation result , The scanner will eventually be a SQL Sentences are segmented into their corresponding types token.
2.2.2 Regular expression scanning
In fact, the essence of a program is a set of strings , And language can be regarded as a collection of legal programs , So the compiler or SQL The essence of parsing is to judge that the input string is the legal type of the language , In addition, it is also a legal program that converts the legal program in the language into the target language . So the essence of regular expression scanning , That is to judge whether the string matches the regular expression in a finite state machine , In the following introduction, we will mention flex,flex The essence of is to construct a finite state automaton from the word segmentation matching pattern written by users in regular expressions .
2.3 Syntax analysis
After lexical analysis ,SQL The character stream of the statement is split into token, Then grammatical analysis is to analyze SQL The grammatical structure of , Will be linear token The flow is transformed into a tree structure , For subsequent semantic analysis and AST Prepare for generation . In the compiler , Regular expressions are still difficult to represent the set of sentences represented by programming languages , So we introduce context free grammar , Context free grammar can describe the grammatical structure of current programming languages .
Take our natural language as an example , Suppose a programming language is SQLX, It only contains the main - Predicate - Bin For this structure , The subject is only
you 、
I 、
He , Predicate only
Love , The object has
Rust and
Pisanix, Then the grammar can be in the following form ：
sentence -> The subject Predicate The object
The subject -> I
The subject -> you
The subject -> He
Predicate -> Love
The object -> Rust
The object -> Pisanix
From the above example, we can replace the subject predicate object respectively , So as to write all the statements that meet this structure . On the contrary, we can compare any sentence with this structure to judge whether it meets SQLX Language . This leads to several concepts , In the above grammar, the form is “ The subject -> Predicate -> The object ” The formula of becomes
Generative formula The symbol on the left of production （ sentence 、 The subject 、 Predicate 、 The object ） be called
non-terminal . and “ I , you , He , Love ,Rust,Pisanix” These symbols can no longer produce new symbols , So it's called
Terminator , The terminator can only appear on the right of the production . The word "sentence" is the starting point of all sentences , So it's also called
Start symbol .
Usually put a non The production of terminators is written together , use “｜” separate , It can be summed up as follows ：
sentence -> The subject Predicate The object
The subject -> you ｜ I ｜ He
Predicate -> Love
The object -> Rust | Pisanix
We start with a SQL Statements, for example ： SELECT 1 + 1, We can write the push expression of this statement as , The analysis tree is shown in the figure 2.3.1
Expr => Expr Expr + Expr => SELECT Expr + Expr => SELECT number + Expr => SELECT number + number => SELECT 1 + 2
chart 2.3.1
2.3.1 Two analytical methods
Grammar analysis includes two analysis methods ：
- Top down analysis ： Top down analysis starts with the starting symbol , Keep picking out the right production , Expand the non terminator in the middle sentence , Finally, expand to the given sentence .
- Bottom up analysis ： The order of bottom-up analysis is just the opposite to that of top-down analysis , Start with the given sentence , Keep picking out the right production , Fold the substring in the middle sentence into a non terminator , Finally collapse to the starting symbol
In the process of derivation , At each step, only one production can be applied , Every step can eliminate all other production formulas . But in actual analysis , In the intermediate process, you may encounter that all productions are not applicable or there are multiple productions that can be applied . For the second case , Backtracking is required , First try to choose a production application , If it is deduced until the final sentence （ Or starting symbol ）, Then it shows that this production is available , If we continue to deduce, we will encounter the first case , Then go back here , Choose another production . If all the production formulas here have been tried, all of them encounter the first case , It shows that the final sentence does not conform to the grammatical structure . If there are multiple production expressions here, they can be deduced to the final sentence （ Or starting symbol ）, It shows that the grammar is ambiguous . Backtracking analysis is generally very slow , Therefore, we usually avoid backtracking by carefully constructing grammar .
2.4 Summary
The above content mainly introduces the related concepts of compiler , And through a simple example to intuitively feel the basic principle and working process of lexical analysis , Next, I will briefly introduce the two most commonly used tools in lexical analysis and grammatical analysis Lex and Yacc.
3、 ... and 、 know Lex and Yacc
3.1 know Lex
Flex（ Fast lexical analyzer generator ） yes Lex Free open source software alternatives . It is a generated lexical analyzer （ Also known as “ Scanner ” or “ Lexical analyzer ”） A computer program for . Scanner is a program that recognizes lexical patterns in text , Used to recognize lexical patterns in text .
3.1.1 Lex It's made up of three parts
- Definition section ： The definition segment includes text blocks 、 Definition 、 Internal table declaration 、 Starting conditions and transitions .
- The rules section ： The rule segment is a series of matching patterns and actions , Patterns are usually written in regular expressions , The action part is C Code .
- User subroutine segment ： Here for C Code , Will be copied to c In file , Generally, some auxiliary functions are defined here , Such as the auxiliary function used in the action code .
Here we make a simple example , use Lex Implement a simple one SQL Lexical analyzer ,lex The code is as follows :
%{
#include <stdio.h>
%}
%%
select printf("KW-SELECT : %s\n", yytext);
from printf("KW-FROM : %s\n", yytext);
where printf("KW-WHERE : %s\n", yytext);
and printf("KW-AND : %s\n", yytext);
or printf("KW-OR : %s\n", yytext);
[*] printf("IDENTIFIED : %s\n", yytext);
[,] printf("IDENTIFIED : %s\n", yytext);
[=] printf("OP-EQ : %s\n", yytext);
[<] printf("KW-LT : %s\n", yytext);
[>] printf("KW-GT : %s\n", yytext);
[a-zA-Z][a-zA-Z0-9]* printf("IDENTIFIED: : %s\n", yytext);
[0-9]+ printf("NUM: : %s\n", yytext);
[ \t]+ printf(" ");
. printf("Unknown : %c\n",yytext[0]);
%%
int main(int argc, char* argv[]) {
yylex();
return 0;
}
int yywrap() {
return 1;
}
# flex sql.l # use flex compile .l File generation c Code
# ls
lex.yy.c sql.l
# gcc -o sql lex.yy.c # Compile and generate executable binaries
# ./sql # Execute binary
select * from pisaproxy where id > 1 and sid < 2 # Input test sql
KW-SELECT : select
IDENTIFIED : *
KW-FROM : from
IDENTIFIED: : pisaproxy
KW-WHERE : where
IDENTIFIED: : id
KW-GT : >
NUM: : 1
KW-AND : and
IDENTIFIED: : sid
KW-LT : <
NUM: : 2
We can see from the above example that ,Lex Successfully put a SQL The statement is split into separate token.
3.2 know Yacc
Yacc It is an industrial tool for developing compilers , use LALR(1) Grammar analysis method .LR(k) Analysis method , In brackets k(k>=0) Indicates to view the number of input string symbols to the right .LR The analysis method gives a method that can view the input string according to the symbol string in the current analysis stack and the right order k A symbol can uniquely determine whether the analyzer's action is to move in or to specify and which production specification to use .
Yacc and Lex equally , It also includes “%%” Three separate segments ： Definition statement 、 Rule of grammar 、C Code segment .
- Define segments and predefined tag sections ：
above %{ %} The code and Lex equally , Generally referred to as definition segment . Just some header file declarations , Macro definition 、 Variable definition declaration 、 Function declaration, etc . among
%left It means left combination ,
%right Right combination . The last listed definitions have the highest priority . Therefore, multiplication and division have higher priority than addition and subtraction .+ - * / All four arithmetic symbols are left combined . Use this simple technique , We can disambiguate grammar .
- The rules section ： Rule segments consist of grammatical rules and include C The action composition of the code . In the rule, the target or non terminal character is placed on the left , Followed by a colon （:）, Then there is the right side of production , Then there is the corresponding action （ use {} contain ）
- Code section ： This part is the function part . When Yacc When parsing error , Would call
yyerror(), Users can customize the implementation of functions .
Here we use a simple example to pass Yacc and Lex To achieve a simple SQL Parser
sql.l Code example
%{
#include <stdio.h>
#include <string.h>
#include "struct.h"
#include "sql.tab.h"
int numerorighe=0;
%}
%option noyywrap
%%
select return SELECT;
from return FROM;
where return WHERE;
and return AND;
or return OR;
[*] return *yytext;
[,] return *yytext;
[=] return *yytext;
[<] return *yytext;
[>] return *yytext;
[a-zA-Z][a-zA-Z0-9]* {yylval.Mystr=strdup(yytext);return IDENTIFIER;}
[0-9]+ return CONST;
\n {++yylval.numerorighe; return NL;}
[ \t]+ /* ignore whitespace */
%%
sql.y Some code examples
%{
%}
%token <numerorighe> NL
%token <Mystr> IDENTIFIER CONST '<' '>' '=' '*'
%token SELECT FROM WHERE AND OR
%type <Mystr> identifiers cond compare op
%%
lines:
line
| lines line
| lines error
;
line:
select identifiers FROM identifiers WHERE cond NL
{
ptr=putsymb($2,$4,$7);
}
;
identifiers:
'*' {$="ALL";}
| IDENTIFIER {$=$1;}
| IDENTIFIER','identifiers
{
char* s = malloc(sizeof(char)*(strlen($1)+strlen($3)+1));
strcpy(s,$1);
strcat(s," ");
strcat(s,$3); $=s;
}
;
select:
SELECT
;
cond:
IDENTIFIER op compare
| IDENTIFIER op compare conn cond;
compare:
IDENTIFIER
| CONST
;
op:
'<'
|'='
|'>'
;
conn:
AND
| OR
;
%%
# Here, because the compilation process is cumbersome , Here are just the key results
# ./parser "select id,name,age from pisaproxy1,pisaproxy2,pisaproxy3 where id > 1 and name = 'dasheng'"
''Row #1 is correct
columns: id name age
tables: pisaproxy1 pisaproxy2 pisaproxy3
It can be seen through Lex First of all, will SQL It can be interpreted as token, And then by yacc Do grammar analysis , according to .y The rules in will
column and
tables Correctly solve .
Four 、Pisa-Proxy SQL Analysis and implementation
stay Pisa-Proxy Medium SQL The parser is through Grmtools This tool implements ,Grmtools yes Rust Realized lex and yacc library .Pisa-Proxy Of SQL Parsing mainly includes two parts , First of all
lex.rs file , This document was passed Grmtools The method provided realizes the handwriting lexical analyzer , As mentioned earlier , This module will SQL Sentence segmentation , Generate token. And then there was
grammar.y file , This document describes SQL The derivation of the statement ,Grmtools The file will be parsed and finally generated SQL AST.
5、 ... and 、 summary
This article mainly shares the relevant concepts and principles of compilers , We can see SQL Parser for SQL What is the meaning of the sentence , And how to SQL The form of statement string is transformed into the abstract syntax tree we need .Lex and Yacc Are two very powerful tools , It can help developers easily and quickly implement their own parser , However, the compilation principle is a very complex subject .Pisa-Proxy Of SQL The parser also encountered many problems in the implementation process , For example, how to resolve conflicts , Two senses , Priority and so on . There will continue to be an in-depth analysis of the article later SQL Statements in Rust The specific implementation of , This article will not repeat .
6、 ... and . Related links ：
6.1 Pisanix:
Project address ：
https://github.com/database-mesh/pisanix
Official website address ：
Hello from Pisanix | Pisanix
Database Mesh：
https://www.database-mesh.io/
SphereEx Official website ：
https://www.sphere-ex.com
6.2 Community
Tens of millions of steps for open source projects ,Pisanix Just started. . Open source is a door ,Pisanix Welcome to join us , Express your ideas , Share your insights , Whether it's code or documentation ,issue still pull request, The community welcomes . You guys who are willing to help with database management , Let's build Pisanix Community bar ~
at present Pisanix The community organizes online discussions every two weeks , The detailed arrangement is as follows , we will wait for you ~
7、 ... and 、 Reference material
- 《 Compiler principle 》
- 《 Principles of modern compilation 》
- https://github.com/mysql/mysql-server/blob/8.0/sql/sql_yacc.yy
- http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/
边栏推荐
- Notes on installing MySQL in centos7
- QML beginner
- Flask搭建api服务-SQL配置文件
- PLC: automatically correct the data set noise, wash the data set | ICLR 2021 spotlight
- SIGGRAPH 2022最佳技术论文奖重磅出炉！北大陈宝权团队获荣誉提名
- LeetCode 1477. Find two subarrays with sum as the target value and no overlap
- [source code interpretation] | source code interpretation of livelistenerbus
- Blue Bridge Cup final XOR conversion 100 points
- LeetCode 1049. Weight of the last stone II daily question
- 电脑无法加域，ping域名显示为公网IP，这是什么问题？怎么解决？
猜你喜欢
Sort out several important Android knowledge and advanced Android development interview questions
Skimage learning (1)
Sator推出Web3遊戲“Satorspace” ，並上線Huobi
How to add aplayer music player in blog
Direct dry goods, 100% praise
The top of slashdata developer tool is up to you!!!
Module VI
麒麟信安携异构融合云金融信创解决方案亮相第十五届湖南地区金融科技交流会
DevOps 的运营和商业利益指南
skimage学习（1）
随机推荐
Skimage learning (1)
Sator推出Web3游戏“Satorspace” ，并上线Huobi
[source code interpretation] | source code interpretation of livelistenerbus
自定义View必备知识，Android研发岗必问30+道高级面试题
Is AI more fair than people in the distribution of wealth? Research on multiplayer game from deepmind
LeetCode 1696. 跳跃游戏 VI 每日一题
【饭谈】那些看似为公司着想，实际却很自私的故事 （一：造轮子）
Number of exchanges in the 9th Blue Bridge Cup finals
Leetcode brush questions day49
Pycharm IDE下载
DNS 系列（一）：为什么更新了 DNS 记录不生效？
【Seaborn】组合图表：FacetGrid、JointGrid、PairGrid
First in China! Todesk integrates RTC technology into remote desktop, with clearer image quality and smoother operation
测试用例管理工具推荐
【饭谈】Web3.0到来后，测试人员该何去何从？（十条预言和建议）
Mrs offline data analysis: process OBS data through Flink job
LeetCode 1049. 最后一块石头的重量 II 每日一题
LeetCode 300. Daily question of the longest increasing subsequence
How to choose the appropriate automated testing tools?
User defined view essential knowledge, Android R & D post must ask 30+ advanced interview questions