parser

Documentation

Overview

Package parser contains the EQL parser.

Lexer

Lex() is a lexer function to convert a given search query into a list of tokens.

Based on a talk by Rob Pike: Lexical Scanning in Go

https://www.youtube.com/watch?v=HxaD_trXwRE

Parser

Parse() is a parser which produces a parse tree from a given set of lexer tokens.

Based on an article by Douglas Crockford: Top Down Operator Precedence

http://crockford.com/javascript/tdop/tdop.html

which is based on the ideas of Vaughan Pratt and his paper: Top Down Operator Precedence

http://portal.acm.org/citation.cfm?id=512931 https://tdop.github.io/

ParseWithRuntime() parses a given input and decorates the resulting parse tree with runtime components which can be used to interpret the parsed query.

Index

• Constants
• Variables
• func FirstWord(input string) string
• func Lex(name string, input string) chan LexToken
• func PrettyPrint(ast *ASTNode) (string, error)
• type ASTNode
  • func ASTFromPlain(plainAST map[string]interface{}) (*ASTNode, error)
  • func Parse(name string, input string) (*ASTNode, error)
  • func ParseWithRuntime(name string, input string, rp RuntimeProvider) (*ASTNode, error)
  • func (n *ASTNode) Plain() map[string]interface{}
  • func (n *ASTNode) String() string
• type Error
  • func (pe *Error) Error() string
• type LexToken
  • func LexToList(name string, input string) []LexToken
  • func (t LexToken) PosString() string
  • func (t LexToken) String() string
• type LexTokenID
• type Runtime
• type RuntimeProvider

Constants

const (
	NodeEOF = "EOF"

	NodeVALUE         = "value"
	NodeTRUE          = "true"
	NodeFALSE         = "false"
	NodeNULL          = "null"
	NodeFUNC          = "func"
	NodeORDERING      = "ordering"
	NodeFILTERING     = "filtering"
	NodeNULLTRAVERSAL = "nulltraversal"

	NodeCOMMA  = "comma"
	NodeGROUP  = "group"
	NodeEND    = "end"
	NodeAS     = "as"
	NodeFORMAT = "format"

	NodeGET    = "get"
	NodeLOOKUP = "lookup"
	NodeFROM   = "from"
	NodeWHERE  = "where"

	NodeUNIQUE      = "unique"
	NodeUNIQUECOUNT = "uniquecount"
	NodeISNOTNULL   = "isnotnull"
	NodeASCENDING   = "asc"
	NodeDESCENDING  = "desc"

	NodeTRAVERSE = "traverse"
	NodePRIMARY  = "primary"
	NodeSHOW     = "show"
	NodeSHOWTERM = "showterm"
	NodeWITH     = "with"
	NodeLIST     = "list"

	NodeOR  = "or"
	NodeAND = "and"
	NodeNOT = "not"

	NodeGEQ = ">="
	NodeLEQ = "<="
	NodeNEQ = "!="
	NodeEQ  = "="
	NodeGT  = ">"
	NodeLT  = "<"

	NodeIN    = "in"
	NodeNOTIN = "notin"

	NodeLIKE        = "like"
	NodeCONTAINS    = "contains"
	NodeBEGINSWITH  = "beginswith"
	NodeENDSWITH    = "endswith"
	NodeCONTAINSNOT = "containsnot"

	NodePLUS   = "plus"
	NodeMINUS  = "minus"
	NodeTIMES  = "times"
	NodeDIV    = "div"
	NodeMODINT = "modint"
	NodeDIVINT = "divint"

	NodeLPAREN = "("
	NodeRPAREN = ")"
	NodeLBRACK = "["
	NodeRBRACK = "]"
)

Available parser AST node types

const RuneEOF = -1

RuneEOF is a special rune which represents the end of the input

const TokenSHOWTERM = LexTokenID(-1)

TokenSHOWTERM is an extra token which is generated by the parser to group show terms

Variables

var (
	ErrUnexpectedEnd            = errors.New("Unexpected end")
	ErrLexicalError             = errors.New("Lexical error")
	ErrUnknownToken             = errors.New("Unknown term")
	ErrImpossibleNullDenotation = errors.New("Term cannot start an expression")
	ErrImpossibleLeftDenotation = errors.New("Term can only start an expression")
	ErrUnexpectedToken          = errors.New("Unexpected term")
)

Parser related error types

Functions

func FirstWord

func FirstWord(input string) string

FirstWord returns the first word of a given input.

func Lex

func Lex(name string, input string) chan LexToken

Lex lexes a given input. Returns a channel which contains tokens.

func PrettyPrint

func PrettyPrint(ast *ASTNode) (string, error)

PrettyPrint produces a pretty printed EQL query from a given AST.

Types

type ASTNode

type ASTNode struct {
	Name     string     // Name of the node
	Token    *LexToken  // Lexer token of this ASTNode
	Children []*ASTNode // Child nodes
	Runtime  Runtime    // Runtime component for this ASTNode
	// contains filtered or unexported fields
}

ASTNode models a node in the AST

func ASTFromPlain

func ASTFromPlain(plainAST map[string]interface{}) (*ASTNode, error)

ASTFromPlain creates an AST from a plain AST. A plain AST is a nested map structure like this:

{
	name     : <name of node>
	value    : <value of node>
	children : [ <child nodes> ]
}

func Parse

func Parse(name string, input string) (*ASTNode, error)

Parse parses a given input string and returns an AST.

func ParseWithRuntime

func ParseWithRuntime(name string, input string, rp RuntimeProvider) (*ASTNode, error)

ParseWithRuntime parses a given input string and returns an AST decorated with runtime components.

func (*ASTNode) Plain

func (n *ASTNode) Plain() map[string]interface{}

Plain returns this ASTNode and all its children as plain AST. A plain AST only contains map objects, lists and primitive types which can be serialized with JSON.

func (*ASTNode) String

func (n *ASTNode) String() string

String returns a string representation of this token.

type Error

type Error struct {
	Source string // Name of the source which was given to the parser
	Type   error  // Error type (to be used for equal checks)
	Detail string // Details of this error
	Line   int    // Line of the error
	Pos    int    // Position of the error
}

Error models a parser related error

func (*Error) Error

func (pe *Error) Error() string

Error returns a human-readable string representation of this error.

type LexToken

type LexToken struct {
	ID    LexTokenID // Token kind
	Pos   int        // Starting position (in runes)
	Val   string     // Token value
	Lline int        // Line in the input this token appears
	Lpos  int        // Position in the input line this token appears
}

LexToken represents a token which is returned by the lexer.

func LexToList

func LexToList(name string, input string) []LexToken

LexToList lexes a given input. Returns a list of tokens.

func (LexToken) PosString

func (t LexToken) PosString() string

PosString returns the position of this token in the origianl input as a string.

func (LexToken) String

func (t LexToken) String() string

String returns a string representation of a token.

type LexTokenID

type LexTokenID int

LexTokenID represents a unique lexer token ID

const (
	TokenError LexTokenID = iota // Lexing error token with a message as val
	TokenEOF                     // End-of-file token

	TokenVALUE    // Simple value
	TokenNODEKIND // Node kind value

	TokenGeneral // General token used for plain ASTs

	TOKENodeSYMBOLS // Used to separate symbols from other tokens in this list

	TokenGEQ
	TokenLEQ
	TokenNEQ
	TokenEQ
	TokenGT
	TokenLT
	TokenLPAREN
	TokenRPAREN
	TokenLBRACK
	TokenRBRACK
	TokenCOMMA
	TokenAT
	TokenPLUS
	TokenMINUS
	TokenTIMES
	TokenDIV
	TokenDIVINT
	TokenMODINT

	TOKENodeKEYWORDS // Used to separate keywords from other tokens in this list

	TokenGET
	TokenLOOKUP
	TokenFROM
	TokenGROUP
	TokenWITH
	TokenLIST
	TokenNULLTRAVERSAL
	TokenFILTERING
	TokenORDERING
	TokenWHERE
	TokenTRAVERSE
	TokenEND
	TokenPRIMARY
	TokenSHOW
	TokenAS
	TokenFORMAT
	TokenAND
	TokenOR
	TokenLIKE
	TokenIN
	TokenCONTAINS
	TokenBEGINSWITH
	TokenENDSWITH
	TokenCONTAINSNOT
	TokenNOT
	TokenNOTIN
	TokenFALSE
	TokenTRUE
	TokenUNIQUE
	TokenUNIQUECOUNT
	TokenNULL
	TokenISNULL
	TokenISNOTNULL
	TokenASCENDING
	TokenDESCENDING
)

Available lexer token types

type Runtime

type Runtime interface {

	/*
	   Validate this runtime component and all its child components.
	*/
	Validate() error

	/*
		Eval evaluate this runtime component.
	*/
	Eval() (interface{}, error)
}

Runtime provides the runtime for an ASTNode.

type RuntimeProvider

type RuntimeProvider interface {

	/*
	   Runtime returns a runtime component for a given ASTNode.
	*/
	Runtime(node *ASTNode) Runtime
}

RuntimeProvider provides runtime components for a parse tree.