7

Is SQL a context free language or some other type of language?

Sascha Wolf
  • 18,810
  • 4
  • 51
  • 73
Abhinav Arya
  • 225
  • 3
  • 9
  • 3
    Do you mean is SQL *also* regular? CFG's encompass regular languages. So, they aren't mutually exclusive. To answer your question though, SQL is *not* a regular language. – aquinas Oct 27 '14 at 19:47
  • Does SQL uses both regular and context free grammar contexts ? In that case, being an intersection of both, it is still context free. – Abhinav Arya Oct 28 '14 at 05:00
  • 1
    Just to clarify, a language is context-free when it is generated by a context-free grammar. There're SQL context-free grammar definitions online. Just google around and you'll find some. [Here](http://savage.net.au/SQL/sql-99.bnf.html)'s one, for example. – MSX Oct 30 '14 at 20:07
  • 1
    Does the DELIMITER command throw a wrench in that at all? – Jacob Jul 20 '18 at 20:41

4 Answers4

7

According to https://stackoverflow.com/a/31265136 SQL is not a regular language. The short explanation is that each select query looks like

 SELECT x FROM y WHERE z

and y can be another select query itself, so it cannot be simulated with finite-state machine. As mentioned before, there are some CFGs for SQL standarts in Backus–Naur Form, thereby SQL is nonregular context free language.

Community
  • 1
  • 1
SGP
  • 176
  • 2
  • 9
3

Any CFG for SQL will do most of the work, but will always be slightly too permissive.

A good example of an SQL CFG comes from antlr: https://github.com/antlr/grammars-v4/blob/master/sql/plsql/PlSqlParser.g4#L1982

But at that line (1982), you see that in a values_clause, column values are recursively added regardless of how many columns might be specified, or how many values are in another row, which is invalid sql:

insert into xyz values
  (1, 'hello'),
  (2, 'bye'),
  (3, 'hi', 'uhm...'); -- invalid!

Try running it here: https://www.db-fiddle.com/f/6gwgcg6qBLKpFbCEPtB6dy/0

This syntax can never be fully encapsulated by a CFG, as it is equivalent to the { (a^n)(b^n)(c^n) : n ≥ 1 } language, which is famously not allowed in CFGs (but allowed in CSGs)

You could argue this is a runtime error instead of a parsing error. But you can use the same argument for every language that is interpreted, so it's a bit of a grey area.

towc
  • 1,983
  • 2
  • 22
  • 36
2

@aquinas wrote:

Do you mean is SQL also regular? CFG's encompass regular languages. So, they aren't mutually exclusive. To answer your question though, SQL is not a regular language.

@MSX wrote:

Just to clarify, a language is context-free when it is generated by a context-free grammar. There're SQL context-free grammar definitions online. Just google around and you'll find some. Here's one, for example.

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
-1

Similar in PL/SQL context can be exactly what code it is SQL or PL/SQL because if we define function keywords as concrete, then if we want to control which functions can be used, this context must be known

Dainis Polis
  • 1
  • By me it's when some syntax nonterminal resoult depends on some state (or context), that can be determinated early in parsing process – Dainis Polis Jul 18 '20 at 07:47