Building a database from scratch in C: Part 3

What is SQL?

Note: If you already know what SQL is, the syntax, and how to use it, you can skip down to Syntactic and Lexical Analysis

If you have not already heard of SQL, it’s quite important to understand what it is, what it does, and how you use it before proceeding.

SQL stands for Structured Query Language, and it’s the language used to query a relational database (I talked about this in Part 2). It’s important to follow the SQL standard as a baseline, so that it’s easier for other people to learn how to use it, as they will most likely already know basic SQL syntax.

Syntax

SQL can vary in complexity, from being simply INSERT, SELECT, DELETE, and a few others, to complex multi-statement (separated be a semicolon) query.

If you do not already know the SQL syntax, I would highly recommend you learn about it, since you are about to make a parser for it, which is difficult if you do not already know the syntax. I recommend W3School’s SQL Tutorial for absolute beginners.

Syntactic and Lexical Analysis

Syntactic and Lexical analysis actually analysis the SQL statement(s), translating them to a form that can be interpreted by the program more efficiently. We will be developing a parser, which is also what scripting languages (such as Python) use. Programming languages however compile instructions down, but SQL is an interpreted (structured) query language (not to be confused with a scripting/programming language, SQL does not meet the requirements to be a scripting/programming language).

Lexical analysis comes first in the process, this is where all of the comments, and any unnecessary white space are removed. The query is then converted into a set of tokens, which are then checked for any illegal identifiers (E.g. naming a table INSERT, or SELECT), and at this stage, it is looking for any illegal names, such as a space in a table name. These tokens are then passed along to the syntactic analysis.

Syntactic analysis comes next in the process, this checks to ensure that the tokens follow the rules of SQL, and then places the tokens into an abstract syntax tree. At this stage, any errors about breaking the rules of SQL arise, and the entire process will be stopped.

The abstract syntax tree is then placed in a form that the database can use to make the query, and then passed onto the next stage.

Series

Part 1: Environment set up
Part 2: Architecture design
Part 3: What is SQL? (This)