パパカルロとインクリメンタルコンパイラ

同僚



プログラミング言語 Colin Macmillenの開発者の Habr Checklistに、新しいプログラミング言語の問題に関する翻訳記事があったことを覚えていますか？ 記事は驚くばかりです！ まだ読んでいない場合は、必ずチェックしてください。



Colinが語っている重要な問題の1つは、優れたIDEのない言語は誰も必要としないことです。 もちろん、プログラミング言語の開発者が直面する問題はこれだけではありません。 しかし、多くの編集者がサポートしている言語であるceteris paribusがすでに優れた競争上の優位性を持っていることに全員が同意すると思います。



偶然にも、IDEのコンパイラと言語プラグインを数年間扱ってきました。 そして、多くの最新のコードエディターとの統合がはるかに簡単になるコンパイラーの作成方法について、私の経験を皆さんと共有できることを嬉しく思います。 同時に、この分野での私自身の開発についても少しお話しします。

問題

私たちの多くが私たち自身の言語を作成することを考えたことは秘密ではありません、友達もいます。 このプロセスは非常に創造的で魅力的です。 詳細に説明しない場合、一般的に、コンパイラは次のコンポーネントで構成されます。

• ソースコードを解析し、構文ツリーに変換するパーサー 。
• 言語の本質を互いに結びつけるセマンティックアナライザー ：名前、変数、クラス間のリンク。
• マシンコードの生成と最適化を担当するバックエンド 。

ほとんどのコンパイラは1つのパスで動作します。プログラマはソースを送信し、出力で完成したプログラム、または修正が必要な構文エラーのリストを受け取ります。 ソースのサイズと言語の複雑さに応じて、コンパイルプロセスには数秒から数分かかることがあります。



コードエディタ用の言語プラグイン、たとえばJavaのような静的型付けの言語用のプラグインを開発する場合、このアプローチは適用できません。 つまり、コンパイラーがプロジェクト全体を再コンパイルし、1回の小さな変更の後、コードにエラーがないかどうかを確認するまで、プログラマーを待たせることはできません。 もちろん、構文の強調表示ほど簡単ではないが、少なくともリアルタイムで構文エラーを表示したい場合。



プロジェクトを完全に再コンパイルするアプローチは、コンパイラバックエンドを無効にしても、IDEには適用されません。 プロジェクト内のソースコードの量が増加しても、コンパイル時間は増加します。



いわゆるインクリメンタルアプローチが助けになります。 アイデアは、コンパイラがその作業のほぼすべての中間結果、つまり個々のファイル、その構文ツリー、さらには個々の言語トークンのコンパイル結果をキャッシュするということです。 また、ユーザープログラマーがソースコードに小さな変更を加えた場合、コンパイラはこれらの変更に関連するローカルコードの一部のみを解析します。 したがって、コンパイラーのパフォーマンスは、コード全体のボリュームではなく、コードに加えられた変更に比例します。



残念ながら、インクリメンタルコンパイラ用のパーサーを開発することは、かなり重要な作業です。 特に、パーサーが構文エラーを含むコードを解析できることを考慮してください。 たとえば、プログラマーがクラス宣言の先頭で構文エラーを作成した場合：

import javax.swing.JApplet; import java.awt.Graphics; public class Hello extends JApplet { int x = //    ,    . public void paintComponent(final Graphics g) { g.drawString("Hello, world!", 65, 95); //         . } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以下のメソッドでは、プログラマーはエディターが理解できるコードを記述することができます。ユーザーは、コード補完、定義へのジャンプ、および他の多くのIDE機能の両方にアクセスできます。



インクリメンタルパーサーの既製のジェネレーターとコンビネーターは非常に少数であり、非常に具体的です。 ANTLRのような巨大な製品では、最新バージョンが何らかの形式で増分解析のサポートを追加したとしましょう 。 ANTLRはかなり重い製品であり、JavaScriptのPEG.jsのような通常の（非インクリメンタル）パーサーのPEGコンビネーターよりも作業がはるかに難しいと言わなければなりません。



今日では、まれな例外を除いて、個々のテキストエディタまたはIDEの言語プラグインの開発が多かれ少なかれ「膝にかかっている」という悲しい事実を認めなければなりません。 そして、それはかなり難しい仕事であり、そこから独立した製品がしばしば成長します。

解決策

現在、IDE用の言語プラグインを作成するタスクを大幅に簡素化するのに役立つPapa Carloプロジェクトに取り組んでいます。 これはロック上のライブラリであり、言語プラグイン、または本格的なインクリメンタルコンパイラの作成に適した、完全に機能するインクリメンタルパーサーを構築できます。



開発者は、このライブラリのAPIを使用して、Rockのコードに言語の文法を直接設定します。 また、結果のパーサーは構文エラーを含むコードを含めて解析し、「そのまま」構文ツリーを直接作成できます。 コード生成に追加のステップはありません。 パーサーは、同じJParsec for Javaのような通常のパーサーの多くの最新のコンビネーターのように、ランタイムで作成されます。



次に、開発者は、作成したコンパイラの出力を、サポートしたいコードエディタのAPIに関連付けます。 たとえば、Sublime Text APIを使用します 。



私の意見では、このアプローチは、コンパイラと言語プラグインを最初から別々に開発するよりもはるかに簡単です。



プロジェクトはまだ完了していませんが、 Apacheライセンスの下でGitHubに作業バージョンをアップロードし、いくつかの実験を実施しました。 たとえば、JSONファイル用のインクリメンタルインクリメンタルパーサーがあります。 パーサーは、Scalaの1つの文法ファイルによって定義されます。 パーサーコードはここにあります 。



テストの1つでは、次のjsonが入力で提供され、明示的な構文エラーが含まれます。

 { "key 1": "hello world", "key 1.1": "key 2": ["array value 1", "array value 2", "array value 3"], }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それにもかかわらず、出力では、パーサーはエラーを含まない部分を非常にうまく解析します。 そして彼はそのようなツリーを作成します：

 object 1 { entry: entry 27 { key: "key 1" value: string 26 { value: "hello world" } } entry: entry 25 { key: "key 1.1" value: string 24 { value: "key 2" } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

もちろん、構文エラーを指す：

  > code mismatched: { "key 1": "hello world", "key 1.1": "key 2"<<<: ["array value 1", "array value 2", "array value 3"],>>> }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、600行のサイズの比較的大きなファイルが導入される別の例は、はるかに興味深いものです。 最初の開始後、パーサーは安全に構文ツリーを作成し、0.27秒動作します。 一般に、これでは十分ではありません。 次に、ファイルに小さな変更が2回行われ、2回目と3回目の開始時に、パーサーはそれぞれ0.007秒と0.008秒動作します。 同様に、これらの新しいファイルの600行すべての構文ツリーを作成します。 この効果は、以前のパーサーの起動中に取得されたキャッシュを使用することにより正確に達成されます。

入力ファイル	サイズ（行）	前との違い（行）	AST解析および構築時間（ミリ秒）
step0.json	634	-	270
step1.json	634	1	7
step2.json	634	2	8

結論と参考文献

残念ながら、この記事の形式では、詳細を省略して、最も一般的な用語でのみトピックの概要を説明することができます。 それでも、インクリメンタルコンパイルの問題の本質と、コードエディタの言語拡張機能の仕事を伝えることができたと思います。



IDEの拡張機能を作成した経験のある開発者がまだいると確信しています。 あなたの追加やコメントを聞くのは非常に興味深いでしょう。



最後に役立つリンクをいくつか紹介します。

• 文法キット 。 IntelliJ Ideaのプラグイン開発で使用されるJetBrainsパーサーコンストラクター。
• Java開発ツール 。 Eclipseが内部的に使用するJavaインクリメンタルパーサー。
• ゆでた 。 ScalaおよびJava用の非増分パーサーコンストラクター。 彼は通常の非増分パーサーを構築しているという事実にもかかわらず、Scalaコミュニティーで最も開発された有名なパーサーコンストラクターの1つです。 私の意見では、プロジェクトは注目に値します。
• パパ・カルロ 。 前述のScala用の独自のインクリメンタルパーサーコンストラクター。