パーサーをゼロから作成する：悪魔はとてもひどいですか？

最後のトピックでは、友人と私がエンターテイメントのために.NETプラットフォーム用に独自の組み込みプログラミング言語を書くことにした方法について話しました。 最初のバージョンには重大な欠点がありました-パーサーはサードパーティのライブラリを使用してF＃に実装されました。 このため、多くの依存関係が必要であり、パーサーの動作は遅く、そのサポートは非​​常に退屈な仕事でした。



明らかに、パーサーはC＃で書き直す必要がありましたが、パーサーをゼロから作成することを考えたとき、他にも急を要するものがたくさんありました。 したがって、タスクはスローされ、ほぼ6か月間延期され、圧倒されるように見えましたが、最終的には4日で完了しました。 カットの下で、サードパーティのライブラリを使用せずに心に触れることなく、かなり複雑な文法のパーサーを実装する便利な方法と、これによりLENS言語がどのように改善されたかについて説明します。



しかし、まず最初に。

最初のパンケーキ

前述のように、パーサーコアとしてFParsecライブラリを使用しました 。 この選択の理由は客観的というよりも歴史的です。軽量の構文が好きで、F＃を使用して練習したかったので、ライブラリの作成者は電子メールでいくつかの質問に非常に素早く答えました。



このプロジェクトのこのライブラリの主な欠点は、外部の依存関係でした。

• 約10メガバイトのF＃ランタイム
• 450 kbのFParsecビルド

さらに、コンパイラ自体が、パーサー、構文ツリー、エントリポイントの3つのアセンブリに分割しました。 パーサーアセンブリは、130 kbという印象的なものでした。 組み込み言語の場合、これは絶対に下品です。



別の問題はエラーの表示でした。 誤って入力されたプログラムを使用してローカルDSLでの簡単な文法記録を行うと、予想されるトークンをリストする読み取り不能なエラーが生成されました。

> let x = > :           'new'  ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

カスタムエラー処理は可能ですが、DSLは明らかにそれを対象としていません。 文法の説明はくなり、完全にサポートされなくなります。



別の不快な瞬間は仕事のスピードでした。 最も単純なスクリプトでさえ、「コールドスタート」コンパイルでは、私のマシンで約350〜380ミリ秒かかりました。 同じスクリプトを再起動するのに5〜10ミリ秒しかかからなかったという事実から判断すると、遅延はJITコンパイルが原因でした。



すぐに予約します。ほとんどの実際のタスクでは、解析に費やされる数百ミリ秒の追加ライブラリや数百ミリ秒よりも、開発時間が非常に重要です。 この観点から、ハンズツーハンドパーサーの作成は、より教育的または難解な演習です。

理論のビット

バキューム内の球状パーサーは、ソースコードを受け取り、使用する仮想マシンまたはプロセッサのコードを生成するのに便利な中間表現を返す関数です。 ほとんどの場合、この表現はツリー構造を持ち、 抽象構文木 -ASD（外国文学では-抽象構文木、AST）と呼ばれます。



ツリー構造は、多くの最新の仮想マシン（JVMや.NETなど）で使用されているスタック構成と深く関係しているという点で特に優れています。 この記事では、コード生成については考慮しませんが、構文解析ツリーの要素については、パーサーの結果として随時言及します。



したがって、入力には行があります。 文字セット。 この形式で直接操作するのはあまり便利ではありません。スペース、改行、コメントを考慮する必要があります。 生活を簡素化するために、パーサー開発者は通常、分析をいくつかのパスに分割します。各パスは1つの簡単なタスクを実行し、その作業の結果を次のパスに渡します。

1. 字句解析器： string -> IEnumerable<Lexem>
   
   
   
   
2. パーサー： IEnumerable<Lexem> -> IEnumerable<Node>
   
   
   
   
3. セマンティックアナライザー： IEnumerable<Node> -> ?
   
   
   
   

セマンティックアナライザーは純粋に個別のものであるため、その説明はこの記事には含まれていません。 それにもかかわらず、最初の2つのアナライザーについて、いくつかの便利なトリックを共有します。

字句解析器

要件：

• 作業速度
• 拡張のしやすさ
• 実装のしやすさ
• ソース追跡

字句解析アルゴリズムは簡単です。行を左から右にスキャンし、行の現在の位置と既知の各トークンを一致させようとします。 一致が成功した場合、レクサーは前のトークンが占有した文字数だけ行内を右に移動し、行の末尾まで新しいトークンを検索し続けます。 ほとんどの文法のスペース、タブ、および改行は単純に無視できます。



すべてのトークンは、最初に静的と動的の 2つのタイプに分割する必要があります 。 最初の行には、通常の行で表現できるトークン（キーワードと演算子）が含まれています。 識別子、数字、文字列などのトークンは、正規表現を使用して簡単に説明できます。



静的トークンには、 演算子とキーワードに分ける理由があります。 キーワードは、それに続く文字が識別子に対して有効でない場合（またはさらに-行の終わり）にのみ一致します。 そうしないと、キーワードが先頭に一致する識別子の問題が発生します。たとえば、 "information" -> keyword(in), keyword(for), identifier(mation)



です。





利点：

• 高速に動作します
• 基本的なデバイスで、30分で書くことができます
• 新しいトークンは非常に簡単に追加されます
• この方法は多くの文法に適しています

短所：

• 舌を有意なスペースで解析する際にタンバリンで踊る
• トークンを宣言する順序は重要です。長さでソートすることをお勧めします

パーサー

要件：

• 文法を変更するときの簡単な拡張
• 詳細なエラーメッセージを説明する機能
• 無限のポジションを先読みする機能
• ソースコード内の位置の自動追跡
• 簡潔、元の文法に近い

パーサーを書くときの生活を簡素化するために、特別な方法で文法を整理する必要があります。 複雑なデザインはありません！ すべてのルールは、3つのタイプに分類できます。

• 説明-1つの特定のノード：
  
  (var_expr = "var" identifier "=" expr)
  
  
  
  
  
  
• 繰り返し-1つの特定のノードが何回も繰り返され、場合によってはセパレータが付きます：
  
  main = { stmt ";" }
  
  
  
  
  
  
• 代替 -複数ノードの選択
  
  (stmt = var_expr | print_expr | assign_expr | other)
  
  
  
  
  
  

説明ルールはステップに分割されます。現在のトークンのタイプを確認し、次のトークンに移動して、ルールの最後まで続きます。 チェックされた各トークンで、いくつかのアクションを実行できます。不一致の場合に詳細なエラーを表示したり、ノードに値を保存したりします。



列挙規則はループです。 値のシーケンスを返すために、C＃にはyield return



を使用してジェネレーターを作成するための非常に便利な機能があります。



次に、代替ルールは、元の状態にロールバックできる特別なラッパーを使用してバリアントルールを呼び出します。 ルールは、少なくとも1つのルールが一致するまで順番に呼び出され、合体（ ??



）演算子に関連付けられます。



好奇心itive盛な読者は尋ねます：

-それはどうですか、彼らは順番に呼び出されますか？ しかし、主要なチェックはどうですか？ たとえば、次のように：

 if(CurrentLexem.Type == LexemType.Var) return parseVar(); if(CurrentLexem.Type == LexemType.For) return parseFor(); ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私は認める、私は私の最初の深刻なパーサーをそのように書いた。 しかし、これは悪い考えです！



まず、文字の固定数のみを見ることができます。 もちろん、 for



またはvar



には適切です。 しかし、文法にこれらのルールがあるとしましょう：

 assign = id_assign | member_assign | index_assign id_assign = identifier "=" expr member_assign = lvalue "." identifier "=" expr index_assign = lvalue "[" expr "]" "=" expr
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

id_assign



ですべてが明確な場合、他のルールは両方ともlvalue



非終端記号で始まり、その下でキロメートル式を非表示にできます。 明らかに、ここで主要なチェックに出くわすことはありません。



もう1つの問題は、責任分野の混乱です。 文法が拡張可能であるためには、ルールは可能な限り互いに独立している必要があります。 このアプローチでは、外部ルールが内部ルールの構成を認識する必要があり、これにより接続性が向上し、文法変更のサポートが複雑になります。



では、なぜ高度なチェックが必要なのでしょうか？ それぞれのルールに、それが最も適切なルールであることを確認するためにどれだけ先を見越す必要があるかを自分自身に知らせてください。



上記の例を考えてください。 テキストがあるとします： a.1 = 2



：

1. id_assign
   
   
   
   代替がid_assign
   
   
   
   呼び出されます。
2. 識別子a
   
   
   
   正常に一致します。
3. 次はピリオドですが、等号が必要です。 ただし、他のルールは識別子で始まるため、エラーはスローされません。
4. 割り当てルールは状態をロールバックし、さらに試行します。
5. member_assign
   
   
   
   の代替member_assign
   
   
   
   ます。
6. 識別子と期間が正常に一致しました。 文法には識別子とドットで始まる他のルールはないため、状態をロールバックしてさらにエラーを処理しようとすることは意味がありません。
7. 番号1
   
   
   
   識別子で1
   
   
   
   ないため、エラーがスローされます。

最初に、いくつかの便利なメソッドを作成します。





彼らの助けを借りて、上記の文法の実装はほとんど簡単になります：

 partial class Parser { public Node ParseAssign() { return Attempt(ParseIdAssign) ?? Attempt(ParseMemberAssign) ?? Ensure(ParseIndexAssign, "  !"); } public Node ParseIdAssign() { var id = TryGetValue(LexemType.Identifier); if (id == null) return null; if (!Check(LexemType.Assign)) return null; var expr = Ensure(ParseExpr, "  !"); return new IdAssignNode { Identifier = id, Expression = expr }; } public Node ParseMemberAssign() { var lvalue = Attempt(ParseLvalue); if (lvalue == null) return null; if (!Check(LexemType.Dot)) return null; var member = TryGetValue(LexemType.Identifier); if (member == null) return null; if (!Check(LexemType.Assign)) return null; var expr = Ensure(ParseExpr, "  !"); return new MemberAssignNode { Lvalue = lvalue, MemberName = member, Expression = expr }; } public Node ParseIndexAssign() { var lvalue = Attempt(ParseLvalue); if (lvalue == null) return null; if (!Check(LexemType.SquareBraceOpen)) return null; var index = Ensure(ParseExpr, "  !"); Ensure(LexemType.SquareBraceClose, "  !"); Ensure(LexemType.Assign, "  !"); var expr = Ensure(ParseExpr, "  !"); return new IndexAssignNode { Lvalue = lvalue, Index = index, Expression = expr }; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

DebuggerStepThrough



属性は、デバッグに非常に役立ちます。 ネストされたルールへのすべての呼び出しは、何らかの方法でAttemptおよびEnsureを通過するため、この属性がないと、ステップインに常に目を向け、呼び出しスタックを詰まらせます。



この方法の利点：

• ステータスロールバックは非常に安価な操作です
• どこにロールバックできるかを簡単に制御できます
• 詳細なエラーメッセージを簡単に表示
• 外部ライブラリは不要
• 少量の生成コード

短所：

• パーサーを手動で実装するには時間がかかります
• 文章の難易度と最適なパフォーマンスは、文法の質に依存します
• 左再帰文法は独立して解決する必要があります

演算子と優先順位

繰り返し、文法の説明で、操作の優先順位を示す次の規則について説明しました。

 expr = expr_1 { op_1 expr_1 } expr_1 = exp2_2 { op_2 expr_2 } expr_2 = exp2_3 { op_3 expr_3 } expr_3 = int | float | identifier op_1 = "+" | "-" op_2 = "*" | "/" | "%" op_3 = "**"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ブール演算子、比較演算子、シフト演算子、バイナリ演算子、または適切な演算子がまだあると想像してください。 いくつのルールを取得できますか？途中で優先順位のある新しい演算子を突然追加する必要がある場合、どれだけ変更する必要がありますか？



代わりに、一般的な優先順位の記述全体を文法から削除し、宣言的にエンコードできます。





ここで、新しい演算子を追加するには、対応する行を優先度リストの初期化に追加するだけです。



単項プレフィックス演算子のサポートを追加することは、好奇心の強い人のためのワークアウトとして残されています。

それは私たちに何を与えましたか？

奇妙なことに、手書きのパーサーのメンテナンスがずっと簡単になりました。 文法にルールを追加し、コード内の適切な場所を見つけ、その使用を追加しました。 古いパーサーに新しいルールを追加するときに頻繁に発生し、一見無関係な一群のテスト全体で突然のドロップを引き起こしたバックトラッキングの地獄は過去にありました。



結果の合計比較表：

パラメータ	FParsecパーサー	純粋なc＃
1回の実行の解析時間	220ミリ秒	90ミリ秒
さらに実行するための解析時間	5ミリ秒	6ミリ秒
ライブラリーに必要なサイズ	800 KB + F＃ランタイム	260 KB

おそらく、最適化を実行し、パーサーからより多くのパフォーマンスを絞り出すことが可能ですが、これまでのところ、この結果は非常に満足のいくものです。



文法の変更に伴う頭痛を取り除き、 LENSでいくつかの楽しいことをすることができました。

forループ

シーケンスのバイパスと範囲の両方に使用されます。

 var data = new [1; 2; 3; 4; 5] for x in data do println "value = {0}" x for x in 1..5 do println "square = {0}" x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

機能構成

演算子:>



を使用して、既存の関数を「ストリング化」する新しい関数を作成できます。

 let invConcat = (a:string b:string) -> b + a let invParse = incConcat :> int::Parse invParse "37" "13" // 1337
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

匿名関数を使用すると、部分的な使用が可能です。

 fun add:int (x:int y:int) -> x + y let addTwo = int::TryParse<string> :> (x:int -> add 2 x) addTwo "40" // 42
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

構文の強化

• 単一行コメント：
  
  

   somecode () // comment
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  
  
  
• 初期化されていない変数：
  
  

   var x : int
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  
  
  
• 単一のラムダ引数を囲む括弧はオプションです。
  
  

   var inc = x:int -> x + 1
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  
  
  
• 削除された制御構造内のブラケット：
  
  

   if x then a () else b () while a < b do println "a = {0}" a a = a + 1
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  
  
  
• try/finally
  
  
  
  ブロックが登場しました
  
  
• 関数にインデックスまたはフィールドを渡すときの括弧はオプションです。
  
  

   print "{0} = {1}" a[1] SomeType::b
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

このプロジェクトは、ゆっくりですが、開発中です。 まだ多くの興味深いタスクがあります。 次のバージョンが計画されています。

• ジェネリック型と関数を宣言する
• 関数またはタイプに属性をタグ付けする機能
• イベントサポート

収集されたWindows用のデモをダウンロードすることもできます 。