Python、Haskell、YAMLのように行頭の字下げが文法構造に影響を与えるような構文を、字下げ依存構文(indentation-sensitive syntax)と呼ぶことにする。
Peter J. Landin「The Next 700 Programming Languages」(pdf)では、字下げ依存構文のための規則をオフサイドルールと呼んでいる(6節(3))。 そこでは
句の最初のシンボルをちょうど含んだ右下象限が、句全体を含んでいなければならない。
と説明している。
つまり
<first symbol>------------------------------------->
--------------------------------------------------->
--------------------------------------------------->
--------------------------------------------------->
--------------------------------------------------->
の範囲に入れろというルール。
この文章では、このルールにこだわらず字下げを利用する構文全般を考える。そうすると、行の先頭を特別扱いするような構文も含まれる。字下げすると意味が変わるので。
* 行の先頭が「*」だと見出しになる * 見出しにならない - 行の先頭が「-」リストのエントリになる - リストエントリにならない
Pythonなどの名前をあげたように、字下げ依存構文はそれなりに使われている。にもかかわらずコンパイラの本をいくつか調べてみても、字下げ依存構文の字句解析・構文解析を全然扱っていない。わざわざ扱うほどの問題ではないのかもしれないけど。
いくらか調べてみた。
- Leonhard Brunauer, Bernhard Mühlbacher. 2006 Indentation Sensitive Languages
- Michael D, Adams Ömer S. Ăgacan. 2014 Indentation-Sensitive Parsing for Parsec
Pythonの場合
ドキュメントを読んでみると、Pythonの字下げ依存構文はシンプルで解析も難しくなさそう。ドキュメントの2.1. Line structureを読めば、字句解析のやり方までだいたいわかる。
Pythonの字下げ依存構文
基本は、インデントが深くなったところがブロックの開始を示し、インデントが浅くなるとブロックの終了を示す。また空白(スペース、タブ、コメント等)しかない行は無視され、ブロック構造には影響を与えない。
インデントを戻すときは、対応するインデントレベルに戻さないとエラーになる。
# 正しいif-elseの対応 if x==1: if y==1: print "a" else: print "b" # 構文エラー if x==1: if y==1: print "a" else: # ←インデントレベルがifと対応していない print "b"
プログラムの字下げは、プログラムの構造を示す以外に、長い数式や配列データを複数行に分けて書いて見やすくするときにも使われる。
Pythonでは、式を複数行にまたいで書くことはできない。その代わりに、行の最後尾に「\」を入れ改行をエスケープすると、次の行と一続きの行だと見なされる。次の行は前の行の続きなのでいくらインデントしても単なる空白扱いになる。また式の途中にカッコが現れると対応するカッコが閉じられるまでは一つの行として扱われ、新しい行のインデントは空白扱いになる。たとえば次のように書くことができる。
if x == 1 + 2 + \ 3 + (4 + 5 + 6) + 7 \ + 8 + 9 + 10: print "a" else: print "b"
字句解析・構文解析の仕方
字下げが深くなったところがブロック構造の始まりで浅くなったところでブロックの終わりというルールは字句解析の範囲で処理できる。
まずスタックを用意する。スタックの一番上には現在処理中の字下げの深さが記録されている。あとは次のように字句解析すればよい。
- 新しい行が始まったら空白でない文字が現れるまで読み進め、字下げの深さを見る。
- 改行はエスケープされていれば読み飛ばす。エスケープされていない通常の改行の場合は、改行を表すトークン<NEWLINE>を生成する。
- カッコも適当に処理する(字下げ深さを記録するスタックに、開きカッコ(を示す情報)をプッシュして、トップがそれの間は<INDENT>などの生成を抑制すればよいかもしれない)。
- EOFに到達したら、スタックの長さを見て必要なだけ<DEDENT>を生成する。
構文解析のレベルでは特に変わった処理は必要なくて、<IEDENT> <DEDENT>をbegin endのように扱い、<NEWLINE>をターミネータ、セパレータのように扱えばよいはず。
SRFI 49の場合
(字句解析レベルの処理はPythonとだいたい同じだけど、構文解析がPythonよりもややこしい)
SRFI 49は、SchemeのプログラムをS式ではなく字下げを用いた構文で記述するための仕様を定めている。
(同様の構文拡張をLisp、Schemeに与えているものとしてSweet-expressions: A readable format for Lisp-like languages、P4P: A Syntax Proposalがある)
たとえば
define (fact n) if (= n 0) 1 * n fact (- n 1)
は
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
を表す。完全にカッコを省略して
define fact n if = n 0 1 * n fact - n 1
とも書ける。
字句解析
字句解析の処理はだいたいPythonと同じで、字下げが深まればトークン<INDENT>を生成し、浅くなれば<DEDENT>を生成する(ただし参照実装では、実際にはそういう処理はしていないみたい)。
違う部分としてはタブの扱いがある。Pythonではタブストップが8文字であるとみなして字下げの深さを計算する。SRFI 49では、字下げをするときは、前の行と次の行で空白文字・タブ文字の並びかたが同じであるように字下げをしないといけない。字下げ幅を比較するときは、字下げの文字数ではなく、字下げに使われた文字を順番に比較していく。
構文解析
Pythonの場合とは違って、構文解析のレベルでの処理もいくらか考える必要がある。
たとえばある行を読み終わったあと
- 次の行で字下げが深くなる(=トークン<INDENT>が現れる)場合
- 深くならない場合
- 行の要素が一つだけだった
- 行の要素が二つ以上だった
で異なる扱いをしないといけない。このことは、SRFI 49のSpecificationでは
expr -> head INDENT body DEDENT
(append $1 $3)
expr -> head
(if (= (length $1) 1)
(car $1)
$1)で示されている。その他の処理もSpecificationの文法規則によって示されている。
このように字句解析と構文解析の両方のレベルを使って字下げ依存構文に対応することもできる。
HAMLに対しても同様の解析の仕方を使えると思う。
Haskellの場合
Haskellはキーワードlet、where、do、ofに続く部分でオフサイドルールを使うことができる。
たとえば
x = let a = 1 b = p + q where p = 10 -- whereの束縛 q = 20 p = 100 -- letの束縛 in a + b + p
では、二つのレイアウトを使っている。
「q = 20」の次の行で字下げが浅くなっているのでwhere節が終了し、「p = 100」の次の行で字下げが浅くなっているのでletの宣言部が終了している。
一見すると字下げしたところが一つのまとまりになる仕組みに見えるけど、そうではない。たとえば、判りやすいかどうかはともかく
x = alpha + beta + gamma where alpha = 1 beta = 2 gamma = 3
と書くことができる。Haskellでは、whereやletなどのキーワードの次に出てくるシンボル(この例ではalpha)がオフサイドルールの左端を定めるので、whereやlet自体よりも字下げを浅くすることもできる。
ただしレイアウトが入れ子になった場合は内側のレイアウトの方が外側よりも深く字下げしないといけない、という補助規則がある。次の例2の「z = 7」は字下げが外側のレイアウトより深くなっていないので、外側のletでの束縛として扱われ、その結果構文エラーになる。
-- 例1: 正しいプログラム a = let x = 7 y = let z = 8 in z in x + y
-- 例2: 構文エラーになる a = let x = 7 y = let z = 8 -- 字下げが浅い in z in x + y
ただし次のように波カッコ"{"、"}"でくくれば、正しいプログラムになる。
a = let x = 7 y = let { z = 8 } in z in x + y
letやwhereなどのキーワードの次のトークンが波カッコの場合、オフサイドルールが働かなくなり字下げは無関係になる(改行も無視され必要ならばセミコロン";"を入れる)。ただしその内部でまたletなどのキーワードが出てくると、(その次に波カッコが出てこなければ)オフサイドルールが働く。
他にも判りにくい事例がある。次の例。
-- 正しいプログラム x = let a = 1 b = a in (a,b)
この例では、オフサイドルールが定める範囲を抜ける前に「in」が登場している。にもかかわらず、このプログラムは正しいことになっている。これについては
レイアウトリストを含んでいる構文カテゴリーが終了する場合は常に閉じブレースが挿入される。
http://haskell.org/onlinereport/lexemes.html#lexemes-layout
と説明されている。例でいえば「in」の前で閉じブレースが入る(=レイアウト終了)。でも判りにくい。レイアウトの規則をプログラムを使って説明している9.3 LayoutではNote 5で説明しているけど、どう実現するのかよくわからないところ。
あとは
x = let a = 1 b = 2 c = 3 in a + b + c
とは書けるけど、次のように書くとエラーになる。
-- 構文エラー x = let a = 1 b = 2 -- 字下げの深さのズレ c = 3 in a + b + c
これをエラーにするのは、式を複数行に書けるようにするため。
x = let a = 1 b = 2 + 3 + 4 + 5 -- 前の行からの続き c = 6 in a + b + c
-- 構文エラー x = let a = 1 b = 2 + 3 + 4 + 5 -- 新しいエントリーと見なされる → エラー c = 6 in a + b + c
Haskellのレイアウト規則をまとめると、だいたい次のようになる。
- (字下げからではなく)キーワードで新しいレイアウトの開始。
- レイアウトの左端の位置は、キーワードの次のトークンの開始位置で決まる。
- レイアウトが入れ子になる場合、字下げの深さは内側のレイアウトほど深くないといけない。
- 改行のあと字下げが
- 浅くなった →レイアウト終了
- 同じ →新しい式
- 深くなった →前の式の続き
- オフサイドルールが適用されなくなる場合もある(キーワード+波カッコ)。
- 例外事項: 字下げが浅くならなくてもレイアウトが終了する場合がある(ただし基準が判りにくい)。
字句解析
レイアウトを使ったHaskellプログラムは、字句解析の過程で波カッコ"{"、"}"とセミコロン";"が追加される。そのため構文解析の段階には、レイアウト規則や字下げの概念は全く登場しない(ただし、波カッコを追加する過程で、本来構文解析のレベルの処理が登場することがある。(1)開き波カッコなしで閉じ波カッコが登場するとき。(2)字下げが浅くならずにレイアウトが終了するときの判定)。
たとえば、次の例の上のプログラムは、カッコとセミコロンの追加により、構文解析では下のプログラムと同等に処理される。
x = let a = 1; b = 2 c = 10 * p where p = 20 d = 3 + 4 + 5 + 6 in (a, b, c, d)
→
x = let { a = 1; b = 2; c = 10 * p where { p = 20 }; d = 3 + 4 + 5 + 6 }in (a, b, c, d)
波カッコとセミコロンの追加は、2段階でおこなわれる。
まずトークンにする過程で、レイアウトの左端を示すトークン「{n}」と、字下げの深さを示すトークン「<n>」を追加する。「{n}」は、letやwhereなどのキーワードの次に現れるトークンの前に挿入する(トークンが開き波カッコ"{"のときは挿入しない)。「
x = let{12}a = 1; b = 2 <12>c = 10 * p <14>where {16}p = 20 <12>d = 3 + 4 <18>+ 5 + 6 <6>in (a, b, c, d)
次の段階で、このトークンの列を読みながら波カッコとセミコロンを追加していく。「{n}」で示された数はスタックに追加され、処理しているレイアウトの字下げレベルを管理する。また開き波カッコが現れた場合はスタックに0を追加して、レイアウト処理をしないことを示す。「
波カッコとセミコロンを追加するための具体的な処理の仕方は省略(詳細は9.3 Layout(またはその日本語訳))。
YAML
YAMLの仕様をちょっと読んでみたけど、書き方が豊富すぎて把握しきれない。YAMLには、字下げを利用するブロックスタイルと利用しないフロースタイルの両方を使うことができるので、特に重要なのは
あたりだけど、この部分だけでも結構ある。
さわりだけ取り上げるとこんな感じ。
- 「-」で、シーケンス(配列)の各エントリの開始を示す。
- alpha - beta - gamma
→
["alpha", "beta", "gamma"]
- 「文字列:」で、マッピング(ハッシュ)の各エントリの開始を示す。「文字列」がマップのキーになる。
aaa: A b: B ccccc: C
→
{"aaa"=>"A", "b"=>"B", "ccccc"=>"C"}
- シーケンスやマッピングの各エントリは、同じ字下げ深さで開始される。エントリが複数行にわたる場合は、2行目以降の字下げは開始行より深くないといけない。
- aaa bbb ccc ddd - eee
→
["aaa bbb ccc ddd", "eee"] # 改行とそれに続くインデントは一つの空白になる
- "|"を指定すると、字下げの空白だけが取り除かれ改行は残る。字下げの深さは1行目の字下げ幅で決まる。ただし"|"の後ろに数を指定すると、その数が字下げ幅になる。
sample1: | a b c sample2: |2 d e f sample3: - |4 # 字下げの文字数はエントリの開始(この場合"-")の位置から数える ggg hhh
→
{"sample1"=>"a\n b\n c\n",
"sample2"=>" d\n e\n f\n",
"sample3"=>[" ggg\n hhh\n"]}
alef: - first - second bet: - aaa - bbb - ccc
→
{"alef"=>["first", "second"], "bet"=>["aaa", "bbb", "ccc"]}
YAMLの字句解析・構文解析
YAMLのブロックスタイルは、Haskellのレイアウトにわりと近い。
- 複数のエントリは同じ字下げ深さで縦に並べる。エントリを次の行に継続させる場合は、字下げを深くする。
なので、スタックを用意して「今、字下げレベルnでシーケンス(orマッピング)を処理している」みたいな情報をプッシュして、スタックを見ながら処理を進めればできるはず。でも実際には仕様が大きいから簡単にはいかなそう。
YAMLの構文定義
YAMLの仕様を少しだけ眺める。シーケンスの部分だけ。
YAMLの構文定義は、パラメータを付けたBNFを使って定義されている。
たとえばブロックスタイルのシーケンス l+block-sequence(n)は次のように定義されている(nは「字下げの深さ >n」を表す。接頭辞に"+"が使われていると「よりも深い」を示す)
[183] l+block-sequence(n) ::= (s-indent(n+m) c-l-block-seq-entry(n+m))+ /* ∃m>0 */ [63] s-indent(n) ::= s-space × n [184] c-l-block-seq-entry(n) ::= "-" s-l+block-indented(n, block-in)
これは例えば次のような構文要素を表している。
-...... -...... ...... -...... ...... -......
ブロックスタイルのシーケンスには、もうひとつns-l-compact-sequenceというものがある。
[186] ns-l-compact-sequence(n) ::= c-l-block-seq-entry(n)
( s-indent(n) c-l-block-seq-entry(n) )* これは次のような場合に対応する。
- -......
......
-......
-......
foo: -...... -...... ......
エントリ開始"-"に続く要素 s-l+block-indentedは次のようになる。
[185]
s-l+block-indented(n,c)
::= ( s-indent(m) ( ns-l-compact-sequence(n+1+m)
| ns-l-compact-mapping(n+1+m) ) ) /* 改行なしで入れ子 */
| s-l+block-node(n,c)
| ( e-node s-l-comments ) /* 空ノード */s-l+block-nodeは、フロースタイル(非ブロックスタイル)のノード、ブロックスカラー(文字列など)、シーケンス・マッピングの入れ子を扱うので、さらに色々な定義に続いていく。
こんな感じでBNFっぽく定義されているけれど、そこからどうやってうまくパーザの記述に落とすのかよくわからない。実際の処理系のソースを見てみるのがよいかもしれないけど、とりあえずここまで。
