SGF Parsing
Parse a Smart Game Format game tree into nodes of properties and their child trees, with SGF’s escaping rules for text values.
Adapted from Exercism’s problem specification (MIT). Listed under Parsing & Validation.
// FILE: sgf_parsing.nomi
//# A parser for Smart Game Format (SGF) game trees whose values are all
//# SGF Text.
/// A node of the game tree: its properties, each key with one or more
/// values, and the trees that follow it.
pub struct Tree
properties: Map<String, List<String>>
children: List<Tree>
end
/// Why the text is not a game tree.
pub enum Error
TreeMissing
TreeWithNoNodes
PropertiesWithoutDelimiter
PropertyMustBeUppercase
/// Anything else the grammar does not allow: an unclosed tree or value,
/// or text after the tree.
Malformed
end
/// The game tree `encoded` writes.
pub fn parse(encoded: String) -> Result<Tree, Error>
['(', ..rest] = String.to_codepoints(encoded) else return Err(.TreeMissing)
(tree, rest) = node(rest)?
if rest != [] then return Err(.Malformed)
Ok(tree)
end
/// A node from its `;` on, with what follows it: another node is its one
/// child, and parenthesized trees are its children. The node that ends a
/// sequence reads the `)` that closes the sequence's tree.
fn node(text: List<Codepoint>) -> Result<(Tree, List<Codepoint>), Error>
[';', ..rest] = text else return Err(.TreeWithNoNodes)
(properties, rest) = read_properties(rest, {})?
(children, rest) = case rest
[';', ..] ->
(child, rest) = node(rest)?
([child], rest)
_ ->
variations(rest, [])?
end
Ok((Tree{properties:, children:}, rest))
end
/// The parenthesized trees after a node, up to and including the `)` that
/// closes the tree the node is in.
fn variations(
text: List<Codepoint>,
found: List<Tree>,
) -> Result<(List<Tree>, List<Codepoint>), Error>
case text
['(', ..rest] ->
(tree, rest) = node(rest)?
variations(rest, found + [tree])
[')', ..rest] ->
Ok((found, rest))
_ ->
Err(.Malformed)
end
end
/// A node's properties: each an upper-case key and one or more values.
fn read_properties(
text: List<Codepoint>,
found: Map<String, List<String>>,
) -> Result<(Map<String, List<String>>, List<Codepoint>), Error>
key =
text
|> Iter.take_while(Codepoint.is_letter)
|> Iter.to_list()
|> String.from_codepoints()
if key == "" then return Ok((found, text))
if not String.is_upper(key) then return Err(.PropertyMustBeUppercase)
rest = text |> Iter.drop_while(Codepoint.is_letter) |> Iter.to_list()
(values, rest) = read_values(rest, [])?
if values == [] then return Err(.PropertiesWithoutDelimiter)
read_properties(rest, Map.put(found, key, values))
end
/// The bracketed values after a key.
fn read_values(
text: List<Codepoint>,
found: List<String>,
) -> Result<(List<String>, List<Codepoint>), Error>
case text
['[', ..rest] ->
(value, rest) = read_text(rest, "")?
read_values(rest, found + [value])
_ ->
Ok((found, text))
end
end
/// One value's text, up to its closing `]`. A `\` keeps the character
/// after it, except that a newline after it is removed; any whitespace
/// other than a newline becomes a space.
fn read_text(text: List<Codepoint>, value: String) -> Result<(String, List<Codepoint>), Error>
case text
[']', ..rest] -> Ok((value, rest))
['\\', '\n', ..rest] -> read_text(rest, value)
['\\', c, ..rest] or [c, ..rest] -> read_text(rest, value + plain(c))
[] or ['\\'] -> Err(.Malformed)
end
end
fn plain(c: Codepoint) -> String
if c != '\n' and Codepoint.is_whitespace(c) then
" "
else
"${c}"
end
end
// FILE: sgf_parsing_test.nomi
import sgf_parsing.{self, Error, Tree}
test "parse"
cases: List<(String, String, Result<Tree, Error>)> = [
("empty input", "", Err(.TreeMissing)),
("tree with no nodes", "()", Err(.TreeWithNoNodes)),
("node without tree", ";", Err(.TreeMissing)),
("node without properties", "(;)", Ok({properties: {}, children: []})),
("single node tree", "(;A[B])", Ok({
properties: {"A" => ["B"]},
children: [],
})),
(
"multiple properties",
"(;A[b]C[d])",
Ok({
properties: {"A" => ["b"], "C" => ["d"]},
children: [],
}),
),
("properties without delimiter", "(;A)", Err(.PropertiesWithoutDelimiter)),
("all lowercase property", "(;a[b])", Err(.PropertyMustBeUppercase)),
("upper and lowercase property", "(;Aa[b])", Err(.PropertyMustBeUppercase)),
(
"two nodes",
"(;A[B];B[C])",
Ok({
properties: {"A" => ["B"]},
children: [
{
properties: {"B" => ["C"]},
children: [],
},
],
}),
),
(
"two child trees",
"(;A[B](;B[C])(;C[D]))",
Ok({
properties: {"A" => ["B"]},
children: [
{
properties: {"B" => ["C"]},
children: [],
},
{
properties: {"C" => ["D"]},
children: [],
},
],
}),
),
(
"multiple property values",
"(;A[b][c][d])",
Ok({
properties: {"A" => ["b", "c", "d"]},
children: [],
}),
),
(
"within property values, whitespace characters such as tab are converted to spaces",
"(;A[hello\t\tworld])",
Ok({
properties: {"A" => ["hello world"]},
children: [],
}),
),
(
"within property values, newlines remain as newlines",
"(;A[hello\n\nworld])",
Ok({
properties: {"A" => ["hello\n\nworld"]},
children: [],
}),
),
(
"escaped closing bracket within property value becomes just a closing bracket",
"(;A[\\]])",
Ok({
properties: {"A" => ["]"]},
children: [],
}),
),
(
"escaped backslash in property value becomes just a backslash",
"(;A[\\\\])",
Ok({
properties: {"A" => ["\\"]},
children: [],
}),
),
(
"opening bracket within property value doesn't need to be escaped",
"(;A[x[y\\]z][foo]B[bar];C[baz])",
Ok({
properties: {"A" => ["x[y]z", "foo"], "B" => ["bar"]},
children: [
{
properties: {"C" => ["baz"]},
children: [],
},
],
}),
),
(
"semicolon in property value doesn't need to be escaped",
"(;A[a;b][foo]B[bar];C[baz])",
Ok({
properties: {"A" => ["a;b", "foo"], "B" => ["bar"]},
children: [
{
properties: {"C" => ["baz"]},
children: [],
},
],
}),
),
(
"parentheses in property value don't need to be escaped",
"(;A[x(y)z][foo]B[bar];C[baz])",
Ok({
properties: {"A" => ["x(y)z", "foo"], "B" => ["bar"]},
children: [
{
properties: {"C" => ["baz"]},
children: [],
},
],
}),
),
(
"escaped tab in property value is converted to space",
"(;A[hello\\\tworld])",
Ok({
properties: {"A" => ["hello world"]},
children: [],
}),
),
(
"escaped newline in property value is converted to nothing at all",
"(;A[hello\\\nworld])",
Ok({
properties: {"A" => ["helloworld"]},
children: [],
}),
),
(
"escaped t and n in property value are just letters, not whitespace",
"(;A[\\t = t and \\n = n])",
Ok({
properties: {"A" => ["t = t and n = n"]},
children: [],
}),
),
(
"mixing various kinds of whitespace and escaped characters in property value",
"(;A[\\]b\nc\\\nd\t\te\\\\ \\\n\\]])",
Ok({
properties: {"A" => ["]b\ncd e\\ ]"]},
children: [],
}),
),
]
subtests cases, (description, encoded, expected), description
assert sgf_parsing.parse(encoded) == expected
end
end
// Not canonical cases: the canonical data has no case for text the grammar
// leaves unfinished or follows with more.
test "malformed trees"
[
("a tree with no closing parenthesis", "(;A[B]"),
("a value with no closing bracket", "(;A[B)"),
("a value ending in a backslash", "(;A[B\\"),
("text after the tree", "(;A[B])x"),
("a child tree with no closing parenthesis", "(;A[B](;B[C])"),
]
|> subtests (description, encoded), description
assert sgf_parsing.parse(encoded) == Err(.Malformed)
end
endok parse (23 cases)
ok malformed trees (5 cases)
test result: ok. 28 passed, 0 failed
How it’s written
Section titled “How it’s written”- The parser is recursive descent over
String.to_codepoints, one function per part of the grammar (node,variations,read_properties,read_values,read_text). Each answers what it read and the codepoints after it,Result<(T, List<Codepoint>), Error>, and?passes a failure up. The delimiters are codepoint literals in list patterns,[';', ..rest]and['\\', '\n', ..rest](style §20). - A
;after a node starts its one child, and(starts its variations. The node that ends a sequence reads the)that closes the sequence’s tree, so(;A[B];B[C])needs no count of open parentheses. - A property’s key is read as the run of letters, turned into a
Stringat once, and checked withString.is_upper. Treeis a struct of aMap<String, List<String>>and aList<Tree>, as the canonical data’s JSON is shaped, so the expected trees in the tests are literals of it.- SGF Text’s rules are three arms of
read_text: a\before a newline drops both, a\before anything else keeps that character, and any whitespace but a newline becomes a space. The escaped and unescaped character share one arm,['\\', c, ..rest] or [c, ..rest]. - The canonical errors are variants of
Error. Text the canonical data has no case for, an unclosed tree or value or text after the tree, is one more variant,Malformed; five tests marked as not canonical cover it. - The canonical cases are one
subteststable. The canonical data replaces “escaped property” with “mixing various kinds of whitespace and escaped characters in property value” (reimplements); the table holds only the replacement.