言語実装 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)言語を作るのは難しい、しかしLL(1)言語は素晴らしい](https://cdn-ak-scissors.b.st-hatena.com/image/square/e0a9b0c9e96a6e36b7aecc7c83402f06cd804ba0/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--ZOVtqnAh--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3ALL%2525281%252529%2525E8%2525A8%252580%2525E8%2525AA%25259E%2525E3%252582%252592%2525E4%2525BD%25259C%2525E3%252582%25258B%2525E3%252581%2525AE%2525E3%252581%2525AF%2525E9%25259B%2525A3%2525E3%252581%252597%2525E3%252581%252584%2525E3%252580%252581%2525E3%252581%252597%2525E3%252581%25258B%2525E3%252581%252597LL%2525281%252529%2525E8%2525A8%252580%2525E8%2525AA%25259E%2525E3%252581%2525AF%2525E7%2525B4%2525A0%2525E6%252599%2525B4%2525E3%252582%252589%2525E3%252581%252597%2525E3%252581%252584%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3ARyo%252520Hirayama%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyL2RhYzkwNmNmNDIuanBlZw%3D%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)