parser.peg

{
// This is the parser for Quantum-Annealing Prolog.  It was written using the
// Pigeon parser generator's DSL (https://github.com/PuerkitoBio/pigeon) and is
// inspired by the Prolog grammar found at
// https://raw.githubusercontent.com/simonkrenger/ch.bfh.bti7064.w2013.PrologParser/master/doc/prolog-bnf-grammar.txt
// but with various bugs corrected, support for relational and arithmetic
// expressions added, and the whole grammar converted to a PEG.

package main

// An ASTNodeType indicates the type of AST node we're working with.
type ASTNodeType int

// Declare all of the AST node types we intend to use.
const (
        UnknownType            ASTNodeType = iota // Should never be used
        NumeralType                               // Non-negative integer (e.g., "123")
        AtomType                                  // Atom, with quotes stripped (e.g., "scott")
        VariableType                              // Variable (e.g., "Name")
        TermType                                  // Term (a numeral, atom, or variable)
        TermListType                              // List of terms
        ListTailType                              // Tail of a list (e.g., the "T" in "[H|T]").
        ListType                                  // List (e.g., "[a, b, c]" or "[x, y, z|More]")
        PrimaryExprType                           // Primary expression (e.g., "(2+3)")
        UnaryExprType                             // Unary expression (e.g., "-X")
        UnaryOpType                               // Unary operator (e.g., "-")
        MultiplicativeExprType                    // Multiplicative expression (e.g., "7 * 5")
        MultiplicativeOpType                      // Multiplicative operator (e.g., "*")
        AdditiveExprType                          // Additive expression (e.g., "7 - 5")
        AdditiveOpType                            // Additive operator (e.g., "+")
        RelationOpType                            // Relation operator (e.g., "=<")
        RelationType                              // Relation (e.g., "happy(X) = Y" or "N < 10")
        PredicateType                             // Predicate (e.g., "likes(john, mary)")
        StructureType                             // Structure (e.g., "likes(john, mary)")
        PredicateListType                         // List of predicates (e.g., "likes(john, X), likes(X, mary)")
        ClauseType                                // Clause (e.g., "likes(john, X) :- likes(mary, X).")
        ClauseListType                            // List of clauses (e.g., "likes(john, X) :- likes(mary, X). likes(mary, cheese).")
        QueryType                                 // Query (e.g., "?- likes(john, X).")
        ProgramType                               // A complete Prolog program
)

// An ASTNode defines a single node in an abstract syntax tree.
type ASTNode struct {
        Type     ASTNodeType // What this node represents
        Text     string      // Node's textural represntation
        Pos      position    // Node's position in the input file
        Value    interface{} // Node's value (int, string, etc.)
        Children []*ASTNode  // Child AST node(s), if any
}

// String outputs an AST node and all its children, mostly for debugging.
func (a *ASTNode) String() string {
        result := ""
        var showAll func(*ASTNode, int)
        showAll = func(n *ASTNode, depth int) {
                // Display this node.
                indent := strings.Repeat("  ", depth)
                result += fmt.Sprintf("%sType:  %s\n", indent, n.Type)
                result += fmt.Sprintf("%sValue: %#v\n", indent, n.Value)
                result += fmt.Sprintf("%sText:  %q\n", indent, n.Text)
                result += fmt.Sprintf("%sPos:   %d:%d\n", indent, n.Pos.line, n.Pos.col)

                // Recursively display all children.
                for i, child := range n.Children {
                        if i > 0 {
                                result += "\n"
                        }
                        showAll(child, depth+1)
                }
        }
        showAll(a, 0)
        return result
}

// ConstructList constructs a list-type AST node from a parent type, a parent
// value (which defaults to the node's textual representation), a head child,
// and tail children.  (Children may be nil.)  The idea is to produce a single
// list of children (e.g., [a, b, c]) rather than a degenerate tree (e.g., [a,
// [b, [c]]]), which is what straightforward construction would naturally
// produce.
func (c *current) ConstructList(t ASTNodeType, v, n, ns interface{}) *ASTNode {
        head, hasHead := n.(*ASTNode)
        tail, hasTail := ns.(*ASTNode)
        node := ASTNode{
                Type:  t,
                Text:  string(c.text),
                Value: v,
                Pos:   c.pos,
        }
        if v == nil {
                node.Value = node.Text
        }
        if !hasHead {
                return &node
        }
        node.Children = []*ASTNode{head}
        if !hasTail {
                return &node
        }
        node.Children = append(node.Children, tail.Children...)
        return &node
}

// PrepareRelation takes two expressions and an operator and returns an ASTNode
// representing that relation.
func (c *current) PrepareRelation(e1, o, e2 interface{}) *ASTNode {
        kids := []*ASTNode{
                e1.(*ASTNode),
                o.(*ASTNode),
                e2.(*ASTNode),
        }
        node := ASTNode{
                Type:     RelationType,
                Text:     string(c.text),
                Pos:      c.pos,
                Value:    kids[1].Text,
                Children: kids,
        }
        return &node
}

}

// For now, we define a Prolog program as a list of clauses followed by an
// optional query.
Program <- Skip cl:ClauseList Skip q:Query Skip '.' Skip EOF {
	// Append the query to the list of clauses.
	prog := c.ConstructList(ProgramType, nil, cl, nil)
	prog.Children = append(prog.Children, q.(*ASTNode))
	return prog, nil
} / Skip cl:ClauseList Skip EOF {
        return c.ConstructList(ProgramType, nil, cl, nil), nil
}

// Return an AST node of type QueryType.
Query <- "?-" Skip ps:PredicateList {
	// Acquire a list of all variables that appear in the query.
	vSet := make(map[string]Empty)
	for _, v := range ps.(*ASTNode).FindByType(VariableType) {
		vSet[v.Value.(string)] = Empty{}
	}
	vList := make([]string, 0, len(vSet))
	for v := range vSet {
		vList = append(vList, v)
	}

	// Insert a head predicate so we can process the query as if it were a
	// clause.
	pKids := make([]*ASTNode, 0, len(vList)+1)
	pKids = append(pKids, &ASTNode{
		Type:  AtomType,
		Value: "Query",
		Text:  "Query",
	})
	for _, v := range vList {
		vr := &ASTNode{
			Type:  VariableType,
			Value: v,
			Text:  v,
		}
		trm := &ASTNode{
			Type:     TermType,
			Value:    v,
			Text:     v,
			Children: []*ASTNode{vr},
		}
		pKids = append(pKids, trm)
	}
	hd := &ASTNode{
		Type:     PredicateType,
		Value:    "Query",
		Text:     "Query",
		Children: pKids,
	}
	name := fmt.Sprintf("Query/%d", len(vList))
	return c.ConstructList(QueryType, name, hd, ps), nil
}

// Return an AST node of type ClauseListType.
ClauseList <- cl:Clause Skip cls:ClauseList {
        return c.ConstructList(ClauseListType, nil, cl, cls), nil
} / cl:Clause {
        return c.ConstructList(ClauseListType, nil, cl, nil), nil
}

// Return an AST node of type ClauseType.
Clause <- p:Predicate Skip ":-" Skip ps:PredicateList Skip '.' {
        // Rule
	pn := p.(*ASTNode)
	name := fmt.Sprintf("%s/%d", pn.Children[0].Value.(string), len(pn.Children)-1)
        return c.ConstructList(ClauseType, name, p, ps), nil
} / p:Predicate Skip '.' {
        // Fact
	pn := p.(*ASTNode)
	name := fmt.Sprintf("%s/%d", pn.Children[0].Value.(string), len(pn.Children)-1)
        return c.ConstructList(ClauseType, name, p, nil), nil
}

// Return an AST node of type PredicateListType.
PredicateList <- p:Predicate Skip ',' Skip ps:PredicateList {
        return c.ConstructList(PredicateListType, nil, p, ps), nil
} / p:Predicate {
        return c.ConstructList(PredicateListType, nil, p, nil), nil
}

// Return an AST node of type PredicateType.
Predicate <- r:Relation {
        return c.ConstructList(PredicateType, nil, r, nil), nil
} / a:Atom Skip '(' Skip ts:TermList Skip ')' {
        return c.ConstructList(PredicateType, nil, a, ts), nil
} / a:Atom {
        return c.ConstructList(PredicateType, nil, a, nil), nil
}

// Return an AST node of type RelationType.
Relation <- (e1:AdditiveExpr Skip o:RelationOperator Skip e2:AdditiveExpr) {
        return c.PrepareRelation(e1, o, e2), nil
} / (e1:Term Skip o:EqualityOperator Skip e2:Term) {
        return c.PrepareRelation(e1, o, e2), nil
}

// A RelationOperator relates two numerical expressions.
RelationOperator <- ("=<" / ">=" / "<" / ">" / "=" / "\\=") {
        return c.ConstructList(RelationOpType, nil, nil, nil), nil
}

// An EqualityOperator relates two arbitrary expressions by equality or
// inequality.
EqualityOperator <- ("=" / "\\=" ) {
        return c.ConstructList(RelationOpType, nil, nil, nil), nil
}

// An AdditiveExpr adds two values.
AdditiveExpr <- e1:MultiplicativeExpr Skip o:AdditiveOperator Skip e2:AdditiveExpr {
        kids := []*ASTNode{
                e1.(*ASTNode),
                o.(*ASTNode),
                e2.(*ASTNode),
        }
        node := ASTNode{
                Type:     AdditiveExprType,
                Text:     string(c.text),
                Value:    kids[1].Value,
                Pos:      c.pos,
                Children: kids,
        }
        return &node, nil
} / e:MultiplicativeExpr {
        return c.ConstructList(AdditiveExprType, "", e, nil), nil
}

// An AdditiveOperator applies to two values.
AdditiveOperator <- ('+' / '-') {
        return c.ConstructList(AdditiveOpType, nil, nil, nil), nil
}

// A MultiplicativeExpr multiplies two values.
MultiplicativeExpr <- e1:UnaryExpr Skip o:MultiplicativeOperator Skip e2:MultiplicativeExpr {
        kids := []*ASTNode{
                e1.(*ASTNode),
                o.(*ASTNode),
                e2.(*ASTNode),
        }
        node := ASTNode{
                Type:     MultiplicativeExprType,
                Text:     string(c.text),
                Value:    kids[1].Value,
                Pos:      c.pos,
                Children: kids,
        }
        return &node, nil
} / e:UnaryExpr {
        return c.ConstructList(MultiplicativeExprType, "", e, nil), nil
}

// A MultiplicativeOperator applies to two values.
MultiplicativeOperator <- '*' {
        return c.ConstructList(MultiplicativeOpType, nil, nil, nil), nil
}

// A UnaryExpr transforms a single value.
UnaryExpr <- o:UnaryOperator Skip e:PrimaryExpr {
        kids := []*ASTNode{
                o.(*ASTNode),
                e.(*ASTNode),
        }
        node := ASTNode{
                Type:     UnaryExprType,
                Text:     string(c.text),
                Value:    kids[1].Value,
                Pos:      c.pos,
                Children: kids,
        }
        return &node, nil
} / e:PrimaryExpr {
        return c.ConstructList(UnaryExprType, "", e, nil), nil
}

// A UnaryOperator applies to a single value.
UnaryOperator <- '-' {
        return c.ConstructList(UnaryOpType, nil, nil, nil), nil
}

// A PrimaryExpr is the lowest-level expression, an atomic unit.
PrimaryExpr <- '(' Skip a:AdditiveExpr Skip ')' {
        return c.ConstructList(PrimaryExprType, "()", a, nil), nil
} / n:Numeral {
        return c.ConstructList(PrimaryExprType, "", n, nil), nil
} / v:Variable {
        return c.ConstructList(PrimaryExprType, "", v, nil), nil
}

// Return an AST node of type TermListType.
TermList <- t:Term Skip "," Skip ts:TermList {
        return c.ConstructList(TermListType, nil, t, ts), nil
} / t:Term {
        return c.ConstructList(TermListType, nil, t, nil), nil
}

// Return an AST node of type TermType.
Term <- child:(Numeral / Structure / Atom / Variable / List) {
        return c.ConstructList(TermType, nil, child, nil), nil
}

// A List can be either of bounded or unbounded extent (e.g., [1, 2, 3] vs. [1,
// 2, 3|Rest]).
List <- '[' Skip h:TermList Skip '|' Skip t:ListTail Skip ']' {
        // Unbounded extent
        return c.ConstructList(ListType, "[|]", h, t), nil
} / '[' Skip h:TermList Skip ']' {
        // Bounded extent
        return c.ConstructList(ListType, "[]", h, nil), nil
}

// A ListTail represents the "everything else" part of a list.
ListTail <- v:Variable {
        return c.ConstructList(ListTailType, nil, v, nil), nil
}

// Return an AST node of type StructureType.
Structure <- a:Atom Skip '(' Skip ts:TermList Skip ')' {
        return c.ConstructList(StructureType, nil, a, ts), nil
}

// Return an AST node of type VariableType.
Variable <- Uppercase_letter Symbol_trailer {
        return c.ConstructList(VariableType, nil, nil, nil), nil
}

// Return an AST node of type AtomType.
Atom <- Small_atom {
        return c.ConstructList(AtomType, nil, nil, nil), nil
} / Single_quoted_string {
        s := string(c.text)
        node := ASTNode{
                Type:  AtomType,
                Text:  s,
                Pos:   c.pos,
                Value: s[1 : len(s)-1],
        }
        return &node, nil
}

Single_quoted_string <- "'" Single_quoted_string_char* "'"

Single_quoted_string_char <- Character / '\\' .

Small_atom <- Lowercase_letter Symbol_trailer {
        return string(c.text), nil
}

Symbol_trailer <- (Lowercase_letter / Uppercase_letter / Digit)*

Character <- Lowercase_letter / Uppercase_letter / Digit / Not_single_quote

Lowercase_letter <- [\p{Ll}]

Uppercase_letter <- [\p{Lu}_]

Digit <- [\p{Nd}]

Whitespace <- [\p{Zs}\n\r\t]

One_line_comment <- '%' [^\n\r]* '\r'? '\n'

Multi_line_comment <- "/*" (Multi_line_comment / '*' !'/' / [^*])* "*/"

// Skip represents material to ignore, specifically whitespace and comments.
Skip <- (Whitespace / One_line_comment / Multi_line_comment)*

// Return an AST node of type NumeralType.
Numeral <- Digit+ {
        num, err := strconv.Atoi(string(c.text))
        if err != nil {
                return nil, err
        }
        node := ASTNode{
                Type:  NumeralType,
                Text:  string(c.text),
                Value: num,
                Pos:   c.pos,
        }
        return &node, nil
}

Not_single_quote <- [^']

EOF <- !.