Crafting a Compiler in Rust: Syntactic Analysis
Tags: rust, compiler, tutorial, computerscience
Published: 2022-12-10 22:25:35

In this post, I will introduce you to the basics of **Syntactic Analysis**. Moreover, we'll write a basic parser that takes the token stream and converts it into Abstract Syntax Trees.

---

## Update on the Lexer

Before going into writing the parser, let me inform you about changes I've made to the Lexer🌟.

- Now, the Lexer supports two more literal constant categories: `Floating` and `Boolean`.

- The literal suffix is now available. For example, in the code `let number = 0i64`, the `0i64` has a literal suffix being `i64` and a literal value of `0`.

``` rust
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum LiteralConstantType<'a> {
    Integer {
        value: &'a str,
        literal_suffix: Option<&'a str>,
    },
    Float {
        value: &'a str,
        literal_suffix: Option<&'a str>,
    },
    Boolean(bool),
}

/// Enumeration containing all patterns of token
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TokenKind<'a> {
    Identifier,
    Space,
    Comment,
    Keyword(Keyword),
    LiteralConstant(LiteralConstantType<'a>),
    Punctuator(char),
    EndOfFile,
}
```

Full code changes to the [`pernix_lexer`](https://github.com/Simmypeet/pernix-lang/commit/8ede2baaf58993ab296660eac9b669cf13ce992d) module is available.

---

## Syntactic Analysis Basics

As mentioned in the introduction, The **Syntactic Analysis** continues from the *Lexical Analysis* phase. But what does it do? 

It takes a token stream produced in the earlier phase into a meaningful data structure called **Abstract Syntax Tree** (**AST**). Additionally, this is the phase where all the syntactic errors are caught.

### The Abstract Syntax Tree

The Abstract Syntax Tree is a tree representation of the code fed to the compiler. It contains only the crucial information of the code and extracts away the syntactic detail of the language.

Take the following code snippets as an example:

``` javascript
function add(a, b) {
    return a + b;
}
```
```python
def add(a, b):
    return a + b
```

There's JavaScript and Python code above. Both functions from both languages behave precisely the same. If both code snippets are parsed, it will produce an AST similar to this:


![The Abstract Syntax Tree Representation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nue0ct2zok8l332wxkc9.jpg)

> In JSON representation
```json
{
  "function": {
    "parameters": [
      "a",
      "b"
    ],
    "statements": [
      {
        "type": "ReturnStatement",
        "expression": {
          "type": "BinaryOperatorExpression",
          "left": {
            "type": "VariableExpression",
            "variable": "a"
          },
          "operator": "+",
          "right": {
            "type": "VariableExpression",
            "variable": "b"
          }
        }
      }
    ]
  }
}
```

The AST produced contains all the crucial information about the function.
- Its parameter names and count.
- The statement inside the function body; contains only one return statement, which returns an expression of `a + b`.

Even though Javascript and Python have different syntaxes, the AST produced by both languages here would be similar or identical since AST doesn't consider the language's syntax detail. That's why it's called ***Abstract*** **Syntax Tree**.

---

## The Goal

Before diving into writing the parser, it's necessary to scope the feature of the parser. What features will be included? What does the code that will be parsed look like? 

Therefore, I made a reference snippet of code to guide us when writing the parser:

``` csharp
using Simmypeet.Math;

namespace Simmypeet {
    namespace Math {
        int32 Add(int32 a, int32 b) {
            return a + b;
        }

        int32 Subtract(int32 a, int32 b) {
            return a + b;
        }
    }

    int32 Fibonacci(int32 n) {
        if (n == 0) {
            return 0;
        }
        else if (n == 1) {
            return 1;
        } 
        else {
            return Add(Fibonacci(n - 1) + Fibonacci(n - 2));
        }
    }
}
```
The code above is similar to C#, which is😁. It also tells us a lot about what features we have to implement. 
- If-else statement 
- Namespace 
- Using declaration (bringing the namespace scope)
- Function call
- Arithmetic operation
- Comparison
- Function declaration

The ultimate goal is to implement a parser that correctly parses the above code. Now, it's time to write some code and get our hands dirty!

---

## The `pernix_parser` Crate

Let's start by creating a new crate named `pernix_parser`.

``` sh
cargo new --lib compiler/pernix_parser
```
``` toml
[workspace]
members = [
    "compiler/pernix_project",
    "compiler/pernix_lexer",
    "compiler/pernix_parser",
]
```

Before going into implementing the actual parser, it's necessary to write all sorts of **Abstract Syntax Tree** data structures first.

## The `abstract_syntax_tree` Module

We'll create a new module called `abstract_syntax_tree` in the `pernix_parser` crate. This module holds all data structures relating to the **Abstract Syntax Tree**.

When producing an AST, it would be beneficial to include the source code position the parser parsed to make an AST. So, in the later phase, when errors occur, the error message can consist of the position in the source code that produces the errors.

Therefore, in `pernix_parser/abstract_syntax_tree.rs`, we'll write a wrapper struct consisting of two fields: the abstract syntax tree value and its position range.

``` rust
/// A wrapper around a value that also contains the position of the value in the
/// source code
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PositiionWrapper<T> {
    pub position: Range<SourcePosition>,
    pub value: T,
}
```

Next, let's write an enum that holds all the values of binary operators.
``` rust
/// List of all available binary operators
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryOperator {
    Add,
    Subtract,
    Asterisk,
    Slash,
    Percent,
    LessThan,
    GreaterThan,
    LessThanEqual,
    GreaterThanEqual,
    Equal,
    NotEqual,
    And,
    Or,
}
```

Next, write an enum that contains all the values of unary operators.
``` rust
/// List of all available unary operators
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnaryOperator {
    Plus,
    Minus,
    LogicalNot,
}
```

Next, include another enum with all the ways to refer to a type.
``` rust
/// An enumeration containing all kinds of types referenced in the program
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Type {
    Identifier(String),
    Array {
        element_type: Box<Type>,
        size: usize,
    },
}
```
For example, a code with `int32[5]`, an array of five `int32`s, would produce an `Type` enum in the code similar to this:
``` rust
Type::Array {
    element_type: Box::new(Type::Identifier("int32".to_string)),
    size: 5
}
```

---

Next, let's create a submodule inside the `abstract_syntax_tree` module called `expression`. This submodule contains all the code related to Expresison Abstract Syntax Tree. 

> Expression refers to a code in the program that can be evaluated and yields a value. For example, in the `x = 4 + 3` statement, the `4 + 3` is an expression.

Now, let's write an enum containing all the forms of an expression.

``` rust
/// Enumeration containing all possible expressions
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expression<'a> {
    /// Represents an expression of the form `left operator right`
    BinaryExpression {
        left: Box<PositiionWrapper<Expression<'a>>>,
        operator: PositiionWrapper<BinaryOperator>,
        right: Box<PositiionWrapper<Expression<'a>>>,
    },

    /// Represents an expression of the form `operator operand`
    UnaryExpression {
        operator: PositiionWrapper<UnaryOperator>,
        operand: Box<PositiionWrapper<Expression<'a>>>,
    },

    /// Represents an expression of the form `literal`
    LiteralExpression(LiteralConstantType<'a>),

    /// Represents an expression of the form `identifier`
    IdentifierExpression {
        identifier: PositiionWrapper<String>,
    },

    /// Represents an expression of the form `function_name(arguments)`
    FunctionCallExpression {
        function_name: PositiionWrapper<String>,
        arguments: Vec<PositiionWrapper<Expression<'a>>>,
    },
}
```
- The `BinaryExpression` variant consists of two operand expressions separated by one binary operator, such as `4 + 5`.
- The `UnaryExpression` variant consists of an operand expression and a unary operator, for example, `!true`.
- The `LiteralExpression` is straightforward; the expression yielded from the hardcoded value.
- The `IdentifierExpression` refers to a reference to a variable.
- The `FunctionCallExpression` refers to a call to a specific function by name and by providing arguments.

Next, let's write all the variants of the statement.
``` rust
/// Enumeration containing all kinds of statements
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Statement<'a> {
    /// Represents a statement of the form `return expression;`
    ReturnStatement {
        expression: PositiionWrapper<Expression<'a>>,
    },

    /// Represents a statement of the form `expression;`
    ExpressionStatement {
        expression: PositiionWrapper<Expression<'a>>,
    },

    /// Represents a statement of the form `let identifier = expression;`
    VariableDeclarationStatement {
        identifier: PositiionWrapper<String>,
        expression: PositiionWrapper<Expression<'a>>,
    },

    /// Represents an if statement of the form `if (condition) then_statement
    /// else else_statement`
    IfStatement {
        condition: PositiionWrapper<Expression<'a>>,
        then_statement: Vec<PositiionWrapper<Statement<'a>>>,
        else_statement: Option<Vec<PositiionWrapper<Statement<'a>>>>,
    },
}
```
> Statement is a fragment of code that carries out a specific action in the program.

- The `ReturnStatement` variant represents a statement that returns a value from a function.
- The `ExpressionStatement` variant represents a statement that evaluates an expression.
- The `VariableDeclarationStatement` variant represents a statement that declares a new variable.
- The `IfStatement` variant represents a statement that executes a block of code if a condition is true. It can also execute a different block of code if the condition is false.

---

Next, let's create a new submodule inside the `abstract_syntax_tree` module called `declaration`. This module holds all the AST code related to all the declarations that you would define in a program, such as namespace declarations, functions, and classes. 

``` rust
/// A declaration is a statement that declares a new name in the current scope.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Declaration<'a> {
    /// Represents a namespace declaration of the form `namespace namespace_name { declarations* }`
    NamespaceDeclaration {
        namespace_name: PositiionWrapper<String>,
        declarations: Vec<PositiionWrapper<Declaration<'a>>>,
    },

    /// Represents a function declaration of the form `type function_name(parameters) { statements* }`
    FunctionDeclaration {
        function_name: PositiionWrapper<String>,
        parameters: Vec<PositiionWrapper<String>>,
        return_type: PositiionWrapper<Type>,
        body: Vec<PositiionWrapper<Statement<'a>>>,
    },

    /// Represents a namespace using statement of the form `using namespace_name;`
    UsingStatement{
        namespace_name: PositiionWrapper<String>,
    },
}
```
- The `NamespaceDeclaration` variant represents a declaration that declares a new namespace and contains other declarations inside it.
- The `FunctionDeclaration` variant represents a declaration that declares a new function and contains a list of statements inside it.
- The `UsingDeclaration` variant represents a declaration that imports a namespace into the current scope.

---

## The `error` Module

Now, it's time to implement an `error` module.  This module will contain all the error types that we will use in the parser. 

``` rust
/// Enumeration containing all possible contexts that the error can occur in.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Context {
    Program,
    Statement,
    Expression,
    Namespace,
}

/// Enumeration containing all possible errors that can occur during parsing.
#[derive(Debug, Clone)]
pub enum Error<'a> {
    LexicalError(pernix_lexer::error::Error<'a>),
    KeywordExpected {
        expected_keyword: Keyword,
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
    IdentifierExpected {
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
    PunctuatorExpected {
        expected_punctuator: char,
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
    UnexpectedToken {
        context: Context,
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
}
```

- The `Context` enumeration contains all the possible contexts in which the error can occur. For example, if the error occurs in the `Program` context, it means that the error occurred in the top level of the program.

- The `Error` enumeration contains all the possible errors that can occur during parsing. The `LexicalError` variant is used to wrap the error that occurred during the lexical analysis. The other variants are used to represent the errors that occurred during the parsing.

---

## Writing The Parser

The parser is a state machine that behaves similarly to the lexer. It turns the token stream into a meaningful AST data structure. The parser that we will write is a combination of [Recursive Descent Parsing](https://en.wikipedia.org/wiki/Recursive_descent_parser) and [Operator-Precedence Parsing](https://en.wikipedia.org/wiki/Operator-precedence_parser).

``` rust
/// Represents a struct that parases the given token stream into abstract syntax
/// trees
pub struct Parser<'a> {
    // The lexer that is used to generate the token stream
    lexer: Lexer<'a>,
    // the accumulated tokens that have been tokenized by the lexer so far
    accumulated_tokens: Vec<Token<'a>>,
    // the accumulated errors that have been found during parsing so far
    accumulated_errors: Vec<Error<'a>>,
    // The current position in the source code
    current_position: usize,
    // Flag that indicates whether the parser should produce errors into the
    // list or not
    produce_errors: bool,
}
```
In the following sections, I'll explain the fields of the `Parser` struct.

- The `lexer` field is used to generate the token stream. It's a struct that 
we've already implemented in the previous post.
- The `accumulated_tokens` field is used to store the tokens that have been
tokenized by the lexer so far. The parser will use this field to get the token
already tokenized by the lexer.
- The `accumulated_errors` field stores the errors 
found during parsing.
- The `current_position` field stores the current token stream index.
- The `produce_errors` field indicates whether the parser should
produce errors into the list or not. This field prevents the parser
from producing errors when recovering from an error. 

Let's create a `new` constructor for the `Parser` struct.
``` rust
impl<'a> Parser<'a> {
    /// Creates a new parser instance from the given source code
    pub fn new(source_code: &'a SourceCode) -> Self {
        let mut lexer = Lexer::new(source_code);
        let mut accumulated_errors = Vec::new();

        // get the first token
        let accumulated_tokens = vec![{
            let token_return;
            loop {
                match lexer.lex() {
                    Ok(token) => {
                        token_return = token;
                        break;
                    }
                    Err(err) => {
                        accumulated_errors.push(Error::LexicalError(err));
                    }
                }
            }
            token_return
        }];

        Self {
            lexer,
            accumulated_tokens,
            accumulated_errors,
            current_position: 0,
            produce_errors: true,
        }
    }
}
```

The function creates a new `Lexer` instance from the source code. First, it gets the first token from the lexer and stores it in the `accumulated_tokens` field. Then, it creates a new `Parser` instance and returns it.

Now, let's implement the `next` function. This function will return the current token and move the `current_position` field to the next token. If the `current_position` field is equal to the length of the `accumulated_tokens` field, it means that the parser has reached the end of the token stream. In this case, the function will get the next token from the lexer and store it in the `accumulated_tokens` field. Moreover, if the lexer encounters an error, the function will store the error in the `accumulated_errors` field.

``` rust
impl<'a> Parser<'a> {
    // Gets the current token stream and moves the current position forward
    pub(crate) fn next(&mut self) -> &Token<'a> {
        // need to generate more tokens
        if self.current_position == self.accumulated_tokens.len() - 1 {
            let new_token;
            loop {
                match self.lexer.lex() {
                    Ok(token) => {
                        new_token = token;
                        break;
                    }
                    Err(err) => {
                        self.accumulated_errors.push(Error::LexicalError(err));
                    }
                }
            }

            // append the new token to the accumulated tokens
            self.accumulated_tokens.push(new_token);
        }
        // panic if the current position is greater than or equal the length
        else if self.current_position >= self.accumulated_tokens.len() {
            panic!("current position is greater than or equal the length of the accumulated tokens");
        }

        // increment the current position
        self.current_position += 1;

        &self.accumulated_tokens[self.current_position - 1]
    }
}
```

Now, let's implement the `peek` function. This function will simply index the
`accumulated_tokens` field with the `current_position` field. It will not 
move the position forward.

``` rust
impl<'a> Parser<'a> {
    // Gets the current token without moving the current position forward
    fn peek(&self) -> &Token<'a> {
        &self.accumulated_tokens[self.current_position]
    }

    // Gets the token back by one position without moving the current position
    fn peek_back(&self) -> &Token<'a> {
        &self.accumulated_tokens[self.current_position - 1]
    }
}
```

Before going into writing the parsing function, let's discuss insignificant tokens. In the previous post, we implemented the lexer that can tokenize the comments and whitespaces into tokens. However, in most cases, the syntax doesn't care about these whitespaces and comments. For example, the following code is valid in the language.

``` rust
let x =   5;          // extra spaces? it's okay!
let x=5;              // no spaces? it's okay too!
let x = /*hello?*/ 5; // comment in the middle? that's fine!
```

However, in some cases, it can be crucial. For example, the only difference between the comparison operators `==` and two assignment operators `=` is the space between them. In the following code, the first line will assign the value of `5` to the variable `x`; the second line will compare the value of `x` with `5`;  the rest is  invalid.

``` rust
x = 5;            // yes
x == 5;           // yeah
x = = 5;          // ???
x =/*hello?*/= 5; // what?
```

Therefore, we need to implement a function that can skip insignificant tokens. The function will be called `move_to_significant` and implemented as follows.

``` rust
impl<'a> Parser<'a> {
    /// Moves the current position to the next significant token
    pub(crate) fn move_to_significant(&mut self) {
        while !self.peek().is_significant_token() {
            self.next();
        }
    }
}
```

And on top of that, implement the function that moves to the next significant token, returns it, and moves the position forward.

``` rust
impl<'a> Parser<'a> {
    // Moves the current position to the next significant token and emits it
    pub(crate) fn next_significant(&mut self) -> &Token<'a> {
        self.move_to_significant();
        self.next()
    }
}
```

And if you are wondering how the `is_significant_token` is implemented, it is as follows.

``` rust
impl<'a> Token<'a> {
    /// Returns a boolean indicating whether this [`Token`] is a significant.
    /// Insignificant tokens are spaces and comments.
    pub fn is_significant_token(&self) -> bool {
        match self.token_kind() {
            TokenKind::Space | TokenKind::Comment => false,
            _ => true,
        }
    }
}
```

Next, let's implement the function that appends an error to the `accumulated_errors` field if the `produce_errors` field is `true`.

```rust
impl<'a> Token<'a> {
    // Appends the given error to the list of accumulated errors if the
    // `produce_errors` flag is set to true. Moreover, it also rolls the parser
    // position back to the `rollback_position`.
    #[must_use]
    pub fn append_error<T>(&mut self, error: Error<'a>) -> Option<T> {
        if self.produce_errors {
            self.accumulated_errors.push(error);
        }

        None
    }
}
```

Now that we've got the basic functions, let's implement the parsing function. 

### Parsing The Qualified Name

Let's start with something simple. Let's implement the function that parses the qualified name. The qualified name is the scope's name, such as `Simmypeet.Compiler.Parser`. It follows the pattern of an identifier followed by a dot, followed by another identifier, and so on.

``` rust
pub fn parse_qualified_name(&mut self) -> Option<PositiionWrapper<String>> {
    self.move_to_significant();
    let starting_position = self.peek().position_range().start;

    // the string to return
    let mut string = String::new();

    // expect the first identifier
    if let TokenKind::Identifier = self.next().token_kind() {
        string.push_str(self.peek_back().lexeme());
    } else {
        return self.append_error(Error::IdentifierExpected {
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    // found additional scopes
    while matches!(self.peek().token_kind(), TokenKind::Punctuator('.')) {
        // eat the dot
        self.next();

        string.push('.');

        // expect the next identifier
        if let TokenKind::Identifier = self.next().token_kind() {
            string.push_str(self.peek_back().lexeme());
        } else {
            return self.append_error(Error::IdentifierExpected {
                found_token: self.peek_back().clone(),
                source_reference: self.source_code(),
            });
        }
    }

    Some(PositiionWrapper {
        position: starting_position..self.peek_back().position_range().end,
        value: string,
    })
}
```
The function first moves the position to the next significant token, as sometimes the parser's position is not at the significant token. Then, it records the starting position of the qualified name. This pattern will be used in the rest of the parsing functions. 

It then expects the first identifier and stores it in the `string` variable. If the first token is not an identifier, it records an error and returns `None`.

Finally, it checks if a dot follows the identifier. If it is, it eats the dot, eats more identifiers, and pushes them to the `string` variable. It then checks again if the next token is a dot. If it is, it repeats the process. If it is not, it returns the `string` variable.

### Parsing The Using Statement

Next, let's implement the function that parses the `using` statement. The statement uses the qualified name we've implemented in the previous section. The parser will expect the `using` keyword, the qualified name, and a semicolon.

``` rust
/// Parses the current token stream as a using_statement
///
/// Using_Statement:
///   `using` Qualified_Name `;`
pub fn parse_using_statement(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    // move to the first significant token
    self.move_to_significant();
    let starting_position = self.peek().position_range().start;

    // expect the `using` keyword
    if !matches!(
        self.next().token_kind(),
        TokenKind::Keyword(Keyword::Using)
    ) {
        return self.append_error(Error::KeywordExpected {
            expected_keyword: Keyword::Using,
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    let qualified_name = self.parse_qualified_name()?;

    // expect the semicolon
    if !matches!(
        self.next_significant().token_kind(),
        TokenKind::Punctuator(';')
    ) {
        return self.append_error(Error::PunctuatorExpected {
            expected_punctuator: ';',
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    Some(PositiionWrapper {
        position: starting_position..self.peek_back().position_range().end,
        value: Declaration::UsingStatement {
            namespace_name: qualified_name,
        },
    })
}
```
### Parsing The Namespace Declaration

This one is a bit more complicated. Before we start, let's look at our error recovery strategy. In a naive approach, we can stop parsing if the parser encounters an error. However, this is not a good idea, as it discards the rest of the possible valid tokens. Instead, we can use the error recovery strategy to continue parsing the rest of the tokens after the error. 

We'll use the **Panic Mode Error Recovery** strategy in our cases. In this strategy, after the parser encounters an error, it will look for the next valid token and continue working from there, discarding the invalid tokens. This strategy is the most used error recovery strategy, as it is simple to implement and effective.

Let's put us in the perspective of the parser. Consider the following code:

``` rust
mod simmypeet {
    use something;
    use something_else;

    1234 420 // Oops! it should not be here

    mod name {}
}
```

As you can see, there're number literals in the middle of the module declaration. When the parser encounters the number literals, it will record an error saying something like "unexpected token, number literal is not expected here". Then, it will look for the next valid token, which is the `mod` keyword. Our parser will not simply continue parsing from the `1234` token then to encounter another `420` token and record another error. Instead, it will skip the `1234` and `420` tokens, and continue parsing from the next `mod name` declaration.

Now that we've got the error recovery strategy, let's implement the namespace declaration parsing function. The parser will expect the `namespace` keyword, followed by the qualified identifier, followed by the opening curly brace.

``` rust
/// Parses the current token stream as a namespace declaration
///
/// Namespace_Declaration:
///    `namespace` Qualified_Name `{` Declaration* `}`
pub fn parse_namespace_declaration(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    // move to the first significant token
    self.move_to_significant();
    let starting_position = self.peek().position_range().start;

    // expect the `namespace` keyword
    if !matches!(
        self.next().token_kind(),
        TokenKind::Keyword(Keyword::Namespace)
    ) {
        return self.append_error(Error::KeywordExpected {
            expected_keyword: Keyword::Namespace,
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    let namespace_name = self.parse_qualified_name()?;

    // expect the opening curly bracket
    if !matches!(
        self.next_significant().token_kind(),
        TokenKind::Punctuator('{')
    ) {
        return self.append_error(Error::PunctuatorExpected {
            expected_punctuator: '{',
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    /* More to come ... */
}
```

Next, we'll instantiate a new `Vec` to store the declarations inside the namespace. Then, we'll start a loop that will parse the declarations inside the namespace. The loop is terminated when the parser encounters the closing curly brace or reaches the end of the file.

``` rust
/// Parses the current token stream as a namespace declaration
///
/// Namespace_Declaration:
///    `namespace` Qualified_Name `{` Declaration* `}`
pub fn parse_namespace_declaration(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    /* From the previous code ... */

    // loop through all the declarations
    let mut declarations = Vec::new();

    // move to the next significant token
    self.move_to_significant();

    // loop through all the declarations until closing curly bracket or
    // EOF is found
    while !matches!(
        self.peek().token_kind(),
        TokenKind::Punctuator('}') | TokenKind::EndOfFile
    ) {
        let declaration = match self.peek().token_kind() {
            TokenKind::Keyword(Keyword::Namespace) => {
                self.parse_namespace_declaration()
            }
            TokenKind::Keyword(Keyword::Using) => {
                self.parse_using_statement()
            }
            _ => self.append_error(Error::UnexpectedToken {
                context: Context::Namespace,
                found_token: self.peek().clone(),
                source_reference: self.source_code(),
            }),
        };

        if let Some(declaration) = declaration {
            declarations.push(declaration);
        } else {
            // skip to the next available declaration all delimeter
            self.skip_to(|token| {
                matches!(
                    token.token_kind(),
                    TokenKind::Keyword(Keyword::Namespace)
                        | TokenKind::Keyword(Keyword::Using)
                        | TokenKind::Punctuator('}')
                )
            });
        }

        // move to the next significant token
        self.move_to_significant();
    }

    /* More to come ... */
}
```

You might have noticed that we're using the `skip_to` method to skip to the subsequent available declaration or the closing curly brace. This method is a helper method that will bypass the tokens until the predicate returns `true`. In our case, we're skipping the tokens until we encounter the `namespace`, `using`, or `}` tokens.

Finally, we'll expect the closing curly brace and return the namespace declaration.

``` rust
/// Parses the current token stream as a namespace declaration
///
/// Namespace_Declaration:
///    `namespace` Qualified_Name `{` Declaration* `}`
pub fn parse_namespace_declaration(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    /* From the previous code ... */

    // expect the closing curly bracket
    if !matches!(
        self.next_significant().token_kind(),
        TokenKind::Punctuator('}')
    ) {
        return self.append_error(Error::PunctuatorExpected {
            expected_punctuator: '}',
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    Some(PositiionWrapper {
        position: starting_position..self.peek_back().position_range().end,
        value: Declaration::NamespaceDeclaration {
            namespace_name,
            declarations,
        },
    })
}
```

### Parsing The Program

Finally, we'll write the `parse_program` method that will parse the entire program. Luckily, the program is just a list of declarations, so we'll just loop through all the declarations and parse them similarly to how we parsed the namespace declaration.

``` rust
/// Parses all token stream as a program
///
/// Program:
///  Declaration*
pub fn parse_program(&mut self) -> Option<Program<'a>> {
    let mut program = Program {
        declarations: Vec::new(),
    };

    // move to the next significant token
    self.move_to_significant();

    while !matches!(self.peek().token_kind(), TokenKind::EndOfFile) {
        let declaration = match self.peek().token_kind() {
            TokenKind::Keyword(Keyword::Namespace) => {
                self.parse_namespace_declaration()
            }
            TokenKind::Keyword(Keyword::Using) => {
                self.parse_using_statement()
            }
            _ => self.append_error(Error::UnexpectedToken {
                context: Context::Program,
                found_token: self.peek().clone(),
                source_reference: self.source_code(),
            }),
        };

        if let Some(declaration) = declaration {
            program.declarations.push(declaration);
        } else {
            // skip to the next available declaration all delimeter
            self.skip_to(|token| {
                matches!(
                    token.token_kind(),
                    TokenKind::Keyword(Keyword::Namespace)
                        | TokenKind::Keyword(Keyword::Using)
                )
            });
        }

        // move to the next significant token
        self.move_to_significant();
    }

    Some(program)
}
```

---

## Summary

Phew!!😮‍💨😮‍💨 We've created a simple language parser that can understand the basic program structures. However, we're still going; in the next post, we'll continue writing the parser, which will parse the function declarations.

As always, you can find the source code for this post on [GitHub](https://github.com/Simmypeet/pernix-lang/tree/08d7d48ff6a070315d2841a02645749e8ea452d6)

Feel free to comment if you have any thoughts, questions, feedbacks, or suggestions. I will be happy to read them 😊.