likes
comments
collection
share

使用goyacc实现sql语法解析

作者站长头像
站长
· 阅读数 23

使用goyacc实现sql语法解析

程序设计语言的分析分为三个阶段：

  • 线性分析（词法分析），读取源程序为字节流，将字节流分组为多个记号（token，具有整体含义的字符序列）
  • 层次分析（语法分析），将字符串或记号划分为具有一定层次的多个嵌套组，一颗分析树
  • 语义分析，检查语义错误，收集类型信息

语言的语法一般会用上下文无关文法来表示，上下文无关文法，由终结符、非终结符、开始符号、产生式组成：

  • 终结符：组成字符串的基本符号
  • 非终结符：表示字符串集合的语法变量
  • 开始符号：文法中有一个非终结符被指定为开始符号，开始符号表示的字符串集合就是要定义的语言
  • 产生式：终结符和非终结符组合成串的方式，由非终结符开始，跟随一个箭头，后面是终结符非终结符组成的串

语法解析方法分为两类类：

  • 自顶向下，按从根结点到叶节点的顺序构造分析树，常见分析法：LL(1)
  • 自底向上，按从叶节点到根结点的顺序构造分析树，常见分析法：LR(1)、LALR(1)

yacc是基于LALR算法的语法分析器，在程序设计语言编译中被广泛使用，goyacc是yacc的go版本，我们使用goyacc来解析sql语句生成抽象语法书。

yacc语法文件由三个部分构成：

  • 声明分为两节：
    • 第一节是目标语言声明，包含在分界符%{和}%之间，使用goyacc时中存放go的一些声明，如包名、import等
    %{
    package sql

    import (
        "strconv"
        "strings"
    )

 %}
    • 第二节是文法记号，声明一些符号，用于后续翻译规则， 如%union、%token、%type等
      • %union 声明要使用的类型
      • %token 声明终结符
      • %type 声明非终结符
      • %left/%right 声明符号是左结合/右结合
        %union {
        str string
    }

    %token <str> 
        CREATE "CREATE"
        TABLE "TABLE"

    %type <str> Expr
  • 翻译规则：与第一部分通过%%符号隔开，每条规则由一个文法产生式和后续的语义动作构成：
    • 具有相同左部的产生式可以合并到一起，每个右部用|分隔
    • $i 表示右边第i（起始为1）个文法符号（包含终结符、非终结符）的值
    • 语义动作一般为根据$i计算$$
    • 默认语义动作为 { $$ = $1 }，可省略

SelectStmt:
    "SELECT" SelectFieldList SelectStmtLimit ';'
    {
        $$ = &SelectStmt{ Filed: $2 , Limit: $3}
    }
    |  "SELECT" SelectFieldList SelectStmtFrom SelectStmtWhere SelectStmtOrder SelectStmtLimit ';'
    {
        $$ = &SelectStmt{ Filed: $2, From: $3 ,Where: $4, Order: $5, Limit: $6 }
    }
  • 支持例程，提供yylex()词法分析器，在goyacc中是通过实现yyLexer接口来提供词法分析

依据mysql的Select Statement编写相应文法，将select语句分为下述几个部分

type SelectStmt struct {
	Filed []*SelectField
	From  *SelectStmtFrom
	Where []BoolExpr
	Order []*OrderField
	Limit *SelectStmtLimit
}
  • 查询字段
type SelectField struct {
    Field string
    Pos   int
    Expr  *SqlFunction
    Alias string
}
  • 查询来源
type SelectStmtFrom struct {
	Table string
}
  • 查询条件，由多个布尔表达式组成合取范式(CNF)，转换时用Negation标记是否对真值取反，WhereExpr、WhereField实现BoolExpr接口
type WhereExpr struct {
	Negation bool
	Cnf      []BoolExpr
}

type BoolExpr interface {
	Prepare(fieldMapping map[string]int) error
	Filter(row *[]string) bool
	Negate()
}

type WhereField struct {
	Field   string
	Pos     int
	Value   string
	Compare CompareOp
}
  • 排序条件
type OrderField struct {
	Field string
	Asc   bool
}
  • 限制条件
type SelectStmtLimit struct {
	Offset int
	Size   int
}

在yacc定义上述结构

%union {
    str string
    strArr []string
    boolean bool
    
    stmt Statment
    stmtList []Statment

    selectStmt *SelectStmt
    sqlFunc *SqlFunction
    selectFieldList []*SelectField
    selectStmtFrom *SelectStmtFrom
    whereExprList []BoolExpr
    orderFieldList []*OrderField
    selectStmtLimit *SelectStmtLimit
    compareOp CompareOp
}

定义selec语句关键字

%token <str> 
    SELECT "SELECT" 
    FROM "FROM" 
    WHERE "WHERE" 
    ORDER "ORDER"
    BY "BY" 
    LIMIT "LIMIT" 
    OFFSET "OFFSET" 
    ASC "ASC" 
    DESC "DESC" 
    AND "AND" 
    OR "OR"

%token <str> 
    COMP_NE "!="
    COMP_LE "<=" 
    COMP_GE ">=" 

%token <str> VARIABLE
%type <str> Expr
%type <strArr> VaribleList
%type <stmt> Stmt
%type <stmtList> StmtList
%type <selectStmt> SelectStmt
%type <sqlFunc> AggregateFunction
%type <selectFieldList> SelectFieldList   
%type <selectStmtFrom> SelectStmtFrom
%type <whereExprList> SelectStmtWhere WhereExprList
%type <orderFieldList> SelectStmtOrder OrderFieldList
%type <selectStmtLimit> SelectStmtLimit 
%type <compareOp> CompareOp
%type <boolean> Ascend

%left OR
%left AND
%left '+' '-'
%left '*' '/'

定义开始符号

%start start

编写语法规则，允许多条语句，语义动作 保存Stmt到StmtList

start:
    StmtList

StmtList:
    Stmt
    {
        $$ = append($$, $1)
    }
    | StmtList Stmt
    {
        $$ = append($$, $2)
    }

Stmt:
    SelectStmt
    {
        $$ = Statment($1)
    }

select语句必须具有结构仅有"select" expr，其他关键字都是可选，无"from"子句时，后续只允许"limit"子句，将select分为两个候选产生式，语义动作都是将子句的结构保存到SelectStmt结构中

  • 候选1形如 select expr [limit expr]
  • 候选2形如 select expr from table [ where expr] [ order by expr ] [ limit expr ]
SelectStmt:
    "SELECT" SelectFieldList SelectStmtLimit ';'
    {
        $$ = &SelectStmt{ Filed: $2 , Limit: $3}
    }
    |  "SELECT" SelectFieldList SelectStmtFrom SelectStmtWhere SelectStmtOrder SelectStmtLimit ';'
    {
        $$ = &SelectStmt{ Filed: $2, From: $3 ,Where: $4, Order: $5, Limit: $6 }
    }

select字段可能是表的字段，或是一个函数，yacc使用LALR(1)每次只读入一个记号，新字段读入时要区分是否已读取过字段，这样讲select查询字段分为了4个候选，当字段为第一个时在语义动作中创建新的查询字段切片，将第一个字段写入，当不是第一个字段将新字段写入已存在的切片

SelectFieldList:
    Expr
    {
        $$ = []*SelectField{ &SelectField{ Field: $1 } }
    }
    | SelectFieldList ',' Expr
    {
        $$ = append( $1, &SelectField{ Field: $3 } )
    }
    | AggregateFunction
    {
        $$ = []*SelectField{ &SelectField{ Expr: $1 }}
    }
    | SelectFieldList ',' AggregateFunction
    {
        $$ = append( $1, &SelectField{ Expr: $3 } )
    }

select from后面需要时一个表，允许实际表、子查询、join后的表，这里仅定义实际表

SelectStmtFrom:
    "FROM" Expr
    {
        $$ = &SelectStmtFrom{
            Table: $2,
        }
    }

select where关键字可选，将其分为两个候选

SelectStmtWhere:
    {
        $$ = nil
    }
    | "WHERE" WhereExprList
    {
        $$ = $2
    }

将where子句由多个布尔表达式构成，为方便计算真值，需要将其转换为合取范式(CNF)

  • 当为第一个条件，建立切片，将条件构造为BoolExpr
  • 当新条件与之前已存在BoolExpr关系为 or 时，标记对BoolExpr真值取反，将条件添加到BoolExpr，构造一个新BoolExpr包含旧BoolExpr，标记真值取反
  • 当新条件与之前BoolExpr关系为 and 时，将条件添加到BoolExpr
  • 当新BoolExpr与与之前BoolExpr关系为 or 时，标记新旧BoolExpr取反，合并新旧BoolExpr，标记合并后BoolExpr真值取反
  • 当新BoolExpr与与之前BoolExpr关系为 and 时，将新子句添加到旧子句
WhereExprList:
    Expr CompareOp Expr
    {
        $$ = []BoolExpr{ &WhereField{Field:$1, Value:$3, Compare:$2} }
    }
    | WhereExprList OR Expr CompareOp Expr  %prec OR
    {
        $4.Negate()
        filed := &WhereField{ Field:$3, Value:$5, Compare:$4 }
        if len($$) == 1{
            $$[0].Negate()
            $$ = append($$, filed)
            $$ = []BoolExpr{ &WhereExpr{ Negation: true, Cnf: $$ }  }
        }else{
            $$ = []BoolExpr{ &WhereExpr{ Negation: true, Cnf: []BoolExpr{ &WhereExpr{ Negation: true, Cnf: $$ } , filed} } }
        }
    }
    | WhereExprList AND Expr CompareOp Expr %prec AND
    {
        $$ = append($$, &WhereField{ Field:$3, Value:$5, Compare:$4} )
    }
    | WhereExprList OR '(' WhereExprList ')' %prec OR
    {
        if len($$) == 1{
            $$[0].Negate()
            $$ = append($$, &WhereExpr{ Negation: true, Cnf: $4 })
            $$ = []BoolExpr{ &WhereExpr{ Negation: true, Cnf: $$ }  }
        }else{
           $$ =[]BoolExpr{ &WhereExpr{ Negation: true, Cnf: []BoolExpr{ &WhereExpr{ Negation: true, Cnf: $$ } , &WhereExpr{ Negation: true, Cnf: $4 } } } }
        }
    }
    | WhereExprList AND '(' WhereExprList ')' %prec AND
    {
        $$ = append($$, $4... )
    }

selec order关键字可选，分为两个候选，子句由多个order字段构成，分两个候选

SelectStmtOrder:
    {
        $$ = nil
    }
    | "ORDER" "BY" OrderFieldList 
    {
        $$ = $3
    }

OrderFieldList:
    Expr Ascend
    {
        $$ = []*OrderField{&OrderField{ Field: $1, Asc: $2 }}
    }
    | OrderFieldList ',' Expr Ascend
    {
        $$ = append($1, &OrderField{ Field: $3, Asc: $4 })
    }

select limit子句支持三种语法对应yacc三种候选，语义动作中将字符串转换数字

SelectStmtLimit:
    {
        $$ = nil
    }
    | "LIMIT" VARIABLE
    {
        size,err :=  strconv.Atoi($2)
        if err != nil{
            yylex.Error(err.Error())
            goto ret1
        }
        $$ = &SelectStmtLimit{Size: size }
    }
    | "LIMIT" VARIABLE ',' VARIABLE
    {   

        offset,err :=  strconv.Atoi($2)
        if err != nil{
            yylex.Error(err.Error())
            goto ret1
        }
        size,err :=  strconv.Atoi($4)
        if err != nil{
            yylex.Error(err.Error())
            goto ret1
        }
        $$ = &SelectStmtLimit{Offset: offset, Size: size }
    }
    | "LIMIT" VARIABLE "OFFSET" VARIABLE
    {
        offset,err :=  strconv.Atoi($4)
        if err != nil{
            yylex.Error(err.Error())
            goto ret1
        }
        size,err :=  strconv.Atoi($2)
        if err != nil{
            yylex.Error(err.Error())
            goto ret1
        }
        $$ = &SelectStmtLimit{Offset: offset, Size: size }
    }

要利用yyParser需要实现yyLexer或yyLexerEx接口

type yyLexer interface {
	Lex(lval *yySymType) int
	Error(e string)
}

type yyLexerEx interface {
	yyLexer
	Reduced(rule, state int, lval *yySymType) (stop bool) 
}

定义一个简单的词法分析器,实现yyLexer，解析sql语句将token语法解析器

type Lexer struct {
	sql    string
    stmts  []Statement
	offset int
	errs   []string
}

实现Lex方法，逐个读取sql中的字符，分割语句为token，将token写入lval，返回token对应符号表位置。

func (l *Lexer) Lex(lval *yySymType) int {
	start := l.offset
	end := len(l.sql)
	if l.offset >= end {
		return 0
	}

	prevQuote := false
	prevBacktick := false
	prevSingleQuotes := false
	prevDoubleQuotes := false
	for i := l.offset; i < len(l.sql); i++ {
		switch l.sql[i] {
		case '\\':
			continue
		case '\'':
			prevSingleQuotes = !prevSingleQuotes
			prevQuote = prevBacktick || prevSingleQuotes || prevDoubleQuotes
		case '"':
			prevDoubleQuotes = !prevDoubleQuotes
			prevQuote = prevBacktick || prevSingleQuotes || prevDoubleQuotes
		case '`':
			prevBacktick = !prevBacktick
			prevQuote = prevBacktick || prevSingleQuotes || prevDoubleQuotes
		}

		if !prevQuote {
			switch l.sql[i] {
			case ' ', '\n', '\t':
				end = i
			case '<', '>', '!':
				end = i
				if start == end {
					if i+1 < len(l.sql) && l.sql[i+1] == '=' {
						end += 2
					} else {
						end++
					}
				}
			case '=', ',', ';', '(', ')':
				end = i
				if start == end {
					end++
				}
			}
		}

		if i == end {
			break
		}
	}

	l.offset = end
	for l.offset < len(l.sql) {
		char := l.sql[l.offset]
		if char == ' ' || char == '\n' || char == '\t' {
			l.offset++
		} else {
			break
		}
	}

	token := l.sql[start:end]
	lval.str = token

	num, ok := SqlTokenMapping[token]
	if ok {
		return num
	} else {
		return VARIABLE
	}
}

实现Reduced()方法，记录归约结果

func (l *Lexer) Reduced(rule, state int, lval *yySymType) bool {
	if state == 2 {
		l.stmts = lval.stmtList
	}
	return false
}

实现Error()方法，记录语法解析中的错误

func (l *Lexer) Error(s string) {
	l.errs = append(l.errs, s)
}

使用goyacc用sql.y生成go语言的sql解析器

goyacc -o yyParser.go -v yacc.output sql.y

调用yyParse()函数，传入一个Lexer实例，完成语法解析。

lex := &Lexer{sql: sql}
n := yyParse(lex)

[]kvdb/pkg/sql.Statment len: 1, cap: 1, 
[*kvdb/pkg/sql.SelectStmt {
    Filed: []*kvdb/pkg/sql.SelectField len: 1, cap: 1, [*(*"kvdb/pkg/sql.SelectField")(0xc0000145d0)], 
    From: *(*"kvdb/pkg/sql.SelectStmtFrom")(0xc00005e5a0), 
    Where: []kvdb/pkg/sql.BoolExpr len: 2, cap: 2, [...,...], 
    Order: []*kvdb/pkg/sql.OrderField len: 0, cap: 0, nil, 
    Limit: *(*"kvdb/pkg/sql.SelectStmtLimit")(0xc000020320)}]

完整代码

参考：

转载自:https://juejin.cn/post/7234787766151331899
评论
请登录