/ 
Params-Validate-Strict-0.40
/ Params::Validate::Strict::BNF

NAME

Params::Validate::Strict::BNF - compile a BNF grammar to a string matcher

SYNOPSIS

use Params::Validate::Strict::BNF qw(bnf_to_matcher);

my $matcher = bnf_to_matcher([
    '<greeting> ::= "hello" | "hi"',
]);
$matcher->('hello');  # 1
$matcher->('bye');    # 0

DESCRIPTION

Converts an arrayref of BNF grammar lines into a closure that tests whether a string is a member of the language defined by that grammar.

Used internally by Params::Validate::Strict when a schema rule includes a bnf key. Results are cached by grammar content, so repeated calls with the same grammar pay no compilation cost after the first call.

GRAMMAR FORMAT

Each element of the arrayref is either a rule definition or a continuation line.

Rule definition

'<rule-name> ::= <alternatives>'

The left-hand side is a non-terminal name enclosed in angle brackets. The right-hand side is one or more alternatives separated by |.

Continuation lines

A line that contains no ::= is appended (with a space) to the preceding rule's right-hand side. This lets long rules span multiple array elements:

'<telephone-number> ::= <country-code-opt> <area-code> <separator-opt>',
'<central-office-code> <separator-opt> <station-code>',

Terminals

Literal text is enclosed in double quotes. An empty terminal "" matches the empty string (makes a production optional):

'<sep> ::= "" | "-" | " "'

Backslash escapes inside terminals (e.g. "\"") are passed through to the compiled regex via quotemeta, so no special treatment is needed for regex metacharacters.

Non-terminals

References to other rules are enclosed in angle brackets: <rule-name>. Recursive rules are not supported and will raise an exception.

Start rule

The first rule defined in the grammar is the start rule. A value must match the language generated by that rule (anchored ^...$) to be accepted.

FUNCTIONS

bnf_to_matcher( \@grammar_lines )

Purpose

Compiles a BNF grammar into a reusable string-membership predicate. Parses the grammar lines into production rules, builds a compiled regular expression, and returns a closure that tests whether a given string belongs to the language. Results are cached by grammar content so repeated calls with identical grammar lines pay the compilation cost only once.

Arguments

grammar_lines (required)

An arrayref of one or more BNF grammar lines. Each line is either a rule definition ('<name> ::= <rhs>') or a continuation line (no ::=, appended to the preceding rule with a space). Terminals are double-quoted; non-terminals use angle brackets; alternatives are separated by |.

Returns

A code reference sub ($str) - 0|1> that returns 1 if $str is defined and matches the start rule, 0 otherwise (including when $str is undef).

Side Effects

The compiled matcher is stored in a module-level cache keyed by grammar content and is never freed. Grammars are expected to be defined once at program start-up and reused across many calls.

Usage Example

use Params::Validate::Strict::BNF qw(bnf_to_matcher);

my $is_colour = bnf_to_matcher([
    '<colour> ::= "red" | "green" | "blue"',
]);

$is_colour->('red');    # 1
$is_colour->('purple'); # 0
$is_colour->(undef);    # 0

API SPECIFICATION

Input

grammar_lines => {
    type => 'arrayref',
    min  => 1,
}

Output

{ type => 'coderef' }

The returned coderef has the signature sub ($str) - 0|1>.

FORMAL SPECIFICATION

bnf_to_matcher : seq STRING -> (STRING U {undef}) -> B

Let G = <N, T, P, S> be the grammar derived from grammar_lines, where
  N  -- set of non-terminals (angle-bracket names)
  T  -- set of terminals  (double-quoted literals)
  P  -- set of productions in N x (N U T)*
  S  -- start symbol (first defined non-terminal)

L(G) = { w in T* | S =>* w }      (language generated by G)

bnf_to_matcher(lines) =def= lambda s.
    if s is undef then 0
    else if s in L(G) then 1
    else 0

Pre-conditions:
  lines /= empty
  for all n in N referenced in P: n is defined in P  (no dangling non-terminals)
  no cycle in the non-terminal reference graph         (no left recursion / loops)

Post-conditions:
  result is a coderef
  for all s: result(s) = 1  iff  s in L(G)
  result(undef) = 0

Raises an exception if:

  • the argument is not an arrayref

  • the grammar contains no rule definitions

  • a non-terminal reference is not defined elsewhere in the grammar

  • a recursive rule is detected

SEE ALSO

Params::Validate::Strict

AUTHOR

Nigel Horne <njh@nigelhorne.com>

LICENSE

Copyright 2026 Nigel Horne.

This program is released under the following licence: GPL2. If you use it, please let me know.