Digging deeper into the analysis of Go-code
Tags: go, compiler, ast
Published: 2020-09-25 23:57:30

>This article is originally posted [here](https://nakabonne.dev/posts/digging-deeper-into-the-analysis-of-go-code/).

The analysis of source code at the syntactic level can help you with your coding in a variety of ways. For that, the text is almost always converted to AST first to make it easier to handle in most languages.  
As some of you may know, Go has a powerful package [`go/parser`](https://pkg.go.dev/go/parser), with it, you can convert source code to AST relatively easily.
However, I couldn't help but be curious about how it is working, and I realized my mind could only be satisfied by getting started to read the API implementation.
In this article, I will walk you through how it is converted, by reading the implementation of its API.  

Even those unfamiliar with the Go language don't need to close the tab in the browsers, as this is a generic enough article to understand how programming languages are analyzed.  
This article is also the first step in understanding the compiler and interpreter, as well as delving into static analysis.

## AST
Let's start with some of the knowledge you need to read the implementation.
What is AST(Abstract Syntax Tree)? According to [Wikipedia](https://en.wikipedia.org/wiki/Abstract_syntax_tree):
>In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code.

Most compilers and interpreters use AST as an internal representation of the source code; AST typically omits semicolons, line feed characters, white spaces, braces, square brackets, and round brackets from the syntax tree, etc.

**What you can do with AST:**
- Source code analysis
- Code generation
- Can be rewritten

## How to convert to AST
Plain text is quite straightforward for us, but from a machine, nothing is tougher to handle. Therefore, you have to first do lexical analysis the text with a lexer. The general flow is to pass it to a parser and retrieve the AST.

![Parsing](https://dev-to-uploads.s3.amazonaws.com/i/suy8xj3j7t8em6oqvnfz.png)
 

I'd prefer to point out here that there is not a single universal AST format which can be used by any parser.
For instance, `x + 2` in Go is represented by:

```go
*ast.BinaryExpr {
.  X: *ast.Ident {
.  .  NamePos: 1
.  .  Name: "x"
.  .  Obj: *ast.Object {
.  .  .  Kind: bad
.  .  .  Name: ""
.  .  }
.  }
.  OpPos: 3
.  Op: +
.  Y: *ast.BasicLit {
.  .  ValuePos: 5
.  .  Kind: INT
.  .  Value: "2"
.  }
}
```

### Lexical analysis
As mentioned earlier, the analysis typically starts by passing the text to a lexer and then fetching the tokens. A token is a string with an assigned and thus identified meaning.
[`go/scanner.Scanner`](https://pkg.go.dev/go/scanner?tab=doc#Scanner) is in charge of the lexer in Go.  
What is the identified meaning? Seeing is believing.

Let's say you write:
```go
package main

const s = "foo"
```

This is what happens when you tokenize it:
```go
PACKAGE(package)
IDENT(main)
CONST(const)
IDENT(s)
ASSIGN(=)
STRING("foo")
EOF()
```

All tokens in Go are defined [here](https://pkg.go.dev/go/token?tab=doc#Token).

## Peeling away at the parsing API
To convert a Go source file to AST, just call [`go/parser.ParseFile`](https://pkg.go.dev/go/parser?tab=doc#ParseFile) as shown below:
```go
fset := token.NewFileSet()
f, _ := parser.ParseFile(fset, "foo.go", nil, parser.ParseComments)
```

Now that we've figured out the conversion steps by the previous chapter, let's actually read the internal implementation of that method! (The version of Go we refer to is 1.14.1).

### Scanner.Scan() — a method for Lexical Analysis
How does Go perform lexical analysis? As previously mentioned, [`go/scanner.Scanner`](https://pkg.go.dev/go/scanner?tab=doc#Scanner) is in charge of the lexer in Go.
Thus at first, let's take a closer look at that [`Scanner.Scan()`](https://pkg.go.dev/go/scanner?tab=doc#Scanner.Scan) method — which is called by `parser.ParseFile()` internally.

[scanner/scanner.go](https://github.com/golang/go/blob/5aef51a729f428bfd4b2c28fd2ba7950660608e0/src/go/scanner/scanner.go#L792-L801)
```go
func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string) {
... // Omission
	switch ch := s.ch; {
	case isLetter(ch):
		lit = s.scanIdentifier()
		if len(lit) > 1 {
			// keywords are longer than one letter - avoid lookup otherwise
			tok = token.Lookup(lit)
			switch tok {
			case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
				insertSemi = true
			}
		} else {
... // Omission
}
```

`ch` is the current character held by Scanner. `Scanner.Scan()` advances to next character by calling `Scanner.next()` and populates `ch`, as long as it is available as an identifier name.
The code above is for the case where `ch` is a letter; It pauses its advance as soon as it encounters a character that cannot be used as an identifier and then determines the type of token.

There are different ways to determine where does a single token start and where does it end, depending on the character. For instance, in the case of String, it continues to advance until `"` appears:

[scanner/scanner.go](https://github.com/golang/go/blob/5aef51a729f428bfd4b2c28fd2ba7950660608e0/src/go/scanner/scanner.go#L823-L826)

```go
case '"':
	insertSemi = true
	tok = token.STRING
	lit = s.scanString()
```

```go

func (s *Scanner) scanString() string {
	// '"' opening already consumed
	offs := s.offset - 1

	for {
		ch := s.ch
		if ch == '\n' || ch < 0 {
			s.error(offs, "string literal not terminated")
			break
		}
		s.next()
		if ch == '"' {
			break
		}
		if ch == '\\' {
			s.scanEscape('"')
		}
	}

	return string(s.src[offs:s.offset])
}
```

Finally, the Scanner.Scan() method returns a token that has been identified.

### Parsing
Before taking a look parsing a file, let's check the file structure in Go.
According to [The Go Programming Language Specification - Source file organization](https://golang.org/ref/spec#Source_file_organization):
>Each source file consists of a package clause defining the package to which it belongs, followed by a possibly empty set of import declarations that declare packages whose contents it wishes to use, followed by a possibly empty set of declarations of functions, types, variables, and constants.

That is, the structure is:
- A package clause
- Import declarations
- Top level declarations

After parsing a package clause and import declarations, `parser.parseFile()` repeats the parsing of the declaration to the end of the file.

[parser/parser.go](https://github.com/golang/go/blob/5aef51a729f428bfd4b2c28fd2ba7950660608e0/src/go/parser/parser.go#L2559-L2562)

```go
for p.tok != token.EOF {
	decls = append(decls, p.parseDecl(declStart))
}
```

So let's look at `parser.parseDecl` next.

#### parser.parseDecl() — a method to parse the syntax of a declaration
`parser.parseDecl()` returns `ast.Decl`, the node of the syntax tree representing the declaration in the Go source code.

[parser/parser.go](https://github.com/golang/go/blob/5aef51a729f428bfd4b2c28fd2ba7950660608e0/src/go/parser/parser.go#L2492-L2516)

```go
func (p *parser) parseDecl(sync map[token.Token]bool) ast.Decl {
	if p.trace {
		defer un(trace(p, "Declaration"))
	}

	var f parseSpecFunction
	switch p.tok {
	case token.CONST, token.VAR:
		f = p.parseValueSpec

	case token.TYPE:
		f = p.parseTypeSpec

	case token.FUNC:
		return p.parseFuncDecl()

	default:
		pos := p.pos
		p.errorExpected(pos, "declaration")
		p.advance(sync)
		return &ast.BadDecl{From: pos, To: p.pos}
	}

	return p.parseGenDecl(p.tok, f)
}
```

It goes through the tokens and process them differently for each keyword. Let's deep dive into `parseFuncDecl()`.

[parser/parser.go](https://github.com/golang/go/blob/5aef51a729f428bfd4b2c28fd2ba7950660608e0/src/go/parser/parser.go#L2442-L2455)

```go
if p.tok == token.LPAREN {
	recv = p.parseParameters(scope, false)
}

ident := p.parseIdent()

params, results := p.parseSignature(scope)

var body *ast.BlockStmt
if p.tok == token.LBRACE {
	body = p.parseBody(scope)
	p.expectSemi()
} else if p.tok == token.SEMICOLON {
	p.next()
```

Internally, it advances the token by calling `Scanner.Scan()` — which we saw in detail earlier.

`token.LPAREN` represents `(`, so you can see that it starts parsing the parameters as soon as `(` is found.  
`token.LBRACE` represents `{`, so you can see that it starts parsing the function body as soon as `{` is found.

.  
.  
.  
Oops, it's going to take forever at this rate...

## Summary
Parsing the tokens by myself has made me feel closer to the compiler and interpreter that I used to feel horrible about.
I'd love to dabble in [Writing A Compiler In Go](https://compilerbook.com/) and [Writing An Interpreter In Go](https://interpreterbook.com/) as well.