Syntax analyzer

[Oidaho]

Recommendations for the task completion process

• Use Ruff for a quick code editor
• Create a separate branch to work on your task
• When naming commits, specify the issue id to which it belongs: Added some files (#1)
• Before creating a PR, make sure that all the pytest tests for your task pass
• When creating a PR, assign @Oidaho as a reviewer

Write Syntax analyzer

Write a code parser that will make up an Abstract Syntax Tree (AST).

List of implementation tasks

• Create an Analyzer module.
• Design An Analyzer.
• Implement it.
• Add all progress information to this issue.

[!NOTE] pyxpp already has implemented code tokenization functionality. That is, the tokenization functionality needs to be combined with the syntactic analysis functionality. Снизу представлен пример того, как код разбирается на токены.

test_code.py:

import re as r
from re._casefix import *

print("privet_mir")

a = 1
b = 3
c = 45

c < 43 > 12

a += 1

a //= 2

class MyClass(object):
    def __init__(self, a) -> None:
        self.a = a

    def some_func(self) -> None:
        print(1)

def a(b):
    pass

g = "AWFAWF"

print(g)

hz = lambda x: x**2

g = hz(g)

if __name__ == "__main__":
    print(b < a)

Console output:

<token:'identifier'|value:'import'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'re'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'as'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'r'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'from'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'re'>
<token:'delimiter'|value:'.'>
<token:'identifier'|value:'_casefix'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'import'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'*'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'print'>
<token:'delimiter'|value:'('>
<token:'string'|value:'"privet_mir"'>
<token:'delimiter'|value:')'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'a'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'integer'|value:'1'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'b'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'integer'|value:'3'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'c'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'integer'|value:'45'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'c'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'<'>
<token:'whitespace'|value:' '>
<token:'integer'|value:'43'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'>'>
<token:'whitespace'|value:' '>
<token:'integer'|value:'12'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'a'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'+='>
<token:'whitespace'|value:' '>
<token:'integer'|value:'1'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'a'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'//='>
<token:'whitespace'|value:' '>
<token:'integer'|value:'2'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'class'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'MyClass'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'object'>
<token:'delimiter'|value:')'>
<token:'delimiter'|value:':'>
<token:'newline'|value:'\n'>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'def'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'__init__'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'self'>
<token:'delimiter'|value:','>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'a'>
<token:'delimiter'|value:')'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'->'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'None'>
<token:'delimiter'|value:':'>
<token:'newline'|value:'\n'>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'self'>
<token:'delimiter'|value:'.'>
<token:'identifier'|value:'a'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'a'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'def'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'some_func'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'self'>
<token:'delimiter'|value:')'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'->'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'None'>
<token:'delimiter'|value:':'>
<token:'newline'|value:'\n'>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'print'>
<token:'delimiter'|value:'('>
<token:'integer'|value:'1'>
<token:'delimiter'|value:')'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'def'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'a'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'b'>
<token:'delimiter'|value:')'>
<token:'delimiter'|value:':'>
<token:'newline'|value:'\n'>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'pass'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'g'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'string'|value:'"AWFAWF"'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'print'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'g'>
<token:'delimiter'|value:')'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'hz'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'lambda'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'x'>
<token:'delimiter'|value:':'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'x'>
<token:'operator'|value:'**'>
<token:'integer'|value:'2'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'g'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'='>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'hz'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'g'>
<token:'delimiter'|value:')'>
<token:'newline'|value:'\n'>
<token:'newline'|value:'\n'>
<token:'identifier'|value:'if'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'__name__'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'=='>
<token:'whitespace'|value:' '>
<token:'string'|value:'"__main__"'>
<token:'delimiter'|value:':'>
<token:'newline'|value:'\n'>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'print'>
<token:'delimiter'|value:'('>
<token:'identifier'|value:'b'>
<token:'whitespace'|value:' '>
<token:'operator'|value:'<'>
<token:'whitespace'|value:' '>
<token:'identifier'|value:'a'>
<token:'delimiter'|value:')'>
<token:'newline'|value:'\n'>

[Oidaho]

Additional Task №1

Right now, your node is some kind of very static class that cannot be transformed. Eliminate the list of types implemented via Enum and create your own class for each possible node:

class ASTNode:
    """The base class for all AST nodes."""
    pass

class Program(ASTNode):
    """Acts as the root of AST."""
    def __init__(self, statements):
        self.statements = statements  # List of instructions

class Comment(ASTNode):
    def __init__(self, text):
        self.text = text

class Assignment(ASTNode):
    def __init__(self, target, operator, value):
        self.target = target  # Target identifier
        self.operator = operator  # '=', '+=' or smt else
        self.value = value  # Statement value

class Identifier(ASTNode):
    def __init__(self, name):
        self.name = name

class Literal(ASTNode):
    def __init__(self, value):
        self.value = value

# And so on....

[Oidaho]

Additional Task №2

After all, it is much easier to implement the construction of an AST based on a ready-made sequence of tokens. I suggest implementing the add_token() method in the ASTBuilder class, which will only add tokens to the internal buffer of the class.

After that, implement the build() method, which will return a ready-made syntax tree, converting the list of tokens in the buffer into a queue using collections.deque.

I see it like this:

ast_builder = ASTBuilder()

for token in ... :
    ast_builder.add_token(token)

ast: ASTNode = ast_builder.build()

In addition, open Internet sources offer something like this implementation option:

def build():
    token_deque = deque(self.tokens)
    statements = []

    while token_deque:
        token = token_deque.popleft()
        if token['type'] == 'comment':
           # Comment Node
            statements.append(Comment(token['value']))
        elif token['type'] == 'identifier':
            # Assignment node
            target = Identifier(token['value'])
            tokens.popleft()  # Skipping whitespace
            operator = tokens.popleft()['value']  # '=', '+='
            tokens.popleft()  # Skipping whitespace
            value_token = tokens.popleft()
            if value_token['type'] == 'integer':
                value = Literal(int(value_token['value']))
            else:
                raise SyntaxError("The literal was expected after the operator")
            statements.append(Assignment(target, operator, value))
        elif token['type'] == 'newline':
            continue  # Skipping newline
        else:
            raise SyntaxError(f"Unexpected token: {token}")

    return Program(statements)

This solution looks concise. But this is not exactly what we need. Try experimenting with this code and create something similar based on it.

[Oidaho]

THIS IS NOT A TASK!!!

In addition to this, there is a similar solution for generating C++ code based on AST nodes:

def generate_cpp_code(ast):
    if isinstance(ast, Program):
        return "\n".join(generate_cpp_code(stmt) for stmt in ast.statements)
    elif isinstance(ast, Comment):
        return f"// {ast.text}"
    elif isinstance(ast, Assignment):
        target = ast.target.name
        operator = ast.operator
        value = generate_cpp_code(ast.value)
        if operator == '=':
            return f"{target} = {value};"
        elif operator == '+=':
            return f"{target} += {value};"
        else:
            raise NotImplementedError(f"Оператор {operator} не поддерживается")
    elif isinstance(ast, Identifier):
        return ast.name
    elif isinstance(ast, Literal):
        return str(ast.value)
    else:
        raise NotImplementedError(f"Тип узла {type(ast)} не поддерживается")

This code is not any good, in my opinion. However, it can be used as a reference.