Skip to content
Tutorials Center
My learning

Topics

Lesson 93 of 132 Β· Standard Library Tour

Parsing Text: Hand-Written Parsers

Learn to parse text in Rust by hand: tokenizers with Peekable<Chars>, recursive-descent expression evaluators, FromStr, parser combinators, and when to use regex or nom.

Sooner or later every program has to make sense of text: a command typed by a user, a configuration line, a formula, a log record. The quick way is split, trim and parse. That is perfect for simple formats, and you should reach for it first. But when the text has nesting, precedence, quoting or real error reporting, string splitting becomes a tangle of special cases, and a proper parser is shorter, safer and easier to extend.

This lesson builds parsers in the order you would meet the need: first FromStr for small formats, then a tokenizer, then a recursive-descent parser that evaluates arithmetic with correct precedence, then parser combinators (small functions that snap together), and finally a wildcard matcher. At the end we look at the regex and nom crates, which are the right tools for many real jobs. Because our editor has only the standard library, those two are shown read-only.

The easy case: FromStr

The trait FromStr is Rust's standard "parse this text into me" interface. Implement it and your type works with str::parse::<T>(), exactly like i32 and f64 do. Its error type should say what went wrong; an enum is ideal.

Rust A FromStr implementation with good errors

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Key ideas: validate in an order that produces the most useful error, convert the text only after you know it is well-formed, and use collect::<Result<Vec<_>, _>>() to stop at the first failing item. See Display and From and custom error types for the error pieces.

Step one of a real parser: the tokenizer

A tokenizer (or lexer) turns a string of characters into a list of tokens: meaningful chunks such as numbers, operators and parentheses. Separating this step simplifies everything after it, because the parser no longer thinks about spaces or how many digits a number has.

We will parse arithmetic like 2 + 3 * (4 - 1). A token is an enum:

Rust Tokenizing with Peekable and Chars

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The pattern while let Some(&c) = chars.peek() is the heart of nearly every hand-written lexer: look at the next character, decide which kind of token starts here, and let a helper consume as many characters as that token needs. peek() returns Option<&char>, so we pattern-match &c to copy the character out, ending the borrow before we call next().

Recursive descent: grammar rules become functions

A grammar says how tokens may be combined. For arithmetic it is a ladder, from weakest-binding operators at the top to strongest at the bottom:

TEXT
expr   = term   { ("+" | "-") term }
term   = factor { ("*" | "/") factor }
factor = "-" factor | power
power  = atom [ "^" factor ]
atom   = NUMBER | "(" expr ")"

The ladder is how precedence works without any extra machinery. Because expr is made of terms, multiplication gets grouped before addition. Each rule becomes a function that calls the rule below it; the { ... } repetition becomes a while loop, which also makes + and - left associative (10 - 3 - 2 means (10 - 3) - 2). Exponent uses recursion on the right (power calls factor), making ^ right associative, as in mathematics: 2 ^ 3 ^ 2 is 2 ^ 9.

Rust A calculator with precedence and errors

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Study the outputs, because they reveal design decisions:

  • 2 + 3 * 4 is 14, not 20: the ladder makes * bind tighter.
  • 10 - 3 - 2 is 5: the while loop makes subtraction left associative.
  • 2 ^ 3 ^ 2 is 512: recursion on the right makes ^ right associative.
  • -2 ^ 2 is -4 here, because factor consumes the minus sign and then parses 2 ^ 2. Mathematicians and most languages agree on that; Excel does not. Grammar decisions like this are yours to make explicitly.
  • Every failure is a Result, and ? carries it up through the whole chain of function calls.

Mutual recursion is natural: atom calls expr for parenthesized parts, and expr eventually calls atom again. If you evaluate untrusted input, add a depth counter, or ((((((... thousands deep overflows the stack. For better error messages, store a position with each token. Instead of evaluating directly you can build a tree (enum Expr { Num(f64), Binary(Box<Expr>, Op, Box<Expr>) }) and evaluate or print that, which is how real compilers work; see Box and recursive types.

When you need many operators with many precedence levels, repeating one function per level gets long. The precedence climbing or Pratt parsing technique handles all levels with a single loop and a small table of binding powers. Learn recursive descent first; Pratt parsing is an optimization of the same idea.

Parser combinators: building parsers from small parts

A parser combinator is a function that builds a bigger parser out of smaller ones. We represent a parser as any function that takes the remaining input &str and returns Option<(value, rest)>: on success the value and the unconsumed rest, on failure None. Small parsers (satisfy, a single character) combine through functions such as many1, map and preceded. This is the style of the popular nom and winnow crates.

Rust Parser combinators from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

What to notice:

  • Every parser has the same shape, so they compose freely. That uniformity is the entire trick.
  • number() is written as a function that returns a parser (impl Fn), so each use builds a fresh one cheaply. Returning closures is covered in closures.
  • "7," parses as [7] with "," left over: many0 stops at the first failure and leaves the input untouched. The caller decides whether leftover input is acceptable, which is why a top-level parse should check that the remainder is empty.
  • Failure carries no message here. Real libraries return an error type with position and context, and an alt combinator to try alternatives in order.

Combinators shine when the format is large and regular. Their weakness is compile time and error-message quality when overused with many nested generics. Hand-written recursive descent is often easier to read and gives better messages, which is why many production compilers use it.

Another everyday tool: a wildcard matcher

Not every pattern needs a full parser. File globs like *.rs or data_??.csv follow two simple rules: ? matches any one character and * matches any run of characters, including none. A compact matcher walks both strings and remembers the last *:

Rust Wildcard matching with a star bookmark

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Working on Vec<char> instead of bytes keeps non-ASCII text correct (? matches the one character ΓΆ, not half of its UTF-8 bytes). The "remember the last star" trick makes the matcher run in time proportional to pattern length * text length in the worst case, never exponential, which matters when patterns come from users.

When to use regex or nom (read-only)

The regex crate implements regular expressions with a guarantee of linear-time matching (no catastrophic backtracking), full Unicode support and capture groups. It is the right choice for searching, validating and extracting from loosely structured text such as logs. It is not the right tool for nested structures (balanced brackets, HTML, JSON), which need a real parser.

TOML
# Cargo.toml (read-only: needs crates.io, not available in our editor)
[dependencies]
regex = "1"
Rust
// Read-only: requires the regex crate.
use regex::Regex;

fn main() {
    // Compile once and reuse; compiling is the expensive part.
    let log_line = Regex::new(r"^(?P<level>[A-Z]+) (?P<code>\d{3}) (?P<msg>.+)$").unwrap();

    if let Some(caps) = log_line.captures("WARN 404 page not found") {
        println!("{} / {} / {}", &caps["level"], &caps["code"], &caps["msg"]);
    }

    let digits = Regex::new(r"\d+").unwrap();
    let total: u32 = digits
        .find_iter("a1 b22 c333")
        .map(|m| m.as_str().parse::<u32>().unwrap())
        .sum();
    println!("{total}");
}

The nom and winnow crates provide production-grade parser combinators (our many0, preceded and map_opt are simplified versions of theirs), working on &str or raw bytes without allocating. For grammars you want to write declaratively, pest (grammar files) and lalrpop (LR parser generator) exist as well.

Rust
// Read-only: requires the nom crate (version 7 style).
use nom::{bytes::complete::tag, character::complete::digit1, sequence::preceded, IResult};

fn port(input: &str) -> IResult<&str, u16> {
    let (rest, digits) = preceded(tag(":"), digit1)(input)?;
    Ok((rest, digits.parse().unwrap_or(0)))
}

A decision guide:

Text looks like Use
key=value, comma lists, fixed layout split, split_once, parse
A small value type ("#ff8000", "3h20m") FromStr
Search or extract patterns in free text regex
Nested structure, operators, a language Recursive descent or combinators
JSON, TOML, YAML, CSV An existing crate (serde_json, toml, csv)

Practical advice

  • Return Result, never panic, on input you do not control. A parser is where you expect garbage.
  • Report positions (line, column or byte offset). "unexpected character" with no location is nearly useless.
  • Check for leftover input after the top-level parse.
  • Cap recursion depth and input size for untrusted text.
  • Work with char or bytes deliberately. Slicing a &str at a position that is not a character boundary panics, so use char_indices or len_utf8.
  • Test with bad input first. Edge cases are empty input, a lone operator, huge numbers, and unterminated groups; the next lessons on testing and test patterns show how to organize such tests.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. What does implementing FromStr for a type give you?

    FromStr provides from_str, and str::parse::<T>() calls it, so your type is parsed the same way as built-in numbers.
  2. 2. In the calculator grammar, why does 2 + 3 * 4 give 14?

    expr is made of terms, and term is made of factors. The multiplication is consumed inside term before expr sees the +.
  3. 3. What makes 10 - 3 - 2 evaluate as (10 - 3) - 2 in the parser?

    The loop in expr repeatedly applies the next operator to the value built so far, which gives left associativity. Recursion on the right would give right associativity, as used for ^.
  4. 4. A combinator-style parser has type Fn(&str) -> Option<(T, &str)>. What does the second part of the tuple hold?

    On success the parser returns the value and whatever input is left, so the next parser can continue from there.
  5. 5. When is the regex crate the wrong tool?

    Regular expressions cannot match arbitrarily nested structures. Use a recursive parser or a format-specific crate.

Summary

  • Use split, split_once and parse for simple formats, and implement FromStr with a descriptive error enum for small value types.
  • A tokenizer built on Peekable<Chars> turns text into tokens so the parser can ignore whitespace and digit-counting.
  • Recursive descent maps each grammar rule to a function; the ladder of rules creates precedence, loops create left associativity, and right recursion creates right associativity.
  • Parser combinators are functions from input to Option<(value, rest)> that compose into larger parsers; nom and winnow are the production versions.
  • Always return Result, report positions, reject trailing input and cap recursion depth for untrusted text.
  • Use regex for pattern search and extraction and existing crates for standard formats; both are read-only here.

Next: Testing in Rust