0

yacc/bison と非常によく似た happy パーサーを使用して記述された関数型言語コンパイラで、次のルールを使用して、いくつかのコア関数map、concatおよびをリストに実装しました。filter

Exp:
...
| concat '(' Exp ',' Exp ')'         { Concat $3 $5 }
| map '(' Exp ',' Exp ')'            { Map $3 $5 }
| filter '(' Exp ',' Exp ')'         { Filter $3 $5 }

これは問題なく機能しますが、ほとんどの関数型言語には括弧やコンマがないため、代わりmap(myfun, [1,2,3])にmap myfun [1,2,3]. 文法の明らかな変更は次のとおりです。

Exp:
...
| concat Exp Exp         { Concat $2 $3 }
| map Exp Exp            { Map $2 $3 }
| filter Exp Exp         { Filter $2 $3 }

しかし、この変更には多くのreduce-reduce競合が含まれています。コンマと括弧なしで関数呼び出しを解析するにはどうすればよいですか?

私が抽出できた最小の矛盾する文法は次のとおりです。

Exp :
    -- Math
     Exp '+' Exp                         { Op $1 Add $3 }
    | Exp '-' Exp                        { Op $1 Sub $3 }

    -- Literals
    | num                                { Num $1 }
    | '-' num %prec NEGATIVE             { Num (-$2) }

    -- Lists
    | map Exp Exp                        { Map $2 $3 }

4 つの削減/削減競合が生成されます。ルールのいずれかを削除すると、競合が発生します。興味のある方は、ここに完全な文法があります。

4

1 に答える 1

1

問題は、関数アプリケーションにトークンがないため、トークンベースの優先順位の競合解決がうまく機能しないことです。関数アプリケーションである可能性のあるシフトと他の式のリデュースを決定しようとすると、先読みトークンは、引数式が始まるものです。使用できる「空白」トークンはありません。

この問題をハックして機能させるには、式である可能性のあるすべてのトークン (FIRST(Exp) 内のすべてのトークン) の優先順位を関数適用の優先順位に設定する必要があります。これらのトークンのいずれかが他の優先順位を必要とする場合 (たとえば、インフィックスまたはプレフィックスのいずれかのトークン)、これはより複雑になり、機能しない可能性があります。

より適切に機能する可能性のある代替手段は、優先順位規則をまったく使用しないことです。代わりに、優先順位のレベルごとに異なる規則を使用して文法を明確にします。

Exp: Term | Exp '+' Term
Term: Factor | Term '*' Factor
Factor: Primary | Factor Primary
Primary: num | id | '(' Exp ')'
于 2016-10-09T21:23:43.347 に答える