Exercise 4.4.5 : The grammar S → a S a | a a generates all even-length strings of a's. We can devise a recursive-descent parser with backtrack for this grammar. If we choose to expand by production S → a a first, then we shall only recognize the string aa. Thus, any reasonable recursive-descent parser will try S → a S a first. a) Show that this recursive-descent parser recognizes inpus aa, aaaa, and aaaaaaaa, but not aaaaaa.
!! b) What language does this recursive-descent parser recognize?

以下naoya_t拙訳:
問題4.4.5 : 文法 S → a S a | a a は、a から成り長さが偶数のあらゆる文字列を生成する。我々はこの文法のためのバックトラック付再帰降下パーサを作ることができる。もし最初に生成規則 S → a a を展開する方を選ぶなら、文字列 aa しか認識しない。それ故、妥当な再帰降下パーサは皆 S → a S a から試すことになる。
　 a) この再帰降下パーサが入力 aa, aaaa, aaaaaaaa は認識するが aaaaaa を認識しないことを示せ。
!! b) この再帰降下パーサが認識するのはどんな言語か。

---

手動再帰降下パーサ（ノートと鉛筆）でステップ実行を繰り返していたら、S → aSa が取れてしまい S → aa に制御が行かないケースがあり、aaaaaa が認識できないのがわかった。

文字列を長くしていくと、長さが 2,4,8,16... の文字列しか認識しないようだ。長さ 2^n ということだろうか。ノートでやるのは16あたりで限界なのでGaucheでスクリプトを書いて実証してみた。

(use srfi-1) ; iota

;;; S → a S a | a a
(define (S st)
  (let1 backtrack [st'backtrack-proc]
    (or (and (eq? #\a [st'first-char])
             (S st)
             (eq? #\a [st'first-char]))
        (and (backtrack)
             (eq? #\a [st'first-char])
             (eq? #\a [st'first-char]))
        (and (backtrack)
             #f))))

;;; Test
(define (test-string string)
  (let1 st (string->stream string)
    (and (S st) [st'at-the-end?])))

(define (test-string-with-length-n n)
  (and (test-string (make-string n #\a)) n))

(define (test-till-n n)
  (remove not (map test-string-with-length-n (iota (/ n 2) 2 2))))

(print (test-till-n 10000))
; => (2 4 8 16 32 64 128 256 512 1024 2048 4096 8192)

さて。これをどう示すか。