⭐️ 🍱 🌄 Elixir：構文解析を正しく準備する-yeccとleex 😛 👩🏽‍🎨 👭

字句解析（トークン化）と解析は、コンピューターサイエンスとプログラミングで最も重要な概念の一部です。これらの概念は膨大な量の理論的知識に基づいていますが、 実際には多くの概念があるため、今日は説明しません。さらに、「科学」による構文解析のアプローチは、深刻な嫌悪感と恐怖を引き起こす可能性があります。一方、実用的なアプリケーションは非常にシンプルで簡単です。理論についてもっと知りたい場合は、ウィキペディア（字句解析と構文解析）に行くか、ドラゴンの楽しい本を読んでください（一般的なプログラマー全員が読むことをお勧めします）。

普通の人は、レクサーやパーサーを使うことを恐れて、代わりに正規表現で自転車を書きます。明らかな複雑さが理由であるように思えます。この投稿では、彼女を非難しようとします！

なんで？

まず、レクサーとパーサーは通常一緒に使用されますが、これは一般的には必要ありません。レクサーを使用して、文字列をトークンのセットにトークン化できます。または、パーサーを使用して、あらゆる文法を理解できます。

私は、人々はテキストを解析し理解するためにしばしば正規表現を使うと言った。構文解析のための単純なタスクで動作するという事実にもかかわらず、ほとんどの場合、自転車は非常に壊れやすく、まったく乗りません。さらに、正規表現は、記述しようとする文法が非常に限られています（たとえば、正規表現を使用してhtmlを解析してみてください）（ 翻訳者 ：実際にはそうではありません。ただし、アセンブラーでクラスターアプリケーションを作成することもできます。問題の規模はほぼ同じです）。したがって、より強力なものが必要になる場合があります。

こんにちは`leex`

と`yecc`

と`yecc`

Erlangには 、解析を優れたものにする2つの組み込みモジュール、 leexとyeccがあります。名前に対応するleexはレクサーです。特定の構文でファイルを読み取り、 erlangモジュールを（ *.erl

ファイルの形式で）生成し、コンパイルしてトークン化に使用できます。 yeccは基本的に同じように動作し、レクサーではなくパーサーを生成するだけです。

モジュールはアーラン （ 解析ツールグループのどこか）のバッテリーとして利用できるため、理論的には、問題を解決できるすべての場所で非常にうまく使用できます。

小さくて虚弱でありがたい例

何かを説明する各記事には例を必要とするので、それをやってみましょう： Elixirの list

を現在化し、解析します。これは、単に文字列で書かれた数字とアトムのみで構成できます。最終目標は、次の行から元のElixirリストを取得することです。

 iex> ListParser.parse("[1, 2, [:foo, [:bar]]]") [1, 2, [:foo, [:bar]]]

これはまったく無意味なので、素晴らしい例として取り上げましょう。

レクサー

まず、行をトークン化する必要があります。トークン化とは、文字列をトークンのリストに変換することを意味します。トークンのリストは、通常の文字のリスト（文字列）と比較して基本的にあまり構造化されていません。

たとえば、トークンの1つは4917

などの数字にすることができます。数字4917

構造は、文字のリスト[?4, ?9, ?1, ?7]

よりも少し多くなっています。

リストのトークン化は一般的に非常に簡単です-個別にトークン化します：

括弧（左[

および右]

）、
コンマ
数字
原子。

簡単にするために、 :foo

または:foo_bar

などの単純なアトムのみを扱い、ハード:'foo and bar'

または"hello world"

扱いません。

このような単純な構文の独自のトークナイザーを非常に簡単かつ迅速に作成できますが、 leexを使用すると作業が大幅に簡素化され、非常に単純な構文でレクサーを作成できます。基本的に、私たちはトークンをレギュラーに設定し、それらをこのトークンを表すErlang式に関連付けます。レギュラーはそのような作業には悪であると述べました。はい、通常、再帰的なデータ構造のために解析には悪いですが、文字列を1次元構造に分割するには優れています。

これらのルールの構文は簡単です。

正規表現：アーランコード。

ここで、 Erlangコードでは、レクサーにトークンを生成させたい場合は{:token, value}

タプルを返す必要があります（実際にはElixirではなくErlangで書いた場合は{token, Value}

タプル）。

レクサーは非常にシンプルに見えます。

 Rules. [0-9]+ : {token, {int, TokenLine, TokenChars}}. :[a-z_]+ : {token, {atom, TokenLine, TokenChars}}. \[ : {token, {'[', TokenLine}}. \] : {token, {']', TokenLine}}. , : {token, {',', TokenLine}}.

{:token, Value}

を返し、一致するトークンを取得する必要があることをleexに伝えます（したがって、タプルの最初の要素は:token

）。これを字句解析の結果に追加します。

TokenLineとTokenCharsは、すべての正規表現に続くErlang式にleexが代入する変数です。これらの変数には、関連付けられたトークンの文字列と、関連付けられたトークンの内容が文字のリストの形式で含まれています。

yeccはこの形式を必要とするため、2要素または3要素のタプルをトークン値として使用します。トークンの意味に興味がある場合があるため、3要素のタプルを使用します。ただし、場合によっては、トークン自体の値は重要ではないため（たとえば、コンマの場合）、2要素のタプルで十分です。このタイプのトークンは必須です。この場合、 yeccは明確なエラーメッセージを簡単に提供できます。

見つかったすべてのトークンを保存する必要はありません。簡単にドロップできます。これを行うには、 :skip_token

をタプルに渡し:skip_token

。最も一般的な用途は、スペースを省略することです。

 [\s\t\n\r]+ : skip_token.

レギュラーは非常に簡単に吐き気を催すことがありますが、フォームを使用して単純に定義できます

エイリアス=正規表現

このような定義は、ルールのリストの前のファイルの先頭に配置されます。それらを通常の定義で使用するには、 {}

ラップできます。

 Definitions. INT = [0-9]+ ATOM = :[a-z_]+ WHITESPACE = [\s\t\n\r] Rules. {INT} : {token, {int, TokenLine, TokenChars}}. {ATOM} : {token, {atom, TokenLine, TokenChars}}. \[ : {token, {'[', TokenLine}}. \] : {token, {']', TokenLine}}. , : {token, {',', TokenLine}}. {WHITESPACE}+ : skip_token.

レクサーを試す準備ができました。まず、拡張子.xrl

ファイルを作成する必要があります。次に、このファイルを次のように.erl

ファイルとしてerlangモジュールに.erl

ます:leex.file/1

最後に、新しく生成されたErlangモジュールをコンパイルできます。ほとんどのアーランモジュールはバイナリ文字列ではなく文字のリストを受け入れるため、二重引用符ではなく一重引用符で囲む必要があることに注意してください。（注： Erlangは、 'foo bar'

などの複雑なアトムに単一引用符を使用し'foo bar'

。これらのアトムは、正規表現では表現できませんが、覚えていますか？）

 iex> :leex.file('list_lexer.xrl') iex> c("list_lexer.erl") iex> {:ok, tokens, _} = :list_lexer.string('[1, [:foo]]') iex> tokens {:"[", 1}, {:int, 1, '1'}, {:",", 1}, {:"[", 1}, {:atom, 1, ':foo'}, {:"]", 1}, {:"]", 1}]

かっこいい！ leexは、レクサーに関連付けるアーランコードを定義する機能も提供します。これは、 Erlang code.

セクションを使用して実装されErlang code.

.xrl

ファイルの最後に。この利点を利用して、アトミックトークンを直接アトムに変換できます。

 ... {INT} : {token, {int, TokenLine, list_to_integer(TokenChars)}}. {ATOM} : {token, {atom, TokenLine, to_atom(TokenChars)}}. ... Erlang code. to_atom([$:|Chars]) -> list_to_atom(Chars).

to_atom/1

は、アトムトークンの最初の文字（コロン、 Erlangの世界では$:

:)をto_atom/1

他のすべてをアトムに変換します。また、 list_to_integer/1

を使用して、トークン番号を直接数値に変換します。

レクサーは完全に次のようになります。

 Definitions. INT = [0-9]+ ATOM = :[a-z_]+ WHITESPACE = [\s\t\n\r] Rules. {INT} : {token, {int, TokenLine, list_to_integer(TokenChars)}}. {ATOM} : {token, {atom, TokenLine, to_atom(TokenChars)}}. \[ : {token, {'[', TokenLine}}. \] : {token, {']', TokenLine}}. , : {token, {',', TokenLine}}. {WHITESPACE}+ : skip_token. Erlang code. to_atom([$:|Chars]) -> list_to_atom(Chars).

すべてが期待どおりに機能します。

 iex> {:ok, tokens, _} = :list_lexer.string('[1, :foo]') iex> tokens [{:"[", 1}, {:int, 1, 1}, {:",", 1}, {:atom, 1, :foo}, {:"]", 1}]

パーサー

これで、単一レベルのトークンリストができました。それらに何らかの構造を与え、リストをElixirに変換したいのです。トークンのリストを解析する必要があります。パーサーの動作は文法に基づいています。文法は、トークンの構造化方法を記述するルールのリストです。

もちろん、独自のパーサーを作成することもできますが（独自のレクサーよりもはるかに複雑ですが）、 yeccを使用する方が簡単です。

小さな余談：この時点で、パーサーとレクサーの名前は意味をなさないと考えるかもしれません。これは実際にはそうではありません。 Obは、 lex lexerとyacc parserの2つの非常に有名なプログラムにちなんで名付けられました。 アーランの男たちはそんなに狂っていないように見える？

yeccに戻る。主な構文要素はルールで、次の形式で説明されています。

左側->右側：Erlang式。

左側にトークンカテゴリがあり、右側にトークンリストカテゴリがあります。トークンのカテゴリには、デッドエンドと非デッドエンド（ ターミナルと非ターミナル ）の2つのタイプがあります。行き止まりは、自身に何も含まれていないトークンです。非デッドロック-それぞれその逆。

たとえば、 :"["

または{atom, Atom}

トークンは行き止まりです。デッドエンドリストは、デッドエンド要素のリストで表すことができます。

 list -> '[' ']'. % or... list -> '[' elems ']'. %  , '%'       Erlang.

ご覧のように、各カテゴリに対していくつかの条件を選択できます。カテゴリは、リストされた値のいずれかを取ることができます（ ORと考えてください）。

elems

自体は非デッドロックです。単一の要素、または要素+コンマ+要素のリストとして表すことができます。

 elems -> elem. elems -> elem ',' elems.

したがって、 elem, elem

またはelem, elem

などになります。

elem

自体も非デッドロックです。これは、数値、アトムまたはリストを表します。リスト内のリストのネストがいかにエレガントに想像できるかに注目してください。

 elem -> int. elem -> atom. elem -> list.

クラサバ！

すべての非デッドエンド要素は、ある段階でデッドエンドに開かれている必要があります。何にも拡張されない非デッドエンド要素を持つことは不可能です。 また、yeccでは、ユーザーがどのカテゴリが端末で、どのカテゴリがファイルの先頭にないかを判断する必要があります。

 Terminals '[' ']' ',' int atom. Nonterminals list elems elem.

ルート要素を定義することもできます。これは、元の文法を生成する非デッドロックの開始要素になります。私たちの場合、これはリストです：

 Rootsymbol list.

ほぼ完了です！解析されたばかりのリストをElixirリストに変えるだけです。これは、各解析ルールに関連付けられたErlangコードで行います。これらの式には、いくつかの特別なアトムがあります： $1

、 $2

、 $3

など。 yeccは、 Erlangコードの結果を置換します。これは、ルールの右側と同じインデックスを持つカテゴリに関連付けられています。私はあなたが「シールド」と思ったのを聞いています。あなたは正しいです、あなたは例なしでは理解できません：

 list -> '[' ']' : []. % an empty list translate to, well, an empty list list -> '[' elems ']' : '$2'. % the list is formed by its elements elems -> elem : ['$1']. % single-element list (and base case for the recursion) elems -> elem ',' elems : ['$1'|'$3']. % '$3' will be replaced recursively elem -> int : extract_token('$1'). elem -> atom : extract_token('$1'). elem -> list : '$1'. % ,      Erlang. Erlang code. extract_token({_Token, _Line, Value}) -> Value.

すべて準備完了です！パーサーの最終バージョンは次のようになります。

 Nonterminals list elems elem. Terminals '[' ']' ',' int atom. Rootsymbol list. list -> '[' ']' : []. list -> '[' elems ']' : '$2'. elems -> elem : ['$1']. elems -> elem ',' elems : ['$1'|'$3']. elem -> int : extract_token('$1'). elem -> atom : extract_token('$1'). elem -> list : '$1'. Erlang code. extract_token({_Token, _Line, Value}) -> Value.

.yrl

行ったように、 yeccファイル（拡張子.yrl

）からErlangファイルを作成できるようになりました 。

 iex> :yecc.file('list_parser.yrl') iex> c("list_parser.erl") iex> :list_parser.parse([{:"[", 1}, {:atom, 1, :foo}, {:"]", 1}]) {:ok, [:foo]}

動作します！

タンクを接着する

レクサーの結果をパーサーand-iiにすぐに投げることができます：

 iex> source = "[:foo, [1], [:bar, [2, 3]]]" iex> {:ok, tokens, _} = source |> String.to_char_list |> :list_lexer.string iex> :list_parser.parse(tokens) {:ok, [:foo, [1], [:bar, [2, 3]]]}

すごい！

わかりません、エリクサーはどこですか？

.xrl

および.yrl

ファイルから手動でErlangファイルを生成し、それらのファイルをすでに非常に迅速にコンパイルします。幸いなことに、 Mixは私たちのために何でもできます！

Mixは、「コンパイラ」の概念をサポートしています。つまり、あなたが想定できることを正確に実行し、コンパイルします。 MixはErlang用のコンパイラ（インストールされているErlangを介して.erl

ファイルをコンパイルする）、Elixir用の別のコンパイラを提供しますが、 leexおよびyecc用のコンパイラもあります。実際、これらはデフォルトでオンになっています。これは、 Mixプロジェクト内でMix.compilers/0

関数を呼び出すことで確認できます（ Mix.compilers/0

：だけでなく。ところで、デフォルトでは実際に確認してください！）：

 iex> Mix.compilers() [:yecc, :leex, :erlang, :elixir, :app]

Mixプロジェクトでこれをすべて正常に動作させるために最後に行う必要があるのは、プロジェクトのsrc/

ディレクトリに.xrl

および.yrl

を配置すること.xrl

そして、モジュールはコンパイル後にコードに表示されます。

 mix new list_parser mkdir list_parser/src mv ./list_parser.yrl ./list_lexer.xrl ./list_parser/src/

そして、小さなラッパーを追加します。

 # ./list_parser/lib/list_parser.ex defmodule ListParser do @spec parse(binary) :: list def parse(str) do {:ok, tokens, _} = str |> to_char_list |> :list_lexer.string {:ok, list} = :list_parser.parse(tokens) list end end

ゲシェフトはここにありますか？

上記のすべては非常に抽象的に見えるかもしれませんが、 leexとyeccには10億通りの使用方法があると確信しています。たとえば、最近、 ElixirのgettextのGNUバインディング開発の一環として、 PO

ファイルのパーサーを作成しました。私はyeccを使用してパーサーを説明しました。それはすべて非常に宣言的でクリーンで理解しやすい文法（ここを参照）をもたらし、一般的に私は非常に魅力的で幸せです。 leexを使用しなかったのは、主に、このような単純なタスクには強力すぎるツールであると思われるためであり、独自のレクサーを作成しました（これも可能です）。

別の例？ええ、1つあります。少なくとも、 エリクサーについて目の前で聞いたことはありますか？言語は非常に悪く、 Erlang VMの最上部に構築され、並列プログラミング、パッド抵抗に重点を置いています...はい、 yeccを解析しました :)

要約する

レクサーとパーサーを簡単に作成して、 Elixirリストのダンプ行を実際のElixirリストに変換しました。 leexを使用してレクサーを生成し、 yeccを使用してパーサーを生成しました。

これらのツールの最も基本的な機能のみを調査しました。より複雑になる可能性があります（ yeccが知っている場合、 yeccはLALRパーサーを生成します）。しかし、このために- ドキュメントへようこそ。

Elixir：構文解析を正しく準備する-yeccとleex