function dbg(x)
{
  printf("dbg: <%s>\n", x)
  return x
}

function empty(s)
{
  return s == ""
}

function eat_char(s)
{
  return substr(s, 2)
}

function eat_chars(s, n)
{
  return substr(s, n + 1)
}

function matches(s, pfx)
{
  return substr(s, 1, length(pfx)) == pfx
}

function match_and_eat(s, pfx)
{
  if (matches(s, pfx))
    return eat_chars(s, length(pfx))
  return s
}

function match_and_eat_else(s, pfx, e)
{
  if (matches(s, pfx))
    return eat_chars(s, length(pfx))
  return e
}

function eat_digits(s)
{
  match(s, /^[0-9]+/)
  if (RLENGTH > 0)
    return eat_chars(s, RLENGTH)
  return s
}

function extract_digits(s)
{
  match(s, /^[0-9]+/)
  if (RLENGTH > 0)
    return substr(s, 1, RLENGTH)
  return ""
}

function eat_rchar(c)
{
  if (c ~ /^\\./)
    return eat_chars(c, 2)

  if (c == "$")
    return c

  if (c !~ /^[\[\*\+\?{}\(\)|]/)
    return eat_char(c)

  return c
}

function eat_bchar(c)
{
  if (c ~ /^\\]|\\-|\\\\/)
    return eat_chars(c, 2)

  if (c !~ /^[\-\[]/)
    return eat_char(c)

  return c
}

function eat_class(c)
{
  c = match_and_eat(c, "[:alnum:]")
  c = match_and_eat(c, "[:alpha:]")
  c = match_and_eat(c, "[:blank:]")
  c = match_and_eat(c, "[:cntrl:]")
  c = match_and_eat(c, "[:digit:]")
  c = match_and_eat(c, "[:graph:]")
  c = match_and_eat(c, "[:lower:]")
  c = match_and_eat(c, "[:print:]")
  c = match_and_eat(c, "[:punct:]")
  c = match_and_eat(c, "[:space:]")
  c = match_and_eat(c, "[:upper:]")
  return match_and_eat(c, "[:xdigit:]")
}

function eat_bracket_exp(e,
                         #local
                         f, o, x, y)
{
  o = e
  e = eat_char(e)

  for (;;) {
    if (matches(e, "]")) {
      return eat_char(e)
    }

    if (matches(e, "[")) {
      f = eat_class(e)
      if (f == e)
        return o
      e = f
      continue
    }

    x = substr(e, 1, 1);
    f = eat_bchar(e)

    if (f == e)
      return o
    e = f

    if (matches(e, "-")) {
      e = eat_char(e)
      y = substr(e, 1, 1);
      f = eat_bchar(e)

      if (x > y || f == e)
        return o
      e = f
    }
  }
}

function eat_rep_notation(n,
                          # local
                          o, x, y)
{
  o = n
  n = eat_char(n)

  x = extract_digits(n)

  if (empty(x))
    return o

  n = eat_digits(n)

  if (matches(n, "}"))
    return eat_char(n)

  if (!matches(n, ","))
    return o

  n = eat_char(n)

  if (matches(n, "}"))
    return eat_char(n)

  y = extract_digits(n)

  if (empty(y))
    return o

  if (x + 0 > y)
    return o

  n = eat_digits(n)

  return match_and_eat_else(n, "}", o)
}

function eat_factor(f)
{
  if (matches(f, "("))
    return match_and_eat_else(eat_regex(eat_char(f)), ")", f)

  if (matches(f, "["))
    return eat_bracket_exp(f)

  return eat_rchar(f)
}

function eat_term(t,
                  #local
                  s)
{
  s = eat_factor(t)

  if (empty(s) || s == t)
    return s

  t = s

  if (t ~ /^[?+*]/)
    return eat_char(t)

  if (matches(t, "{"))
    return eat_rep_notation(t)

  return t
}

function eat_regex(r,
                   #locals
                   s)
{
  if (empty(r))
    return r

  s = eat_term(r)

  if (empty(s) || s == r)
    return s

  r = s

  if (matches(r, "|"))
    r = eat_char(r)

  return eat_regex(r)
}

function regex_check(r)
{
  if (matches(r, "^"))
    r = eat_char(r)

  if (empty(r))
    return r

  r = eat_regex(r)

  if (r == "$")
    r = ""

  return r
}

function is_regex(r)
{
  return empty(regex_check(r))
}

{
  ok = is_regex($0)

  printf("is_regex(\"%s\") = %d", $0, ok)
  if (!ok)
    printf(", junk = \"%s\"", regex_check($0))
  printf("\n")
}