Clever Geek Handbook

プログラマーの金曜日、または字句解析コードのライブラリを書いたとき

みなさんこんにちは！ プログラマーとして、自分のスキルを向上させる方法を常に探しています。 ある金曜日の夜、私の考えが思い浮かびました-「コンパイラーを書いてくれませんか？」



誰がそれから来たのかを知りたい、猫へようこそ。



「コンパイラの古典理論」V. E. Karpovに基づいて、コンパイルの5つの主要な段階を区別できます。



  1. 字句解析
  2. 解析
  3. 中間コード生成
  4. 最適化
  5. 最終的なオブジェクト、コードの生成


5つのパートすべてについて、たくさんの文章や記事を書くことができます。 しかし、今日は、最初の2つと、別のライブラリでどのように構造を選択したかについて説明します。



コンパイラのほんの一部であっても、書くことを決めたとき、私はどの言語を書いているのか考えていませんでした。そのため、結果はどの言語の字句解析および構文解析のためのライブラリでした。



トークン化



構文および語彙ツリーを構築し、結果のコードを生成し、他のおいしいことを行う前に、ソースコードを行、文字、数字に分割する必要があります。



各要素には、正確に定義されたタイプがあります。 未定義のタイプトークンは、解析中に構文エラーと見なされます。



コンパイルのコンテキストでは、ソースコードはソースマップと見なされます。プログラマーからのフィードバックとソースコードの構文エラーを示すために、字句解析のプロセスに保存することをお勧めします。



単純な正規表現を使用して、ソースコードをトークンの配列に分割できます。 



/\S+/gm


改行解析、タブ解析、スペース解析などの追加の解析条件に応じて変更できます。



分離の結果は、ソースコードの単語の配列になります。単語はスペースからスペースへと解析されます。 そのような設計： 



 let hello = 'world';


次のトークンセットに変換されます。 



 ["let", "hello", "=", "'world';"]


トークンの最終セットを取得するには、追加の正規表現を使用して各トークンを通過する必要があります。 



 /(\W)|(\w+)/gm


結果は、必要なトークンのセットになります。 



 ["let", "hello", "=", "'", "world", "'", ";"]


受け取ったすべてのトークンは、ソースマップ内のインデックスと共に配列に書き込みます。



字句解析



トークンの配列ができたので、解析に渡すためにそれらのタイプを決定する必要があります。



トークンとそのタイプを定義するアルゴリズムはLexerと呼ばれます

Lexerが定義するトークンとそのタイプは-Tokenと呼ばれます



各トークンには、一意に定義されたタイプを含めることができます。例： 



 ['let', 'const', 'var'] // Keywords ['=', '+', '-', '*', '/'] // Operators  ..


しかし、私は、いわゆるSolver'ovを使用して、トークンのタイプを決定するためのスキームを実装しました。

次のように機能します。



1.トークンタイプの定数を定義します。 



 const DefaultTokenTypes = { KEYWORD: "Keyword", IDENTIFIER: "Identifier", OPERATOR: "Operator", DELIMITER: "Delimiter", LINEBREAK: "Linebreak", STRING: "String", NUMERIC: "Numeric", UNKNOWN: 'Unknown' };


2.次に、いわゆるSolver'yを決定する必要があります。 



 const solvers = {}; solvers[MyTokenTypes.KEYWORD] = { include: [ 'const', 'let' ] }; solvers[MyTokenTypes.NUMERIC] = { regexp: /^[0-9.]*$/gm }; solvers[DefaultTokenTypes.STRING] = { type: StringSolver, delimiters: ['"', "'", '`'] }; solvers[MyTokenTypes.IDENTIFIER] = { regexp: /^[a-zA-Z_][a-zA-Z_0-9]*$/gm }; solvers[MyTokenTypes.DELIMITER] = { default: true };


ご覧のとおり、トークンにはさまざまな設定があります。



include-一致することにより、トークンのタイプを判別できる単語の配列。

regexp-同時に、トークンのタイプを判別できる正規表現。

デフォルト -未定義トークンの標準タイプ。



typeパラメーターに注目することもできます。これは、このソルバーがtypeで指定されたものから継承されることを示します



この場合、ソルバーは、 区切り文字で指定された文字の 1つで囲まれた文字列を定義します



3.トークン配列にソルバーを使用して、型付きトークンの配列を取得します。 特定のソースコードの場合： 



 let a = 50;


次のツリーを取得します。 



 [ { "type": "Keyword", "value": "let", "range": [0, 3] }, { "type": "Identifier", "value": "a", "range": [4, 5] }, { "type": "Delimiter", "value": "=", "range": [6, 7] }, { "type": "Numeric", "value": "50", "range": [8, 10] }, { "type": "Delimiter", "value": ";", "range": [10, 11] } ]


rangeは、ソースコード内のフラグメントの始まりと終わりです。



解析



トークンの配列を受け取ったら、それらを解析し、ソースコードの構文構造（ツリー）を決定する必要があります。



解析にはさまざまなオプションがありますが、トップダウンの直接アルゴリズムを選択しました。



トークンは、テンプレートの配列を使用して1つずつ解析されます。 テンプレートが現在のトークンのシーケンスと一致する場合-構文ツリーで、新しいブランチが作成されます。



配列からの1つのテンプレートの例： 



 let declaration = new SequenceNode({ tokenType: MyTokenTypes.KEYWORD, type: MyNodeTypes.DECLARATION, sequence: [ {type: MyTokenTypes.KEYWORD}, {type: MyTokenTypes.IDENTIFIER}, {type: MyTokenTypes.DELIMITER}, {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]}, ';' ], onError: (e) => { //e - Syntax error } });


tokenType-一致のチェックを開始するトークンを記述します。

type-ノードのタイプを記述します。トークンタイプと同様に、すべてのタイプも定義する必要があります。

シーケンス -シーケンスの配列。トークンのタイプ、特定の値、または構文ツリーの他のノードが含まれます。

onError-構文エラーが発生したときに機能するコールバック。このノードの解析中に、エラーのタイプ+ソースコード内の場所を返します。



このノードのシーケンスを分析しましょう： 



 [ {type: MyTokenTypes.KEYWORD}, //   ->     {type: MyTokenTypes.IDENTIFIER},//   + 1 ->    {type: MyTokenTypes.DELIMITER},//   + 2 ->    {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]},//   + 2 ->      ';' //   + 3 ->      ],


さまざまな目的のために、ノードのいくつかのバリエーションを実装しました。トークンのシーケンスの定義、要素のグループ（引数、ブロック）の定義です。 これにより、矢印関数を問題なく解析できます。



このライブラリのドキュメントで実装したソルバーとノードのすべてのバリエーションについて読むことができます。



素材



→ソースリンク： Tyk

→ 古典的なコンパイラ理論


More articles:


All Articles