概要 †このテキストは,解説資料に掲載した線形時間のアルゴリズムのアルゴリズムの正当性の説明を試みるものである.なお,便宜のため,このテキストではスライドに載せたアルゴリズムそのものについても改めて説明をおこなっている. 目次 †文の簡略化 †「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 の直前まで,次の手順にしたがって前から順番に走査する.
最後の and に関しては,以下のように特別扱いをする.なお,ある lst の対応関係が未解決であるとは,その lst といずれかの and との対応関係がある時点(ここでは上記の手順が完了した時点)では記録されていないことを意味する.
具体例 †ここでは,実際の文に上記のアルゴリズムを適用したときにおける,スタックの内容変化を記す.なお,* はその時点において曖昧フラグがセットされていることをあらわす.文全体が一意に解析されるとき,すなわち一意である 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] 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[2] lst[1] A and[1] A and[2] A ((A A) A) [] → [0] → [0,1] → [0] → [] lst A lst A lst A and B and C AMBIGUOUS [0] → [0,2] → [0,2,4] → [0,2]* → [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]* lst C lst A B and lst Y and Z AMBIGUOUS [] → [0] → [0,2] → [0] → [0,7]* → [0]* or [7]* 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] → [] 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] 正当性の説明 †(まだ書きかけです) [定理1] [証明(概略)] ... 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) ... という対応関係も可能になる.すなわち上記の部分に関して複数の解析が可能となり,文全体が一意に解析可能であるという仮定に反する.(証明終) [定理2] [証明(概略)] (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)) [系1] [証明] [定理3] [証明(概略)]
最初の場合はそもそも文中に and が現れない.2番目の場合は文頭においてふたつの lst が連続するので,定理2によって最後の and は文頭の lst と対応する.そこで,3番目の場合において,最後の 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 と対応するときは定理の内容は満たされる.対応しないときは,これまでの議論を再帰的に適用することができる.すなわち,いずれの場合であっても定理の内容は満たされる.(証明終) |