35

私が聞きたい質問は、タイトルに簡潔に示されています。問題の文法の例を挙げましょう。

identifier_list
    : identifier
    | identifier_list identifier;

lambda_arguments
    : '(' identifier_list ')'
    | identifier;

lambda
    : lambda_arguments '=>' expression

次に、通常の C 式の文法を追加します。特に、

primary_expression
    : '(' expression ')'
    | identifier
    | lambda;

問題は、この文法 LALR(1) が解析可能かどうか、つまり、自動パーサー ジェネレーターで解析できるかどうかです。それとも手動または GLR パーサーが必要ですか? 文脈依存のキーワードやその他のセクションではなく、このサブセクションについて具体的に知りたいことに注意してください。

私が今考えているのは、パーサーが を見た場合'(' identifier ')'、これには 2 つの有効な解析があるため、パーサーが を見た場合、identifierを先に見て、')'どの解析ツリーを下るかを決定できないということです。ただし、これはシフト/リデュースの競合である可能性がありますが、任意の優先順位を割り当てることで排除できます (おそらく favouring '(' identifier ')')。

編集: 実際、私は文法のこのサブセクションを使用して、新しい言語で同様の機能を盗むことを検討していました. 私はすでに JavaScript に似た無名関数を文法形式で持っていますが、モルモットは多くの用途に対して冗長すぎると不満を漏らし、C# ラムダ式がより理想的な解決策であると指摘しました。私は、この解決策から生じる潜在的なあいまいさを懸念していました。だから、本当に、私はそのサブセクションにしか興味がありませんでした. ジェネリックやキャストなどの他のものは、私にとっては問題ではありません。

私の文法の以前の版は機械的に解析可能であり、私はこの特性を失いたくありません。機械式ジェネレーターに関する私の以前の経験から、自分で試すよりもここで確認するのが最善であることがわかります。私の手巻きのパーサーでは、もちろん'(' identifier、通常よりも少し先を読むという単純な特殊なケースも考えられます。

4

4 に答える 4

10

C# スタイルのラムダで拡張された式の文法は LALR(1) ではありませんが、おそらく LALR(2) です。その結果、同等の LALR(1) 文法を生成することが可能です (必ずしも自明ではありません): 以下の編集を参照してください。

入力で削減/削減の競合が発生します。

( id )

は (2 番目のケースでは間接的に)または(間接的に)idに還元される可能性があり、パーサーは 1 つの先読みトークン ( ) に基づいてどちらが正しいかを判断できないためです。identifier_listexpression)

identifier_list2 番目の次のトークンが である場合にのみ削減が可能であり、言語の演算子でない限り=>、 2 番目の次のトークンが である場合は削減できないため、2 つの先読みトークンに基づいて判断できます。なので断言はできませんが、おそらくLALR(2)だと思います。=>expression=>

複数の識別子がある場合は問題ありません。

( id1 id2 )

id1 id2式に還元することはできません (ほとんどの式言語では、もちろん、あなたのものは異なるかもしれません)。=>`=>' が有効な演算子でない限り、括弧で囲まれていない単一の識別子が直後に続く場合も問題にはなりません。

編集

元の回答で、LALR(2) 言語のようなものは存在しないと言い忘れていました。LALR(2) 文法で認識される言語は、一部の LALR(1) 文法でも認識されます。実際、この主張の建設的な証明があり、元の構文木を復元する手順とともに、そのような LALR(1) 文法を機械的に作成できます。

この場合、上で述べたように、追加の先読みを必要とするプロダクションは 1 つしかないため、LALR(1) 文法を生成する方がさらに簡単です。解決策は、削減を 1 トークン遅らせることです。つまり、元の文法には次のようなものが含まれます。

primary:           '(' expression ')'
lambda_parameters: '(' id_list ')'

ここで、 と の両方が端末id_listをexpression派生させますID。は別としてID、これら 2 つの非終端記号の派生は素であるため、次のように問題を解決できます。

primary:           '(' expression_not_id ')'
       |           '(' ID ')'


lambda_parameters: '(' id_list_not_id ')'
                 | '(' ID ')'

残りは、 と の作品を分割して、ケースを分離するだけですがexpression、id_listこれIDはそれほど難しいことではありません。以下は、簡単に拡張できる簡単な例です。加算、乗算、および関数の適用に制限されています (2 つのカンマ区切りのリストが問題にならないことを示すために含めました)。

%token ID LITERAL RIGHT_ARROW
%start expr
%%
primary: primary_not_id | ID ;
term:    term_not_id    | ID ;
sum:     sum_not_id     | ID ;
expr:    expr_not_id    | ID ;

expr_list: expr         | expr_list ',' expr ;
arguments: '(' ')'      | '(' expr_list ')' ;

ids: ID ',' ID          | ids ',' ID ;
parameters: '(' ID ')'  | '(' ids ')' ;

primary_not_id: LITERAL
              | '(' expr_not_id ')'
              | '(' ID ')'
              | primary arguments
              ;

term_not_id: primary_not_id
           | term '*' primary
           ;

sum_not_id: term_not_id
          | sum '+' term
          ;

expr_not_id: sum_not_id
           | parameters RIGHT_ARROW expr
           ;

注: OP の文法は、コンマで区切られていない一連の識別子として、複数のパラメーターを持つラムダを生成します: (a b) => a + b. 実際の意図はコンマを使用することだったと思います: (a, b) => a + b、そしてそれが上記の文法で行ったことです。C ファミリのように言語にカンマ演算子がある場合、この違いは重要です。その場合、式が になる可能性があり'(' expression_list ')'、ラムダ パラメータ リストと競合するからです。単純な実装では、が任意に長くなる可能性があるため、有限先読みでは解決できないの最初expressionのリデュース/リデュース コンフリクトが発生します。expression_listexpression_list

ただし、この場合にも解決策があります。次のようにid_listから分離することで構成されます。expression_list

id_list:         ID
       |         id_list ',' ID
       ;
expression_list_not_id_list: expression_not_id
                           | id_list ',' expression_not_id
                           | expression_list_not_id_list ',' expression
                           ;
expression_list: expression_list_not_id_list
               | id_list
               ;

ただし、ターゲット言語が何を必要としているのかわからないため、完全な文法は実行しませんでした。

于 2013-06-05T04:35:32.633 に答える
3

言語の残りの部分が LALR(1) であることを知っていない限り、ラムダ式文法の質問自体は興味深いものではないと思います。

答えを知りたい場合は、サブグラマーを LALR(1) パーサー ジェネレーターにフィードします。shift-reduce または reduce-reduce の競合について不平を言う場合、それは LALR(1) ではありません。文法がLALR(1) であるかどうかは、定義上、遷移表を作成できるかどうかによって決まります。

ほとんどの場合、言語全体のパーサーが必要です。

ここで興味深い質問が 2 つあります。

1) 言語としての C# 4.5 は LALR(1) ですか? (たとえば、 LALR(1) である文法はありますか? LALR(1) ではない特定の文法は、別の文法がないことを意味しないことに注意してください。

2) Microsoft が (さまざまな形式で) LALR(1) として公開している C# 文法はありますか?

エリックは、1) は正しくないと言っていると思います。これは、2) も正しくないことを示唆しています。

C++ では、そのテンプレートを解決するために無限先読みが必要です。これは主に、ローカルで ">" が「テンプレートの終了引数」または「より大きい」と解釈される可能性があるためです。C# はこれをコピーしたので、テンプレートの解決にも無限の先読み要件があると思います。それは間違いなく LALR(1) ではありません。[">>" をシフト演算子として扱うことができるかどうか、および "> >" をシフト演算子として扱うことができないかどうかについて、追加の混乱があります。これは、空白が見えないため、文法で修正できません。]

私の会社では言語処理ツールに GLR を使用しており、問題なく動作する C# 4.5 文法があります。GLR は、文脈自由文法を LALR(1) 互換形式 (例えば、曲げ、ねじれ、左/右因子、シャッフル) に変換する方法や、アドホックな先読みなどをコーディングする方法を考える必要がないことを意味します。したがって、解析ではなく、コードの処理の問題に集中できます。

これは、キャストやその他の構造が解析時にあいまいなツリーを生成することを意味しますが、型情報があれば簡単に解決できます。

于 2013-06-05T00:36:33.673 に答える