1

現在、私は VHDL 用のパーサーを構築しようとしていますが、これには C++ パーサーが直面しなければならない問題がいくつかあります。VHDL の文脈自由文法は、関数呼び出しと配列サブスクリプションに関するあいまいさのため、単一の解析ツリーではなく解析フォレストを生成します。

foo := fun(3) + arr(5);

この代入は、パーサーが曖昧さを多少オンザフライで解決するために使用する、階層的に型を認識するシンボル テーブルを保持する場合にのみ、明確に解析できます。

前述のようなステートメントの場合、解析フォレストは指数関数的に成長するのではなく、関数呼び出しと配列サブスクリプションの量に応じて線形になるため、これを行いたくありません。

（もちろん、次のようなステートメントでパーサーを苦しめることを除いて）

foo := fun(fun(fun(fun(fun(4)))));

bison はユーザーに単一の解析ツリーを作成することを強制するため、%merge 属性を使用してすべてのサブツリーを再帰的に収集し、シングルトン AST のいわゆる AMBIG ノードの下にそれらのサブツリーを追加しました。

結果は次のようになります。

上記を生成するために、トークン ストリーム「I=I(N);」を解析しました。parse.y ファイル内で使用した文法の内容を以下にまとめます。VHDL のあいまいな部分に似せようとします。

start: prog
;

/* I cut out every semantic action to make this
   text more readable */
prog: assignment ';'
| prog assignment ';'
;

assignment: 'I' '=' expression
;

expression: function_call   %merge <stmtmerge2>
| array_indexing            %merge <stmtmerge2>
| 'N'
;

function_call: 'I' '(' expression ')'
| 'I'
;

array_indexing: function_call '(' expression ')'   %merge <stmtmerge>
| 'I' '(' expression ')'                           %merge <stmtmerge>
;

ソースコード全体は、この github リポジトリで読むことができます。

それでは、実際の問題に取り掛かりましょう。上記の生成された構文解析ツリーでわかるように、ノード FCALL1 と ARRIDX1 は同じ単一ノード EXPR1 を参照し、それは N1 を 2 回参照します。

これは、絶対に起こってはならないことであり、その理由はわかりません。代わりにパスがあるはずです

FCALL1 -> EXPR2 -> N2
ARRIDX1 -> EXPR1 -> N1

バイソンが前述のノードを再利用する理由がわかりましたか?

また、bison の公式 gnu メーリング リストにバグレポートを書きましたが、この点に対する返信はありませんでした。残念ながら、新しいスタックオーバーフロー ユーザーに対する制限により、このバグ レポートへのリンクを提供することはできません...

4

1 に答える 1

0

その動作は想定されています。

expression明確に削減でき、その削減された値は、値を含む可能なあいまいな削減の両方で使用されます。LR と同様に、GLR は左から右へのパーサーであることを思い出してください。リダクション アクションが実行されると、すべての子リダクションがすでに発生しています。効果は右側の端子の使用と変わりません。端末は、それを使用するあいまいなプロダクションで異なるインスタンスを生成するために人為的にコピーされることはありません。

ほとんどの人にとって、これはバグではなく機能であり、冗談で言っているのではありません。グラフ構造のスタックがない場合、GLR の実行時間は指数関数的になります。パース ツリーをマージするときに共有 AST ノードのディープ コピーを本当に作成したい場合は、自分で行う必要がありますが、パース フォレストが実際には有向非循環であるという事実を利用する方法を見つけることをお勧めします。ツリーではなくグラフ。おそらく、重複がないことを利用できるでしょう。

于 2016-04-07T17:37:53.100 に答える