Entendiendo el Compilador de Go: El Parser

Por Jesús Espino • • 18 min de lectura
#Go #Compiler
📚 Entendiendo el Compilador de Go (2 of 4) ▼
  1. 1. El Scanner
  2. 2. El Parser Estás aquí
  3. 3. El Comprobador de Tipos
  4. 4. El Formato Unified IR
El Parser

En el artículo anterior del blog, exploramos el scanner—el componente que convierte tu código fuente de un flujo de caracteres en un flujo de tokens.

Ahora estamos listos para el siguiente paso: el parser.

Aquí está el desafío que resuelve el parser: ahora mismo, tenemos una lista plana de tokens sin relaciones entre ellos. El scanner nos dio package, main, {, fmt, ., Println… pero no tiene idea de que Println pertenece al paquete fmt, o que toda la declaración fmt.Println("Hello world") vive dentro de la función main.

El trabajo del parser es tomar ese flujo plano de tokens y darle estructura. Lo hace construyendo lo que se llama un Árbol de Sintaxis Abstracta (o AST para abreviar).

¿Qué es un Árbol de Sintaxis Abstracta?

Un AST es una estructura de datos de árbol donde cada nodo representa una construcción significativa en tu código—cosas como definiciones de funciones, declaraciones de variables, expresiones o sentencias. La estructura de árbol misma captura las relaciones entre estas construcciones.

Por ejemplo, el código dentro de una función se convierte en un nodo hijo de esa función en el árbol. Un identificador usado en una expresión se convierte en parte del subárbol de esa expresión. La estructura de árbol nos dice “esto pertenece a aquello.”

Esto es probablemente más fácil de entender con un ejemplo concreto. Volvamos a nuestro programa hola mundo:

package main

import "fmt"

func main() {
    fmt.Println("Hello world")
}

Este código fuente puede representarse como el siguiente AST:

     0  *ast.File {
     1  .  Package: 1:1
     2  .  Name: *ast.Ident {
     3  .  .  NamePos: 1:9
     4  .  .  Name: "main"
     5  .  }
     6  .  Decls: []ast.Decl (len = 2) {
     7  .  .  0: *ast.GenDecl {
     8  .  .  .  TokPos: 3:1
     9  .  .  .  Tok: import
    10  .  .  .  Lparen: -
    11  .  .  .  Specs: []ast.Spec (len = 1) {
    12  .  .  .  .  0: *ast.ImportSpec {
    13  .  .  .  .  .  Path: *ast.BasicLit {
    14  .  .  .  .  .  .  ValuePos: 3:8
    15  .  .  .  .  .  .  Kind: STRING
    16  .  .  .  .  .  .  Value: "\"fmt\""
    17  .  .  .  .  .  }
    18  .  .  .  .  .  EndPos: -
    19  .  .  .  .  }
    20  .  .  .  }
    21  .  .  .  Rparen: -
    22  .  .  }
    23  .  .  1: *ast.FuncDecl {
    24  .  .  .  Name: *ast.Ident {
    25  .  .  .  .  NamePos: 5:6
    26  .  .  .  .  Name: "main"
    27  .  .  .  .  Obj: *ast.Object {
    28  .  .  .  .  .  Kind: func
    29  .  .  .  .  .  Name: "main"
    30  .  .  .  .  .  Decl: *(obj @ 23)
    31  .  .  .  .  }
    32  .  .  .  }
    33  .  .  .  Type: *ast.FuncType {
    34  .  .  .  .  Func: 5:1
    35  .  .  .  .  Params: *ast.FieldList {
    36  .  .  .  .  .  Opening: 5:10
    37  .  .  .  .  .  Closing: 5:11
    38  .  .  .  .  }
    39  .  .  .  }
    40  .  .  .  Body: *ast.BlockStmt {
    41  .  .  .  .  Lbrace: 5:13
    42  .  .  .  .  List: []ast.Stmt (len = 1) {
    43  .  .  .  .  .  0: *ast.ExprStmt {
    44  .  .  .  .  .  .  X: *ast.CallExpr {
    45  .  .  .  .  .  .  .  Fun: *ast.SelectorExpr {
    46  .  .  .  .  .  .  .  .  X: *ast.Ident {
    47  .  .  .  .  .  .  .  .  .  NamePos: 6:5
    48  .  .  .  .  .  .  .  .  .  Name: "fmt"
    49  .  .  .  .  .  .  .  .  }
    50  .  .  .  .  .  .  .  .  Sel: *ast.Ident {
    51  .  .  .  .  .  .  .  .  .  NamePos: 6:9
    52  .  .  .  .  .  .  .  .  .  Name: "Println"
    53  .  .  .  .  .  .  .  .  }
    54  .  .  .  .  .  .  .  }
    55  .  .  .  .  .  .  .  Lparen: 6:16
    56  .  .  .  .  .  .  .  Args: []ast.Expr (len = 1) {
    57  .  .  .  .  .  .  .  .  0: *ast.BasicLit {
    58  .  .  .  .  .  .  .  .  .  ValuePos: 6:17
    59  .  .  .  .  .  .  .  .  .  Kind: STRING
    60  .  .  .  .  .  .  .  .  .  Value: "\"Hello, World!\""
    61  .  .  .  .  .  .  .  .  }
    62  .  .  .  .  .  .  .  }
    63  .  .  .  .  .  .  .  Ellipsis: -
    64  .  .  .  .  .  .  .  Rparen: 6:32
    65  .  .  .  .  .  .  }
    66  .  .  .  .  .  }
    67  .  .  .  .  }
    68  .  .  .  .  Rbrace: 7:1
    69  .  .  .  }
    70  .  .  }
    71  .  }
    72  .  Scope: *ast.Scope {
    73  .  .  Objects: map[string]*ast.Object (len = 1) {
    74  .  .  .  "main": *(obj @ 27)
    75  .  .  }
    76  .  }
    77  .  Imports: []*ast.ImportSpec (len = 1) {
    78  .  .  0: *(obj @ 12)
    79  .  }
    80  .  Unresolved: []*ast.Ident (len = 1) {
    81  .  .  0: *(obj @ 46)
    82  .  }
    83  }

Desglosemos lo que estamos viendo aquí:

  • El nodo raíz es *ast.File—representando el archivo fuente completo
  • Nombre del paquete (main) se almacena directamente en el nodo de archivo
  • Declaraciones están en una lista (Decls), conteniendo tanto la importación como la declaración de función
  • La función main tiene su propio subárbol con un nombre, información de tipo (parámetros, valores de retorno) y un cuerpo
  • Dentro del cuerpo puedes encontrar la llamada fmt.Println, que se descompone en sus componentes: la expresión selectora (fmt.Println) y los argumentos ("Hello, World!")

La idea clave es esta: el AST es solo otra representación de tu código, estructurada de una manera que hace fácil para el compilador entender relaciones y semántica.

Pruébalo Tú Mismo

¿Quieres explorar ASTs tú mismo? La biblioteca estándar de Go incluye un paquete ast que te permite parsear código Go e inspeccionar el árbol resultante. Aquí hay un programa completo que puedes ejecutar:

import (
	"go/ast"
	"go/parser"
	"go/token"
)

func main() {
	// src es la entrada para la que queremos imprimir el AST.
	src := `package main

import "fmt"

func main() {
	fmt.Println("Hello, World!")
}
`

	// Crea el AST parseando src.
	fset := token.NewFileSet() // las posiciones son relativas a fset
	f, err := parser.ParseFile(fset, "", src, 0)
	if err != nil {
		panic(err)
	}

	// Imprime el AST.
	ast.Print(fset, f)

}

Ahora que entendemos cómo se ve un AST, sumerjámonos en cómo el parser realmente construye esta estructura de árbol desde el flujo de tokens.

Cómo Funciona el Parser

El parser tiene algunas similitudes con el scanner que exploramos en el artículo anterior. Como el scanner, procesa entrada una pieza a la vez—excepto que en lugar de leer un carácter a la vez, el parser lee un token a la vez.

Pero aquí hay una diferencia clave: el scanner devuelve cada token a medida que lo encuentra, transmitiéndolos uno por uno. El parser, por otro lado, consume todos los tokens y construye el árbol completo antes de devolver algo. No obtienes nodos individuales—obtienes el AST completo para todo el archivo cuando termina el parsing.

Otro detalle interesante: el parser en realidad embebe el scanner directamente dentro de sí mismo. Así es como se ve en el código fuente:

type parser struct {
    file  *PosBase
    errh  ErrorHandler
    mode  Mode
    pragh PragmaHandler
    scanner

    base   *PosBase // base de posición actual
    first  error    // primer error encontrado
    errcnt int      // número de errores encontrados
    pragma Pragma   // pragmas

    fnest  int    // nivel de anidamiento de función (para manejo de errores)
    xnest  int    // nivel de anidamiento de expresión (para resolución de ambigüedad de complit)
    indent []byte // soporte de rastreo
}

¿Ves ese campo scanner sin nombre? Eso significa que el parser embebe el tipo scanner directamente, dándole acceso a todos los métodos del scanner. Así es como el parser puede llamar next() para avanzar a través de tokens.

El parser siempre opera a nivel de archivo—parseas un archivo completo de una vez. Haces esto usando las funciones Parse o ParseFile del paquete src/cmd/compile/internal/syntax.

Veamos cómo comienza este proceso de parsing.

Comenzando el Parseo

La función ParseFile es simple: lee el contenido del archivo y lo entrega a la función Parse. Aquí es donde comienza el trabajo real:

func Parse(base *PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) (_ *File, first error) {
	defer func() {
		if p := recover(); p != nil {
			if err, ok := p.(Error); ok {
				first = err
				return
			}
			panic(p)
		}
	}()

	var p parser
	p.init(base, src, errh, pragh, mode)
	p.next()
	return p.fileOrNil(), p.first
}

Aquí está lo que está sucediendo:

  1. La función crea un nuevo parser y lo inicializa con el código fuente
  2. Llama a next() para cargar el primer token—esto prepara el parser, poniéndolo listo para comenzar a reconocer patrones
  3. Llama a fileOrNil() para parsear el archivo completo y construir el AST

Antes de sumergirnos en lo que hace fileOrNil(), hablemos sobre el enfoque de parsing que usa el compilador de Go. Entender esto te ayudará a dar sentido a los patrones de código que estás a punto de ver.

Descenso Recursivo y Descomposición Jerárquica

El parser de Go se clasifica como un parser de descenso recursivo. Este término describe una técnica de parsing donde:

  1. Descenso: El parser trabaja de arriba hacia abajo, comenzando desde la construcción de más alto nivel (un archivo) y dividiéndola en piezas más pequeñas (declaraciones, sentencias, expresiones)
  2. Recursivo: Ciertas construcciones pueden contenerse a sí mismas—las expresiones pueden contener otras expresiones, las sentencias pueden contener bloques de sentencias, los tipos pueden contener otros tipos

Ahora aquí hay una distinción importante: la mayor parte de lo que veremos en este artículo es en realidad descomposición jerárquica en lugar de recursión directa. Descomposición jerárquica significa dividir un problema en sub-problemas más pequeños y delegar a funciones especializadas—como cómo fileOrNil() llama a constDecl(), que llama a nameList(), que llama a helpers de nivel inferior. Cada función maneja un nivel de la jerarquía.

La recursión verdadera sucede en partes que no cubriremos en detalle—específicamente al parsear expresiones, sentencias y tipos. Por ejemplo, al parsear la expresión a + (b * c), el parser de expresiones tiene que llamarse a sí mismo para parsear la expresión anidada (b * c). Esa es recursión genuina: la misma función llamándose a sí misma antes de terminar.

Así que mientras el parser de Go es un parser de descenso recursivo en general, los ejemplos que recorreremos demuestran principalmente el patrón de descomposición jerárquica. El nombrado viene del hecho de que el parser usa ambas técnicas, siendo la recursión esencial para manejar construcciones de lenguaje anidadas.

Recorramos el proceso de parsing paso a paso, comenzando desde la raíz del AST.

Parseando un Archivo

El parser siempre comienza llamando a la función fileOrNil. Esta función es responsable de construir el nodo raíz de nuestro AST—el nodo *File.

Veamos cómo funciona, pieza por pieza.

Creando el Nodo File

func (p *parser) fileOrNil() *File {
	if trace {
		defer p.trace("file")()
	}

	f := new(File)
	f.pos = p.pos()
    ...

El parser crea un nuevo nodo File vacío—esto se convertirá en la raíz de nuestro AST. A medida que progresa el parsing, poblará este nodo con todo lo que encuentra: el nombre del paquete, importaciones, declaraciones de funciones, y así sucesivamente.

También registra la posición del archivo en el código fuente, que es útil más tarde para mensajes de error.

Con el nodo de archivo vacío listo, el parser puede comenzar a llenarlo—comenzando con la declaración de paquete.

Parseando la Declaración de Paquete

    ...
	// PackageClause
	if !p.got(_Package) {
		p.syntaxError("package statement must be first")
		return nil
	}

	f.Pragma = p.takePragma()
	f.PkgName = p.name()
	p.want(_Semi)

	// don't bother continuing if package clause has errors
	if p.first != nil {
		return nil
	}
    ...

Ahora el parser verifica si el primer token es package. Recuerda, cada archivo Go debe comenzar con una declaración de paquete. Si ese token no está ahí, el parser inmediatamente reporta un error de sintaxis y se rinde.

Si encuentra package, lee el nombre del paquete (como main) y lo almacena en f.PkgName. Luego espera un punto y coma—que, como aprendimos en el artículo del scanner, fue insertado automáticamente por el scanner después del nombre del paquete.

Si hay algún error en este punto, el parsing se detiene. No tiene sentido continuar si ni siquiera tenemos una declaración de paquete válida.

Ahora que tenemos un paquete válido, el parser puede pasar a la siguiente parte de un archivo Go: importaciones.

Parseando Importaciones

    ...
	// { ImportDecl ";" }
	for p.got(_Import) {
		f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
		p.want(_Semi)
	}
    ...

El parser hace un bucle, verificando repetidamente si el siguiente token es import. Mientras siga encontrando tokens import, los procesa uno a la vez.

Para cada importación que encuentra, llama a p.importDecl—una función que sabe cómo parsear una sola declaración de importación—y agrega el resultado a la lista de declaraciones del archivo. Luego espera un punto y coma antes de continuar.

Hay un detalle inteligente aquí: p.importDecl se pasa como una referencia de función, no se llama directamente. El helper appendGroup es el que en realidad la llama. Este diseño maneja ambos estilos de importaciones igualmente bien:

import "fmt"              // Importación única

import (                  // Importaciones agrupadas
    "fmt"
    "strings"
)

El bucle continúa hasta que no hay más tokens import, luego el parser pasa al resto del archivo.

Parseando Declaraciones de Nivel Superior

	// { TopLevelDecl ";" }
	for p.tok != _EOF {
		switch p.tok {
		case _Const:
			p.next()
			f.DeclList = p.appendGroup(f.DeclList, p.constDecl)

		case _Type:
			p.next()
			f.DeclList = p.appendGroup(f.DeclList, p.typeDecl)

		case _Var:
			p.next()
			f.DeclList = p.appendGroup(f.DeclList, p.varDecl)

		case _Func:
			p.next()
			if d := p.funcDeclOrNil(); d != nil {
				f.DeclList = append(f.DeclList, d)
			}

		default:
			if p.tok == _Lbrace && len(f.DeclList) > 0 && isEmptyFuncDecl(f.DeclList[len(f.DeclList)-1]) {
				// opening { of function declaration on next line
				p.syntaxError("unexpected semicolon or newline before {")
			} else {
				p.syntaxError("non-declaration statement outside function body")
			}
			p.advance(_Const, _Type, _Var, _Func)
			continue
		}

		// Reset p.pragma BEFORE advancing to the next token (consuming ';')
		// since comments before may set pragmas for the next function decl.
		p.clearPragma()

		if p.tok != _EOF && !p.got(_Semi) {
			p.syntaxError("after top level declaration")
			p.advance(_Const, _Type, _Var, _Func)
		}
	}

Aquí es donde el parser maneja el resto del archivo. A nivel superior de un archivo Go, solo se permiten cuatro cosas: declaraciones de constantes, declaraciones de tipos, declaraciones de variables y declaraciones de funciones.

El parser hace un bucle hasta que se encuentra con un EOF, verificando qué tipo de token ve:

  • Si es const, llama a constDecl para parsear la constante
  • Si es type, llama a typeDecl para parsear la definición de tipo
  • Si es var, llama a varDecl para parsear la variable
  • Si es func, llama a funcDeclOrNil para parsear la función

Cada una de estas funciones construye su propio subárbol (un nodo ConstDecl, un nodo TypeDecl, etc.) y lo devuelve. El parser luego agrega ese subárbol al DeclList en el nodo de archivo.

Si el parser encuentra algo más—digamos, una declaración como x := 5 fuera de cualquier función—reporta un error de sintaxis. Go es estricto sobre qué pertenece dónde.

Una vez que el parser ha trabajado a través de todas las declaraciones y alcanza el final del archivo, solo hay un último paso.

Finalizando el Archivo

	// p.tok == _EOF

	p.clearPragma()
	f.EOF = p.pos()

	return f
}

Cuando el bucle termina (habiendo encontrado un EOF), el parser registra la posición del final del archivo y devuelve el nodo File completo.

Y eso es todo—¡hemos construido la raíz de nuestro AST!

Pero recuerda, fileOrNil delegó trabajo a otras funciones como constDecl, typeDecl y funcDeclOrNil. Acerquémonos a una de esas para ver cómo se parsean las declaraciones individuales. Comenzaremos con declaraciones de constantes ya que son relativamente directas.

Parseando una Declaración de Constante

Aquí está la función constDecl completa:

func (p *parser) constDecl(group *Group) Decl {
	if trace {
		defer p.trace("constDecl")()
	}

	d := new(ConstDecl)
	d.pos = p.pos()
	d.Group = group
	d.Pragma = p.takePragma()

	d.NameList = p.nameList(p.name())
	if p.tok != _EOF && p.tok != _Semi && p.tok != _Rparen {
		d.Type = p.typeOrNil()
		if p.gotAssign() {
			d.Values = p.exprList()
		}
	}

	return d
}

¿Notas el patrón? Al igual que con el nodo de archivo, comenzamos creando un nodo vacío y luego lo poblamos.

Primero, crea un nuevo nodo ConstDecl y registra su posición.

Luego maneja el parámetro group. Esto trata con casos donde tienes múltiples constantes declaradas juntas dentro de paréntesis:

const (
    A = 1
    B = 2
)

Todas las constantes en los paréntesis comparten el mismo grupo. Si declaras una constante independiente (const X = 5), el grupo es nil.

Luego, lee el nombre(s) de constante. Ya que puedes declarar múltiples constantes en una línea (const A, B, C = 1, 2, 3), recopila todos los nombres en una lista.

Después de eso, si hay más para parsear, busca dos piezas opcionales:

  • Una anotación de tipo (como const X int = 5)
  • Una asignación con valores (como = 1, 2, 3)

Ambas son opcionales porque Go puede inferir tipos de valores. Y en bloques de constantes agrupados, constantes posteriores pueden incluso heredar valores de las anteriores.

Finalmente, la función devuelve el nodo ConstDecl completado, que se agrega a la lista de declaraciones del archivo.

Este patrón—crear un nodo, parsear sus componentes, devolver el nodo—es la estructura fundamental para todas las funciones de parser. La función varDecl funciona casi idénticamente, y typeDecl y funcDeclOrNil siguen el mismo enfoque general, solo con más complejidad.

Casos Más Complejos

No he cubierto todo aquí. Las declaraciones de funciones involucran parsear listas de parámetros, tipos de retorno y cuerpos de función (que contienen sentencias y expresiones). Las declaraciones de tipos pueden definir structs, interfaces y otros tipos complejos. El parsing de expresiones maneja cosas como precedencia de operadores, llamadas a funciones, aserciones de tipo y más.

Estos siguen el mismo patrón de descomposición jerárquica que hemos visto—pero también involucran la recursión verdadera que discutimos antes, donde los parsers se llaman a sí mismos para manejar construcciones anidadas.

Si tienes curiosidad sobre los detalles, te animo a explorar src/cmd/compile/internal/syntax/parser.go tú mismo—es sorprendentemente legible una vez que entiendes los patrones básicos.

Ahora veamos todas estas piezas trabajando juntas en acción.

Recorriendo un Ejemplo

Sigamos nuestro programa hola mundo y veamos exactamente cómo el parser construye su AST.

El parser comienza con el flujo de tokens del scanner. ¿Recuerdas cómo se veía? package, IDENT(main), ;, import, STRING("fmt"), ;, func, IDENT(main), (, ), {, y así sucesivamente.

Así es como se desarrolla el parsing:

Creación de archivo: El parser llama a fileOrNil() y crea un nuevo nodo File.

Declaración de paquete: Ve el token package, lee el nombre main, espera un punto y coma (que el scanner insertó), y almacena el nombre del paquete en el nodo de archivo.

Declaración de importación: Ve import, llama a importDecl, que lee la cadena "fmt" y crea un nodo ImportSpec. Esto se agrega a la lista de declaraciones del archivo.

Declaración de función: Ve func, llama a funcDeclOrNil, que:

  • Lee el nombre de función (main)
  • Parsea la lista de parámetros (vacía: ())
  • Parsea el tipo de retorno (ninguno)
  • Parsea el cuerpo de función (el bloque { ... })

Dentro del cuerpo de función, el parser encuentra una declaración: fmt.Println("Hello world"). Reconoce esto como una declaración de expresión conteniendo una expresión de llamada. La expresión de llamada tiene:

  • Una expresión selectora (fmt.Println) como la función siendo llamada
  • Una lista de argumentos conteniendo un literal de cadena ("Hello world")

El parser construye nodos para todos estos: CallExpr, SelectorExpr, nodos Ident para fmt y Println, y un nodo BasicLit para la cadena.

Finalizando: Cuando el parser se encuentra con un EOF, registra la posición final y devuelve el nodo File completo, que ahora contiene el árbol AST completo representando nuestro programa.

Y así es como un flujo plano de tokens se convierte en un árbol estructurado que captura el significado y relaciones en nuestro código.

Ahora que entiendes cómo funciona el parser, podrías preguntarte: ¿puedo usar este conocimiento en mis propios proyectos? Absolutamente.

Usando el AST en Tu Propio Código

Entender el AST no es solo útil para aprender cómo funcionan los compiladores—es una herramienta práctica que puedes usar en tus propios proyectos Go. Muchos desarrolladores Go aprovechan el paquete go/ast para parsear código Go programáticamente y construir herramientas poderosas.

Aquí hay algunos proyectos interesantes que usan parsing de AST:

  • mage - Una alternativa a Make que usa código Go como su lenguaje de script de compilación
  • goa - Un framework que usa ASTs para generar implementaciones de API desde diseños de alto nivel
  • goql - Te permite consultar paquetes Go usando SQL, como si fueran bases de datos

Estos son solo algunos ejemplos de lo que es posible. Tú también puedes construir tus propias herramientas basadas en AST: extractores de texto traducible, generadores automáticos de mocks, linters personalizados que aplican las convenciones de codificación de tu equipo, herramientas de refactorización y más. Si puedes representar lo que estás buscando como patrones en estructura de código, el AST lo hace accesible.

Resumamos lo que hemos aprendido.

Resumen

El parser es la segunda fase del compilador de Go. Toma el flujo plano de tokens del scanner y construye un Árbol de Sintaxis Abstracta—una representación estructurada que captura el significado y relaciones en tu código.

Hemos visto cómo el parser:

  • Usa descomposición jerárquica para dividir el parsing en funciones pequeñas y enfocadas, con cada función manejando un nivel de estructura
  • Embebe el scanner para acceder a tokens bajo demanda
  • Construye el AST de arriba hacia abajo, comenzando con el nodo de archivo y trabajando hacia abajo a través de declaraciones, sentencias y expresiones
  • Sigue un patrón consistente: crear un nodo, parsear sus componentes, delegar a funciones especializadas para subárboles, devolver el nodo completado

El parser de Go es estricto y predecible. Cada archivo Go debe seguir la misma estructura: declaración de paquete, importaciones, luego declaraciones de nivel superior. Esta consistencia hace que el código Go sea fácil de parsear—y fácil tanto para humanos como para máquinas de entender.

Si quieres profundizar más, recomiendo mucho explorar src/cmd/compile/internal/syntax/parser.go. Una vez que entiendes los patrones que hemos cubierto, el resto del parser se vuelve mucho más accesible.

En un artículo futuro, cubriré la Representación Intermedia (IR)—cómo el compilador transforma este AST en una representación de nivel inferior que está más cerca de operaciones de máquina reales. Aquí es donde el compilador comienza a preparar tu código para optimización y generación de código.