askeladdk/prattle

Scan and parse LL(1) grammars simply and efficiently.

Prattle

Overview

Package prattle implements a general purpose, unicode-aware lexical scanner and top down operator precedence parser suitable for parsing LL(1) grammars. The scanner and parser can be used independently from each other if desired.

Install

go get -u github.com/askeladdk/prattle

Quickstart

Use Scanner to produce a sequence of Tokens by scanning a source text using a ScanFunc. Use the Expect*, Skip and Advance methods to scan tokens.

// Prepare the scanner.
scanner := prattle.Scanner{
	// Scan scans the next token and returns its kind.
	Scan: func(s *prattle.Scanner) (kind int) {
		// Skip any whitespace.
		s.ExpectAny(unicode.IsSpace)
		s.Skip()

		// Scan the next token.
		switch {
		case s.Done(): // Stop when the entire input has been consumed.
			return 0
		case s.Expect('+'): // Scan the addition operator.
			return 1
		case s.ExpectOne(unicode.IsDigit): // Scan a number consisting of one or more digits.
			s.ExpectAny(unicode.IsDigit)
			return 2
		}

		// Invalid token.
		s.Advance()
		return -1
	},
}

Use Parser and Driver to associate tokens produced by Scanner with ParseFuncs. Define the Driver first.

// Define the parsing Driver.
type driver struct {
	stack []int
}

func (d *driver) push(i int) {
	d.stack = append(d.stack, i)
}

func (d *driver) pop() (i int) {
	n := len(d.stack)
	i, d.stack = d.stack[n-1], d.stack[:n-1]
	return
}

func (d *driver) number(p *prattle.Parser, t prattle.Token) error {
	n, _ := strconv.Atoi(t.Text)
	d.push(n)
	return nil
}

func (d *driver) add(p *prattle.Parser, t prattle.Token) error {
	// Parse the right hand operator.
	_ = p.Parse(d.Precedence(t.Kind))

	right := d.pop()
	left := d.pop()
	sum := left + right
	fmt.Printf("%d + %d = %d\n", left, right, sum)
	d.push(sum)
	return nil
}

func (d *driver) Prefix(kind int) prattle.ParseFunc {
	return d.number
}

func (d *driver) Infix(kind int) prattle.ParseFunc {
	return d.add
}

func (d *driver) Precedence(kind int) int {
	return kind
}

func (d *driver) ParseError(t prattle.Token) error {
	return fmt.Errorf("%s", t)
}

// Prepare the parser.
parser := prattle.Parser{
	Driver: &driver{},
}

Finally, Init the scanner and parser, and parse an expression.

source := "1 + 23 + 456 + 7890"
scanner.InitWithString(source)
parser.Init(&scanner).Parse(0)

// Output:
// 1 + 23 = 24
// 24 + 456 = 480
// 480 + 7890 = 8370

See the calculator for a complete example featuring prefix, postfix, infix, left, right and non-associative operators. Also read the documentation on pkg.go.dev.

License

Package prattle is released under the terms of the ISC license.