gll.go

package main

// Implementation of a GLL parser, from
//
// 	Elizabeth Scott and Adrian Johnstone. "GLL Parsing". LTDA 2009, pp 113-126
// 	http://ldta.info/2009/ldta2009proceedings.pdf
//
// ...with some modifications ;)

import (
	"fmt"
	"strings"
	"time"
)

const eof rune = -1

var debug = true

type label int

type stack struct {
	L        label
	k        int
	q        interface{}
	children []*stack
	pos      []int // popped j's
	retval   []interface{}
}

// S := A S d | B S | ε
// A := a | c
// B := a | b

func gll(I []rune) bool {
	type desc struct {
		L label
		u *stack
		i int
		q interface{}
		r interface{}
	}
	type ukey struct {
		L label
		u *stack
		i int
	}
	type gkey struct {
		L label
		k int
	}

	const (
		_ label = iota
		L_S
		L_0
		L_S1
		L_S2
		L_S3
		L_1
		L_2
		L_3
		L_4
		L_A
		L_B
		L_success
	)

	G := map[gkey]*stack{}
	newnode := func(L label, k int, q interface{}) *stack {
		v := G[gkey{L, k}]
		if v == nil {
			v = &stack{L: L, k: k, q: q}
			G[gkey{L, k}] = v
		}
		return v
	}

	u_0 := &stack{}
	u_1 := newnode(L_success, 0, nil)
	u_1.children = append(u_1.children, u_0)

	var R []desc // queue of "active" stack records
	U := map[ukey]bool{}

	// add a descriptor to R if we haven't done so yet
	add := func(L label, u *stack, j int, q, r interface{}) {
		if !U[ukey{L, u, j}] {
			U[ukey{L, u, j}] = true
			R = append(R, desc{L, u, j, q, r})
		}
	}

	// pop graph node u
	// and add j to its pos list
	// and activate every child stack frame of u
	// "return" from stack frame
	pop := func(u *stack, j int, r interface{}) {
		if u != u_0 {
			u.addpos(j, r)
			for _, v := range u.children {
				add(u.L, v, j, u.q, r)
			}
		}
	}

	// create graph node L,j as a parent of u
	// or reuse existing node, if one exists,
	// and activate stack frames for each pos in v
	// "enter" a stack frame
	create := func(L label, u *stack, j int, q interface{}) *stack {
		v := newnode(L, j, q)
		if !v.parentof(u) {
			v.children = append(v.children, u)
			for i := range v.pos {
				add(L, u, v.pos[i], v.q, v.retval[i])
			}
		}
		return v
	}

	L := L_S          // current state
	i := 0            // current input position
	c := u_1          // stack node of parent call
	var q interface{} // current value
	var r interface{} // return value from last call

	for {
		if debug {
			fmt.Printf("i=%v, L=%v, q=%v, r=%v, c=%v\n", i, L, q, r, c)
		}
		switch L {
		case L_0:
			if len(R) > 0 {
				// pop the last element of R
				x := R[len(R)-1]
				R = R[:len(R)-1]
				L = x.L
				c = x.u
				i = x.i
				q = x.q
				r = x.r
				//fmt.Println("popped", L, c, i)
				break
			} else {
				fmt.Printf("len(U) = %d\n", len(U))
				return U[ukey{L_success, u_0, len(I) - 1}]
			}
		case L_success:
			fmt.Println("q =", q)
			fmt.Println("r =", r)
			L = L_0

		case L_S:
			if I[i] == 'a' || I[i] == 'c' {
				add(L_S1, c, i, q, nil)
			}
			if I[i] == 'a' || I[i] == 'b' {
				add(L_S2, c, i, q, nil)
			}
			if I[i] == 'd' || I[i] == eof {
				add(L_S3, c, i, q, nil)
			}
			L = L_0
			break
		case L_S1:
			c = create(L_1, c, i, q)
			L = L_A
			break
		case L_1:
			q = r
			c = create(L_2, c, i, q)
			L = L_S
			break
		case L_2:
			if I[i] == 'd' {
				s := "S1(" + q.(string) + "," + r.(string) + ",d)"
				i++
				pop(c, i, s)
			}
			L = L_0
			break
		case L_S2:
			c = create(L_3, c, i, q)
			L = L_B
			break
		case L_3:
			//fmt.Println("L_3", c.L, q, r)
			q = r
			c = create(L_4, c, i, q)
			L = L_S
			break
		case L_4:
			//fmt.Println("L_4", c.L, q, r)
			s := "S2(" + q.(string) + "," + r.(string) + ")"
			pop(c, i, s)
			L = L_0
			break
		case L_S3:
			pop(c, i, "S3")
			L = L_0
			break
		case L_A:
			if I[i] == 'a' {
				i++
				pop(c, i, "A")
				L = L_0
				break
			} else {
				if I[i] == 'c' {
					i++
					pop(c, i, "A")
				}
				L = L_0
				break
			}
		case L_B:
			if I[i] == 'a' {
				i++
				pop(c, i, "B")
				L = L_0
				break
			} else {
				if I[i] == 'b' {
					i++
					pop(c, i, "B")
				}
				L = L_0
				break
			}
		}
	}
}

func (u *stack) parentof(v *stack) bool {
	for _, w := range u.children {
		if w == v {
			return true
		}
	}
	return false
}

func (s *stack) addpos(j int, q interface{}) {
	for _, k := range s.pos {
		if j == k {
			return
		}
	}
	s.pos = append(s.pos, j)
	s.retval = append(s.retval, q)
}

func (s *stack) String() string {
	return fmt.Sprintf("L%v,%v %v", s.L, s.k, s.children)
}

func test(s string, want bool) {
	I := append([]rune(s), eof)
	fmt.Println()
	got := gll(I)
	fmt.Printf("%q = %v\n", s, got)
	if want != got {
		fmt.Println("FAIL")
	}
}

func main() {
	test("", true)
	test("a", true)
	test("b", true)
	test("c", false)
	test("aad", true)
	test("abc", false)
	//test("bbbbbbbbb", true)

	if false {
		debug = false
		for _, n := range []int{1, 10, 100, 1000, 10000} {
			t := time.Now()
			I := append([]rune(strings.Repeat("a", n)), 'd', eof)
			got := gll(I)
			fmt.Printf("a^%d d = %v %v\n", n, got, time.Since(t))
		}

		for _, n := range []int{1, 10, 100, 1000, 10000} {
			t := time.Now()
			I := append([]rune(strings.Repeat("a", n)), 'c', eof)
			got := gll(I)
			fmt.Printf("a^%d c = %v %v\n", n, got, time.Since(t))
		}
	}

	//test(strings.Repeat("a", 20)+strings.Repeat("b", 150)+"a", true)
}