yacc/ocamlyacc でのreduce/reduce競合の解決

StackOverflow https://stackoverflow.com/questions/24516

  •  09-06-2019
  •  | 
  •  

質問

私はocamlyacc（通常のyaccとほぼ同じ）で文法を解析しようとしています。これは、演算子のない関数適用（OcamlやHaskellなど）と、通常の二項演算子と単項演算子の組み合わせをサポートしています。減算と否定の両方に使用できる「-」演算子とのreduce/reduce競合が発生します。私が使用している文法のサンプルは次のとおりです。

%token <int> INT
%token <string> ID
%token MINUS

%start expr
%type <expr> expr

%nonassoc INT ID
%left MINUS
%left APPLY

%%

expr: INT
    { ExprInt $1 }
| ID
    { ExprId $1 }
| expr MINUS expr
    { ExprSub($1, $3) }
| MINUS expr
    { ExprNeg $2 }
| expr expr %prec APPLY
    { ExprApply($1, $2) };

問題は、「a - b」のような式を取得した場合、パーサーはこれを「a (-b)」 (b の否定、その後に適用) として縮小する必要があるのか​​、「a - b」 (引き算）。減算リダクションは正しいです。そのルールを支持して競合を解決するにはどうすればよいですか?

役に立ちましたか？

解決

残念ながら、私が思いつく唯一の答えは、文法の複雑さを増すことです。

  1. スプリット expr の中へ simple_expr そして expr_with_prefix
  2. のみ許可する simple_expr または (expr_with_prefix) APPLYで

最初のステップでは、reduce/reduce の競合が shift/reduce の競合に変わりますが、括弧でそれが解決されます。

「a b c」でも同じ問題が発生します。それは...ですか a(b(c)) または (a(b))(c)?断ち切ることも必要だろう applied_expression そして必要な (applied_expression) 文法的には。

これでうまくいくと思いますが、わかりません:

expr := INT
      | parenthesized_expr
      | expr MINUS expr

parenthesized_expr := ( expr )
                    | ( applied_expr )
                    | ( expr_with_prefix )

applied_expr := expr expr

expr_with_prefix := MINUS expr

他のヒント

そうですね、最も簡単な答えは、それを無視して、デフォルトの縮小/縮小解像度で処理させることです。つまり、文法で最初に現れるルールを減らすことです。この場合、それは減らすことを意味します expr MINUS expr を優先して MINUS expr, 、まさにあなたが望むものです。見た後 a-b, 、単項マイナスとして解析してから適用するのではなく、二項マイナスとして解析したいとします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top