---

Everything You Need to Know About SGF Parsing in C#

SGF Parsing in C# involves creating a parser to read a Smart Game Format string and convert it into a hierarchical tree data structure. This process requires handling nested nodes, property lists with key-value pairs, and special character escaping to accurately represent the game data in memory.

Ever stared at a block of nested text, like a JSON file or a complex log, and felt a wave of dread? You know the data you need is in there, but extracting it feels like untangling a knotted fishing line in the dark. This is a common pain point for developers dealing with custom text-based formats, and the Smart Game Format (SGF) is a classic example.

SGF is the standard for storing board game records, especially for the game of Go. Its deceptively simple-looking structure of parentheses and brackets hides a powerful, recursive tree. Your mission, should you choose to accept it, is to build a robust C# parser that can transform this string representation into a clean, navigable object model. This guide will take you from zero to hero, turning that tangled mess into an elegant data structure you can actually work with.

---

What is the Smart Game Format (SGF)?

The Smart Game Format (SGF) is a file format designed to store records of board games. While it's most famously associated with Go (also known as Baduk or Weiqi), its flexible design allows it to be used for many other games like Chess, Reversi, and even some abstract puzzles.

At its core, SGF is a tree-based format. A single SGF file represents a "game tree," which starts from a root node. This root node contains properties that set up the game, such as board size (SZ), game type (GM), and player information (PB for Player Black, PW for Player White).

From the root, the tree branches out. Each subsequent node typically represents a move in the game. What makes SGF powerful is its ability to store variations. For example, after a specific move, a game could have proceeded in several different ways. SGF captures this by allowing a node to have multiple children, each representing the start of a different variation or branch in the game's history.

The Core Components of SGF Syntax

Understanding the syntax is the first step to building a parser. The structure is composed of a few key elements:

• GameTree: The entire structure, enclosed in a single pair of parentheses (...).
• Node: Represented by a semicolon ;. Each node contains a list of properties.
• Property: A key-value pair. The key is an uppercase letter identifier (e.g., FF for File Format, C for Comment). The value(s) are enclosed in square brackets [...].
• Property Values: A property can have multiple values, each in its own set of brackets (e.g., AB[ab][bc][cd]). Values are text strings, and special characters like ] and \ must be escaped with a backslash \.
• Nesting: Variations are represented by nested GameTrees. A sequence of nodes can be followed by one or more parenthesized groups, each representing a new branch.

Here's a simple SGF example to illustrate:

(;FF[4]GM[1]SZ[19]
  ;B[aa]C[Black plays first]
  ;W[bb]
  ( ;B[cc]
    ;W[dd]
  )
  ( ;B[ee]
    ;W[ff]
  )
)

In this example, the root node sets up a 19x19 Go game. Black plays at `aa`, then White at `bb`. After White's move, there are two variations: one where Black plays `cc`, and another where Black plays `ee`.

---

Why is Parsing SGF a Unique Challenge?

Parsing SGF isn't like splitting a CSV or deserializing a standard JSON object. The challenge lies in its recursive, tree-like nature. A simple loop or a single regular expression won't be enough to handle the arbitrarily deep nesting of variations. This is a classic computer science problem that calls for a more sophisticated approach.

The primary difficulty is state management. As your parser reads the string, it needs to keep track of its current position within the tree. When it encounters an opening parenthesis `(`, it must descend into a new branch. When it sees a closing parenthesis `)`, it must ascend back to the parent branch. This "last-in, first-out" behavior is a perfect candidate for a stack data structure or, more elegantly, a recursive function call stack.

Furthermore, the parser must be robust. It needs to correctly handle property values, including escaped characters, and associate multiple values with a single property key. A naive implementation might fail on edge cases like empty values [] or values containing escaped brackets [a value with a \] here].

This challenge is a fantastic exercise from the kodikra.com C# learning path because it forces you to think about data structures (trees, dictionaries, lists) and algorithms (recursion, state machines) in a practical, real-world context.

---

How to Implement an SGF Parser in C#

We'll build a recursive descent parser. This approach mirrors the recursive structure of the SGF format itself, making the code intuitive and clean. The main idea is to have a function that parses a single sequence of nodes, and when it encounters a new GameTree (a `(`), it calls itself to parse that subtree.

Step 1: Define the Data Structure

First, we need a C# class to represent a node in the SGF tree. This class will hold the properties and a list of its children nodes.

// In SgfParsing.cs

using System.Collections.Generic;
using System.Linq;
using System.Text;

public class SgfNode
{
    // Properties are stored as a dictionary. The key is the property identifier (e.g., "B", "W", "C").
    // The value is a list of strings, as SGF properties can have multiple values.
    public IDictionary<string, List<string>> Properties { get; }

    // Each node can have multiple children, representing variations in the game.
    public List<SgfNode> Children { get; }

    public SgfNode(IDictionary<string, List<string>> properties = null, List<SgfNode> children = null)
    {
        Properties = properties ?? new Dictionary<string, List<string>>();
        Children = children ?? new List<SgfNode>();
    }

    // An equality override is useful for testing purposes.
    public override bool Equals(object obj)
    {
        if (obj is not SgfNode other)
        {
            return false;
        }

        var propertiesEqual = Properties.Count == other.Properties.Count &&
                              Properties.All(kvp => other.Properties.ContainsKey(kvp.Key) && 
                                                     kvp.Value.SequenceEqual(other.Properties[kvp.Key]));

        var childrenEqual = Children.Count == other.Children.Count &&
                            Children.SequenceEqual(other.Children);

        return propertiesEqual && childrenEqual;
    }

    public override int GetHashCode() => (Properties, Children).GetHashCode();
}

Step 2: The Parser Logic (Recursive Descent)

Now for the main parser class. We'll manage the input string with an index to keep track of our current position. This avoids creating substrings, which is more memory-efficient.

Here is the first ASCII diagram illustrating the high-level structure of an SGF string, which our parser will deconstruct.

    ● Start SGF String: "(;FF[4]...)"
    │
    ▼
  ┌───────────────────┐
  │ Parse GameTree ( )  │
  └─────────┬─────────┘
            │
            ▼
       ┌────────────┐
       │ Parse Node ; │
       └──────┬─────┘
              │
    ┌─────────┴─────────┐
    │                   │
    ▼                   ▼
┌──────────────┐   ┌───────────────┐
│ Parse Property │   │ Parse Property  │
│   (e.g., FF)   │   │   (e.g., SZ)    │
└──────┬───────┘   └────────┬────────┘
       │                    │
       ▼                    ▼
┌──────────────┐   ┌───────────────┐
│ Parse Value [4]│   │ Parse Value [19]│
└──────────────┘   └───────────────┘

The parser class will contain the core logic. Let's build it piece by piece.

public class SgfParser
{
    private int _index;
    private readonly string _input;

    public SgfParser() { }

    public SgfNode Parse(string input)
    {
        if (string.IsNullOrWhiteSpace(input) || !input.Trim().StartsWith("(") || !input.Trim().EndsWith(")"))
        {
            throw new ArgumentException("Invalid SGF: must be a single tree in parentheses.");
        }
        
        _input = input;
        _index = 0;
        
        // The SGF string itself represents a single GameTree.
        // We expect it to contain one or more nodes.
        var nodes = ParseGameTree();
        
        // The problem statement implies a single root node which may have children.
        // Our parsing results in a list of nodes at the top level of the tree.
        // Let's structure the final output as a single root with children.
        if (nodes.Count == 0)
        {
             throw new ArgumentException("Invalid SGF: tree cannot be empty.");
        }

        var root = nodes[0];
        for (int i = 1; i < nodes.Count; i++)
        {
            // In SGF, subsequent nodes in a sequence are children of the previous one.
            // This logic is a bit simplified. A more robust parser might handle this differently,
            // but for the kodikra module, we link them sequentially.
            // The main challenge is handling branches `(...)`, which our recursive structure does.
            var parent = nodes[i - 1];
            parent.Children.Add(nodes[i]);
        }
        
        return root;
    }
    
    // ... helper methods will go here ...
}

Step 3: Implementing the Helper Methods

The `Parse` method is just the entry point. The real work happens in helper methods that parse specific parts of the syntax.

Parsing a GameTree

A GameTree is a sequence of nodes and other GameTrees enclosed in parentheses.

    private List<SgfNode> ParseGameTree()
    {
        Consume('(');
        var nodes = new List<SgfNode>();
        
        while (_index < _input.Length && _input[_index] != ')')
        {
            SkipWhitespace();
            if (_input[_index] == ';')
            {
                nodes.Add(ParseNode());
            }
            else if (_input[_index] == '(')
            {
                // This is a variation. It belongs to the last node we parsed.
                if (nodes.Any())
                {
                    nodes.Last().Children.AddRange(ParseGameTree());
                }
                else
                {
                    // This case handles malformed SGF like `((;B[a]))`
                    // For our purposes, we can treat it as a nested tree to parse.
                    nodes.AddRange(ParseGameTree());
                }
            }
            else
            {
                // Unexpected character
                throw new ArgumentException($"Invalid character at index {_index}");
            }
            SkipWhitespace();
        }

        Consume(')');
        return nodes;
    }

Parsing a Node and its Properties

A node starts with a semicolon and is followed by properties.

    private SgfNode ParseNode()
    {
        Consume(';');
        SkipWhitespace();
        
        var properties = new Dictionary<string, List<string>>();
        
        while (_index < _input.Length && char.IsUpper(_input[_index]))
        {
            var key = ParsePropertyIdentifier();
            var values = ParsePropertyValues();
            
            if (properties.ContainsKey(key))
            {
                properties[key].AddRange(values);
            }
            else
            {
                properties[key] = values;
            }
            SkipWhitespace();
        }
        
        return new SgfNode(properties);
    }

Parsing Property Identifiers and Values

This is where we handle the low-level details: reading the uppercase keys and the bracketed, potentially-escaped values.

    private string ParsePropertyIdentifier()
    {
        var sb = new StringBuilder();
        while (_index < _input.Length && char.IsUpper(_input[_index]))
        {
            sb.Append(_input[_index++]);
        }
        return sb.ToString();
    }

    private List<string> ParsePropertyValues()
    {
        var values = new List<string>();
        while (_index < _input.Length && _input[_index] == '[')
        {
            values.Add(ParseSingleValue());
        }

        if (values.Count == 0)
        {
            throw new ArgumentException("Property must have at least one value.");
        }
        
        return values;
    }

    private string ParseSingleValue()
    {
        Consume('[');
        var sb = new StringBuilder();
        bool isEscaped = false;
        
        while (_index < _input.Length)
        {
            char c = _input[_index++];
            if (isEscaped)
            {
                // Handle escaped newlines - they might be represented as \r\n, \n, or \r
                // SGF spec says they should be converted to a single space, or removed if whitespace is not significant.
                // For simplicity here, we'll just append the character.
                sb.Append(c);
                isEscaped = false;
            }
            else if (c == '\\')
            {
                isEscaped = true;
            }
            else if (c == ']')
            {
                return sb.ToString();
            }
            else
            {
                sb.Append(c);
            }
        }
        
        throw new ArgumentException("Unclosed property value.");
    }

    // Utility methods
    private void Consume(char expected)
    {
        SkipWhitespace();
        if (_index >= _input.Length || _input[_index] != expected)
        {
            throw new ArgumentException($"Expected '{expected}' but found '{(_index < _input.Length ? _input[_index] : "EOF")}' at index {_index}.");
        }
        _index++;
    }

    private void SkipWhitespace()
    {
        while (_index < _input.Length && char.IsWhiteSpace(_input[_index]))
        {
            _index++;
        }
    }

This set of methods forms a complete recursive descent parser. The `ParseGameTree` method is the core of the recursion, correctly handling nested game variations by calling itself. The second ASCII diagram below visualizes this recursive logic.

    ● Call ParseGameTree()
    │
    ▼
  ┌─────────────┐
  │ Consume '('   │
  └──────┬──────┘
         │
         ▼
    ◆ While not ')'?
   ╱           ╲
  Yes           No ⟶ Return nodes
  │
  ▼
┌──────────────────┐
│ Peek next char   │
└────────┬─────────┘
         │
  ┌──────┴──────┐
  │             │
  ▼             ▼
◆ Is ';'?     ◆ Is '('?
  │ Yes         │ Yes
  ▼             ▼
┌──────────┐ ┌────────────────────┐
│ ParseNode()│ │ Recurse:           │
│ Add to list│ │ Call ParseGameTree() │
└──────────┘ └────────────────────┘
  │             │
  └──────┬──────┘
         │
         ▼
    Loop back

---

Where This Parser Fits: A Code Walkthrough

Let's trace the execution with a simple SGF string: (;B[aa](;W[bb])(;W[cc]))

1. `Parse("...")` is called: The `_index` is 0. It calls `ParseGameTree()`.
2. `ParseGameTree()` (Level 1):
   • It consumes the first `(`.
   • It enters the `while` loop. The character at the index is `;`, so it calls `ParseNode()`.
   • `ParseNode()`: Consumes `;`. It finds the property identifier `B` and calls `ParsePropertyValues()`. This reads `[aa]` and returns a dictionary `{"B": ["aa"]}`. A new `SgfNode` is created and added to the `nodes` list.
   • The loop continues. The next character is `(`. This is a variation.
   • It calls `ParseGameTree()` again (recursion!).
3. `ParseGameTree()` (Level 2, First Branch):
   • It consumes `(`.
   • It sees `;` and calls `ParseNode()` which parses `W[bb]`. A new node is created.
   • It reaches `)` and consumes it. It returns a list containing the `W[bb]` node.
4. Back in `ParseGameTree()` (Level 1):
   • The returned list with the `W[bb]` node is added to the `Children` of the `B[aa]` node.
   • The loop continues. The next character is again `(`. It calls `ParseGameTree()` for the second variation.
5. `ParseGameTree()` (Level 2, Second Branch):
   • This process repeats for the `(;W[cc])` part, creating another child node.
6. Back in `ParseGameTree()` (Level 1):
   • The `W[cc]` node is also added as a child to the `B[aa]` node.
   • The loop continues. The next character is the final `)`. The loop terminates.
   • The outer `)` is consumed. The method returns the list containing just the root `B[aa]` node (which now has two children).
7. Back in `Parse()`: The method receives the single root node and returns it, completing the parse.

This walkthrough demonstrates how the recursive calls naturally handle the nested structure, building the tree from the inside out as the call stack unwinds.

---

Alternative Approaches & Performance Considerations

While recursive descent is a great fit, it's not the only way. For production systems or more complex grammars, other techniques might be considered.

Approach	Pros	Cons
Recursive Descent (Our Method)	Intuitive and easy to read/debug. Mirrors the grammar of the format. No external dependencies.	Can lead to StackOverflowException on extremely deep nesting (though rare for SGF). Can be slower than iterative approaches due to function call overhead.
Iterative Parsing with a Stack	Avoids recursion depth limits. Potentially higher performance. Gives explicit control over the state.	Code is often more complex and harder to follow. Manually managing the stack can be error-prone.
Regular Expressions	Good for finding simple patterns. Quick for one-off extraction tasks.	Extremely brittle for nested/recursive structures. Regex for SGF would be a complex, unmaintainable nightmare. (Not Recommended)
Parser Combinator Library (e.g., Sprache)	Declarative: you define the grammar, the library builds the parser. Highly composable and expressive. Often results in very concise code.	Introduces an external dependency. Can have a steeper learning curve. May have performance overhead compared to a hand-rolled parser.

For the scope of this problem, our hand-rolled recursive descent parser provides the best balance of clarity, performance, and self-containment. It's a fundamental technique every developer should understand. For more complex parsing needs in your career, exploring parser combinators is a worthwhile investment. To dive deeper into advanced C# topics, check out the full Kodikra C# language guide.

---

Frequently Asked Questions (FAQ)

1. What happens if the input SGF string is malformed?

Our current implementation will throw an ArgumentException if it encounters unexpected syntax, such as an unclosed parenthesis, a missing bracket, or a property without a value. A production-grade parser might implement more granular error reporting, including line and column numbers, or even attempt to recover from minor errors.

2. How does the parser handle different character encodings?

The SGF specification allows for a CA property to define the character set (e.g., CA[UTF-8]). Our C# parser operates on a standard string, which is UTF-16 internally. As long as the input string is correctly decoded into a C# string when read from a file or stream (e.g., using File.ReadAllText(path, Encoding.UTF8)), the parser itself will handle the characters correctly.

3. Is this parser thread-safe?

The SgfParser class as written is not thread-safe because it uses instance fields (_index, _input) to maintain its state during a parse operation. You should create a new instance of SgfParser for each string you need to parse. If you wanted to make it thread-safe, you would need to refactor it to pass the state (input string and current index) as parameters to the parsing methods instead of storing them as instance fields.

4. How could I improve the performance for extremely large SGF files?

For very large files (hundreds of megabytes), the main bottlenecks would be memory allocation for the tree and string manipulations. Our current parser is already quite efficient by avoiding creating substrings. Further optimizations could include using a ReadOnlySpan<char> instead of a string to avoid allocations, or converting the recursive approach to an iterative one with a manual stack to prevent potential stack overflows on deeply nested game variations.

5. What is the difference between a node and a GameTree in SGF?

A Node (starts with ;) represents a single point in the game's history and contains properties describing the state or the move made. A GameTree (starts with () is a container for a sequence of nodes and other GameTrees. It represents a whole game or a variation branch within a game. Our parser reflects this by having the ParseGameTree method orchestrate the parsing of nodes and nested trees.

6. Can this parser write an SGF string back from the tree structure?

This implementation focuses only on parsing (reading). To add writing capabilities, you would need to implement a "serializer" or "writer" function. This would typically be a recursive method on the SgfNode class that traverses the tree and uses a StringBuilder to construct the SGF string, properly formatting properties, values, and nested parentheses for children.

---

Conclusion: From Text to Tree

You've successfully journeyed through the intricate world of SGF parsing in C#. We've deconstructed the SGF syntax, designed a clean data structure to represent it, and implemented a robust recursive descent parser to transform raw text into a meaningful, navigable game tree. This is more than just a solution to a single problem; it's a deep dive into fundamental parsing techniques that are applicable across countless domains, from compilers to data analysis tools.

By mastering this concept from the kodikra.com curriculum, you've added a powerful tool to your developer toolkit. You now have the skills to tackle complex, nested data formats with confidence, turning chaotic text into structured, elegant code.

Disclaimer: The C# solution provided is based on .NET 8 and C# 12 features. While the core logic is compatible with older versions, syntax like file-scoped namespaces or certain LINQ methods might require adjustments for different environments.

---

Published by Kodikra — Your trusted Csharp learning resource.