0

私はここ数週間、flex と bison を使用してパーサーを作成してきましたが、最初のいくつかのルールの定義が似ている二重再帰のために停止しました。Bison は、ある特定の段階で常に間違ったパスを選択し、文法が適合しないためにクラッシュします。バイソンのコードは次のようになります。

set : 
TOKEN_    /* token */
QString
QString
Integer  /* number of descrs (see below) */
M_op     /*'M' optional*/
alts;

と

alts  :
alt | alts alt ;

alt   :
QString
pName_op   /* empty | TOKEN1 QString */
deVal_op    /* empty | TOKEN2 Integer */
descrs
;

と

descrs  :   
descr | descrs descr ;
descr :
QString
QString_op   /* optional qstring */
Integer
D_op         /* optional 'D' */

Bison は再帰にとどまりdescrs、次の に進むために再帰を終了することはありませんalt。ただし、最初のブロックで読み取られる整数は、 のインスタンスがdescrいくつ来るかを示しています。だから私の質問はこれです：

バイソンがこの再帰を終了して「上」の再帰に入ることができるように、再帰の特定の数のインスタンスに対してバイソンを準備する方法はありますか? Cコードでこの整数にアクセスできますが、上記の移動の構文はわかりませんdescrs : {for (int i=0;i<n;++i){descr}}（おそらくばかげているように見えることはわかっています）

これに失敗した場合、この問題を回避する他の方法はありますか?

任意の入力をいただければ幸いです。前もって感謝します。

4

1 に答える 1

1

文脈自由文法は、意味情報に依存することはできません。しかし、それこそまさにあなたが求めていることです: 数値トークンの値が式の構文で考慮されることを望んでいます。

要求として、それは不合理でも不道徳でもありません。それは単に文脈自由文法の範囲外です。またbison、文脈自由文法のパーサーを作成することを目的としています。したがって、この問題に対する正しいツールではありません。

そうは言っても、 GLR文法のサポートを含むかなり最近のバージョンを使用している場合、この方法でバイソンを使用することは可能です。bisonBison の GLR サポートには、セマンティック述語を使用して解析を制御するオプションが含まれています。(詳細については、バイソンのマニュアルを参照してください。) そのメカニズムに基づく解決策は可能であり、おそらくそれほど複雑ではありません。

はるかに簡単なのは (文法で許可されている場合)、トップダウン パーサーを使用することです。たとえば、数値を解析してからその数のdescrs を解析することは、再帰降下パーサーでは簡単です。

文法で非終端記号を自由に使用するFOO_opことは、トップダウンの構文解析が問題にならないことを示唆していますが、文法全体を見ずに確実に言うことは不可能です。人為的な非終端記号 ( などFOO_op) は、LR(1) 言語でシフト/リデュースの競合を引き起こすことがよくあります。LR(1) 言語では、形式: の生成は、通常、置換ではなく、A → ω B? χ 生成のペアとしてレンダリングされます。A → ω B χ; A → ω χBop → B | ε; A → ω Bop χC → ω ζFIRST(ζ) ∩ FIRST(B ∪ ω) ≠ ∅

于 2015-03-24T20:37:08.203 に答える