Introducci贸n al desarrollo de int茅rpretes y lenguajes de programaci贸n

1

Aprende a desarrollar lenguajes de programaci贸n con int茅rpretes

2

Desarrolla LPP o Lenguaje de Programaci贸n Platzi

Construcci贸n del lexer o tokenizador

3

驴Qu茅 es an谩lisis l茅xico? Funcionamiento del lexer y tokens

4

Estructura y definici贸n de tokens en Python

5

Lectura de caracteres y tokens

6

Tokens ilegales, operadores de un solo car谩cter y delimitadores

7

Reconocimiento y diferenciaci贸n entre letras y n煤meros

8

Declaraci贸n y ejecuci贸n de funciones

9

Extensi贸n del lexer: condicionales, operaciones y booleanos

10

Operadores de dos caracteres

11

Primera versi贸n del REPL con tokens

Construcci贸n del parser o analizador sint谩ctico

12

驴Qu茅 es un parser y AST?

13

Estructura y definici贸n de nodos del AST en Python

14

Parseo del programa o nodo principal

15

Parseo de assignment statements

16

Parseo de let statements

17

Parseo de errores

18

Parseo del return statement

19

T茅cnicas de parsing y pratt parsing

20

Pruebas del AST

21

Implementaci贸n del pratt parser

22

Parseo de Identifiers: testing

23

Parseo de Identifiers: implementaci贸n

24

Parseo de enteros

25

Prefix operators: negaci贸n y negativos

26

Infix operators y orden de las operaciones: testing

27

Infix operators y orden de las operaciones: implementaci贸n

28

Parseo de booleanos

29

Desaf铆o: testing de infix operators y booleanos

30

Parseo de expresiones agrupadas

31

Parseo de condicionales: testing y AST

32

Parseo de condicionales: implementaci贸n

33

Parseo de declaraci贸n de funciones: testing

34

Parseo de declaraci贸n de funciones: AST e implementaci贸n

35

Parseo de llamadas a funciones: testing y AST

36

Parseo de llamadas a funciones: implementaci贸n

37

Completando los TODOs o pendientes del lexer

38

Segunda versi贸n del REPL con AST

Evaluaci贸n o an谩lisis sem谩ntico

39

Significado de s铆mbolos

40

Estrategias de evaluaci贸n para int茅rpretes de software

41

Representaci贸n de objetos

42

Evaluaci贸n de expresiones: enteros

43

Evaluaci贸n de expresiones: booleanos y nulos

44

Evaluaci贸n de expresiones: prefix

45

Evaluaci贸n de expresiones: infix

46

Evaluaci贸n de condicionales

47

Evaluaci贸n del return statement

48

Manejo de errores

49

Ambiente

50

Bindings

51

Evaluaci贸n de funciones

52

Llamadas a funciones

Mejora del int茅rprete

53

Implementaci贸n de strings

54

Operaciones con strings

55

Built-in functions: objeto y tests

56

Built-in functions: evaluaci贸n

Siguientes pasos

57

Retos para expandir tu int茅rprete

58

Contin煤a con el Curso de Creaci贸n de Compiladores de Software

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Tokens ilegales, operadores de un solo car谩cter y delimitadores

6/58
Recursos

Aportes 12

Preguntas 1

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

Escapar: hacer que el caract茅r sea tomado c贸mo texto plano en lugar de su significado por defecto en la expreci贸n regular.

Decid铆 crear otra funci贸n para obtener los tipos de token en mi Lexer

class Lexer:
    def __init__(self, source: str) -> None:
        self._source: str = source
        self._character: str = ''
        self._read_position: int = 0
        self._position: int = 0

        self._read_character()

    def next_token(self) -> Token:
        token_type = self._get_token_type()
        token = Token(token_type, self._character)

        self._read_character()

        return token

    def _get_token_type(self):
        if match(r'^=$', self._character):
            token_type = TokenType.ASSIGN
        elif match(r'^\+$', self._character):
            token_type = TokenType.PLUS
        elif match(r'^$', self._character):
            token_type = TokenType.EOF
        elif match(r'^\($', self._character):
            token_type = TokenType.LPAREN
        elif match(r'^\)$', self._character):
            token_type = TokenType.RPAREN
        elif match(r'^\{$', self._character):
            token_type = TokenType.LBRACE
        elif match(r'^}$', self._character):
            token_type = TokenType.RBRACE
        elif match(r'^,$', self._character):
            token_type = TokenType.COMMA
        elif match(r'^;$', self._character):
            token_type = TokenType.SEMICOLON
        else:
            token_type = TokenType.ILLEGAL

        return token_type

    def _read_character(self) -> None:
        if self._read_position >= len(self._source):
            self._character = ''
        else:
            self._character = self._source[self._read_position]

        self._position = self._read_position
        self._read_position += 1

Como programadores debemos siempre optimizar el c贸digo para que sea f谩cil de leer y darle mantenimiento, por eso modifiqu茅 la funci贸n next_token para que no hay a necesidad de hacer un elif cada vez que agregue un nuevo token.
.
Con esta funci贸n, solo agregamos los token v谩lidos a un diccionario, donde la expresi贸n regular es la clave y el el tipo de token es el valor. Luego, un loop evaluar谩 las expresiones y si pasa correctamente, le asignar谩 el tipo que e fue asociado en el diccionario. Si ninguna expresi贸n regular 鈥渕achea鈥, entonces le asigna TokenType.ILEGAL

    def next_token(self) -> Token:
        
        token_dict = {
            "^=$": TokenType.ASSIGN,
            "^\+$": TokenType.PLUS,
            "^\($": TokenType.LPAREN,
            "^\)$": TokenType.RPAREN,
            "^{$": TokenType.LBRACE,
            "^}$": TokenType.RBRACE,
            "^,$": TokenType.COMMA,
            "^;$": TokenType.SEMICOLON,
            "^$": TokenType.EOF,
        }

        token = None

        for regex, token_type in token_dict.items():
            if match(regex, self._character):
                token = Token(token_type, self._character)
                break
        
        if token is None:
            token = Token(TokenType.ILLEGAL, self._character)

        self._read_character()

        return token

Reto conseguido:
.
Mi funci贸n de test (lo 煤nico que hace es espectar sus tokens y los tipos):

def test_delimiters(self) -> None:

        source: str = "(){},;"
        lexer: Lexer = Lexer(source)

        tokens: List[Token] = []

        for i in range(len(source)):

            tokens.append(lexer.next_token())

        expected_tokens: List[Token] = [
            Token(TokenType.LPAREN, "("),
            Token(TokenType.RPAREN, ")"),
            Token(TokenType.LBRACE, "{"),
            Token(TokenType.RBRACE, "}"),
            Token(TokenType.COMMA, ","),
            Token(TokenType.SEMICOLON, ";"),
        ]

        self.assertEquals(tokens, expected_tokens)

.
Mi funci贸n next_token, realmente al poner demasiados if/else se vuelve un poco complejo de leer as铆 que igual se puede llegar a hacer algo para ello 馃

def next_token(self) -> Token:
        
        if match(r"^=$", self._character):
            token = Token(TokenType.ASSIGN, self._character)

        elif match(r"^\+$", self._character):
            token = Token(TokenType.PLUS, self._character)

        elif match(r"^\($", self._character):
            token = Token(TokenType.LPAREN, self._character)

        elif match(r"^\)$", self._character):
            token = Token(TokenType.RPAREN, self._character)

        elif match(r"^{$", self._character):
            token = Token(TokenType.LBRACE, self._character)

        elif match(r"^}$", self._character):
            token = Token(TokenType.RBRACE, self._character)

        elif match(r"^,$", self._character):
            token = Token(TokenType.COMMA, self._character)

        elif match(r"^;$", self._character):
            token = Token(TokenType.SEMICOLON, self._character)

        elif match(r"^$", self._character):
            token = Token(TokenType.EOF, self._character)

        else:
            token = Token(TokenType.ILLEGAL, self._character)

        self._read_character()

        return token

Yo estoy haciendo el proyecto con Deno y TypeScript.

Tests:

import { assertEquals } from "https://deno.land/[email protected]/testing/asserts.ts"

import { Token, TokenType } from '../src/token.ts'
import { Lexer } from '../src/lexer.ts'

Deno.test("lexer test", async (t) => {
    await t.step("test illegal", () => {
        const source = "!驴@"
        const lexer = new Lexer(source)

        const tokens: Token[] = []
        for (let i = 0; i < source.length; i++) {
            tokens.push(lexer.nextToken())
        }

        const expected_tokens = [
            new Token(TokenType.ILLEGAL, '!'),
            new Token(TokenType.ILLEGAL, '驴'),
            new Token(TokenType.ILLEGAL, '@'),
        ]

        assertEquals(tokens, expected_tokens)
    })

    await t.step('test one character operator', () => {
        const source = '+='
        const lexer = new Lexer(source)

        const tokens: Token[] = []
        for (let i = 0; i < source.length; i++) {
            tokens.push(lexer.nextToken())
        }

        const expected_tokens = [
            new Token(TokenType.PLUS, '+'),
            new Token(TokenType.ASSIGN, '='),
        ]

        assertEquals(tokens, expected_tokens)
    })
})

Tokens:

export enum TokenType {
    ASSIGN,
    COMMA,
    EOF,
    FUNCTION,
    IDENT,
    ILLEGAL,
    INT,
    LBRACE,
    LET,
    LPAREN,
    PLUS,
    RBRACE,
    RPAREN,
    SEMICOLON,
}

export class Token {
    tokenType: TokenType
    literal: string

    constructor(tokenType: TokenType, literal: string) {
        this.tokenType = tokenType
        this.literal = literal
    }

    public toString(): string {
        return `Type: ${this.tokenType}, Literal: ${this.literal}`
    }
}

Lexer:

import { Token, TokenType } from "./token.ts"

export class Lexer {
    private source: string
    private chraacter: string
    private readPosition: number
    private position: number

    private TOKENS: { [key: string]: TokenType } = {
        '=': TokenType.ASSIGN,
        ',': TokenType.COMMA,
        ';': TokenType.SEMICOLON,
        '+': TokenType.PLUS,
        '{': TokenType.LBRACE,
        '}': TokenType.RBRACE,
        '(': TokenType.LPAREN,
        ')': TokenType.RPAREN,
        'let': TokenType.LET,
        'fn': TokenType.FUNCTION,
        '': TokenType.EOF,
    }

    constructor(source: string) {
        this.source = source
        this.chraacter = ''
        this.readPosition = 0
        this.position = 0

        this.readCharacter()
    }

    nextToken(): Token {
        const tokenType: TokenType = this.TOKENS[this.chraacter] ?? TokenType.ILLEGAL
        const token = new Token(tokenType, this.chraacter)
        this.readCharacter()
        return token
    }

    private readCharacter(): void {
        if (this.readPosition >= this.source.length) this.chraacter = ''
        else this.chraacter = this.source[this.readPosition]

        this.position = this.readPosition
        this.readPosition++
    }
}

He aqu铆 mi soluci贸n:

# Challenge
    def test_delimiters(self) -> None:
        source = '(){},;'
        lexer: Lexer = Lexer(source)

        tokens: List[Token] = []
        for i in range(len(source)):
            tokens.append(lexer.next_token())

        expected_tokens: List[Token] = [
            Token(TokenType.LPAREN, '('),
            Token(TokenType.RPAREN, ')'),
            Token(TokenType.LBRACE, '{'),
            Token(TokenType.RBRACE, '}'),
            Token(TokenType.COMMA, ','),
            Token(TokenType.SEMICOLON, ';'),
        ]
        self.assertEquals(tokens, expected_tokens) # Se revisa que los tokens que aviente el lexer sean especificamente los tokens que tenemos en expected tokens

Condicionales en next_token:

 def next_token(self) -> Token:
        # Se va a revisar con expresiones regulares
        """
        En Python las expresiones regulares empiezan con cadenas row
        # Comience al principio de la cadena, encuentre un igual y que termine en esto, se quiere un igual desde el principio hasta el final
        """
        if match(r'^=$', self._character):
            token = Token(TokenType.ASSIGN, self._character)
        elif match(r'^\+$', self._character): 
            token = Token(TokenType.PLUS, self._character)
        elif match(r'^\($', self._character):
            token = Token(TokenType.LPAREN, self._character)
        elif match(r'^\)$', self._character):
            token = Token(TokenType.RPAREN, self._character)
        elif match(r'^{$', self._character):
            token = Token(TokenType.LBRACE, self._character)
        elif match(r'^}$', self._character):
            token = Token(TokenType.RBRACE, self._character)
        elif match(r'^,$', self._character):
            token = Token(TokenType.COMMA, self._character)
        elif match(r'^;$', self._character):
            token = Token(TokenType.SEMICOLON, self._character)
        elif match(r'^$', self._character):
            token = Token(TokenType.EOF, self._character)            
        else: # Si no reconoce entonces dir谩 que es un Token ilegal
            token = Token(TokenType.ILLEGAL, self._character)
        """
        Se tiene que escapar especificamente el caracter de suma porque suma significa algo especifico en las expresiones regulares, significa que haga match por lo menos una o mas veces pero aqui no interesa la funcionalidad sino especificamente el caracter, se escapa con la diagonal
        """
        # Escapar: hacer que el caract茅r sea tomado c贸mo texto plano en lugar de su significado por defecto en la expreci贸n regular.

        
        # Se necesita correrlo despues de que se genere el token y antes de regresarlo
        self._read_character()
        
        return token # Se regresa el token

Implemente una clase Tokens para ahorrarnos tantas condiciones, aunque creo que habr谩 que refactorizarlo en las pr贸ximas clases.

class Tokens(object):
    TOKENS = {
        '=': TokenType.ASSIGN,
        ',': TokenType.COMMA,
        ';': TokenType.SEMICOLON,
        '+': TokenType.PLUS,
        '{': TokenType.LBRACE,
        '}': TokenType.RBRACE,
        '(': TokenType.LPARENT,
        ')': TokenType.RPARENT,
        'let': TokenType.LET,
        'fn': TokenType.FUNCTION,
        '': TokenType.EOF,
    }

    @classmethod
    def exists(cls, value: str) -> TokenType:

        if value in cls.TOKENS:
            return cls.TOKENS[value]
        
        return TokenType.ILLEGAL

En la u nos dejaron las practicas de trabajo pero no podemos utilizar la libreria 鈥榬e鈥. a puro if else y for. pero las pruebas unitarias estan en todo!

Definici贸n del reto: test_delimiters

Yo tuve un problema a la hora de definir la validaci贸n de los tokens de par茅ntesis, ya que para las expresiones regulares al igual que con el signo suma el par茅ntesis es considerado un car谩cter especial. Por lo que se soluciona de la misma forma que con al suma:

Test, la unica diferencia con la que ven铆amos haciendo es que se separo la generaci贸n de la lista de token a una funci贸n aparte para que la lectura del test sea un poco m谩s simple

def test_delimeters(self) -> None:
        source = '(){},;'

        tokens = self._load_tokens(source)

        expected_tokens: List[Token] = [
            Token(TokenType.LPAREN, '('),
            Token(TokenType.RPAREN, ')'),
            Token(TokenType.LBRANCE, '{'),
            Token(TokenType.RBRACE, '}'),
            Token(TokenType.COMMA, ','),
            Token(TokenType.SEMICOLON, ';'),
        ]

        self.assertEqual(tokens, expected_tokens)

    def _load_tokens(self, source: str) -> List[Token]:
        lexer: Lexer = Lexer(source)

        tokens: List[Token] = []
        for i in range(len(source)):
            tokens.append(lexer.next_token())
        
        return tokens

Lexer

def next_token(self) -> Token:
        token = self._character_to_token()

        self._read_caracter()

        return token

    def _character_to_token(self) -> Token:
        if match(r'^=$', self._character):
            token = Token(TokenType.ASSIGN, self._character)
        elif match(r'^\+$', self._character):
            token = Token(TokenType.PLUS, self._character)
        elif match(r'^$', self._character):
            token = Token(TokenType.EOF, self._character)
        elif match(r'^\($', self._character):
                    token = Token(TokenType.LPAREN, self._character)
        elif match(r'^\)$', self._character):
                    token = Token(TokenType.RPAREN, self._character)
        elif match(r'^\{$', self._character):
                    token = Token(TokenType.LBRANCE, self._character)
        elif match(r'^}$', self._character):
                    token = Token(TokenType.RBRACE, self._character)
        elif match(r'^,$', self._character):
                    token = Token(TokenType.COMMA, self._character)
        elif match(r'^;$', self._character):
                    token = Token(TokenType.SEMICOLON, self._character)
        else:
            token = Token(TokenType.ILLEGAL, self._character)

        return token
# lexer_test.py
def test_delimeters(self) -> None:
        source: str = '(){},;'
        lexer: Lexer = Lexer(source)

        tokens: List[Token] = []
        for i in range(len(source)):
            tokens.append(lexer.next_token())

        expected_tokens: List[Token] = [
            Token(TokenType.LPAREN, '('),
            Token(TokenType.RPAREN, ')'),
            Token(TokenType.LBRACE, '{'),
            Token(TokenType.RBRACE, '}'),
            Token(TokenType.COMMA, ','),
            Token(TokenType.SEMICOLON, ';'),
        ]

        self.assertEquals(tokens, expected_tokens)
# lexer.py
def next_token(self) -> Token:
        # Token '='
        if match(r'^=$', self._character):
            token = Token(TokenType.ASSIGN, self._character)
        # Token '+'
        elif match(r'^\+$', self._character):
            token = Token(TokenType.PLUS, self._character)
        # Token ''
        elif match(r'^$', self._character):
            token = Token(TokenType.EOF, self._character)
        # Token '('
        elif match(r'^\($', self._character):
            token = Token(TokenType.LPAREN, self._character)
        # Token ')'
        elif match(r'^\)$', self._character):
            token = Token(TokenType.RPAREN, self._character)
        # Token '{'
        elif match(r'^\{$', self._character):
            token = Token(TokenType.LBRACE, self._character)
        # Token '}'
        elif match(r'^\}$', self._character):
            token = Token(TokenType.RBRACE, self._character)
        # Token ','
        elif match(r'^,$', self._character):
            token = Token(TokenType.COMMA, self._character)
        # Token ';'
        elif match(r'^\;$', self._character):
            token = Token(TokenType.SEMICOLON, self._character)
        # Illegal Token
        else:
            token = Token(TokenType.ILLEGAL, self._character)

        self._read_character()

        return token