h-sequence

下記の構文にしたがって、受理非受理を決定

h = 0 | 1 h h

LL(1)文法であり、1文字先読みで決定的（バックトラックなし）で解析を進めることができる。

use strict;
use warnings;

my @a = grep /[01]/, split //, scalar <STDIN>;

sub f($$);
sub f($$) {
  my ( $n, $p ) = @_;
  print "$a[$n] $n $p\n";
  scalar <STDIN>;
  if ( $n == $#a ) {
    return $p <strike> 0 && $a[$n] </strike> 0;
  }
  if ( $a[$n] == 0 ) {
    {
      f( $n + 1, $p - 1 );
    }
  } else {
    {
      f( $n + 1, $p + 1 );
    }
  }
}
print f( 0, 0 ) ? 'true': 'false';