概要 †

このテキストは，解説資料に掲載した線形時間のアルゴリズムのアルゴリズムの正当性の説明を試みるものである．なお，便宜のため，このテキストではスライドに載せたアルゴリズムそのものについても改めて説明をおこなっている．

目次 †

文の簡略化 †

「a list of」は一単語として処理するほうが都合がよい．そこで，このテキストでは単に「lst」と略記する．また，カンマはその有無によらず解析結果は同じになるので省略する．たとえば

a list of A, a list of P and Q, B, a list of X, Y and Z and C

という文は次のように変形される．

lst A lst P and Q B lst X Y and Z and C

基本的発想 †

「lst（a list of）」と「and」との対応関係が定まれば，その対応関係から S 式を復元することは（比較的）容易におこなうことができる．したがって，以降では文中にあらわれる「lst」と「and」をいかにして対応させるかということを議論する．

以降の議論においては，「lst」と「and」の対応関係を [1] のように角括弧＋数字で表記することにする．たとえば，この表記法を先の例文に適用すると次のようになる．

lst[1] A lst[2] P and[2] Q B lst[3] X Y and[3] Z and[1] C

ただし，「lst」は常に「and」と対応するとは限らない．そのような「lst」に対しては数字のかわりにハイフンを付する．たとえば次のとおりである．

lst[1] A lst[-] B and[1] C

アルゴリズム †

曖昧フラグ，スタック，および対応関係の記録場所をそれぞれ用意する．また，曖昧フラグは初期化の段階において偽に設定する．まず，最後の and の直前まで，次の手順にしたがって前から順番に走査する．

• lst が現れたら，現在位置をスタックに積む．このとき直前が and で，かつ現在位置を積む直前の時点においてスタックが空でなかったときは曖昧フラグをセットする．それ以外の場合は曖昧フラグの値を変更しない．
• and が現れたら，スタックから要素をひとつ取り出して，取り出した位置と現在位置との対応関係を記録する．取り出した直後において，スタックの要素数が 2 以上のときは曖昧フラグをセットする．そうでないときは逆に曖昧フラグをクリアする．
• それ以外の単語は S 式の要素なので，この時点では無視する．

最後の and に関しては，以下のように特別扱いをする．なお，ある lst の対応関係が未解決であるとは，その lst といずれかの and との対応関係がある時点（ここでは上記の手順が完了した時点）では記録されていないことを意味する．

• スタックに要素がひとつしかないときは，常に対応関係は一意である．
• 曖昧フラグがセットされていて，かつスタックに複数の要素があるときは，与えられた文は曖昧である．
• 対応関係が未解決である lst のうちで最も左側に現れる lst について，その直後にも lst が現れて，かつその lst が未解決のときは，スタックに複数の要素があるならば与えられた文は曖昧である．
• 上記のいずれにも該当しないときは，最後の and は対応関係が未解決である lst のうちで最も左側に現れるものと対応する．なお，この時点でスタックに残っている lst は，単一の要素からなるリストの開始をあらわしている．

具体例 †

ここでは，実際の文に上記のアルゴリズムを適用したときにおける，スタックの内容変化を記す．なお，* はその時点において曖昧フラグがセットされていることをあらわす．文全体が一意に解析されるとき，すなわち一意である lst と and の対応関係が存在するときは，文中に対応関係を表す角括弧+数字ないしハイフンを付した．

lst[3] A lst[1] P and[1] Q B lst[2] X Y and[2] Z and[3] C
(A (P Q) B (X Y Z) C)

[] → [0] → [0,2] → [0] → [0,7] → [0] → []

lst[1] A lst[-] B C D E and[1] F
(A (B) C D E F)

[] → [0] → [0,2] → [2]
最後の and が特別扱いされる典型例である．スタックに 2 という要素が残っているが，これは位置が 2 のところにある lst，この場合は後者の lst が単一の要素からなるリストの開始をあらわしていることを意味する．

lst[2] A lst[1] B C D and[1] E and[2] F
(A (B C D E) F)

[] → [0] → [0,2] → [0] → []

lst lst A A and A
AMBIGUOUS

[] → [0] → [0,1] → [1]*
文頭において lst が連続するため曖昧になる．すなわち，最後の and が最初の lst と 2 番目の lst のどちらに対応するかわからない．

lst[2] lst[1] A and[1] A and[2] A
((A A) A)

[] → [0] → [0,1] → [0] → []
文頭において lst が連続しているが，スタックが空になる場合は問題ない．

lst A lst A lst A and B and C
AMBIGUOUS

[0] → [0,2] → [0,2,4] → [0,2]* → [2]*
B の直前にある and は 2 番目，3 番目にある lst のどちらにも対応する可能性がある．そのため，[0,2]* のところで曖昧フラグがセットされる．

lst[3] A lst[2] lst[1] B and[1] C and[2] D lst[-] E F and[3] G
(A ((B C) D) (E) F G)

[0] → [0,2] → [0,2,3] → [0,2]* → [0] → [0,9] → [9]

lst lst A lst B and C lst D and E
AMBIGUOUS

[] → [0] → [0,1] → [0,1,3] → [0,1]* → [0,1,7]* → [0,7]* or [1,7]*
最初の and が A の直前にある lst と B の直前にある lst とのどちらと対応させるかという点に曖昧性がある．

lst C lst A B and lst Y and Z
AMBIGUOUS

[] → [0] → [0,2] → [0] → [0,7]* → [0]* or [7]*
これは and lst の連続によって曖昧性が生まれる例である．すなわち Y の直前にある lst が単一要素のリストであるか，あるいは Y と Z の 2 要素からなるリストであるかを決定できない．

lst lst A B and lst Y and Z
AMBIGUOUS

[] → [0] → [0,1] → [0] → [0,5]* → [0]* or [5]*
これは直前の例と同じである．

lst[1] A and[1] lst[2] B and[2] lst[3] C and[3] D
(A (B (C D)))

[] → [0] → [] → [3] → [] → [6] → []
これも and lst の連続があるが，それぞれの and を処理した時点でスタックが空になる，すなわちどの lst と対応するか一意に決まるため，曖昧ではない．

lst[1] A B and[1] lst[2] C D lst[3] E F and[2] G
(A B (C D (E) F G))

[] → [0] → [] → [4] → [4,7] → [7]
これは直前の例と同じである．

lst[0] A lst[-] B and[0] lst[-] C
(A (B) (C))

[] → [0] → [0,2] → [2]
これも and lst の連続があるが，最後の and は特別扱いされるので曖昧フラグはセットされない．

正当性の説明 †

（まだ書きかけです）

［定理１］
文全体が一意に解析可能ならば，最後に現れるものを除いて，and は対応関係が未解決である lst のうちで最も内側にあるものと対応する．

［証明（概略）］
文中に「... lst A1 ... Am lst B1 ... Bn and C ...」という部分があって，

... lst[1] A1 ... Am lst[-] B1 ... Bn and[1] C ...

という対応関係が可能だとする．ここに，A1，B1，C 等はいずれも要素，あるいは一意に解析されたリストである．これに対応する S 式は次のとおりである．

... (A1 ... Am (B1) B2 ... Bn C) ...

ところで，and は常にいずれかの lst と対応することから，これよりも後ろに and が現れるならば，すなわち上記の部分における and が最後に現れる and でないならば，上記の部分よりも前方に lst が存在する．いいかえれば上記の部分は外側にあるリストの一部である．したがって，

... lst[-] A1 ... Am lst[1] B1 ... Bn and[1] C ...
... (A1) A2 ... Am (B1 ... Bn C) ...

という対応関係も可能になる．すなわち上記の部分に関して複数の解析が可能となり，文全体が一意に解析可能であるという仮定に反する．（証明終）

［定理２］
文頭において lst が連続するとき，最初に現れるもの以外の lst について，最後に現れる and よりも前方にある and との対応関係が存在しないならば，文全体は一意に解析可能でない．

［証明（概略）］
以下の (a) のような対応関係が可能ならば，すなわち (b) のような対応関係も可能であるから，文全体について複数の解析が可能となる．（証明終）

(a) lst[1] lst[-] A1 ... A(n-1) and[1] An
    ((A1) ... An)

(b) lst[-] lst[1] A1 ... A(n-1) and[1] An
    ((A1 ... An))

［系１］
文全体が一意に解析可能で，かつ文頭において lst が連続するならば，連続する lst のそれぞれは，最初のものを除いて，最後に現れる and よりも前方にある and のいずれかと対応する．

［証明］
定理２より明らか．（証明終）

［定理３］
文全体が一意に解析可能ならば，最後に現れる and は，文頭にある lst または最後以外の and の直後にある lst と対応する．

［証明（概略）］
一番外側のリストの構造によって，以下の３通りに分けることができる．

• 単一の要素からなりその要素はリストでない．
• 単一の要素からなりその要素はリストである．
• 複数の要素からなる．

最初の場合はそもそも文中に and が現れない．２番目の場合は文頭においてふたつの lst が連続するので，定理２によって最後の and は文頭の lst と対応する．そこで，３番目の場合において，最後の and と文頭の lst とが対応しない場合を考える．リストは複数の要素からなるので，文頭の lst に対応する and が常に存在する．すなわち

lst[1] A1 ... Am and[1] ...

の形になる．ここで and[1] の直後が lst でないとすると，文全体は次のような形にあるが，これは最も外側にあるリストとしては妥当ではない．したがって，and[1] の直後は lst である．

lst[1] A1 ... Am and[1] X1 ... Xi lst ...
(A1 ... Am X1) X2 ... Xi (...)

and[1] の直後にある lst が最後の and と対応するときは定理の内容は満たされる．対応しないときは，これまでの議論を再帰的に適用することができる．すなわち，いずれの場合であっても定理の内容は満たされる．（証明終）