Formula Construction & the AST

Every example on this page is mirrored by a test in LogicalOptimizer.Tests/Documentation/DocExamplesTests.cs, so the outputs shown are the real, asserted values.

FormulaFactory — the canonical construction entry point

Since v2.0 FormulaFactory is the single canonical way to build And/Or trees and to parse text. It canonicalizes at construction time — flatten, sort, dedup, fold constants/complements, and intern — so equal formulas print identically and are the same instance. The public low-level AndNode/OrNode constructors remain available for building raw AST directly (used, for example, by tests), but they deliberately skip canonicalization and therefore do not guarantee those invariants; go through FormulaFactory whenever you rely on canonical form.

using LogicalOptimizer;

var f = new FormulaFactory();

// Parsing produces a canonical, n-ary AST.
Console.WriteLine(f.Parse("c & a & b"));   // a & b & c   (operands sorted)

// Degenerate formulas fold to a constant at parse time.
Console.WriteLine(f.Parse("a | !a"));      // 1

// Structurally equal factory trees are reference-equal (interning).
var parsed = f.Parse("c & a & b");
var built  = f.And(f.Variable("a"), f.Variable("b"), f.Variable("c"));
Console.WriteLine(ReferenceEquals(parsed, built));   // True
Console.WriteLine(((AndNode)parsed).Operands.Count); // 3  (n-ary, flattened)

The factory's building blocks: Parse, Variable, Not, And, Or, Xor, Implication, Equivalence, the constants True / False, and Import (which re-canonicalizes an externally built node, decomposing derived operators into And/Or/Not).

The n-ary AST

The canonical core is And / Or / Not / Variable / Constant. AndNode and OrNode are n-ary (NaryNode with IReadOnlyList<AstNode> Operands); one n-ary node counts as 1 node in the cost model regardless of operand count. The derived binary nodes XorNode / ImpNode / EqvNode / NandNode / NorNode live outside the canonical core and are used for extended-syntax parsing and pattern-recognition display.

Every AstNode exposes Clone(), GetVariables(), structural Equals/GetHashCode, and ToString() (which renders through AstFormatter).

AstFormatter — precedence-based rendering

A single renderer inserts parentheses exactly where precedence requires:

Console.WriteLine(AstFormatter.Format(f.Parse("!(a & b) | c")));  // c | !(a & b)

AstMetrics — structural size

var ast = f.Parse("a & (b | c)");
AstMetrics.CountNodes(ast);      // 5
AstMetrics.CountLiterals(ast);   // 3
AstMetrics.CountOperators(ast);  // 2
AstMetrics.GetDepth(ast);        // 3

TryParse — structured error handling

For untrusted input (an API body, a configuration UI, a build tool), TryParse avoids exceptions and returns a structured ParseDiagnostic instead — with the error position, offending length, expected tokens, a stable ParseErrorCode, and a caret snippet:

if (f.TryParse("a & b", out var formula, out _))
    Console.WriteLine(formula);            // a & b

if (!f.TryParse("a & & b", out _, out var diagnostic))
{
    Console.WriteLine(diagnostic!.Code);     // UnexpectedToken
    Console.WriteLine(diagnostic.Position);  // 4
    Console.WriteLine(diagnostic.Snippet);   // "a & & b" then a caret under the second '&'
}

Parse(string) still throws on invalid input — a FormulaParseException (a subclass of ArgumentException) carrying the same Diagnostic.

AstVisualizer — debugging trees

AstVisualizer.VisualizeTree(node) returns an indented tree dump and AstVisualizer.GetCompactVisualization(node) a one-line form — both useful for debugging and teaching.

Next steps

Edit this page