LRジェネレーターの記述機能と可能な機能

はじめに

こんにちは

LALRパーサーの独自のジェネレーターの作成に関する最後の部分では、可能な機能と機能について説明します。 さらに、既存のソリューションに欠けていたものと、自転車を書き始めた理由を説明します。



コンテキストを設定するために、分析用の文法はJavaScriptとも呼ばれるECMAScriptであることをお知らせします。 具体的な仕様は、ECMA-262、2011年6月のリビジョン5.1です。





書くのが初めての困難に出会ったとき、私はすぐにコンパイラコードを書くことを急ぎませんでした。 最初に、大企業がこれらの問題をどのように解決したかを調査しました。MozillaとGoogle（OperaとIEの情報源はパブリックドメインにありません）。 判明したように、彼らは実際に文法の形式化でスチームバスを使用せず、そのままコードを記述しました。つまり、最初の部分で行うように警告しました。 v8でif'aを処理する例（Chrome JSエンジン）：

IfStatement* Parser::ParseIfStatement(ZoneStringList* labels, bool* ok) { // IfStatement :: // 'if' '(' Expression ')' Statement ('else' Statement)? Expect(Token::IF, CHECK_OK); Expect(Token::LPAREN, CHECK_OK); Expression* condition = ParseExpression(true, CHECK_OK); Expect(Token::RPAREN, CHECK_OK); Statement* then_statement = ParseStatement(labels, CHECK_OK); Statement* else_statement = NULL; if (peek() == Token::ELSE) { Next(); else_statement = ParseStatement(labels, CHECK_OK); } else { else_statement = factory()->NewEmptyStatement(); } return factory()->NewIfStatement(condition, then_statement, else_statement); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

なぜそうしたのですか？ いくつかの理由があります。

1. 仕事のスピード。 FSMは非常に高速ですが、「線形」実行はさらに高速です。
2. 柔軟性。 bison / ANTLR / boost :: spirit /が使用されなかったという事実は、私自身の開発により、この文法ではそれほど単純ではないという考えに間接的に突入し、制限に陥ったのは私だけではありませんでした。
3. 彼らはゼロからの言語の開発者ではないので（たとえばDartのように）、標準に新たに変更が加えられる前に、数年間は一度書くだけで十分です。 このことから、文法の変更は毎日行われません。

もちろん、多くのマイナスがあります：

1. 解析のみを目的とした5〜1万行のコードは少し多くなります。
2. 仕様なしでは生きられません。 コードは非常に断片化されているため、ソースからのみ言語スキームをゼロから組み立てることは非常に困難です。
3. トリッキーなマクロにもかかわらず、エラー処理によりコードが大きくなる：
   
   

    #define CHECK_OK ok); \ if (!*ok) return NULL; \ ((void)0
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

パーサー/パーサージェネレーターの要件

これで、文法の落とし穴と私の期待に進むことができます。 いくつかのポイントはサードパーティのソフトウェアによって完全に実行されるとすぐに言わなければなりません。 しかし、全体的には全体的なプログラムはなく、解決策を見つけることができなかった点があります。

コメントは役に立ちます！

私の仕事では、コメントを破棄せずに、テキストとコメントの位置を保存する必要がありました。 ANTLRとbison / flexはこれを行うことができます。 最初はレクサーの多重化によるもの、2番目はflexの力によるものです。 レクサーの作成をまだ開始していないため、フレックスを使用します。 彼はこの問題を次のように解決しました。

  /* [Comment] = [MultiLineComment] | [SingleLineComment] */ /* [MultiLineComment] */ /* start of multiline, grab whole comment, that's why i use yymore() */ "/*" { BEGIN(multilinecomment); yymore(); m_loc.setMore(true); } /* skip all comments chars except "*" */ <multilinecomment>[^*\n\r]* { yymore(); } /* skip all "*", that not followed by "/" */ <multilinecomment>"*"+[^*/\n\r]* { yymore(); } /* end of comment */ <multilinecomment>"*"+"/" { m_comments.push_back(CParser::Comment(yytext, m_loc.tokenLine(), m_loc.tokenCol())); m_loc.setMore(false); BEGIN(INITIAL); } /* [SingleLineComment] increment lineNo */ ("//"([^\r\n])*{LineTerminator})|("//"([^\r\n])*) { m_comments.push_back(CParser::Comment(yytext, m_loc.tokenLine(), m_loc.tokenCol())); m_loc.linc(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは特別なことは何もありません。 レクサーの内部状態とyymore（）を使用します。これにより、いくつかのルールから完全なトークンを作成できます。

パーサー制御のレクサーモード

JSには、正規表現を定義するための特別な形式があります。 それらはソースコードでそのように書くことができ、シグナルは「/」です。 しかし同時に、それは分裂の兆候でもあります。 したがって、これらの場合、トークンの流れは大きく異なります。 この位置にあるパーサーがスラッシュを表示できる場合、スラッシュは除算記号として扱われます。 そして、正規表現の始まりの兆候として-他のすべての場合：

 //     regexp'a /asd[^c]/i.match(s); //    -   a = b / c;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、除算演算子がその時点で来ることができる場合、パーサーはチェックボックスをオンにする必要があります。 フレックスレベルでは、単純に解決されます。

  /* [RegularExpressionLiteral] it has more length then [DivPunctor] (at least 3 == "/X/" versus 2 == "/="), that's why it would be proceeded first, before [DivPunctor] */ "/"{RegularExpressionFirstChar}({RegularExpressionFirstChar}|"*")*"/"({IdentifierStart}|[0-9])* { if (m_mode != Mode::M_REGEXP) REJECT; yylval->assign(yytext, yyleng); return token::T_REGEXP; } /* [DivPunctuator]: "/" or "/=" */ "/" return token::T_DIV; "/=" return token::T_DIVAS;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

flexは貪欲な字句解析器であり、できるだけ長い語彙素を処理しようとするため、最初に正規表現の規則に該当し、そこで分割モードが設定されている場合、次の規則に進みます。

出口のパーサーツリー

解析の結果として、パーサーツリーを正確に取得したいです。 私の仕事の一部として彼と仕事をすることは非常に便利です。 ASTも適していますが、残念ながら、この形式をサポートする唯一のANTLR形式では、文法の上に明示的なルールを構築する必要があります。 特別なアクションは必要ありません。 アナライザーアルゴリズムに小さな追加がない限り：

  while (!accepted && !error) { ... switch (act.type) { ... case Action::ACTION_SHIFT: ... node.col = m_loc.tokenCol(); node.line = m_loc.tokenLine(); node.type = ParseNode::NODE_TERM; node.termVal = s; node.symb.term = tok; nodes.push(tree.create(node)); break; case Action::ACTION_REDUCE: ... node.type = ParseNode::NODE_NONTERM; node.symb.nonTerm = (Symbols::SymbolsType)act.reduce.nonTerm; CTree<ParseNode>::TreeNode * parent = tree.create(node); unsigned long ruleLen = act.reduce.ruleLength; while (ruleLen) { tree.add(parent, nodes.top(), true); nodes.pop(); ruleLen--; } nodes.push(parent); break; } } if (nodes.top()) tree.SetRoot(nodes.top());
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

カスタム先読み

文法では、あなたはまさにそのようなものを見ることができます

 ExpressionStatement = [lookahead ∉ {{, function}] Expression ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

いいえ、これは標準の期待コンボリューションシンボルではありません。前のセクションで説明しました。 これは、最初の式文字をフィルタリングしようとすることの反対です。 つまり、この規則に従って、ターミナル「{」で始まる余分な娘製品をExpressionから除外する必要があります。 この場合、これは「{}」のように見えるブロックと、空のjavascriptオブジェクトObjectのタスクである「{}」という単純なクリーチャーとの衝突を避けるために行われます。 「関数」についても同様です。



パーサーの魔法がなくても、文法を微調整するだけで決定できます。

 ExpressionStatement = ExpressionWithoutBracket ExpressionWithoutBracket = ... | AssignmentExpressionWithoutBracket | ... ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、終端「{」で始まるルールに到達するまで、最後から2番目の文法からこのルールを除外します。 問題は、約20の中間ステップがあることです。さらに、これを2倍します（「関数」も！）そして、この手法は同じルールに異なる状況で使用されるため（2行-式とExpressionNoIn）。 いいえ、それは私をまったく喜ばせません。



技術的には、私のパーサーでは、これは非常に簡単に解決されます：

 ExpressionStatement = Expression {filter: [objectLiteral, functionDeclaration]} ... ObjectLiteral = {commonId: objectLiteral} '{' '}' | '{ 'PropertyNameAndValueList '}' | '{' ',' '}'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

閉じるとき、必要に応じて、親から子にフィルタリングラベルを切ります。 そして、フィルタリングの対象となるルールに出会った場合、それをクロージャーに含めないだけです。

いくつかの子ルールをオフにします

これはほとんど前の段落の亜種ですが、ここでは最初の文字だけでなく、任意の文字も見る必要があります。 図は、前述のExpressionNoInおよび関連するVariableDeclarationListNoInです。 より詳細に見ると、問題の原因は次の2種類のfor'aになります。

//最初の構文

for（var id in obj）alret（id）;

// 2番目の構文

for（var id = 1; id <10; id）alert（id）;



通常の状態では、変数を初期化するときに、ウィンドウ内でa a a = 'eval'を使用できます。 この演算子は、指定されたオブジェクト内のメンバーの存在をチェックします（ハサー、黙って！）。 ただし、ループでは、オブジェクトのすべてのメンバーを反復処理するために使用されます。 実際、混乱は非常に簡単に発生する可能性があるため、2番目の構文で使用することは禁じられています。 実際、LALRパーサーは、次の文字（ ';'または '）'）をチェックする畳み込みのおかげで、これらすべてを簡単に解決しますが、文法の作成者は明らかに、より広いクラスのパーサーに焦点を当てているため、「in」演算子のない場合に重複する20のルールを導入しています。 ただし、文法に従う必要があるため、好ましくない子（great-great -...）ルールをオフにするメカニズムも必要です。



詳細の違いを除いて、前の段落と完全に似ています。

 ExpressionNoIn = Expression {filter: [RelationalExpression_6]} ... RelationalExpression = ShiftExpression | RelationalExpression '<' ShiftExpression | RelationalExpression '>' ShiftExpression | RelationalExpression '<=' ShiftExpression | RelationalExpression '>=' ShiftExpression | RelationalExpression 'instanceof' ShiftExpression | {id: RelationalExpression_6} RelationalExpression 'in' ShiftExpression
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、人生を楽にするオプション機能です。 また、エラーの例はどれだけ正確に示されていますか。 文法自体では、ルールの1つにNoInを追加するのを忘れていました。

 ConditionalExpressionNoIn = LogicalORExpressionNoIn ? AssignmentExpression : AssignmentExpressionNoIn
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2番目のAssignmentExpressionは、後置記号で明らかになります。

自動挿入 ';'

別の面白いjavascriptは、ステートメントをセミコロンで終了する必要がないことです。 文法がそれを必要とする場所でさえ。 挿入ルールは、説明が簡単であると同時に実装が困難です。

1. パーサーが次のトークンでエラーを返し、このトークンが '{'である場合、少なくとも1つの改行によって前のトークンと分離されます。
2. EOFを満たしましたが、予想外でした。
3. for'aルールは適用されません。 for'aヘッダーの角括弧間のコンマ。

挿入は非常に簡単です。このアクションの必要性を判断したら、新しいFSM'aサークルに移動して、最後に読み取ったトークンをセミコロンに置き換えます。 さて、次のシフトでは、新しいトークンを読み取らず、エラーの原因となったトークンを使用します。

Unicodeサポート

JSは、この点で非常に有能な言語です。 utf16のサポートは、標準では厳密に記述されています。 ソース全体を解析する前にutf16に変換する必要がある時点まで。 ただし、残念ながら、flexはこれを行う方法を知りません（いいえ、\ xXXは適切ではありません。手短に、約1000文字をエンコードする必要があります）。 したがって、この条件は満たされません。

数量詞のサポート

文法を簡単にする別の非常に大きなトピック。 まず、次の数量詞が必要でした： "|" -ルールのバリエーション。左側が共通で、右側が異なります。 「？」 -ルールのオプション文字。 「*」-文字は1回以上繰り返されます。 はい、それらはBNF文法のレベルで完全に解決されます：

 A = B | C //   A = B A = C A = B? C //   A = BC A = C A = B* //   A = AB A = B
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、最後の例を除いてすべて問題ありません。 この場合、ツリーのステップを取得します。 つまり、Bを5回繰り返すと、深さが5に等しいノードAが得られます。これは非常に不便です。 したがって、再び、便利な線形表現を提供するパーサーへの変更を導入することにしました-BBBBBは1つのノードAから5つのリーフBを形成します。実際には、これは新しいタイプの操作-ReduceRepeatedの導入のように見えます。 そして、クロージャー関数と畳み込み定義の変更。 closeItem（）で要素をループします。



しかし、いつものように行うとどうなりますか：





それだけです この記事を読んでくれてありがとう。

記事の一部

1. パート1.基本理論
2. パート2. LRジェネレーターの説明
3. パート3.作成の機能とLRジェネレーターの可能な機能