File Coverage

=head1 NAME

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

=head1 SYNOPSIS

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

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

=head1 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 L<Params::Validate::Strict> when a schema rule includes a
C<bnf> key.  Results are cached by grammar content, so repeated calls with
the same grammar pay no compilation cost after the first call.

=head1 GRAMMAR FORMAT

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

=head2 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 C<|>.

=head2 Continuation lines

A line that contains no C<::=> 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>',

=head2 Terminals

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

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

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

=head2 Non-terminals

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

=head2 Start rule

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

=head1 FUNCTIONS

=head2 bnf_to_matcher( \@grammar_lines )

=head3 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.

=head3 Arguments

=head4 grammar_lines (required)

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

=head3 Returns

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

=head3 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.

=head3 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

=head3 API SPECIFICATION

=head4 Input

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

=head4 Output

  { type => 'coderef' }

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

=head3 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:

=over 4

=item * the argument is not an arrayref

=item * the grammar contains no rule definitions

=item * a non-terminal reference is not defined elsewhere in the grammar

=item * a recursive rule is detected

=back

=cut