Programming from Top to Bottom - Parsing
Tags: programming, learning, beginners
Published: 2024-03-18 15:28:30

In the [previous article](https://dev.to/digitalcrafting/programming-from-top-to-bottom-the-basics-ba) we saw that there is quite a gap between what we write and what CPU does and we also saw a simplified flow diagram of interpreted and compiled languages.

We will start with interpreted languages, and then move to VM and natively compiled ones, as they are progressively more complicated.

But before all that, let's ask ourselves more general question: 

### What is _programming language_ built of?

Well, let's start with spoken language. It is built of _words_ and _grammar_. Words are used to _name/describe things/actions_, and grammar defines _how_ it can be done. For example, expression `high mountain`, consists of two words `high` and `mountain`. Grammar tell us, that: 
- **high** is an _adjective_,
- _adjectives_ describe things,
- **mountain** is a _noun_,
- _nouns_ name things,
- _adjective_ must come before _noun_.

Thanks to those simple rules, we know how to decipher the expression `high mountain`, and many more like that.

Getting back to programming: programming language is pretty much **the same**, only the grammar is simpler. Also, when talking about programming languages **words** are called **tokens**, and the types of tokens are named differently (although, you could name them _adjectives_ and _nouns_ if you wished).   

Much like for spoken language, programming language grammar, aside from naming types of tokens and what they look like, tells us what we can do with them. For example, for this expression: `int x;`, it tells us that:
- **int** is a _type_,
- when the expression starts with _type_, it's also a _declaration_,
- **x** is an _identifier_,
- _type_ must always come before _identifier_,
- **;** marks end of expression,

If you compare the `high mountain` with `int x;` side by side, they are not that different in how they are described.

With more words comes the complexity, so in order to group them together, we form `sentences`, and it's no different in programming - it is called an `expression` or a `statement`. As in natural languages, an `expression` can be simple or complex consisting of 1 or more other `expressions` or `statements`, but we will get to that. 

To summarize:
- `word` is called a `token` in programming language,
- `sentence` is called an `expression` or a `statement`,
- other elements differ from language to language.

That's all well and good, but in order for CPU to actually do something, we have to parse programming language and transform it into machine code. So, the next natural questions is:

### What is parsing?

Simply put: _it's translating text into a data structure, based on some specification_.

That's it. In case of programming languages, the specification is called _grammar_, which we explained in previous section. If you are interested in more detailed explanation, you can check [this article](https://tomassetti.me/guide-parsing-algorithms-terminology/).

Parser itself is made out of 2 components: **tokenizer** (also called **lexer**) and **AST generator** (actually it's called **parser** in other sources, don't ask me why parser contains parser, we probably run out of names).

### Tokenizer

**Tokenizer** is responsible for taking in file containing some text, and dividing it into tokens (words).

**Token** is much simpler than a spoken word. Unlike in the spoken language, there can be no confusion about the meaning of a token. Let's look at a bit more complicated example, a code like this:
``` java
int x = a + b;
```
Can be divided into following **tokens**:

![Tokens example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qlfr7vnqs4l46yp07ede.png)

You can never mistake _type_declaration_ with an _identifier_, otherwise the program will not work. Aside from that constraint, you are free to name them whatever you like, there is no one standard, and each parser has it own naming conventions, unless you are planning to use something like [LLVM](https://llvm.org/). If you are interested, you can see examples of naming in different language parsers [in the AST Explorer](https://astexplorer.net/).

Actually, there is one more token type that's not presented on the diagram: _white_spaces_. Unless it's Python or YAML, we will simply ignore the whitespace characters, their only purpose is to divide other tokens that would otherwise be indistinguishable, like `int value` from `intvalue`.

So, a **tokenizer** goes through a file, and reads all the tokens one by one, returning them to **parser**. How does it know which token it read? By using regex. Each token definition has regex expression associated with it, and we check if the beginning of our string matches one of the token types, otherwise we return **null** or throw an error. You could write it simply checking each and every character in order to avoid nested looping, but for this article we are not be doing that.

Notice that we didn't yet touched on the grammar defining the order of tokens, that's the AST generator's task.

### AST generator - actual parser

But wait, what is an AST? It's an acronym for **Abstract Syntax Tree**, and it's a intermediate representation of our code in a form of... well... a tree (finally those data structure courses can be of some use).

Why do we even need that? For type and grammar checking, optimizations, and it's easier to traverse than an array of tokens.

In our example, the code: 
``` java
int x = a + b;
```
Will be represented as:

![AST Example Simple Expression](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yzlp7wd19zr1nssub880.png)

You may notice the missing **;** - that's because it's only a delimiter - it marks the end of a single `expression` and is not relevant for further processing. Also, in this diagram I don't show the metadata for each node, such as type of the token, but it's there.

Going from the top, the expression can be easily interpreted as an assignment `expression`, where we declare a new variable called **x** of type **int**, and _assign_ to it the result of _adding_ value from variable **a** to value from variable **b**.

Let's see more complicated example with a `function` declaration: 
``` java
int square(int y) {
    return y*y;
}
```
The AST for that piece of code would look something like this:

![AST Example Function](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0xecx811rr7d8e3ddd4c.png)

Well, that became quite big really quick, didn't it? If we added a class on top of that, the diagram would be twice as big, so from now on, we will switch to [JSON](https://www.json.org/json-en.html) representation of a tree, and only for parts that we actually need.

Thing to note in this example is that a `function` has 3 children nodes:
- `return type`,
- `parameters`,
- `body`.

A `body` node is just a list of expressions in order of appearance, ending with optional `return` statement.

Given that information, you can probably guess what a `class` declaration would look like, it would have:
- `identifier` as a name,
- `access modifier` - `public`, `private` or `protected`,
- `body` which would a list of `expressions`.

You can see where this is going. Each structure and expression in a programming language is well defined and has a set of parameters that it consists of. It also has a defined _order_ in which they can appear, for example: a class name identifier must appear _after_ a `class` _keyword_.

And that is called **programming language grammar**.

### Grammar

Grammar can be defined using a [Backus-Naur Form](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form), which is a meta language that for me became readable only _after_ I actually implemented parser, but nevertheless, let's go through a brief introduction now.

Let's use our original piece of code as an example, which was variable declaration: `int x;`

This is called a `declaration expression`, and as name suggests, it's used to declare a variable.

The grammar for this type of expression, can be described as:
"A type identifier, which is a keyword, followed by a name".

In Backus-Naur Form (BNF) it can be written as:
```
<declaration-expression> ::= <type-identifier> <identifier> 

```

Let's look at another example:
```java
int x = square(x)
```

In BNF, this type of expression, can be defined as:
```
<assignment-expression> ::= <declaration-expression> '=' <expression> | <identifier> '=' <expression> 

```

Meaning: "An assignment expression is a declaration followed by a '=', followed by an expression, or, an identifier, followed by '=', followed by an expression".

This can go on and on, and as the expressions become more complex, so does the BNF notation, however, when written right, the BNF can reflect the code quite well, which we will see in the next article.

### Summary

Finally, the theory part is over, at least for the parsing that is :wink:

In the next article, we will dive into the tokenizer and parser code. 

Also note, that what I wrote about is applicable to _**any**_ resource, not just programming language. You can use this knowledge to parse JSON, XML, HTML, CSV and whatever else you need, it only comes down to defined grammar.

See you in the next one!