Shulou(Shulou.com)05/31 Report--

This article introduces the knowledge of "how to understand context-free grammar in PostgreSQL parsing". Many people will encounter this dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Context-free grammar

Basic concept

Here is an explanation from Wikipedia

Context-free grammar (grammar) (English: context-free grammar, abbreviated as CFG). In computer science, if the production rule of a formal grammar G = (N, Σ, P, S) takes the following form: v-> w, it is called. Where V ∈ N, w ∈ (N ∪ Σ) *. The reason why context-free grammars are named "context-free" is that the character V can always be replaced freely by the string w, regardless of the context in which the character V appears. A formal language is context-free if it is generated by a context-free grammar (item context-free language).

Context-free grammars are important because they are sufficiently expressive to represent the syntax of most programming languages, including SQL; in fact, almost all programming languages are defined through context-free grammars. On the other hand, the context-free grammar is simple enough that we can construct an effective analysis algorithm to verify whether a given string is generated by a context-free grammar. BNF (Bacchus-Noel paradigm) is often used to express context-free grammars.

Formal definition

Context-free grammar G is a 4-tuple:

G = (V, Σ, R, S) here

V is a finite set of "non-final" symbols or variables. They represent different types of phrases or clauses in a sentence.

Σ is a finite set of Terminators, which do not intersect in V. they constitute the actual content of the sentence.

S is the starting variable, which is used to represent the entire sentence (or program). It must be an element of V.

R is the relation from V to (V ∪ Σ) ∗ such that ∃ w ∈ (V ∪ Σ) ∗: (Sminew) ∈ R.

In addition, R is a finite set. The members of R are called grammatical "rules" or "production". The asterisk indicates the Kleene asterisk operation.

Example

For example, we can define a simple query statement with a context-free syntax:

Simple query statement = (V, Σ, R, S)

Where:

V = {QUERY,STMT_SELECT,STMT_FROM,STMT_WHERE,OBJECT,VAR,EXPR}

S = {QUERY}

Σ = {select,from,where, [a murz] [a-z0-9] +, [a murz] [a-z0-9] *,'}

R:

QUERY-> STMT_SELECT STMT_FROM STMT_WHERE

OBJECT-> [a murz] [a-z0-9] +

VAR-> ['[amurz] [a-z0-9] *']

EXPR-> OBJECT = VAR

STMT_SELECT-> select OBJECT [, OBJECT] *

STMT_FROM-> from OBJECT [, OBJECT] *

STMT_WHERE-> where EXPR

According to this context-free syntax, you can get some sample statements of this simple query statement:

Select aacbdre from T1, T2 where C1 = 'axx1'

Select C1, c2, xx from e1, T2, xx, where C1 =''

That's all for the content of "how to understand context-free grammar in PostgreSQL parsing". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.