# 05.08.2022 - Parsing/Recursive Descent Parser

A parser is a program that usually takes a stream of lexical tokens and transforms them into another data structure, usually in the form of a parse tree that satisfies the language's grammar rules.

## What is a Recursive Descent Parser?

**Recursive Descent Parser** is a top-down parser *where every non-terminal in the BNF grammar is a subroutine*. The parser works by *recursively calling each subroutine to construct the parsed output*. It's not the only algorithm to implement a parser, but it's one of the most simple ones that are very easy to understand and implement.

For example, let's say we have a grammar to parse money amount in `USD`, `GBP`, and `EUR`. The money amount should be written in the form of `<currency_symbol> <amount>`, like `$100`:

```bnf
money           = currency_symbol amount ;
currency_symbol = '$' | '£' | '€' ;
amount          = INTEGER ;
```

The grammar has three _non-terminals_: `money`, `currency_symbol`, and `amount`. When implemented, we should also implement three parsing methods: `parse_money()`, `parse_currency_symbol()`, and `parse_amount()`. Each of the parsing methods will call each other just like how they're related in the grammar rules:

```rust
type ParseResult<T> = Result<T, ParseError>;

impl<'a> Parser<'a> {
    /* amount = INTEGER ; */
    fn parse_amount(&mut self) -> ParseResult<i32> {
        ...
    }

    /* 	currency_symbol = '$' | '£' | '€' ; */
    fn parse_currency_symbol(&mut self) -> ParseResult<Currency> {
        ...
    }

    /* money = currency_symbol amount ; */
    fn parse_money(&mut self) -> ParseResult<MoneyNode> {
        let currency = self.parse_currency_symbol()?;
        let amount = self.parse_amount()?;
        return Ok(MoneyNode { currency, amount });
    }
}
```

## Implementing a Money Parser

Let's dig deeper into the above example. We will focus on the parser. Let's assume that we already have a lexer that converts an input string like `"$100"` into a list of tokens.

### Data Structures

In this program, we have two types of tokens: the `CurrencySymbol` token and the `Number` token:

```rust
#[derive(Debug, PartialEq, Clone, Copy)]
enum TokenType {
    CurrencySymbol,
    Number
}

#[derive(Debug)]
struct Token<'a> {
    token_type: TokenType,
    content: &'a str
}

impl<'a> Token<'a> {
    pub fn new(token_type: TokenType, content: &'a str) -> Self {
        Self {
            token_type,
            content
        }
    }
}
```

The **input** for our parser is a `Vec<Token>` that looks like this:

```rust
// List of tokens for the string "£128"
let tokens = vec![
    Token::new(TokenType::CurrencySymbol, "£"),
    Token::new(TokenType::Number, "128")
];
```

The **output** of our parser is a data structure called `MoneyNode`:

```rust
#[derive(Debug, PartialEq)]
enum Currency {
    USD,
    GBP,
    EUR
}

#[derive(Debug, PartialEq)]
struct MoneyNode {
    currency: Currency,
    amount: i32
}
```

### Error Handling

For this grammar, there are two types of errors that could happen during parsing:

1. **Unexpected token error**: when the parser found a token that was misplaced.
2. **Invalid amount error**: when the parser could not parse the amount number.

We will create a custom error type and a `Result<T>` type to handle these two errors:

```rust
#[derive(Debug, PartialEq)]
enum ParseError {
    UnexpectedToken(TokenType, TokenType),
    InvalidAmount
}

impl Display for ParseError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::UnexpectedToken(expected, found) =>
                write!(f, "Unexpected Token: Expected {:?}. Found {:?}.", expected, found),
            Self::InvalidAmount =>
                write!(f, "Invalid Amount!"),
        }
    }
}

type ParseResult<T> = Result<T, ParseError>;
```

### The Parser and some utility methods

Now, let's create the parser. It takes a list of input tokens and uses a `pos` variable to keep track of the current token.

```rust
struct Parser<'a> {
    tokens: Vec<Token<'a>>,
    pos: usize
}
```

We will implement some utility methods to control the input token stream, like:

1. **is_eof()**: to check if we're at the end of the token stream or not
2. **peek()**: to get the current token
3. **is_match()**: to check if the current token matched the expected type or not
4. **advance()**: to consume the current token and move on to the next

These methods are not exclusive to a recursive descent parser, but they're very helpful, as they keep the actual parsing code looks clean:

```rust
impl<'a> Parser<'a> {
    pub fn new(tokens: Vec<Token<'a>>) -> Self {
        Self {
            tokens,
            pos: 0
        }
    }

    fn is_eof(&self) -> bool {
        self.pos >= self.tokens.len()
    }

    fn peek(&self) -> &Token {
        &self.tokens[self.pos]
    }

    fn is_match(&self, token_type: TokenType) -> bool {
        !self.is_eof() && self.peek().token_type == token_type
    }

    fn advance(&mut self) {
        self.pos += 1;
    }
}
```

### The Recursive Descent Parser

Now, the main part of the parser that we are waiting for. First, let's write a parser for the `amount` rule of the grammar:

```rust
// Grammar:
//   amount = INTEGER ;
fn parse_amount(&mut self) -> ParseResult<i32> {
    let token = self.peek();
    if self.is_match(TokenType::Number) {
        let result = token.content.parse::<i32>()
                          .map_err(|_| ParseError::InvalidAmount);
        self.advance();
        return result;
    }
    Err(ParseError::UnexpectedToken(
            TokenType::Number,
            token.token_type
        )
    )
}
```

We simply check if the current token is a `Number` token or not and parse the content of this token into an `i32` number. In this method, we can see the usage of both the `InvalidAmount` and the `UnexpectedToken` errors.

Next, we will write the parser for the `currency_symbol` rule:

```rust
// Grammar:
//   currency_symbol = '$' | '£' | '€' ;
fn parse_currency_symbol(&mut self) -> ParseResult<Currency> {
    let token = self.peek();
    if self.is_match(TokenType::CurrencySymbol) {
        let currency_symbol = match token.content {
            "$" => Currency::USD,
            "£" => Currency::GBP,
            _ => Currency::EUR
        };
        self.advance();
        return Ok(currency_symbol);
    }
    Err(ParseError::UnexpectedToken(
            TokenType::CurrencySymbol,
            token.token_type
        )
    )
}
```

Now that we have the parser for both the `currency_symbol` and `amount` rules. The last step is to write the parser for the `money` rule, it is implemented the same way the `money` rule is written. We will call the `currency_symbol` parser, then call the `amount` parser.

None of the above parsers will return any error value for valid input. Their return value can be combined to create the output `MoneyNode` object:

```rust
// Grammar:
//   money = currency_symbol amount ;
fn parse_money(&mut self) -> ParseResult<MoneyNode> {
    let currency = self.parse_currency_symbol()?;
    let amount = self.parse_amount()?;
    return Ok(MoneyNode {
        currency,
        amount
    });
}
```

And that's it! We have already finished our parser!

### Test the parser

Now, let's write some tests to see if the parser works or not. First, in a happy path, we will pass a valid token list and expect to see a valid output:

```rust
#[test]
fn test_parse_usd() {
    let tokens = vec![
        Token::new(TokenType::CurrencySymbol, "$"),
        Token::new(TokenType::Number, "512")
    ];
    let mut parser = Parser::new(tokens);
    assert_eq!(parser.parse_money(), Ok(MoneyNode {
        currency: Currency::USD,
        amount: 512
    }))
}
```

Of course, if the input currency is EUR instead of USD, the parser should return the correct value:

```rust
#[test]
fn test_parse_eur() {
    let tokens = vec![
        Token::new(TokenType::CurrencySymbol, "€"),
        Token::new(TokenType::Number, "9372")
    ];
    let mut parser = Parser::new(tokens);
    assert_eq!(parser.parse_money(), Ok(MoneyNode {
        currency: Currency::EUR,
        amount: 9372
    }))
}
```

Don't forget some unhappy paths, the parser should return an `Err` value if any of the parsing steps fails:

```rust
#[test]
fn test_parse_unexpected_token() {
    let tokens = vec![
        Token::new(TokenType::Number, "512"),
        Token::new(TokenType::CurrencySymbol, "$"),
    ];
    let mut parser = Parser::new(tokens);
    assert_eq!(parser.parse_money(), Err(
        ParseError::UnexpectedToken(
            TokenType::CurrencySymbol,
            TokenType::Number
        )
    ))
}

#[test]
fn test_parse_invalid_amount() {
    let tokens = vec![
        Token::new(TokenType::CurrencySymbol, "$"),
        Token::new(TokenType::Number, "3rr0r"),
    ];
    let mut parser = Parser::new(tokens);
    assert_eq!(parser.parse_money(), Err(ParseError::InvalidAmount))
}
```

Run the test with the `cargo test` command, and you should see all tests are passed:

```lua
running 5 tests
test test_parse_eur ... ok
test test_parse_gbp ... ok
test test_parse_invalid_amount ... ok
test test_parse_usd ... ok
test test_parse_unexpected_token ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
```

You can see the complete source code of the parser in [this gist](https://gist.github.com/huytd/2ca7d9b25f539cbcf549f4bd2a19bcca).

---

In this article, we learned what a Recursive Descent Parser is and how to implement the parser for each grammar rule, which serves as building blocks for each other. In the next article, we will look at a more complex parser for solving arithmetic expressions, which will give us a better look at the recursive characteristics of the Recursive Descent Parsing technique.

Recursive Descent Parser

# 02.13.2022 - Parsing/Railroad Diagrams

**Railroad Diagrams** (or **Syntax Diagrams**) are the graphical way to represent [context-free grammars](/everyday/02-10-2022-parsing-context-free-grammar).

Each diagram defines a nonterminal. And they must have an **entry point** and an **endpoint**.

There is no official standard about how should we draw the railroad/syntax diagrams but historically, terminals are represented by round boxes and nonterminals are represented by rectangular boxes.

Let's take a look at the following grammar:

```bnf
sum = signed digit, [ "+", signed digit ] ;
signed digit = [ "-" ], digit ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
```

The railroad diagram of the above grammar can be represented as:

**digit**

![](_meta/digit-railroad.png)

**signed digit**

![](_meta/signed-digit-railroad.png)

**sum**

![](_meta/sum-railroad.png)

In real world, syntax diagram can be seen in [JSON specs](https://www.json.org/json-en.html), or [SQLite](https://www.sqlite.org/syntaxdiagrams.html).

Railroad Diagram

# 02.12.2022 - Parsing/Backus-Naur Form and variants

**Backus-Naur Form (BNF)** is a metasyntax for [context-free grammars](/everyday/02-10-2022-parsing-context-free-grammar), is used to describe the syntax of languages used in computing such as programming languages, instruction sets,...

## The BNF syntax

The specification of BNF is quite simple, it's a set of derivation rules written as:

```bnf
<symbol> ::= expression1 | expression2
```

Where:

- `<symbol>` is the nonterminal, they are always enclosed between the pair `<>`
- `expressions` consists of one or more sequences of either terminals or nonterminals.
- `::=` mean the symbol on the left must be replaced by the expression on the right.
- If a nonterminal can be replaced by multiple expressions, they can be separated by the vertical bar "|"

For example, the following grammar define a signed integer number:

```bnf
<signed integer> ::= <integer> | <sign> <integer>
<integer> ::= <digit> | <integer> <digit>
<digit>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<sign>   ::= -
```

## The Extended BNF syntax

There are many variants of BNF, one of the most popular variants is **Extended BNF (EBNF)**. It added some other symbols so we can explain the grammar better, like the sequence symbol (`,`), repeated symbol (`{}`), optional symbol (`[]`),...

In EBNF, nonterminal does not necessarily enclose between the pair `<>`, and the definition symbol `::=` can be written as `=`. Terminals are strictly enclosed within the quotation marks (`""` or `''`). Each production rule is terminated by the semicolon `;`, and they can contain comments (`(* *)`) too:

```bnf
(* this is a comment *)
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
```

A concatenation symbol is used to express the sequence of terminals, each separated by a comma (`,`), for example:

```bnf
twelve = "1", "2" ;
ten = "1", "0" ;
one ten = "1", ten ;
```

If a symbol needed to be repeated (zero or more times), we can use `{}` symbols. For example, the following definition matches all powers of ten, including 10, 100, 1000, 10000,...

```bnf
powers of ten = one, zero, { zero } ;
one  = "1" ;
zero = "0" ;
```

Optional can be expressed by `[]`, everything that is optional can be present just once or not at all, for example:

```bnf
signed digit = [ "-" ], digit ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
```

# 02.11.2022 - Parsing/Context-Free Grammar/Leftmost and Rightmost Derivations

A derivation of *a string* for *a grammar* is a *sequence of production rule applications*.

The process of getting the string through the derivation is the parsing process.

For example, with the following grammar:

```
S → S + S        (1)
S → 1            (2)
S → a            (3)
```

The string $1 + 1 + a$ can be derived from the start symbol $S$ using 2 types of derivations: **leftmost derivation** and **rightmost derivation**.

## Leftmost Derivation

In the leftmost derivation, the nonterminals are applied from left to right. Initially, we can apply rule 1 on the initial $S$:

$$
\rightarrow \underline{S + S} \qquad \text{(applied rule 1)}
$$

Next, the leftmost $S$ can be applied with rule 2:

$$
\rightarrow \underline{1} + S \qquad \text{(applied rule 2)}
$$

The next nonterminal is the second $S$. If we apply any of rule 2 or 3, there are still underived characters in the input string, so we choose rule 1 instead:

$$
\rightarrow 1 + \underline{S + S} \qquad \text{(applied rule 1)}
$$

Now, with the remaining characters from the input, we can apply rule 2 on the first $S$:

$$
\rightarrow 1 + \underline{1} + S \qquad \text{(applied rule 2)}
$$

Finally, the last $S$ can be applied with rule 3:

$$
\rightarrow 1 + 1 + \underline{a} \qquad \text{(applied rule 3)}
$$

The above derivation can be represented as the following parse tree:

![](_meta/leftmost-parse-tree.png)

## Rightmost Derivation

In the rightmost derivation, the nonterminals are applied from right to left.

Initially, we can apply rule 1 on the initial $S$:

$$
\rightarrow \underline{S + S} \qquad \text{(applied rule 1)}
$$

This time, we apply rule 1 on the rightmost $S$:

$$
\rightarrow S + \underline{S + S} \qquad \text{(applied rule 1)}
$$

We found that rule 3 can be applied to the rightmost $S$:

$$
\rightarrow S + S + \underline{a} \qquad \text{(applied rule 3)}
$$

Next, we can apply rule 2:

$$
\rightarrow S + \underline{1} + a \qquad \text{(applied rule 2)}
$$

And finally, rule 2 can be applied again:

$$
\rightarrow \underline{1} + 1 + a \qquad \text{(applied rule 2)}
$$

This derivation can be represented as the following parse tree:

![](_meta/rightmost-parse-tree.png)

Context-Free Grammar Derivations Leftmost Rightmost

# 02.10.2022 - Parsing/Context-Free Grammar

Context-Free Grammar (CFG) is a grammar where **production (or rewrite) rules** are in the form of:

$$
A \rightarrow \alpha
$$

$A$ is a **single nonterminal symbol**, and $\alpha$ is the **string of terminals or nonterminals**, it can also be empty.

A **terminal** (or **token**) is a symbol that does not appear on the left side of the arrow of any production rule.

In every production rule, a **nonterminal** on the left side of the arrow can always be replaced by everything on the right side of the arrow.

For example, the following grammar defined an integer in [BNF](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form) syntax:

```
<digit>   ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<integer> ::= ['-'] <digit> {<digit>}
```

In this grammar, `<digit>` and `<integer>` are nonterminals, and the symbols (-, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) are the terminals.

---

Formally, a Context-Free Grammar is defined by a 4-tuple:

$$
G = (V, \Sigma, R, S)
$$

Where:

- $V$ is a set of nonterminal symbols that we have in the grammar.
- $\Sigma$ is a set of terminals, which make up the content of the sentences.
- $R$ is a set of production rules of the grammar, sometimes can be symbolized as $P$.
- $S$ is the start symbol of the grammar.

---

For example, to parse an algebraic expression with the variables $x$, $y$ and $z$, like this:

$$
(x + y) * x - z * y / (x + x)
$$

We have a grammar:

$$
G = (\\{ S \\}, \\{ x, y, z, +, -, *, /, (, ) \\}, R, S)
$$

With the following production rules:

```
S → x | y | z
S → S + S
S → S - S
S → S * S
S → S / S
S → (S)
```

---

Another example, a grammar $G$ to match all palindromes of the characters $\\{ a, b \\}$ like $aa$, $aabaa$, $aabbaa$, $bab$,...

$$
G = (\\{ S \\}, \\{ a, b \\}, R, S)
$$

```
S → aSa
S → bSb
S → ε
```

The last rule is called ε-production, which means $S$ be rewritten as an empty string.