Check-in [061baeefcb]
Overview
Comment: A simple parser combinator library Tarball | ZIP archive | SQL archive family | ancestors | descendants | both | files | file ages | folders 061baeefcb27371e64a70378d3deb69946a13db3 spaskalev on 2015-03-19 20:17:55 manifest | tags
Context
 2015-03-19 20:36 Added a string matching parser. check-in: 893c36d683 user: spaskalev tags: trunk 20:17 A simple parser combinator library check-in: 061baeefcb user: spaskalev tags: trunk 2015-01-26 23:02 full dep traversal in the collecting handler check-in: bca8ee3e12 user: spaskalev tags: trunk
Changes

1  +// Package parse provides a simple parser combinator library
2  +package parse
3  +
4  +// The N struct is a parser result node.
5  +type N struct {
6  +	// Match indicates whether the parser succeeded.
7  +	Matched bool
8  +	// Content contains whatever was matched by the parser.
9  +	Content string
10  +	// Nodes contains any result nodes by nested parsers.
11  +	Nodes []N
12  +}
13  +
14  +// Parser function type
15  +// Takes a string and returns a result and the remaining part of the string.
16  +type P func(string) (N, string)
17  +
18  +// A sequence of parsers. Matches when all of p match.
19  +func Seq(p ...P) P {
20  +	return func(s string) (N, string) {
21  +		result := N{Matched: true, Nodes: make([]N, 0, len(p))}
22  +		for _, parser := range p {
23  +			n, r := parser(s)
24  +			result.Nodes = append(result.Nodes, n)
25  +			if !n.Matched {
26  +				result.Matched = false
27  +				break
28  +			}
29  +			result.Content = result.Content + n.Content
30  +			s = r
31  +		}
32  +		return result, s
33  +	}
34  +}
35  +
36  +// Matches and returns on the first match of p.
37  +func Any(p ...P) P {
38  +	return func(s string) (N, string) {
39  +		result := N{Matched: false, Nodes: nil}
40  +		for _, parser := range p {
41  +			n, r := parser(s)
42  +			if n.Matched {
43  +				return n, r
44  +			}
45  +			result.Nodes, s = append(result.Nodes, n), r
46  +		}
47  +		return result, s
48  +	}
49  +}
50  +
51  +// Kleene star (zero or more). Always matches.
52  +func K(p P) P {
53  +	return func(s string) (N, string) {
54  +		result := N{Matched: true, Nodes: nil}
55  +		for n, r := p(s); n.Matched; n, r = p(r) {
56  +			result.Content = result.Content + n.Content
57  +			result.Nodes = append(result.Nodes, n)
58  +			s = r
59  +		}
60  +		return result, s
61  +	}
62  +}
63  +
64  +// Returns a delegating parser whose delegate can be set on later.
65  +// Useful for recursive definitions.
66  +func Defer() (P, *P) {
67  +	var deferred P
68  +	return func(s string) (N, string) {
69  +		return deferred(s)
70  +	}, &deferred
71  +}
72  +
73  +// Returns a parser that accepts the specified number of bytes
74  +func Accept(count int) P {
75  +	return func(s string) (N, string) {
76  +		if len(s) < count {
77  +			return N{Matched: false, Content: "", Nodes: nil}, s
78  +		}
79  +		return N{Matched: true, Content: s[:count], Nodes: nil}, s[count:]
80  +	}
81  +}

1  +package parse
2  +
3  +import (
4  +	"testing"
5  +)
6  +
7  +func TestAccept(t *testing.T) {
8  +	// Accept(0) will always match :)
9  +	p0 := Accept(0)
10  +	if r, s := p0(""); !r.Matched || r.Content != "" || r.Nodes != nil || s != "" {
11  +		t.Error("Invalid result for Accept's negative test", r)
12  +	}
13  +	// Test with a non-zero amount of bytes
14  +	p := Accept(1)
15  +	if r, s := p(""); r.Matched || r.Content != "" || r.Nodes != nil || s != "" {
16  +		t.Error("Invalid result for Accept's negative test", r)
17  +	}
18  +	if r, s := p("a"); !r.Matched || r.Content != "a" || r.Nodes != nil || s != "" {
19  +		t.Error("Invalid result for Accept's positive test", r)
20  +	}
21  +}
22  +
23  +func TestK(t *testing.T) {
24  +	p := Accept(1)
25  +	k := K(p)
26  +	if r, s := k("aaa"); !r.Matched || r.Content != "aaa" || r.Nodes == nil || s != "" {
27  +		t.Error("Invalid result for K* match test", r)
28  +	}
29  +	if r, s := k(""); !r.Matched || r.Content != "" || r.Nodes != nil || s != "" {
30  +		t.Error("Invalid result for K* no-match test", r)
31  +	}
32  +}
33  +
34  +func TestSeq(t *testing.T) {
35  +	p1, p2 := Accept(1), Accept(1)
36  +	s := Seq(p1, p2)
37  +	if r, s := s("aa"); !r.Matched || r.Content != "aa" || r.Nodes == nil || s != "" {
38  +		t.Error("Invalid result for Seq positive test", r)
39  +	}
40  +	if r, s := s("a"); r.Matched || r.Content != "a" || r.Nodes == nil || s != "" {
41  +		t.Error("Invalid result for Seq partial match test", r)
42  +	}
43  +	if r, s := s(""); r.Matched || r.Content != "" || r.Nodes == nil || s != "" {
44  +		t.Error("Invalid result for Seq no-match test", r)
45  +	}
46  +}
47  +
48  +func TestAny(t *testing.T) {
49  +	p, p0 := Accept(1), Accept(0)
50  +	a := Any(p, p0)
51  +	if r, s := a(""); !r.Matched || r.Content != "" || r.Nodes != nil || s != "" {
52  +		t.Error("Invalid result for Any match test", r)
53  +	}
54  +	if r, s := a("aa"); !r.Matched || r.Content != "a" || r.Nodes != nil || s != "a" {
55  +		t.Error("Invalid result for Any match test", r)
56  +	}
57  +}