Steffen Mueller writes:
=> [...]
=> CH-1: context-sensitive grammars (all productions are context sensitive:
=> uAv -> urv, where u and v are 1 or more terminals, A one or more
=> non-terminals, and r any combination of terminals and non-terminals.)
=> [...]
=> u is a number of terminals, A and B a number of non-terminals. [...]
=> Of course, one'd check for CH-1 first, but that's not nearly as easy to
=> do. [...]
Since regexps have backtracking built in, won't it be easy to
test each rule as a string, instead of handling the LHS and
RHS separately? The m{}x regexp at the bottom of the
following code seems to capture your definition of CH-1,
although I may be mistaken.
(Of course, &check_CH1 returns 1 for CH-2 and CH-3 grammars,
too. The tests are to be applied in decreasing order, from
CH-3 down to CH-1, as you've described.)
|| # *** Incomplete code follows! ***
||
|| my $xTerm = qr/.../; # Match any terminal.
|| my $xNon_term = qr/.../; # Match any non-terminal.
|| my $xAlphabet = qr/(?:$xTerm|$xNon_term)/; # Match the alphabet.
||
|| # Choose an arrow not matching the alphabet.
|| my $arrow = "->";
|| assert($arrow !~ $xAlphabet);
|| my $xArrow = qr/$arrow/;
||
|| sub check_CH1 {
|| # Receive an array of @productions (as described by OP in
|| # his examples).
|| # Return 1 if every $production is (at most)
|| # context sensitive; 0 otherwise.
|| #
|| # If @rules is available in main::, we can simplify
|| # this function. We can simply receive @rules here,
|| # instead of @productions, and we won't have to
|| # create $rule from each $production.
|| my @productions = @_;
||
|| foreach my $production (@productions) {
|| # Make a rule from $production, by stringifying the
|| # left and right sides.
|| my $rule = join("", @{$production->{left}}, $arrow,
|| @{$production->{right}});
||
|| return 0 if $rule !~ m{
|| ($xTerm*) $xNon_term+ ($xTerm*) # LHS
|| $xArrow
|| $1 $xAlphabet* $2 # RHS
|| }x;
|| }
|| 1;
|| } # &check_CH1
||
|| # *** Incomplete code above! ***
peace, || Rainwater Harvesting in Karnataka:
--{kr.pA} || http://makeashorterlink.com/?J21521932
--
GAAP, n.: the reason for the gaap between the balance sheet and reality.
