Análisis sintáctico

📐 Fundamento

Gramática BNF de PupusaScript (fragmento):

programa    → PROGRAMA IDENTIFICADOR bloque_vars? INICIO sentencias FIN

bloque_vars → VARIABLES DOSPUNTOS declaracion+

declaracion → IDENTIFICADOR DOSPUNTOS tipo
tipo        → ENTERO | DECIMAL

sentencias  → sentencia*

sentencia   → asignacion
            | si_stmt
            | mientras_stmt
            | imprimir_stmt
            | leer_stmt

asignacion  → IDENTIFICADOR ASIGNACION expr

si_stmt     → SI expr ENTONCES sentencias
              (SINO sentencias)?
              FIN_SI

mientras_stmt → MIENTRAS expr HACER sentencias FIN_MIENTRAS

imprimir_stmt → IMPRIMIR LPAREN expr RPAREN
leer_stmt     → IDENTIFICADOR ASIGNACION LEER LPAREN STRING RPAREN

expr        → expr (MAS | MENOS) term
            | term

term        → term (MUL | DIV) factor
            | factor

factor      → LPAREN expr RPAREN
            | NUM_DECIMAL
            | NUM_ENTERO
            | STRING
            | IDENTIFICADOR
            | (MAS | MENOS) factor      ← unario

Ambigüedad: Una gramática es ambigua si la misma cadena tiene más de un árbol de derivación. La gramática de expr arriba no es ambigua porque la precedencia está codificada en la jerarquía (term tiene mayor precedencia que expr).

📐 Fundamento

Nodos del AST:

from dataclasses import dataclass, field
from typing import Optional, List, Union

@dataclass
class Programa:
    nombre: str
    declaraciones: List['Declaracion']
    cuerpo: List['Sentencia']

@dataclass
class Declaracion:
    nombre: str
    tipo: str  # 'entero' | 'decimal'

@dataclass
class Asignacion:
    destino: str
    valor: 'Expr'

@dataclass
class SiStmt:
    condicion: 'Expr'
    entonces: List['Sentencia']
    sino: Optional[List['Sentencia']] = None

@dataclass
class ImprimirStmt:
    expresion: 'Expr'

@dataclass
class BinOp:
    izq: 'Expr'
    op: str
    der: 'Expr'

@dataclass
class Numero:
    valor: Union[int, float]

@dataclass
class Identificador:
    nombre: str

@dataclass
class StringLiteral:
    valor: str

Expr = Union[BinOp, Numero, Identificador, StringLiteral]
Sentencia = Union[Asignacion, SiStmt, ImprimirStmt]

Parser descendente recursivo:

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0
    
    def peek(self):
        """Ver el token actual sin consumirlo."""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None
    
    def consumir(self, tipo_esperado):
        """Consumir el token actual si es del tipo esperado."""
        tok = self.peek()
        if tok is None:
            raise SyntaxError(f"Se esperaba {tipo_esperado} pero se llegó al final")
        if tok.type != tipo_esperado:
            raise SyntaxError(
                f"Línea {tok.lineno}: se esperaba {tipo_esperado}, "
                f"se encontró {tok.type} ('{tok.value}')"
            )
        self.pos += 1
        return tok
    
    def parse_programa(self) -> Programa:
        self.consumir('PROGRAMA')
        nombre = self.consumir('IDENTIFICADOR').value
        
        declaraciones = []
        if self.peek() and self.peek().type == 'VARIABLES':
            declaraciones = self.parse_bloque_vars()
        
        self.consumir('INICIO')
        cuerpo = self.parse_sentencias()
        self.consumir('FIN')
        
        return Programa(nombre=nombre, declaraciones=declaraciones, cuerpo=cuerpo)
    
    def parse_bloque_vars(self) -> List[Declaracion]:
        self.consumir('VARIABLES')
        self.consumir('DOSPUNTOS')
        declaraciones = []
        while self.peek() and self.peek().type == 'IDENTIFICADOR':
            nombre = self.consumir('IDENTIFICADOR').value
            self.consumir('DOSPUNTOS')
            tipo_tok = self.peek()
            if tipo_tok.type in ('ENTERO', 'DECIMAL'):
                self.pos += 1
                declaraciones.append(Declaracion(nombre=nombre, tipo=tipo_tok.value))
            else:
                raise SyntaxError(f"Tipo inválido: {tipo_tok.value}")
        return declaraciones
    
    def parse_sentencias(self) -> List[Sentencia]:
        stmts = []
        while self.peek() and self.peek().type not in ('FIN', 'SINO', 'FIN_SI', 'FIN_MIENTRAS'):
            stmts.append(self.parse_sentencia())
        return stmts
    
    def parse_sentencia(self) -> Sentencia:
        tok = self.peek()
        if tok.type == 'SI':
            return self.parse_si()
        elif tok.type == 'IMPRIMIR':
            return self.parse_imprimir()
        elif tok.type == 'IDENTIFICADOR':
            return self.parse_asignacion()
        else:
            raise SyntaxError(f"Línea {tok.lineno}: sentencia inesperada '{tok.value}'")
    
    def parse_asignacion(self) -> Asignacion:
        nombre = self.consumir('IDENTIFICADOR').value
        self.consumir('ASIGNACION')
        valor = self.parse_expr()
        return Asignacion(destino=nombre, valor=valor)
    
    def parse_si(self) -> SiStmt:
        self.consumir('SI')
        cond = self.parse_expr()
        self.consumir('ENTONCES')
        entonces = self.parse_sentencias()
        sino = None
        if self.peek() and self.peek().type == 'SINO':
            self.consumir('SINO')
            sino = self.parse_sentencias()
        self.consumir('FIN_SI')
        return SiStmt(condicion=cond, entonces=entonces, sino=sino)
    
    def parse_imprimir(self) -> ImprimirStmt:
        self.consumir('IMPRIMIR')
        self.consumir('LPAREN')
        expr = self.parse_expr()
        self.consumir('RPAREN')
        return ImprimirStmt(expresion=expr)
    
    def parse_expr(self) -> Expr:
        """expr → term (('+' | '-') term)*"""
        izq = self.parse_term()
        while self.peek() and self.peek().type in ('MAS', 'MENOS'):
            op = self.pos; self.pos += 1
            der = self.parse_term()
            izq = BinOp(izq=izq, op=self.tokens[op].value, der=der)
        return izq
    
    def parse_term(self) -> Expr:
        """term → factor (('*' | '/') factor)*"""
        izq = self.parse_factor()
        while self.peek() and self.peek().type in ('MUL', 'DIV'):
            op = self.pos; self.pos += 1
            der = self.parse_factor()
            izq = BinOp(izq=izq, op=self.tokens[op].value, der=der)
        return izq
    
    def parse_factor(self) -> Expr:
        tok = self.peek()
        if tok.type == 'NUM_DECIMAL':
            self.pos += 1
            return Numero(valor=tok.value)
        elif tok.type == 'NUM_ENTERO':
            self.pos += 1
            return Numero(valor=tok.value)
        elif tok.type == 'STRING':
            self.pos += 1
            return StringLiteral(valor=tok.value)
        elif tok.type == 'IDENTIFICADOR':
            self.pos += 1
            return Identificador(nombre=tok.value)
        elif tok.type == 'LPAREN':
            self.consumir('LPAREN')
            e = self.parse_expr()
            self.consumir('RPAREN')
            return e
        else:
            raise SyntaxError(f"Línea {tok.lineno}: factor inesperado '{tok.value}'")

📐 Fundamento

LL(1) — Top-down con 1 token de lookahead:

El parser descendente recursivo es un LL(1) manual. La "L" significa que lee de izquierda a derecha, la segunda "L" que hace derivaciones izquierdas, y el "(1)" que mira 1 token adelante para decidir qué regla aplicar.

Limitación: LL(1) no puede manejar recursión izquierda directa:

expr → expr '+' term   ← recursión izquierda: el parser llama a expr() antes de consumir
     | term             ← un token de lookahead no alcanza para decidir

Solución: eliminar recursión izquierda:

expr  → term expr'
expr' → '+' term expr'
      | '-' term expr'
      | ε

Esta transformación es equivalente pero sin recursión izquierda.

LR(1) — Bottom-up con 1 token de lookahead:

Los parsers LR construyen el árbol de abajo hacia arriba: acumulan tokens en una pila (shift) y cuando reconocen un patrón, lo reducen a un no terminal (reduce).

• Más poderosos que LL(1) — manejan gramáticas más amplias.
• Más difíciles de implementar a mano → se usan herramientas como PLY/yacc, Bison.
• Usados en la mayoría de compiladores de producción.

PLY para el parser:

import ply.yacc as yacc

def p_expr_binop(p):
    '''expr : expr MAS term
            | expr MENOS term'''
    p[0] = BinOp(izq=p[1], op=p[2], der=p[3])

def p_expr_term(p):
    '''expr : term'''
    p[0] = p[1]

def p_term_mul(p):
    '''term : term MUL factor
            | term DIV factor'''
    p[0] = BinOp(izq=p[1], op=p[2], der=p[3])

def p_factor_numero(p):
    '''factor : NUM_DECIMAL
              | NUM_ENTERO'''
    p[0] = Numero(valor=p[1])

def p_error(p):
    if p:
        print(f"Error sintáctico en '{p.value}', línea {p.lineno}")
    else:
        print("Error sintáctico: fin inesperado del archivo")

parser = yacc.yacc()
ast = parser.parse("precio * 1.13", lexer=lexer)