talks/2011: copy in the lexical scanning talk from its old location
It resides in my code.google.com personal repository, but that
will go away and anyway it belongs here, a place that did not
exist when the talk was given.
The only edits are formatting for the present format, an added
line about Go 1 allowing goroutines in init, and a file rename
to avoid a git gofmt precommit.
Change-Id: I4c2f2c2d44fef9cb574ef4f7223d9cb0c7b15060
Reviewed-on: https://go-review.googlesource.com/12839
Reviewed-by: Andrew Gerrand <adg@golang.org>
diff --git a/2011/lex.slide b/2011/lex.slide
new file mode 100644
index 0000000..831e451
--- /dev/null
+++ b/2011/lex.slide
@@ -0,0 +1,343 @@
+Lexical Scanning in Go
+GTUG Sydney
+30 Aug 2011
+
+Rob Pike
+r@golang.org
+
+* Structural mismatch
+
+Many programming problems realign one data structure to fit another structure.
+
+- breaking text into lines
+- "blocking" and "deblocking"
+- packet assembly and disassembly
+- parsing
+- lexing
+
+* Sometimes hard
+
+The pieces on either side have independent state, lookahead, buffers, ...
+Can be messy to do well.
+
+Coroutines were invented to solve this problem!
+They enable us to write the two pieces independently.
+
+Let's look at this topic in the context of a lexer.
+
+
+* A new template system
+
+Wanted to replace the old Go template package.
+It had many problems:
+
+- inflexible
+- inexpressive
+- code too fragile
+
+* A new template system
+
+Key change was re-engineering with a true lexer, parser, and evaluator.
+Has arbitrary text plus actions in `{{` `}}`.
+
+.code lex/snippets /Evaluation/,/Control.structures/
+
+* Today we focus on the lexer
+
+Must tokenize:
+
+- the stuff outside actions
+- action delimiters
+- identifiers
+- numeric constants
+- string constants
+- and others
+
+* Lex items
+
+Two things identify each lexed item:
+
+- its type
+- its value; a string is all we need
+
+.code lex/lex1.oldgo /item.represents/,/^}/
+
+* Lex type
+
+The type is just an integer constant.
+We use `iota` to define the values.
+
+.code lex/lex1.oldgo /itemType.identifies/,/type/
+.code lex/lex1.oldgo /const/,/itemEOF/
+
+* Lex type values (continued)
+
+.code lex/lex1.oldgo /itemElse/,/^\)/
+
+* Printing a lex item
+
+`Printf` has a convention making it easy to print any type: just define a `String()` method:
+
+.code lex/lex1.oldgo /func.*item.*String/,/^}/
+
+* How to tokenize?
+
+Many approaches available:
+
+- use a tool such as lex or ragel
+- use regular expressions
+- use states, actions, and a switch statement
+
+* Tools
+
+Nothing wrong with using a tool but:
+
+- hard to get good errors (can be very important)
+- tend to require learning another language
+- result can be large, even slow
+- often a poor fit
+- but lexing is easy to do yourself!
+
+* Regular expressions
+
+Blogged about this last week.
+
+- overkill
+- slow
+- can explore the state space too much
+- misuse of a dynamic engine to ask static questions
+
+* Let's write our own
+
+It's easy!
+
+Plus, most programming languages lex pretty much the same tokens, so once we learn how it's trivial to adapt the lexer for the next purpose.
+
+- an argument both for and against tools
+
+* State machine
+
+Many people will tell you to write a switch statement,
+something like this:
+
+.code lex/snippets /One/,/^}/
+
+* State machines are forgetful
+
+Boring and repetitive and error-prone, but anyway:
+
+Why switch?
+
+After each action, you know where you want to be;
+the new state is the result of the action.
+
+But we throw the info away and recompute it from the state.
+
+(A consequence of returning to the caller.)
+
+A tool can compile that out, but so can we.
+
+* What is a state? An action?
+
+State represents where we are and what we expect.
+
+Action represents what we do.
+
+Actions result in a new state.
+
+* State function
+
+Let's put them together: a state function.
+
+Executes an action, returns the next state—as a state function.
+
+Recursive definition but simple and clear.
+
+.code lex/lex1.oldgo /stateFn/,/type/
+
+* The run loop
+
+Our state machine is trivial:
+just run until the state goes to `nil`, representing "done".
+
+.code lex/snippets /run.lexes/,/^}/
+
+* The concurrent step
+
+How do we make tokens available to the client?
+Tokens can emerge at times that are inconvenient to stop to return to the caller.
+
+Use concurrency:
+Run the state machine as a goroutine,
+emit values on a channel.
+
+* The lexer type
+
+Here is the `lexer` type. Notice the channel of items; ignore the rest for now.
+
+.code lex/lex1.oldgo /lexer.holds/,/^}/
+
+* Starting the lexer
+
+A `lexer` initializes itself to lex a string and launches the state machine as a goroutine, returning the lexer itself and a channel of items.
+
+The API will change, don't worry about it now.
+
+.code lex/lex1.oldgo /func.lex/,/^}/
+
+* The real run routine
+
+Here's the real state machine run function, which runs as a goroutine.
+
+.code lex/lex1.oldgo /run.lexes/,/^}/
+
+* The token emitter
+
+A token is a type and a value, but (yay Go) the value can just be sliced from the input string.
+The `lexer` remembers where it is in the input and the emit routine just lobs that substring to the caller as the token's value.
+
+.code lex/lex1.oldgo /input.*scanned/,/pos.*position/
+.code lex/lex1.oldgo /emit.passes/,/^}/
+
+* Starting the machine
+
+As the `lexer` begins it's looking for plain text, so the initial state is the function `lexText`.
+It absorbs plain text until a "left meta" is encountered.
+
+.code lex/lex1.oldgo /run.lexes/,/^}/
+.code lex/lex1.oldgo /leftMeta/
+
+* lexText
+
+.code lex/lex1.oldgo /^func.lexText/,/^}/
+
+* lexLeftMeta
+
+A trivial state function.
+When we get here, we know there's a `leftMeta` in the input.
+
+.code lex/lex1.oldgo /^func.lexLeftMeta/,/^}/
+
+* lexInsideAction
+
+.code lex/lex1.oldgo /^func.lexInsideAction/,/itemPipe/
+
+* More of lexInsideAction
+
+This will give you the flavor.
+
+.code lex/lex1.oldgo /case.*"/,/lexRawQuote/
+.code lex/lex1.oldgo /case.*9/,/lexIdentifier/
+
+* The next function
+
+.code lex/lex1.oldgo /next.returns.the/,/^}/
+
+* Some lexing helpers
+
+.code lex/lex1.oldgo /ignore.skips/,/^}/
+.code lex/lex1.oldgo /backup.steps/,/^}/
+
+* The peek function
+
+.code lex/lex1.oldgo /peek.returns.but/,/^}/
+
+* The accept functions
+
+.code lex/lex1.oldgo /accept.consumes/,/^}/
+.code lex/lex1.oldgo /acceptRun.consumes/,/^}/
+
+* Lexing a number, including floating point
+
+.code lex/lex1.oldgo /^func.lexNumber/,/imaginary/
+
+* Lexing a number, continued
+
+This is more accepting than it should be, but not by much. Caller must call `Atof` to validate.
+
+.code lex/lex1.oldgo /Is.it.imaginary/,/^}/
+
+* Errors
+
+Easy to handle: emit the bad token and shut down the machine.
+
+.code lex/lex1.oldgo /error.returns/,/^}/
+
+* Summary
+
+Concurrency makes the lexer easy to design.
+
+Goroutines allow lexer and caller (parser) each to run at its own rate, as clean sequential code.
+
+Channels give us a clean way to emit tokens.
+
+* A problem
+
+Can't run a goroutine to completion during initialization.
+Forbidden by the language specification.
+(Raises awful issues about order of init, best avoided.)
+
+That means we can't lex & parse a template during init.
+
+The goroutine is a problem....
+
+_(Note:_This_restriction_was_lifted_in_Go_version_1_but_the_discussion_is_still_interesting.)_
+
+* Design vs. implementation
+
+…but it's not necessary anyway.
+
+The work is done by the design; now we just adjust the API.
+
+We can change the API to hide the channel, provide a function to get the next token, and rewrite the run function.
+
+It's easy.
+
+* A new API
+
+Hide the channel and buffer it slightly, turning it into a ring buffer.
+
+.code lex/r59-lex.go /lex.creates.a.new/,/^}/
+
+* A function for the next item
+
+Traditional lexer API: return next item.
+Includes the modified state machine runner.
+.
+.code lex/r59-lex.go /nextItem.returns/,/^}/
+
+* That's it
+
+We now have a traditional API for a lexer with a simple, concurrent implementation under the covers.
+
+Even though the implementation is no longer truly concurrent, it still has all the advantages of concurrent design.
+
+We wouldn't have such a clean, efficient design if we hadn't thought about the problem in a concurrent way, without worrying about "restart".
+
+Model completely removes concerns about "structural mismatch".
+
+* Concurrency is a design approach
+
+Concurrency is not about parallelism.
+
+(Although it can enable parallelism).
+
+Concurrency is a way to design a program by decomposing it into independently executing pieces.
+
+The result can be clean, efficient, and very adaptable.
+
+* Conclusion
+
+Lexers are fun.
+
+Concurrency is fun.
+
+Go is fun.
+
+* For more information
+
+Go: [[http://golang.org]]
+
+New templates: http://golang.org/pkg/exp/template/
+
+(Next release will move them out of experimental.)
diff --git a/2011/lex/lex1.oldgo b/2011/lex/lex1.oldgo
new file mode 100644
index 0000000..0a1b1d4
--- /dev/null
+++ b/2011/lex/lex1.oldgo
@@ -0,0 +1,386 @@
+// Copyright 2011 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// reformatted, slightly edited version of lex.go from weekly.11-06-23
+
+package template
+
+import (
+ "fmt"
+ "strings"
+ "unicode"
+ "utf8"
+)
+
+// item represents a token returned from the scanner.
+type item struct {
+ typ itemType // Type, such as itemNumber.
+ val string // Value, such as "23.2".
+}
+
+func (i item) String() string {
+ switch i.typ {
+ case itemEOF:
+ return "EOF"
+ case itemError:
+ return i.val
+ }
+ if len(i.val) > 10 {
+ return fmt.Sprintf("%.10q...", i.val)
+ }
+ return fmt.Sprintf("%q", i.val)
+}
+
+// itemType identifies the type of lex items.
+type itemType int
+
+const (
+ itemError itemType = iota // error occurred;
+ // value is text of error
+ itemDot // the cursor, spelled '.'
+ itemEOF
+ itemElse // else keyword
+ itemEnd // end keyword
+ itemField // identifier, starting with '.'
+ itemIdentifier // identifier
+ itemIf // if keyword
+ itemLeftMeta // left meta-string
+ itemNumber // number
+ itemPipe // pipe symbol
+ itemRange // range keyword
+ itemRawString // raw quoted string (includes quotes)
+ itemRightMeta // right meta-string
+ itemString // quoted string (includes quotes)
+ itemText // plain text
+)
+
+// Make the types prettyprint.
+var itemName = map[itemType]string{
+ itemError: "error",
+ itemDot: ".",
+ itemEOF: "EOF",
+ itemElse: "else",
+ itemEnd: "end",
+ itemField: "field",
+ itemIdentifier: "identifier",
+ itemIf: "if",
+ itemLeftMeta: "left meta",
+ itemNumber: "number",
+ itemPipe: "pipe",
+ itemRange: "range",
+ itemRawString: "raw string",
+ itemRightMeta: "rightMeta",
+ itemString: "string",
+ itemText: "text",
+}
+
+func (i itemType) String() string {
+ s := itemName[i]
+ if s == "" {
+ return fmt.Sprintf("item%d", int(i))
+ }
+ return s
+}
+
+var key = map[string]itemType{
+ ".": itemDot,
+ "else": itemElse,
+ "end": itemEnd,
+ "if": itemIf,
+ "range": itemRange,
+}
+
+const eof = -1
+
+// stateFn represents the state of the scanner
+// as a function that returns the next state.
+type stateFn func(*lexer) stateFn
+
+// lexer holds the state of the scanner.
+type lexer struct {
+ name string // used only for error reports.
+ input string // the string being scanned.
+ start int // start position of this item.
+ pos int // current position in the input.
+ width int // width of last rune read from input.
+ items chan item // channel of scanned items.
+}
+
+// next returns the next rune in the input.
+func (l *lexer) next() (rune int) {
+ if l.pos >= len(l.input) {
+ l.width = 0
+ return eof
+ }
+ rune, l.width =
+ utf8.DecodeRuneInString(l.input[l.pos:])
+ l.pos += l.width
+ return rune
+}
+
+// peek returns but does not consume
+// the next rune in the input.
+func (l *lexer) peek() int {
+ rune := l.next()
+ l.backup()
+ return rune
+}
+
+// backup steps back one rune.
+// Can be called only once per call of next.
+func (l *lexer) backup() {
+ l.pos -= l.width
+}
+
+// emit passes an item back to the client.
+func (l *lexer) emit(t itemType) {
+ l.items <- item{t, l.input[l.start:l.pos]}
+ l.start = l.pos
+}
+
+// ignore skips over the pending input before this point.
+func (l *lexer) ignore() {
+ l.start = l.pos
+}
+
+// accept consumes the next rune
+// if it's from the valid set.
+func (l *lexer) accept(valid string) bool {
+ if strings.IndexRune(valid, l.next()) >= 0 {
+ return true
+ }
+ l.backup()
+ return false
+}
+
+// acceptRun consumes a run of runes from the valid set.
+func (l *lexer) acceptRun(valid string) {
+ for strings.IndexRune(valid, l.next()) >= 0 {
+ }
+ l.backup()
+}
+
+// lineNumber reports which line we're on. Doing it this way
+// means we don't have to worry about peek double counting.
+func (l *lexer) lineNumber() int {
+ return 1 + strings.Count(l.input[:l.pos], "\n")
+}
+
+// error returns an error token and terminates the scan
+// by passing back a nil pointer that will be the next
+// state, terminating l.run.
+func (l *lexer) errorf(format string, args ...interface{})
+ stateFn {
+ l.items <- item{
+ itemError,
+ fmt.Sprintf(format, args...),
+ }
+ return nil
+}
+
+// run lexes the input by executing state functions until
+// the state is nil.
+func (l *lexer) run() {
+ for state := lexText; state != nil; {
+ state = state(l)
+ }
+ close(l.items) // No more tokens will be delivered.
+}
+
+// lex launches a new scanner and returns the channel of items.
+func lex(name, input string) (*lexer, chan item) {
+ l := &lexer{
+ name: name,
+ input: input,
+ items: make(chan item),
+ }
+ go l.run() // Concurrently run state machine.
+ return l, l.items
+}
+
+// state functions
+
+const leftMeta = "{{"
+const rightMeta = "}}"
+
+// lexText scans until a metacharacter
+func lexText(l *lexer) stateFn {
+ for {
+ if strings.HasPrefix(l.input[l.pos:], leftMeta) {
+ if l.pos > l.start {
+ l.emit(itemText)
+ }
+ return lexLeftMeta // Next state.
+ }
+ if l.next() == eof { break }
+ }
+ // Correctly reached EOF.
+ if l.pos > l.start {
+ l.emit(itemText)
+ }
+ l.emit(itemEOF) // Useful to make EOF a token.
+ return nil // Stop the run loop.
+}
+
+// leftMeta scans the left "metacharacter", which is known to be present.
+func lexLeftMeta(l *lexer) stateFn {
+ l.pos += len(leftMeta)
+ l.emit(itemLeftMeta)
+ return lexInsideAction // Now inside {{ }}.
+}
+
+// rightMeta scans the right "metacharacter", which is known to be present.
+func lexRightMeta(l *lexer) stateFn {
+ l.pos += len(rightMeta)
+ l.emit(itemRightMeta)
+ return lexText
+}
+
+// lexInsideAction scans the elements inside "metacharacters".
+func lexInsideAction(l *lexer) stateFn {
+ // Either number, quoted string, or identifier.
+ // Spaces separate and are ignored.
+ // Pipe symbols separate and are emitted.
+ for {
+ if strings.HasPrefix(l.input[l.pos:], rightMeta) {
+ return lexRightMeta
+ }
+ switch r := l.next(); {
+ case r == eof || r == '\n':
+ return l.errorf("unclosed action")
+ case isSpace(r):
+ l.ignore()
+ case r == '|':
+ l.emit(itemPipe)
+ case r == '"':
+ return lexQuote
+ case r == '`':
+ return lexRawQuote
+ case r == '.':
+ // special look-ahead for ".field" so we don't break l.backup().
+ if l.pos < len(l.input) {
+ r := l.input[l.pos]
+ if r < '0' || '9' < r {
+ return lexIdentifier // itemDot comes from the keyword table.
+ }
+ }
+ fallthrough // '.' can start a number.
+ case r == '+' || r == '-' || '0' <= r && r <= '9':
+ l.backup()
+ return lexNumber
+ case isAlphaNumeric(r):
+ l.backup()
+ return lexIdentifier
+ default:
+ return l.errorf("unrecognized character in action: %#U", r)
+ }
+ }
+ return nil
+}
+
+// lexIdentifier scans an alphanumeric or field.
+func lexIdentifier(l *lexer) stateFn {
+Loop:
+ for {
+ switch r := l.next(); {
+ case isAlphaNumeric(r):
+ // absorb
+ default:
+ l.backup()
+ word := l.input[l.start:l.pos]
+ switch {
+ case key[word] != itemError:
+ l.emit(key[word])
+ case word[0] == '.':
+ l.emit(itemField)
+ default:
+ l.emit(itemIdentifier)
+ }
+ break Loop
+ }
+ }
+ return lexInsideAction
+}
+
+// lexNumber scans a number: decimal, octal, hex, float, or imaginary. This
+// isn't a perfect number scanner - for instance it accepts "." and "0x0.2"
+// and "089" - but when it's wrong the input is invalid and the parser (via
+// strconv) will notice.
+// TODO: without expressions you can do imaginary but not complex.
+func lexNumber(l *lexer) stateFn {
+ // Optional leading sign.
+ l.accept("+-")
+ // Is it hex?
+ digits := "0123456789"
+ if l.accept("0") && l.accept("xX") {
+ digits = "0123456789abcdefABCDEF"
+ }
+ l.acceptRun(digits)
+ if l.accept(".") {
+ l.acceptRun(digits)
+ }
+ if l.accept("eE") {
+ l.accept("+-")
+ l.acceptRun("0123456789")
+ }
+ // Is it imaginary?
+ l.accept("i")
+ // Next thing mustn't be alphanumeric.
+ if isAlphaNumeric(l.peek()) {
+ l.next()
+ return l.errorf("bad number syntax: %q",
+ l.input[l.start:l.pos])
+ }
+ l.emit(itemNumber)
+ return lexInsideAction
+}
+
+// lexQuote scans a quoted string.
+func lexQuote(l *lexer) stateFn {
+Loop:
+ for {
+ switch l.next() {
+ case '\\':
+ if r := l.next(); r != eof && r != '\n' {
+ break
+ }
+ fallthrough
+ case eof, '\n':
+ return l.errorf("unterminated quoted string")
+ case '"':
+ break Loop
+ }
+ }
+ l.emit(itemString)
+ return lexInsideAction
+}
+
+// lexRawQuote scans a raw quoted string.
+func lexRawQuote(l *lexer) stateFn {
+Loop:
+ for {
+ switch l.next() {
+ case eof, '\n':
+ return l.errorf("unterminated raw quoted string")
+ case '`':
+ break Loop
+ }
+ }
+ l.emit(itemRawString)
+ return lexInsideAction
+}
+
+// isSpace reports whether r is a space character.
+func isSpace(r int) bool {
+ switch r {
+ case ' ', '\t', '\n', '\r':
+ return true
+ }
+ return false
+}
+
+// isAlphaNumeric reports whether r is an alphabetic, digit, or underscore.
+func isAlphaNumeric(r int) bool {
+ return r == '_' || unicode.IsLetter(r) || unicode.IsDigit(r)
+}
diff --git a/2011/lex/r59-lex.go b/2011/lex/r59-lex.go
new file mode 100644
index 0000000..16ac257
--- /dev/null
+++ b/2011/lex/r59-lex.go
@@ -0,0 +1,431 @@
+// Copyright 2011 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package template
+
+import (
+ "fmt"
+ "strings"
+ "unicode"
+ "utf8"
+)
+
+// item represents a token or text string returned from the scanner.
+type item struct {
+ typ itemType
+ val string
+}
+
+func (i item) String() string {
+ switch {
+ case i.typ == itemEOF:
+ return "EOF"
+ case i.typ == itemError:
+ return i.val
+ case i.typ > itemKeyword:
+ return fmt.Sprintf("<%s>", i.val)
+ case len(i.val) > 10:
+ return fmt.Sprintf("%.10q...", i.val)
+ }
+ return fmt.Sprintf("%q", i.val)
+}
+
+// itemType identifies the type of lex items.
+type itemType int
+
+const (
+ itemError itemType = iota // error occurred; value is text of error
+ itemBool // boolean constant
+ itemComplex // complex constant (1+2i); imaginary is just a number
+ itemEOF
+ itemField // alphanumeric identifier, starting with '.', possibly chained ('.x.y')
+ itemIdentifier // alphanumeric identifier
+ itemLeftDelim // left action delimiter
+ itemNumber // simple number, including imaginary
+ itemPipe // pipe symbol
+ itemRawString // raw quoted string (includes quotes)
+ itemRightDelim // right action delimiter
+ itemString // quoted string (includes quotes)
+ itemText // plain text
+ // Keywords appear after all the rest.
+ itemKeyword // used only to delimit the keywords
+ itemDot // the cursor, spelled '.'.
+ itemDefine // define keyword
+ itemElse // else keyword
+ itemEnd // end keyword
+ itemIf // if keyword
+ itemRange // range keyword
+ itemTemplate // template keyword
+ itemWith // with keyword
+)
+
+// Make the types prettyprint.
+var itemName = map[itemType]string{
+ itemError: "error",
+ itemBool: "bool",
+ itemComplex: "complex",
+ itemEOF: "EOF",
+ itemField: "field",
+ itemIdentifier: "identifier",
+ itemLeftDelim: "left delim",
+ itemNumber: "number",
+ itemPipe: "pipe",
+ itemRawString: "raw string",
+ itemRightDelim: "right delim",
+ itemString: "string",
+ // keywords
+ itemDot: ".",
+ itemDefine: "define",
+ itemElse: "else",
+ itemIf: "if",
+ itemEnd: "end",
+ itemRange: "range",
+ itemTemplate: "template",
+ itemWith: "with",
+}
+
+func (i itemType) String() string {
+ s := itemName[i]
+ if s == "" {
+ return fmt.Sprintf("item%d", int(i))
+ }
+ return s
+}
+
+var key = map[string]itemType{
+ ".": itemDot,
+ "define": itemDefine,
+ "else": itemElse,
+ "end": itemEnd,
+ "if": itemIf,
+ "range": itemRange,
+ "template": itemTemplate,
+ "with": itemWith,
+}
+
+const eof = -1
+
+// stateFn represents the state of the scanner as a function that returns the next state.
+type stateFn func(*lexer) stateFn
+
+// lexer holds the state of the scanner.
+type lexer struct {
+ name string // the name of the input; used only for error reports.
+ input string // the string being scanned.
+ state stateFn // the next lexing function to enter
+ pos int // current position in the input.
+ start int // start position of this item.
+ width int // width of last rune read from input.
+ items chan item // channel of scanned items.
+}
+
+// next returns the next rune in the input.
+func (l *lexer) next() (rune int) {
+ if l.pos >= len(l.input) {
+ l.width = 0
+ return eof
+ }
+ rune, l.width = utf8.DecodeRuneInString(l.input[l.pos:])
+ l.pos += l.width
+ return rune
+}
+
+// peek returns but does not consume the next rune in the input.
+func (l *lexer) peek() int {
+ rune := l.next()
+ l.backup()
+ return rune
+}
+
+// backup steps back one rune. Can only be called once per call of next.
+func (l *lexer) backup() {
+ l.pos -= l.width
+}
+
+// emit passes an item back to the client.
+func (l *lexer) emit(t itemType) {
+ l.items <- item{t, l.input[l.start:l.pos]}
+ l.start = l.pos
+}
+
+// ignore skips over the pending input before this point.
+func (l *lexer) ignore() {
+ l.start = l.pos
+}
+
+// accept consumes the next rune if it's from the valid set.
+func (l *lexer) accept(valid string) bool {
+ if strings.IndexRune(valid, l.next()) >= 0 {
+ return true
+ }
+ l.backup()
+ return false
+}
+
+// acceptRun consumes a run of runes from the valid set.
+func (l *lexer) acceptRun(valid string) {
+ for strings.IndexRune(valid, l.next()) >= 0 {
+ }
+ l.backup()
+}
+
+// lineNumber reports which line we're on. Doing it this way
+// means we don't have to worry about peek double counting.
+func (l *lexer) lineNumber() int {
+ return 1 + strings.Count(l.input[:l.pos], "\n")
+}
+
+// error returns an error token and terminates the scan by passing
+// back a nil pointer that will be the next state, terminating l.run.
+func (l *lexer) errorf(format string, args ...interface{}) stateFn {
+ l.items <- item{itemError, fmt.Sprintf(format, args...)}
+ return nil
+}
+
+// nextItem returns the next item from the input.
+func (l *lexer) nextItem() item {
+ for {
+ select {
+ case item := <-l.items:
+ return item
+ default:
+ l.state = l.state(l)
+ }
+ }
+ panic("not reached")
+}
+
+// lex creates a new scanner for the input string.
+func lex(name, input string) *lexer {
+ l := &lexer{
+ name: name,
+ input: input,
+ state: lexText,
+ items: make(chan item, 2), // Two items sufficient.
+ }
+ return l
+}
+
+// state functions
+
+const (
+ leftDelim = "{{"
+ rightDelim = "}}"
+ leftComment = "{{/*"
+ rightComment = "*/}}"
+)
+
+// lexText scans until an opening action delimiter, "{{".
+func lexText(l *lexer) stateFn {
+ for {
+ if strings.HasPrefix(l.input[l.pos:], leftDelim) {
+ if l.pos > l.start {
+ l.emit(itemText)
+ }
+ return lexLeftDelim
+ }
+ if l.next() == eof {
+ break
+ }
+ }
+ // Correctly reached EOF.
+ if l.pos > l.start {
+ l.emit(itemText)
+ }
+ l.emit(itemEOF)
+ return nil
+}
+
+// lexLeftDelim scans the left delimiter, which is known to be present.
+func lexLeftDelim(l *lexer) stateFn {
+ if strings.HasPrefix(l.input[l.pos:], leftComment) {
+ return lexComment
+ }
+ l.pos += len(leftDelim)
+ l.emit(itemLeftDelim)
+ return lexInsideAction
+}
+
+// lexComment scans a comment. The left comment marker is known to be present.
+func lexComment(l *lexer) stateFn {
+ i := strings.Index(l.input[l.pos:], rightComment)
+ if i < 0 {
+ return l.errorf("unclosed comment")
+ }
+ l.pos += i + len(rightComment)
+ l.ignore()
+ return lexText
+}
+
+// lexRightDelim scans the right delimiter, which is known to be present.
+func lexRightDelim(l *lexer) stateFn {
+ l.pos += len(rightDelim)
+ l.emit(itemRightDelim)
+ return lexText
+}
+
+// lexInsideAction scans the elements inside action delimiters.
+func lexInsideAction(l *lexer) stateFn {
+ // Either number, quoted string, or identifier.
+ // Spaces separate and are ignored.
+ // Pipe symbols separate and are emitted.
+ for {
+ if strings.HasPrefix(l.input[l.pos:], rightDelim) {
+ return lexRightDelim
+ }
+ switch r := l.next(); {
+ case r == eof || r == '\n':
+ return l.errorf("unclosed action")
+ case isSpace(r):
+ l.ignore()
+ case r == '|':
+ l.emit(itemPipe)
+ case r == '"':
+ return lexQuote
+ case r == '`':
+ return lexRawQuote
+ case r == '.':
+ // special look-ahead for ".field" so we don't break l.backup().
+ if l.pos < len(l.input) {
+ r := l.input[l.pos]
+ if r < '0' || '9' < r {
+ return lexIdentifier // itemDot comes from the keyword table.
+ }
+ }
+ fallthrough // '.' can start a number.
+ case r == '+' || r == '-' || ('0' <= r && r <= '9'):
+ l.backup()
+ return lexNumber
+ case isAlphaNumeric(r):
+ l.backup()
+ return lexIdentifier
+ default:
+ return l.errorf("unrecognized character in action: %#U", r)
+ }
+ }
+ return nil
+}
+
+// lexIdentifier scans an alphanumeric or field.
+func lexIdentifier(l *lexer) stateFn {
+Loop:
+ for {
+ switch r := l.next(); {
+ case isAlphaNumeric(r):
+ // absorb.
+ case r == '.' && l.input[l.start] == '.':
+ // field chaining; absorb into one token.
+ default:
+ l.backup()
+ word := l.input[l.start:l.pos]
+ switch {
+ case key[word] > itemKeyword:
+ l.emit(key[word])
+ case word[0] == '.':
+ l.emit(itemField)
+ case word == "true", word == "false":
+ l.emit(itemBool)
+ default:
+ l.emit(itemIdentifier)
+ }
+ break Loop
+ }
+ }
+ return lexInsideAction
+}
+
+// lexNumber scans a number: decimal, octal, hex, float, or imaginary. This
+// isn't a perfect number scanner - for instance it accepts "." and "0x0.2"
+// and "089" - but when it's wrong the input is invalid and the parser (via
+// strconv) will notice.
+func lexNumber(l *lexer) stateFn {
+ if !l.scanNumber() {
+ return l.errorf("bad number syntax: %q", l.input[l.start:l.pos])
+ }
+ if sign := l.peek(); sign == '+' || sign == '-' {
+ // Complex: 1+2i. No spaces, must end in 'i'.
+ if !l.scanNumber() || l.input[l.pos-1] != 'i' {
+ return l.errorf("bad number syntax: %q", l.input[l.start:l.pos])
+ }
+ l.emit(itemComplex)
+ } else {
+ l.emit(itemNumber)
+ }
+ return lexInsideAction
+}
+
+func (l *lexer) scanNumber() bool {
+ // Optional leading sign.
+ l.accept("+-")
+ // Is it hex?
+ digits := "0123456789"
+ if l.accept("0") && l.accept("xX") {
+ digits = "0123456789abcdefABCDEF"
+ }
+ l.acceptRun(digits)
+ if l.accept(".") {
+ l.acceptRun(digits)
+ }
+ if l.accept("eE") {
+ l.accept("+-")
+ l.acceptRun("0123456789")
+ }
+ // Is it imaginary?
+ l.accept("i")
+ // Next thing mustn't be alphanumeric.
+ if isAlphaNumeric(l.peek()) {
+ l.next()
+ return false
+ }
+ return true
+}
+
+// lexQuote scans a quoted string.
+func lexQuote(l *lexer) stateFn {
+Loop:
+ for {
+ switch l.next() {
+ case '\\':
+ if r := l.next(); r != eof && r != '\n' {
+ break
+ }
+ fallthrough
+ case eof, '\n':
+ return l.errorf("unterminated quoted string")
+ case '"':
+ break Loop
+ }
+ }
+ l.emit(itemString)
+ return lexInsideAction
+}
+
+// lexRawQuote scans a raw quoted string.
+func lexRawQuote(l *lexer) stateFn {
+Loop:
+ for {
+ switch l.next() {
+ case eof, '\n':
+ return l.errorf("unterminated raw quoted string")
+ case '`':
+ break Loop
+ }
+ }
+ l.emit(itemRawString)
+ return lexInsideAction
+}
+
+// isSpace reports whether r is a space character.
+func isSpace(r int) bool {
+ switch r {
+ case ' ', '\t', '\n', '\r':
+ return true
+ }
+ return false
+}
+
+// isAlphaNumeric reports whether r is an alphabetic, digit, or underscore.
+func isAlphaNumeric(r int) bool {
+ return r == '_' || unicode.IsLetter(r) || unicode.IsDigit(r)
+}
diff --git a/2011/lex/snippets b/2011/lex/snippets
new file mode 100644
index 0000000..c00822b
--- /dev/null
+++ b/2011/lex/snippets
@@ -0,0 +1,21 @@
+Evaluation: {{.Title}}
+Constants and functions: {{printf "%g: %#3X" 1.2+2i 123}}
+Control structures {{range $s.Text}} {{.}} {{end}}
+
+// One iteration:
+switch state {
+case state1:
+ state = action1()
+case state2:
+ state = action2()
+case state3:
+ state = action3()
+}
+
+// run lexes the input by executing state functions
+// until the state is nil.
+func run() {
+ for state := startState; state != nil; {
+ state = state(lexer)
+ }
+}
