Understanding Parser Combinators

Parsing is the process of transforming unstructured input (such as raw text) into a structured format (such as a JavaScript object).

While many developers rely on Regular Expressions (regex) for text manipulation, regex becomes unmanageable as complexity grows. Conversely, industrial-strength tools like tree-sitter (which powers modern IDE syntax highlighting) are often overkill for smaller projects. Parser Combinators provide the ideal middle ground.

The Fundamental Unit: The Partial Parser

At its core, a partial parser is a simple function. Its job is to examine an input string, "cut" a piece off the front, and return both the parsed value and the remaining text.

Mathematically, we can define the type as: $\text{Parser}\langle T \rangle = \text{string} \rightarrow (T, \text{string})$

In code, it looks like this: type Parser<T> = (input: string) => [T, string];

Example: pInteger

Consider a parser that extracts a number:

const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error("Expected integer");
  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

Execution Trace: pInteger("10, 20 30") $\rightarrow$ [10, ", 20 30"]

---

Chaining Parsers

A single parser is limited, but we can chain them together by passing the "remainder" of the string from one parser into the next.

Manual Chaining Process

To parse the string "Hello 100", we might use these three parsers:

1. pHello: Matches "Hello" $\rightarrow$ returns ["Hello", " 100"]
2. pIgnoreWhitespace: Matches spaces $\rightarrow$ returns [null, "100"]
3. pInteger: Matches digits $\rightarrow$ returns [100, ""]

The step-by-step workflow:

• Run pHello on "Hello 100"
• Run pIgnoreWhitespace on the result of step 1
• Run pInteger on the result of step 2

Wrapping and Generalizing

Instead of manual chaining, we can wrap this sequence into a new parser, pHello100, which returns a tuple: [string, null, number].

To avoid writing this boilerplate repeatedly, we use pSeq. This is a higher-order function that takes multiple parsers and handles the "feeding" of the remaining string automatically.

---

Advanced Applications

Repetition and Lists

Parser combinators can handle repeating patterns. For example, parsing a list of numbers separated by semicolons (10;20;30;) involves repeatedly applying pSeq(pNumber, pSemicolon).

10;20;30; $\rightarrow$ [10, ;] $\rightarrow$ 20;30; $\rightarrow$ [20, ;] $\rightarrow$ 30; $\rightarrow$ [30, ;]

Real-World Example: Parsing ping Output

Imagine converting raw CLI output into a structured object:

Raw Input:

64 bytes from 1.1.1.1: icmp_seq=1 ttl=52 time=389 ms
64 bytes from 1.1.1.1: icmp_seq=2 ttl=52 time=68.7 ms
...
--- 1.1.1.1 ping statistics ---
8 packets transmitted, 7 received, 12.5% packet loss, time 7008ms
rtt min/avg/max/mdev = 47.129/115.880/388.750/112.515 ms

Structured Output:

{
  "header": {
    "targetIp": "1.1.1.1",
    "resolvedIp": "1.1.1.1",
    "icmpPayloadSize": 56,
    "totalPacketSize": 84
  },
  "packets": [
    { "byteCount": 64, "from": "1.1.1.1", "seq": 1, "ttl": 52, "time": 389 },
    { "byteCount": 64, "from": "1.1.1.1", "seq": 2, "ttl": 52, "time": 68.7 }
  ],
  "statistics": {
    "packetsTransmitted": 8,
    "packetsReceived": 7,
    "packetLoss": 12.5,
    "rtt": { "min": 47.129, "avg": 115.88, "max": 388.75, "mdev": 112.515 }
  }
}

Summary: Fold vs. Unfold

The relationship between raw text and structured data can be viewed as two opposite operations:

• Unfold (Parsing): "Hello 100" $\xrightarrow{pSeq}$ ["Hello", null, 100] (Expanding a string into a structured tuple/object)
• Fold (Reducing): ["Hello", null, 100] $\xrightarrow{reduce}$ "Hello 100" (Collapsing structured data back into a string)