2 Parsers and Combinators

9.3

2 Parsers and Combinators🔗

(require parser-combinator/parse)
	package: parser-combinator

procedure
(parse p str) → Value
p : Parser
str : string?

applies Parser p to str and produces the resulting Value. Unlike applying p directly, parse demands that p consume all of str. It raises exn:fail if p fails or leaves text over.

Examples:

> (parse (lit "hi") "hi")
"hi"
> (parse (lit "hi") "bye")
bad input, got error
> (parse (lit "hi") "high")
bad input, had leftover text "gh"

2.1 Data Definitions🔗

Value : any/c

A Value is whatever a Parser produces when it matches. The parsers in this library produce plain Racket values:

emp produces '()
lit, rx, and span produce the matched text, a string
seq and seq* produce whatever their constructor returns, given their parsers’ Values
alt and alt* produce the Value of the parser that matched
switch produces the Value of the parser it chose
opt produces its parser’s Value, or '() if its parser fails
star and plus produce the list of their parser’s Values
where produces its parser’s Value, when its condition is met
unwrap produces the Value of its middle parser

The constructors are where a grammar builds the data the program needs, such as a list, a number, or a structure of its own.

Result : (or/c 'error result?)

A Result is one of:

'error, meaning the parser did not match
(result value remaining), meaning the parser matched a prefix of its input, producing value, and left the string remaining unconsumed

Parser : (-> string? (or/c 'error result?))

A Parser is a function that consumes a string and produces a Result. A parser only ever matches a prefix of its input. It is up to parse to insist that a match covers the whole string.

Parsers are functions. A parser can be applied directly to a string:

Examples:

> ((lit "hi") "high")
(result "hi" "gh")
> ((lit "hi") "bye")
'error

The parsers made by this library pass positions in the input to one another rather than copying it, so applying a parser copies the input only once, for the remaining string of its Result. See Run Parsers to write parsers that work the same way.

struct
(struct result (value remaining)
    #:transparent)
  value : Value
  remaining : string?

represents a successful match, as produced by any Parser that matches. See Result.

2.2 Defining Parsers🔗

syntax
(define-parser id parser-expr)

defines id as a Parser that behaves like parser-expr.

Unlike define, define-parser does not evaluate parser-expr until id is first applied to a string. This lets a parser refer to itself. It can also refer to parsers that are defined later in the module. After that first application, id keeps the parser that parser-expr produced, so parser-expr is evaluated only once, rather than every time the parser runs.

Examples:

; Parser
; matches balanced parentheses, such as "(()())",
; producing a list for each pair
> (define-parser PARENS
(star (unwrap (lit "(") PARENS (lit ")"))))
> (parse PARENS "(()())")
'((() ()))
> (parse PARENS "(()")
bad input, had leftover text "(()"

2.3 Primitive Parsers🔗

procedure
(emp) → Parser

produces a Parser that always succeeds without consuming any input. The Value is '().

Note that emp is a function that produces a parser, not a parser itself, so it is used as (emp).

Example:

> ((emp) "abc")
(result '() "abc")

procedure
(lit str) → Parser
str : string?

produces a Parser that matches the text str at the start of its input. The Value is str.

Examples:

> ((lit "-") "-1.35")
(result "-" "1.35")
> ((lit "hi") "high")
(result "hi" "gh")
> ((lit "high") "hi")
'error
> ((lit "") "walrus")
(result "" "walrus")

procedure
(rx pattern) → Parser
pattern : regexp?

produces a Parser that matches pattern at the start of its input. A match later in the input does not count. The Value is the matched text. pattern may be a regexp or a pregexp, such as #rx"[^ab]" or #px"\\d+".

Examples:

> ((rx #rx"[^ab]") "cab")
(result "c" "ab")
> ((rx #rx"[^ab]") "bad")
'error
> ((rx #px"\\d+") "42x")
(result "42" "x")
> ((rx #rx"a|b") "xb")
'error

procedure
(span ok?) → Parser
ok? : (-> char? any/c)

produces a Parser that matches the longest run of one or more characters at the start of its input that ok? accepts. It fails if the first character isn’t accepted, or if there is no input left. The Value is the matched text.

Examples:

> ((span char-alphabetic?) "abc123")
(result "abc" "123")
> ((span char-numeric?) "abc")
'error

A span matches the same text as an rx for a character class, such as (rx #rx"[a-z]+"), but costs less when the runs are short. Matching a regexp against a string has a cost every time, even when it matches one character or none, and span only checks characters. Because it always takes the longest run, it can’t match a fixed number of characters, which takes an rx such as (rx #px"[0-9]{4}").

2.4 Combinators🔗

procedure
(seq build p1 p2) → Parser
  build : (-> Value Value Value)
  p1 : Parser
  p2 : Parser

produces a Parser that runs p1 and then runs p2 on the input that p1 left over. It fails if either parser does. The Value is (build left right), where left and right are the Values of p1 and p2. build must accept two arguments. If it does not, seq raises exn:fail:contract when it makes the parser.

Examples:

> ((seq list (lit "a") (lit "b")) "abc")
(result '("a" "b") "c")
> ((seq string-append (lit "a") (lit "b")) "abc")
(result "ab" "c")
> ((seq list (lit "a") (lit "b")) "acb")
'error

procedure
(seq* build p ...+) → Parser
build : procedure?
p : Parser

produces a Parser that runs each p in order, each on the input that the previous one left over. It fails if any p does. The Value is the result of calling build with the Values of the ps, one argument per parser, in order.

build must accept as many arguments as there are ps. If it does not, seq* raises exn:fail:contract when it makes the parser, before any input is parsed. A constructor can keep only some of the Values, which is useful for dropping delimiters. For the common case of keeping only the middle of three, see unwrap.

Examples:

> (parse (seq* list (lit "a") (lit "b") (lit "c"))
         "abc")
'("a" "b" "c")
> (parse (seq* (lambda (l x r) (string->symbol x))
               (lit "(") (rx #rx"[a-z]+") (lit ")"))
         "(abc)")
'abc
> (seq* (lambda (a b) a) (lit "a") (lit "b") (lit "c"))
seq*: contract violation
  expected: (procedure-arity-includes/c 3)
  given: #<procedure>

procedure
(alt p1 p2) → Parser
p1 : Parser
p2 : Parser

produces a Parser that tries p1 and, only if it fails, tries p2 on the same input.

Examples:

> ((alt (lit "a") (lit "b")) "bc")
(result "b" "c")
> ((alt (lit "a") (lit "b")) "c")
'error

The choice is ordered and final: once p1 matches, alt never goes back to try p2, even if the rest of the grammar then fails. When one alternative is a prefix of another, list the longer one first.

Examples:

> (parse (seq list (alt (lit "a") (lit "ab")) (lit "c"))
"abc")
bad input, got error
> (parse (seq list (alt (lit "ab") (lit "a")) (lit "c"))
"abc")
'("ab" "c")

procedure
(alt* p ...+) → Parser
p : Parser

produces a Parser that tries each p in order and behaves like the first one that matches. It is the same as nesting alt to the right, and with a single parser (alt* p) is the same as p.

Example:

> ((alt* (lit "x") (lit "y") (lit "z")) "zebra")
(result "z" "ebra")

syntax
(switch [(char ...) parser-expr] ...
maybe-else)

maybe-else =
| [else else-expr]

produces a Parser that looks at the next character of its input without consuming it, and runs only the parser of the clause that lists that character. If no clause lists it, or no input is left, it runs the else parser, or fails if there is none. Each char is a character, and each parser-expr and else-expr produces a Parser. They are evaluated once, when the switch form is, not every time the parser runs. The Value is the chosen parser’s.

Examples:

> (define SIGNED
(switch [(#\+ #\-) (rx #px"[+-]\\d+")]
[else (rx #px"\\d+")]))
> (SIGNED "-12")
(result "-12" "")
> (SIGNED "12")
(result "12" "")

Unlike alt, switch commits to the clause it chooses. If that parser fails, so does switch, without trying any other clause. It behaves like alt* when each alternative can only start with the characters listed for it, and then it costs one case on the next character, instead of trying each alternative in turn.

Examples:

> ((alt (lit "ab") (lit "ac")) "ac")
(result "ac" "")
> ((switch [(#\a) (lit "ab")] [else (lit "ac")]) "ac")
'error

procedure
(opt p) → Parser
p : Parser

produces a Parser that behaves like p if p matches, and otherwise succeeds without consuming input, producing '().

Examples:

> ((opt (lit "-")) "-5")
(result "-" "5")
> ((opt (lit "-")) "5")
(result '() "5")

procedure
(star p) → Parser
p : Parser

produces a Parser that matches p zero or more times, as many times as possible. The Value is the list of the Values of the matches, in order.

Examples:

> ((star (lit "a")) "aab")
(result '("a" "a") "b")
> ((star (lit "a")) "b")
(result '() "b")

Like alt, star never gives back a match, so (seq list (star (lit "a")) (lit "a")) matches nothing at all. It stops at the first match of p that consumes no input, leaving that match out, so a p that can match the empty string, such as (opt q), can’t make it repeat forever.

Example:

> ((star (opt (lit "a"))) "aab")
(result '("a" "a") "b")

procedure
(plus p) → Parser
p : Parser

produces a Parser that matches p one or more times. The Value is the list of the Values of the matches, as for star.

Examples:

> (parse (plus (lit "a")) "aa")
'("a" "a")
> (parse (plus (lit "a")) "")
bad input, got error

procedure
(where p ok?) → Parser
p : Parser
ok? : (-> Value any/c)

produces a Parser that matches what p matches, but only when ok? accepts its Value. Otherwise it fails, as if p had not matched. The Value is p’s.

Examples:

> (define NUMBER (seq* string->number (rx #px"\\d+")))
> (define BYTE (where NUMBER byte?))
> (parse BYTE "200")
200
> (parse BYTE "300")
bad input, got error

It is the way to restrict a match by its Value without writing a Parser as a plain function, which would be given a copy of the rest of the input every time it runs. Written as a plain function, where would be:

> (define (plain-where p ok?)
    (lambda (s)
      (let ([r (p s)])
        (if (and (result? r) (ok? (result-value r)))
            r
            'error))))

procedure
(unwrap left body right) → Parser
  left : Parser
  body : Parser
  right : Parser

produces a Parser that runs left, body, and right in order, and produces the Value of body. It is the same as (seq* (lambda (l b r) b) left body right), and is useful for skipping over text that the program does not care about, such as whitespace.

Examples:

> (define SPACES (star (lit " ")))
> (parse (unwrap SPACES (lit "x") SPACES) " x ")
"x"

2.5 Run Parsers🔗

(require (submod parser-combinator/parse positions))
	package: parser-combinator

The parsers made by parser-combinator/parse each hold a Run, which matches the input from a position, and call each other’s Runs rather than copying the input. This module provides those pieces, for a parser that can’t be built from the combinators, such as one whose grammar depends on what it has already matched.

A Parser written as a plain function also works with the combinators, but it is given a copy of the rest of the input every time it runs, so inside a loop like star it makes parsing quadratic. A parser written with this module doesn’t copy.

Match : (or/c 'error matched?)

A Match is one of:

'error, meaning the parser did not match
(matched value end), meaning the parser matched, producing value, and the match ended just before position end of the input

Run : (-> string? exact-nonnegative-integer? (or/c 'error matched?))

A Run matches its string starting at the given position, and produces a Match.

struct
(struct matched (value end)
    #:transparent)
  value : Value
  end : exact-nonnegative-integer?

represents a successful match, as produced by a Run that matches. See Match.

struct
(struct parser (run))
run : Run

is a Parser made from a Run. Applying it to a string calls its Run from position 0, and turns the Match into a Result, copying the rest of the input once, for its remaining. The combinators in parser-combinator/parse call its Run directly, with positions, so used inside a grammar it never copies.

Examples:

; Char-Predicate -> Parser
; matches one character that `ok?` accepts
> (define (char-where ok?)
    (parser
     (lambda (s i)
       (if (and (< i (string-length s))
                (ok? (string-ref s i)))
           (matched (string (string-ref s i)) (add1 i))
           'error))))
> (parse (plus (char-where char-alphabetic?)) "abc")
'("a" "b" "c")
> ((char-where char-numeric?) "7up")
(result "7" "up")

procedure
(run p str i) → (or/c 'error matched?)
  p : Parser
  str : string?
  i : exact-nonnegative-integer?

runs p on str from position i, producing a Match. If p is a parser, this calls its Run. Otherwise p is a plain function, and it is applied to a copy of str from i on. A Run uses run to run other parsers.

Examples:

; Parser -> Parser
; matches a digit n, then n of `p`, producing their list
> (define (counted p)
    (parser
     (lambda (s i)
       (let ([n (run (rx #rx"[0-9]") s i)])
         (if (symbol? n)
             'error
             (let loop ([k (string->number (matched-value n))]
                        [i (matched-end n)]
                        [vs '()])
               (if (zero? k)
                   (matched (reverse vs) i)
                   (let ([m (run p s i)])
                     (if (symbol? m)
                         'error
                         (loop (sub1 k)
                               (matched-end m)
                               (cons (matched-value m) vs)))))))))))
> (run (counted (lit "ab")) "x2ababab" 1)
(matched '("ab" "ab") 6)
> (parse (counted (lit "ab")) "3ababab")
'("ab" "ab" "ab")
> (parse (counted (lit "ab")) "2ababab")
bad input, had leftover text "ab"

contents ← prev up next →

2.1	Data Definitions
2.2	Defining Parsers
2.3	Primitive Parsers
2.4	Combinators
2.5	Run Parsers