🧮

LL(1)言語を作るのは難しい、しかしLL(1)言語は素晴らしい

2022/12/07に公開

2件

コンパイラ

言語実装 Advent Calendar 2022の6日目です。

本記事ではLL(1)の素晴らしさと難しさについてDesk言語の開発の体験から語ります。

LL(1)とは

LL(1)についてご存知でしょうか。
「LL(1)言語」「LL(1)文法」「LL(1)パーサ」でそれぞれ定義がありますが、一番分かりやすい「LL(1)パーサ」をざっくりいうと、ソースコードの頭から順番にトークン（ifや1や{など）を見ていきながらASTを構築するための情報を集める^[1]パーサのうち、現在見ているトークンの種類を確認するだけで（それ以上の先読みなしに）ASTのノードの種類（IfやIntegerLiteralやBlock）を決定できるもののことです。
そしてLL(1)パーサでパースできるのがLL(1)文法であり、LL(1)言語であるというのがざっくりした説明です^[2]。

次は、LL(1)パーサ（言語）のメリットとデメリットを挙げてみます。

LL(1)のメリット

パーサをつくるのが簡単（手書きする人も多い）
ソースコードを読むときにソースコードの頭から読むだけで頭の中でASTを構築できる^[3]
シンタックスエラーを構文的におかしい最初のトークン^[4]で出すことができ、期待していたトークン種の集合も返すことができる（対抗のLRパーサは構文エラーがわかりにくいこともあると言われている）
パースの最悪時間計算量がトークン数nに対してO(n)のはず（最悪ケースでべらぼうな時間がかかったりしない）
対抗のLALR(1)^[5]に対して格段に小さい空間計算量でパースできる
PDA（プッシュダウンオートマトン）を使って実装すればスタックオーバーフローの心配もない

正直言ってメリットはかなりあります。とくに

ソースコードを読むときにシンタックスハイライトがなくてもソースコードの頭から読むだけで頭の中でASTを構築できる

これとこれに関連する以下のメリットが自分としてはかなり大きく、Desk言語のメインの文法をLL(1)にすることを決定しました。

ソースコードを書くときに、最新の1つ目のトークンを書き終えた時点で必ず正しいシンタックスハイライトを適用できる
ビジュアルプログラミングエディターを作るとき、最新の1つ目のトークンの入力が終わった時点で正しいASTを画面に表示できる

LL(1)のデメリット

LALR(1)に対して（少なくとも言語を設計すれば誰でもわかる程に）記述できる文法が少ない
素朴に再帰で実装するとソースコードが大きくなったときにスタックオーバーフローの危険がある

他にもあると思いますが、少なくとも私が気になったのはこれだけです。

2つめはPDAを使えば解決できるので問題ないですが、1つ目は本当に大きなデメリットになります。
しかし、LL(1)より少し計算量の多いLL(k)であれば、大体の実用的なプログラミング言語は表現できるだろうと言われています。
そのため、基本的にはLL(k)（もしくはLR(1)系の何か）を使うのがいいと思います。
しかし私はLL(1)のメリットを得るために、この厳しい道を進むことに決めました。

LL(1)は難しい

LL(1)は他の文法クラスに比べて記述する文法の集合が人間が実感できるほど小さいと説明しました。
ここからは実際に遭遇した問題について話していきます。
これらの問題の多くはパーサコンビネータを使っている時は問題になりませんでしたが、LL(1)パーサジェネレータを使い始めた途端に問題になったものです。
また、LL(1)だけでなくLR(1)などでも問題になるものも含まれると思われます。

式に対する型アノテーションが一見、後置できない

24: i32

こういうかっこいい書き方を許したい場合、以下のような文法になります。

expr = expr ":" type / integer ;

これはもうすでにLL(1)ではありません。
なぜかというと1というトークンを読んだときに型アノテーション構文か整数構文かを判断できないからです。

（コメントをもらって追記）
これは以下のように文法を変形することでLL(1)で表現できるようになります。

expr1 = integer
expr = expr1 { ":" type };

この問題があるためDesk言語の型アノテーションは以下のようになりました。

<'float> 24

これはこれでこっちの方が使い勝手がいい場面が多いことが分かったのでよかったです。

後置の構文要素をOptionalにできない

! 1 ~> 'integer

Desk言語にはこんな構文があります。
当時は~>以降をOptionalにして以下のような構文を許したいと思っていました。

! 1

これを文法にするとこうなります。

expr = "!" expr [　"~>" type ] / integer;

直感的には大丈夫そうですね。

しかし、! 1 ~> 'floatと! 1が別の構文だとすると、これはLL(無限大)ですね。
なぜなら~>があるかないかを判断するためにexprという最大無限トークンのものを読み飛ばす必要があるためです。

しかしそれらは同じ構文でただ~> typeがつくかつかないかの話ですよね。となると問題ないように見えます。

しかしこの文法は再帰していますね。試しに以下のようなソースコードを考えてみましょう。

! ! 1 ~> 'integer

どうでしょう、この異常性に気づけるでしょうか。

はいそうですね~> 'integerがどちらの!に紐づくかがわかりません。残念でした。

もしかしたら、結合法則のようなものがあればこう言った問題は解決できるかもしれません。しかし、自分の美学上、結合法則がある言語は作れません。

この問題があるためDesk言語では~> typeをOptionalにできませんでした。

無いケースは代わりに推論構文を使って! 1 ~> _と書けることがわかりました。
また一般的に暗黙より明示のほうがいいとされているのでこれはこれでいいと思います。

関数呼び出し構文が一見作れない

Desk言語には変数がないのですが、普通の言語は変数があるので変数がある前提で話をします。

こんな感じの文法が普通だと思います。

expr = variable / application;
variable = ident;
application = ident "(" ... ")";

なんとなく分かってきたでしょうか。
はい、これはLL(1)ではありません。

abc(1)

という関数呼び出しがあったとします。
パーサはまずabcをみます。しかし、あれ、これは変数なのか関数呼び出しなのかわかりません。
LL(2)ならこれは問題ないですね。なので基本的にはLL(2)以上を使います。

（コメントをもらって追記）
もしくは以下のように文法を変形することでもLL(1)のまま関数呼び出し構文を実現できます。

expr1 = variable
expr = expr1 { "(" ... ")" };
variable = ident;

Desk言語ではこの問題とは関係ない別のところで問題があり、Desk言語での関数呼び出し構文は以下のようになりました。

^abc(1)

はい^が頭についています。これによりパーサは^トークンを見た時点で関数呼び出しということがわかります。

どうでしょうか。醜いと感じる方もいるでしょう。私も初めはそう思っていました。しかし、今となってはこっちの方がソースコードがpredictableになって読みやすいのでは無いかと思うようになっています。

以下はDesk言語でフィボナッチ数を計算するコードです。少し長いですがなんとなくざっくり眺めてみてください。

~~ type aliases
'type add \ *<@"l" 'integer, @"r" 'integer> -> @"sum" 'integer;
'type sub \ *<@"minuend" 'integer, @"subtrahend" 'integer> -> 'integer;
'type eq \ *<@"l" 'integer, @"r" 'integer> -> +<@"equal" *<>, @"unequal" *<>>;
'type fib \ 'integer -> 'integer;

~~ let fib
$ \ 'integer -> 'match ^eq *<@"l" &'integer, @"r" 0> {
  ~~ if integer == 0)
  @"equal" *<> => 0
  ~~ if integer != 0
  @"unequal" *<> => 'match ^eq *<@"l" &'integer, @"r" 1> {
    @"equal" *<> => 1
    @"unequal" *<> =>
      ~~ adds fib(integer - 1) and fib(integer - 2)
      <'integer> ^add *<
	^fib ^sub *<@"minuend" &'integer, 1>
	^fib ^sub *<@"minuend" &'integer, 2>
      >
  }
};

^fib 7

どうでしょう^が出てきたら必ず関数呼び出し、意外とよくないですか？

あと気づかれたと思いますが^fib ^sub *<@"minuend" &'integer, 1>のところとか明らかに関数呼び出しの()がないですよね。それが次の話です。

カッコ問題

上で少し話しましたが、実はDesk言語では関数呼び出し時のカッコを省略できます。
ちゃんと理由があります。

Desk言語の仕様上ほとんどの関数呼び出しが変数一つなので、カッコが冗長な場合がおおい
カッコがなくても前述の^があるので、パッと見れば関数呼び出しとわかる

2はわかると思いますが、1は本当にそうかな？と思われる方が多いと思います。確かに

abc(1)

のカッコは明らかに冗長でないです。

しかし、以下の1 + 2をするDesk言語のコードはどうでしょう。

^add(*<@"l" 1, @"r" 2>)

なんかごちゃついてますね。Rustに変換すると以下のようになります。

add((1, 2))

これで言いたいことが分かったのではないでしょうか。
Desk言語では足し算関数のような複数の引数が必要そうな場面でも基本的にタプルを使ってまとめます。
そうすると()と*<>というように二つの括弧が使われコードが読みづらくなります。
カッコを省略できると

~ これを
^add(*<@"l" 1, @"r" 2>)
~ こう
^add *<@"l" 1, @"r" 2>

することができます。

そして次に、全然関係ないような話をします。

ブロックってありますよね。C言語やRustだと{}で囲んだり、Elixirだとdo/endで囲ったりするやつです。

Desk言語には文がなく式しかないのでブロックはいらないように思いますが、必要な場面もあります。
それはdo式やlet式を使う場合です。

コードの意味はわからなくていいので以下のコードを見てください。

'match
  $ 1;
  do ! 1 ~> *<>;
  ^func 1
{
  @"true" *<> => 1
  @"false" *<> => 2
}

これはDeskの文法的に問題ありませんが個人的には'matchから{の間が気になります。それはここが一つの式ということがパッと見るだけだと、インデントしかヒントがないことです。
これは正しくインデントされていますし、現代はひたすらフォーマッタをかけながらコーディングするのが主流だと思うので実用上は問題はないでしょう。

しかし、わたしからすると何か囲うものがないと目が滑ったりなんか不安な気がしてきたり、
とにかく美学上、なにか囲うものが欲しくなってきます。
そこでまず考えたのが()を使うことでした。

しかしここで問題が起きます。

^ func (1)

わかりますでしょうか？

パーサ「このカッコって関数呼び出しのカッコなの？それともブロックを囲うカッコなの？」

はい、こういうことです。

しかし、こっちの問題はさっきの~> typeの問題と違って、構文的には区別できなくても、意味論としては全く同じことです。
じゃあ、実装のほうでいい感じに無視してあげればいいのではないかと思うかもしれません。
しかし、まず、そのことをチュートリアルやドキュメントに書くべきかという問いが生じます。
どうでもいい情報なので普通はノイズを減らすため書かないと思います。

^ func (1)

このコード、わたしがDesk言語のユーザだとしたら、正直夜も眠れません。
なので、コンパイラの実装を読み始めるでしょう。そして知るわけです。この括弧が実際にどう扱われているか。
しかし、それが知ったところで、結局夜も眠れない状況は変わりません。
なんで？ってなるからです。コメントに

// 意味論的には変わらないんだからこれは許してやどっちでもいいじゃないか

って書いてあったとしても、美学上許せなくなり、Desk言語を使うのをやめると思います^[6]。

というわけでDesk言語では'beginと'endを使うことにしました。さっきのコードは以下のようにも書くことができます。

'match 'begin
  $ 1;
  do ! 1 ~> *<>;
  ^func 1
'end {
  @"true" *<> => 1
  @"false" *<> => 2
}

結局()より'begin/'endの方が好きです。なぜならコードを眺めたときに(を見ても関数呼び出しのカッコかブロックのカッコかパッと見るだけではわからないからです。
これは同じ記号を別の構文規則に使い回すかぎり回避できないことです。
しかし、同じ記号を使う回すとしても比喩的に同じようなものに使いたいというのが私の美学です。

let x = 1

let x = 1とlet 1を文法としてどちらも許可したいなとなりました。

後者はナンセンスな文じゃないかと思われるかもしれません。
しかしDeskは変数がないといういう話を先ほどしました。
そのためどちらにせよ&'integerとして参照するのでどちらかというと前者がよそ者です。

では前者のxはなんでしょうか。これは型変数名です。「変数名」はないですが、「型変数名」はあります。型変数名で型を明記したのが前者の文です。

ここで問題が生じました。

例えば以下のDeskコードを考えます（$ = letです）。

$ *<'integer> = *<1>

文法はざっくりこんな感じです

expr: "$" [ type "=" ] expr / "*" "<" { expr } ">" / integer;
type: "*" "<" { type } ">" / "'integer";

どうでしょうか？よく考えてみてください。

はい答えですが、*が来た時点でそれが型なのか式なのか区別できません。
ということで、=のところまで先読みしない限りは、どうしようもないというわけです。
LL(1)難しいです。

というわけでlet x = 1という構文はやめました。
かわりに先ほどの型アノテーション構文を使って以下のようにできます。

$ < *<'integer> > = *<1>

特別なシンタックスを作るよりも、シンプルな文法で色々表現できる方が好きです。なので、こちらの方が良かったです。

おわりに

結局LL(1)によって実現できなかった文法よりも今の文法の方が私は好きです^[7]。
もしかしたら他の方にとってもそういうことがあるかも知れないので、ぜひLL(1)で言語を作ってみてください。
LL(1)にこだわらなくてもLL(k)言語の世界に来てもらえると嬉しいです。
（Rustならparolが最高のLL(k)パーサジェネレータです）

あと、ほかにも色々問題に遭遇した気がするので、また思い出して面白い例であれば追記することもあるかもしれません。

あと、投稿時間過ぎてるじゃんと思われるかも知れませんが、日本じゃなかったらまだ6日なので許してください。

脚注

その場でASTを構築してもいい ↩︎
この記事が詳しい: https://lpha-z.hatenablog.com/entry/2019/01/13/231500 ↩︎
シンタックスハイライトが無くても ↩︎
実際には、ユーザの想定と構文が乖離し始めたのはもっと前からかもしれない ↩︎
実際はLL(1)ではなくLL(k)の対抗である ↩︎
ちょっと誇張しちゃったかもしれません。やめるまではさすがにしないかな…… ↩︎
これは正常性バイアスなどがかかってきてる可能性もあります ↩︎

Discussion

ベイン 2022/12/08

(筆者はご存知かもしれませんが、補足として)
以下は左くくりだしによってLL(1)文法で表現できます

式に対する型アノテーションを後置できない
関数呼び出し構文が作れない

// ここで ( T )* はTの0個以上の繰り返しとします

primary_expr
  = variable | integer ;
  
application_expr
  = primary_expr ( "(" arguments ")" )* ;

annotation_expr
  = application_expr ( ":" type )* ;

expr = annotation_expr ;

Ryo Hirayama 2022/12/09

ありがとうございます！記事に追記します