blob: 049f3b9a4b734055ec54b80526667ef0c57b8bd5 [file] [log] [blame]
Stacks of Tokens
A study in interfaces
Sydney Go Meetup
15 September 2016
Rob Pike
Google
@rob_pike
[[http://golang.org/s/plusrob][+RobPikeTheHuman]]
http://golang.org/
* Background
Spoke at Gophercon this year: [[https://talks.golang.org/2016/asm.slide]]
That talk was about system design and portability.
Today's talk is about its lexer.
Spoke about lexing before: [[https://talks.golang.org/2011/lex.slide]]
That talk showed a way to use concurrency to build a lexer.
Today's talk is about interfaces.
* Lexer
A lexer, also called a scanner, breaks the input stream into distinct "tokens":
- identifiers
- numbers
- quoted strings
- operators
- miscellaneous characters such as comma, colon.
Each token has a _type_ and a _value_.
* Example
MOVQ R0, 4(R1)
The lexer turns this into the stream
- identifier `MOVQ`
- identifier `R0`
- character `,`
- number `4`
- character `(`
- identifier `R1`
- character `)`
Spaces are ignored.
The parser then reads these tokens to parse the input into a _parse_tree_.
* Go's text/scanner package
There is a nice, efficient lexer package in the Go standard library:
- [[https://golang.org/pkg/text/scanner/][`text/scanner`]]
It can do this job just fine.
But.... that is not enough for the assembler because of
* Backwards compatibility
The new Go assembler had to be totally compatible with the ones it replaces, which used YACC and were written in C. (See [[https://talks.golang.org/2015/gogo.slide][]].)
Each assembler (one per architecture) contained these lines at the end of `lex.c`:
#include "../cc/lexbody"
#include "../cc/macbody"
This gave the assemblers the same lexer as the C compiler.
The differences between C tokens and Go tokens are minor and can be handled, but....
The C lexer brings in something problematic.
* The C preprocessor
The old assemblers had a C preprocessor built in!
An old-fashioned one, without `#if` and token pasting, but still:
#include "file"
#define MAXBUF 512
#define MULDIV(a, b, c) ((a)*(b)/(c))
#ifdef MAXBUF
#endif
The `text/scanner` package can't handle this.
But we need to do it to be compatible.
This talk is about how to use Go's interfaces to do it.
* An observation
What is standard input? An input source.
- read the input
What is an included file? An input source.
- read the file
What is a macro invocation? An input source.
- read the macro definition
Sounds a lot like `io.Reader`.
* Token reader
We don't want bytes, we want tokens. (Why?)
Instead of
type Reader interface {
Read(p []byte) (n int, err error)
}
we want something like
type TokenReader interface {
ReadToken() (Token, error)
}
In practice the parser needs something different from `Read`, but the basic idea works.
We build a lexer around an interface that reads tokens.
* The observation in practice
What is standard input? An input source.
- get tokens from the input
What is an included file? An input source.
- get tokens from the file
What is a macro invocation? An input source.
- get tokens from the macro definition
Each of these implements the `TokenReader` interface.
* TokenReader
type TokenReader interface {
// Next returns the next token.
Next() ScanToken
// The following methods all refer to the most recent token returned by Next.
// Text returns the original string representation of the token.
Text() string
// File reports the source file name of the token.
File() string
// Line reports the source line number of the token.
Line() int
// Col reports the source column number of the token.
Col() int
}
Parser calls `Next`, then can ask about the token: what is, where it is.
`ScanToken` is just `text/scanner.Token` with tweaks.
Note: No `Peek`. This has no lookahead.
* Tokenizer
`Tokenizer`, the foundational `TokenReader`, turns a `text/scanner.Scanner` into a `TokenReader`.
// A Tokenizer is a simple wrapping of text/scanner.Scanner, configured
// for our purposes and made a TokenReader. It forms the lowest level,
// turning text from readers into tokens.
type Tokenizer struct {
tok ScanToken // Most recent token.
s *scanner.Scanner
line int
fileName string
}
func NewTokenizer(name string, r io.Reader, file *os.File) *Tokenizer
Either the reader or the file may be nil.
`Tokenizer` implements `TokenReader`
* Tokenizer.Next
To give the flavor:
func (t *Tokenizer) Next() ScanToken {
s := t.s
for {
t.tok = ScanToken(s.Scan())
if t.tok != scanner.Comment {
break
}
length := strings.Count(s.TokenText(), "\n")
t.line += length
histLine += length
// For now, just discard all comments.
}
// Special processing for '\n' etc. elided.
return t.tok
}
* Tokenizer.Text
func (t *Tokenizer) Text() string {
switch t.tok {
case LSH: // Special handling of odd tokens used by ARM.
return "<<"
case RSH:
return ">>"
case ARR:
return "->"
case ROT:
return "@>"
}
return t.s.TokenText()
}
`LSH` etc. are the reason for `ScanToken`: the set of tokens is a superset of the underlying type `text/scanner.Token`.
* Macro definitions
It's easy to see how files work: `NewTokenizer` can do that.
What about a macro definition?
#define A(arg) 27+(arg)
Becomes the tokens
27 + ( arg )
When we encounter `A(x)`, we substitute the argument and get
27 + ( x )
Use a slice of tokens and store them in a `Macro` struct.
type Macro struct {
name string // The #define name.
args []string // Formal arguments.
tokens []Token // Body of macro.
}
* Slice
// A Slice reads from a slice of Tokens.
type Slice struct {
tokens []Token
fileName string
line int
pos int
}
Implements `TokenReader`.
func (s *Slice) Next() ScanToken {
s.pos++
if s.pos >= len(s.tokens) {
return scanner.EOF
}
return s.tokens[s.pos].ScanToken
}
To invoke a macro, substitute the _actuals_ for the _formals_ and make a `Slice`.
* Command-line flags
A command-line flag `-D` can define a macro before execution:
go tool asm -D 'macro=value' file.s
That's easy!
var DFlag MultiFlag
flag.Var(&DFlag, "D", "predefined symbol D=identifier...")
type MultiFlag []string // Implements flag.Value, allows multiple settings.
predefine(DFlag)
* Predefined macros
// predefine installs the macros set by the -D flag on the command line.
func predefine(defines MultiFlag) map[string]*Macro {
macros := make(map[string]*Macro)
for _, name := range defines {
value := "1"
i := strings.IndexRune(name, '=')
if i > 0 {
name, value = name[:i], name[i+1:]
}
// Various error checks elided.
macros[name] = &Macro{
name: name,
args: nil, // No arguments allowed.
tokens: Tokenize(value), // Turn the value into tokens.
}
}
return macros
}
The return value is the initial symbol table of macros.
* The big picture
We know how to:
- tokenize an input stream from text or `io.Reader`
- define a macro
- invoke a macro
But how does it fit together?
Which implementation `TokenReader` does the parser see?
Consider
- `#include` names a file to process next
- macro invocation names a slice of tokens to process next
It's a stack! Push new input, pop at EOF.
* Stack
// A Stack is a stack of TokenReaders. As the top TokenReader hits EOF,
// it resumes reading the next one down.
type Stack struct {
tr []TokenReader
}
// Push adds tr to the top (end) of the input stack. (Popping happens automatically.)
func (s *Stack) Push(tr TokenReader) {
s.tr = append(s.tr, tr)
}
func (s *Stack) Next() ScanToken {
tos := s.tr[len(s.tr)-1]
tok := tos.Next()
for tok == scanner.EOF && len(s.tr) > 1 {
// Pop the topmost item from the stack and resume with the next one down.
s.tr = s.tr[:len(s.tr)-1]
tok = s.Next()
}
return tok
}
* The Input type
// Input is the main input: a stack of readers and some macro definitions.
// It also handles #include processing (by pushing onto the input stack)
// and parses and instantiates macro definitions.
type Input struct {
Stack
includes []string // Directories in which to look for #includes
macros map[string]*Macro
text string // Text of last token returned by Next.
...
}
Note the embedding of `Stack`: `Input` is a wrapping of the `Stack` implementation of `TokenReader`.
The parser uses a single instance of `Input` as its `TokenReader`.
* Example: #include processing
Some error handling elided for brevity.
func (in *Input) include() {
// Find and parse file name, which is next token, a string.
tok := in.Stack.Next()
name, _ := strconv.Unquote(in.Stack.Text())
in.expectNewline("#include") // Checks that a newline comes now.
// Push tokenizer for file onto stack.
fd, err := os.Open(name)
if err != nil {
for _, dir := range in.includes {
fd, err = os.Open(filepath.Join(dir, name))
if err == nil {
break
}
}
}
in.Push(NewTokenizer(name, fd, fd))
}
* Macro definition
Macro definition is similar but more complex because of the variety of forms.
Must deal with constants, empty values, macros with arguments, etc.
The end result is to build a `Macro` value and install it in `Input.macros`.
* The final piece: Input.Next
Here is the implementation of a CPP input stream using these types.
(Error handling mostly elided for brevity.)
func (in *Input) Next() ScanToken {
// If we cannot generate a token after 100 macro invocations, we're in trouble.
for nesting := 0; nesting < 100; {
tok := in.Stack.Next()
switch tok {
case '#':
in.hash()
case scanner.Ident:
// Is it a macro name?
name := in.Stack.Text()
macro := in.macros[name]
if macro != nil {
nesting++
in.invokeMacro(macro)
continue
}
fallthrough
default:
// Continued on next slide.
* Input.Next part 2
func (in *Input) Next() ScanToken {
// Continued from previous slide.
default:
if tok == scanner.EOF && len(in.ifdefStack) > 0 {
// We're skipping text but have run out of input with no #endif.
in.Error("unclosed #ifdef or #ifndef")
}
if in.enabled() {
in.text = in.Stack.Text()
return tok
}
}
}
in.Error("recursive macro invocation")
return 0
}
* Initializing and running the lexer
// NewInput returns an Input from the given path.
func NewInput(name string) *Input {
return &Input{
// include directories: look in source dir, then -I directories.
includes: append([]string{filepath.Dir(name)}, IFlag...),
macros: predefine(DFlag),
}
}
To run, call `in.Push` to put the input file (or `os.Stdin`) on the stack.
Then the lexer runs until the `Stack` is empty.
* Summary
Interfaces give programs structure.
Interfaces encourage design by composition.
- We have an interface that is implemented by a stack of itself!
Interfaces enable and enforce clean divisions between components.
- The simple idea of a `TokenReader` let us implement `#include` files, `#define` macros, command-line flags, `#ifdef` and more with one simple interface.
And a final tip of the hat to `text/scanner` under it all.