python - コンテキストフリーではないプログラミング言語を書き始めるための良いリソースは何ですか?

Question

私は楽しみのためにプログラミング言語を書きたいと思っていますが、私が見たリソースのほとんどは文脈自由言語を書くためのものですが、Pythonのようにインデントを使用する言語を書きたいと思っています。文脈自由にならないでください。

score 19 · Accepted Answer

文脈自由文法とは、単純に、コードを正しく解析するためにシンボルテーブルを必要としない文法です。状況依存の文法はそうです。

Dプログラミング言語は、文脈自由文法の一例です。C++はコンテキストに依存するものです。（たとえば、T * xはxをTへのポインターとして宣言していますか、それともTにxを掛けていますか？シンボルテーブルでTを検索して、それが型であるか変数であるかを確認することによってのみわかります。）

ホワイトスペースはそれとは何の関係もありません。

Dは、構文解析を大幅に簡素化するために文脈自由文法を使用し、単純なツール（構文強調表示エディターなど）で構文解析できるようにします。

score 6 · Accepted Answer

Pythonの解析に関するこのかなりよく書かれたエッセイ、 Python：インデントについての神話を読みたいと思うかもしれません。

yaccのようなものを使用して文脈自由パーサーを作成しようとしたことはありませんが、URLで説明されているように、条件付きレクサーを使用してインデント変更トークンを返すことができると思います。

ちなみに、ここにpython.orgからの公式のpython文法があります：http ：//www.python.org/doc/current/ref/grammar.txt

score 5 · Accepted Answer

まず、この問題について入手できる文献を読んで、この問題に慣れます。Aho らによる古典的なコンパイラの本。アル。数学と計算科学に重きを置いているかもしれませんが、 Jack Crenshaw によるLet's Build a Compiler の記事は、より親しみやすいテキストです。これは、Crenshaw 氏が 80 年代後半に書いた一連の記事であり、これまでに書かれたコンパイラーに関する最も過小評価されているテキストです。アプローチは単純で要点がはっきりしています。Crenshaw 氏は「A" というアプローチがうまくいきます。数晩のうちにコンテンツを簡単に読み進めることができ、コンパイラとは何かをよりよく理解することができます。いくつかの注意点は、テキストの例が Turbo Pascal で書かれていることです。コンパイラは 68K アセンブラを生成します. サンプルはより最新のプログラミング言語に移植するのに十分簡単であり, そのためには Python をお勧めします. しかし, サンプルが示されているようにフォローしたいのであれば, 少なくともTurbo Pascal 5.5と68K アセンブラが必要です.とエミュレータ. テキストは今日でも関連性があり、これらの古いテクノロジーを使用するのは本当に楽しいです. コンパイラに関する最初のテキストとして強くお勧めします。幸いなことに、Python や Ruby などの言語はオープンソース化されており、C のソースコードをダウンロードして学習し、C の仕組みをよりよく理解することができます。

score 3 · Accepted Answer

「コンテキストフリー」は相対的な用語です。ほとんどの文脈自由パーサーは、実際には文脈自由である言語のスーパーセットを解析し、結果の解析ツリーが有効かどうかを確認します。たとえば、次の 2 つの C プログラムは、C の文脈自由文法によれば有効ですが、一方は文脈チェック中にすぐに失敗します。

int main()
{
    int i;
    i = 1;
    return 0;
}

int main()
{
    int i;
    i = "Hello, world";
    return 0;
}

コンテキストの自由はi = "Hello, world";完全に有効な割り当てですが、コンテキストでは、型がすべて間違っていることがわかります。文脈さえあればchar* i;大丈夫です。したがって、コンテキストフリーパーサーは、その代入に何の問題も見ません。コンパイラがエラーをキャッチするのは、(コンテキストに依存する) 型のチェックを開始するまでではありません。

キーボードで生成できるものはすべて、コンテキストフリーとして解析できます。少なくとも、使用されているすべての文字が有効であることを確認できます (表示可能な Unicode 文字のみを含むすべての文字列のセットは、文脈自由文法です)。唯一の制限は、文法がどれほど有用であるか、および結果の構文木に対してどれだけのコンテキスト依存チェックを行う必要があるかです。

Python のような空白に依存する言語では、文脈自由文法の有用性が低下するため、後でより文脈依存のチェックが必要になります (これの多くは、動的型付けによって Python で実行時に行われます)。しかし、コンテキスト依存のチェックが必要になる前に、コンテキストフリーのパーサーができることはまだたくさんあります。

score 2 · Accepted Answer

言語の設計と実装を実際に試してみる場合は、本棚に次のものを追加することをお勧めします。

プログラミング言語語用論、スコット他。
プログラミング言語の設計概念、Turbaketal。
現代のコンパイラ設計、Gruneetal。（私はこれをAhoらの「TheDragonBook」よりも犠牲にしたいと思います。）

次のようなジェントラーの紹介：

Crenshawのチュートリアル（ここで@'Jonas Gorauskas'によって提案されたように）
Parrによる決定的なANTLRリファレンス
マーティンファウラーのDSLに関する最近の研究

実装言語も考慮する必要があります。これは、言語によって促進する内容が大きく異なる分野の1つです。LISP、F＃/ OCaml、GiladBrachaの新しい言語Newspeakなどの言語を検討する必要があります。

score 2 · Accepted Answer

言語でインデントを使用することは、必ずしもその言語の文法が文脈自由であることができないことを意味するわけではありません。つまり、インデントによって、ステートメントが存在するスコープが決まります。ステートメントは、それがどのスコープ内で定義されていても、ステートメントのままです（スコープは、通常、セマンティック解析中に、コンパイラー/インタープリターの別の部分で処理されることがよくあります）。

とはいえ、優れたリソースはantlrツール（http://www.antlr.org）です。ツールの作成者は、antlrを使用した言語のパーサーの作成に関する本も作成しています（http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference）。かなり良いドキュメントとたくさんの例の文法があります。

score 2 · Accepted Answer

チュートリアル/ガイドについては知りませんが、tinypyのソースを見てみることができます。これは、python のような言語の非常に小さな実装です。

score 1 · Accepted Answer

これまでにパーサーを作成したことがない場合は、単純なものから始めてください。パーサーは驚くほど巧妙で、プログラミング言語の構造を勉強したことがない人は、パーサーを書くときにあらゆる種類の問題に直面する可能性があります。

アホ、セティ、ウルマン（「ドラゴンブック」として知られている）を読むのは良い計画です. 他の貢献者とは反対に、最初は Yacc や Bison のような単純なパーサージェネレーターを試してみるべきだと私は言います。 ) Antlr のようなパーサー。

score 1 · Accepted Answer

Aho、Sethi、Ullman による「コンパイラ: 原則、技法、およびツール」を読んだことがありますか? 古典語の参考書です。

/アラン

score 1 · Accepted Answer

パーサーを手動で作成することをお勧めします。その場合、大きな空白があっても実際の問題は発生しません。

パーサージェネレーターを使用する際の主な問題は、パーサーで適切なエラー回復を行うのが難しいことです。自分の言語に IDE を実装する予定がある場合、Intellisence などを機能させるには、適切なエラーリカバリが重要です。インテリジェンスは常に不完全な構文構造に対して機能し、パーサーがユーザーが入力しようとしている構造をより適切に把握できるほど、より優れたインテリジェンスエクスペリエンスを提供できます。

手書きのトップダウンパーサーを作成すると、必要なルールを必要な場所にほぼ実装できます。これにより、エラー回復が容易になります。また、重要な空白を実装することも簡単になります。現在のインデントレベルをパーサークラス内の変数に格納するだけで、新しい行で現在のインデントレベルよりも小さい列位置を持つトークンに遭遇したときに、ブロックの解析を停止できます。また、文法のあいまいさに遭遇する可能性があります。広く使用されているほとんどの「生産」言語には、構文があいまいです。良い例は、C# のジェネリクスです (式コンテキストの "<" にはあいまいさがあり、"より小さい" 演算子または "ジェネリック引数リスト" の開始のいずれかである可能性があります)。手書きのパーサーでは、そのようなあいまいさを解決するのは些細なことです。パーサーの残りの部分への影響は比較的少なく、必要な場所に非決定性を少し追加するだけで済みます。

さらに、自分で言語を設計しているため、その設計は急速に進化すると想定する必要があります (C++ など、標準化委員会を持つ一部の言語ではそうではありません)。自動生成されたパーサーに変更を加えてあいまいさを処理したり、言語を進化させたりするには、文法の大幅なリファクタリングが必要になる場合があり、これはイライラすると同時に時間がかかる可能性があります。手書きのパーサーへの変更、特にトップダウンパーサーの変更は、通常かなりローカライズされています。

パーサージェネレーターは、次の場合にのみ適していると言えます。

IDE を作成する予定はありませんが、
言語の構文が非常に単純である、または
パーサーがすぐに必要になり、ユーザーエクスペリエンスが悪くても問題ありません

score 0 · Accepted Answer

言語が重要なインデントを使用しているからといって、それが本質的に状況依存であることを意味するわけではありません。一例として、Haskellは重要なインデントを利用しており、（私の知る限り）その文法は文脈自由です。

状況依存の文法を必要とするソースの例は、Rubyの次のスニペットです。

my_essay = << END_STR
This is within the string
END_STR

<< self
  def other_method
    ...
  end
end

別の例は、ScalaのXMLモードです。

def doSomething() = {
  val xml = <code>def val <tag/> class</code>
  xml
}

原則として、状況依存言語は、正確な意味で想像するのが少し難しく、したがってあまり一般的ではありません。RubyとScalaでさえ、状況依存機能には言語のマイナーなサブセットしか含まれていないため、実際にはカウントされません。もし私があなたなら、インスピレーションが指示するように文法を定式化し、後日、方法論の構文解析について心配します。思いついたものはすべて、自然に文脈自由、またはそれに非常に近いものになると思います。

最後に、状況依存の解析ツールが本当に必要な場合は、厳密ではない形式の手法を試してみてください。パーサーコンビネーターは、Scalaの構文解析で使用されます。それらにはいくつかの厄介な制限（字句解析なし）がありますが、悪いツールではありません。ANTLRのようなLL（*）ツールも、このような「アドホック」な構文解析エスケープの表現に長けているようです。状況依存の文法でYaccやBisonを使用しようとしないでください。これらは、そのような概念を簡単に表現するために非常に厳密です。

score 0 · Accepted Answer

文脈依存言語？これはインデントされていません: Protium ( http://www.protiumble.com )

python - コンテキストフリーではないプログラミング言語を書き始めるための良いリソースは何ですか?

12 に答える 12

Related

Reference