1

私は本を​​読んでいます—「フレックスとバイソン」パーサジェネレータがどのように機能するかを理解するために、例があります：

calclist: /* nothing */
        | calclist exp EOL { printf("= %d\n", $1); }
        ;

exp: factor
   | exp ADD factor { $$ = $1 + $3; } 
   | exp SUB factor { $$ = $1 - $3; }
   ;

factor: term
      | factor MUL term { $$ = $1 * $3; } 
      | factor DIV term { $$ = $1 / $3; }
      ;

term: NUMBER
    | ABS term { $$ = $2 >= 0? $2 : - $2; }
    ;

また、本では、上記の文法は、個別の非終端記号を使用することにより、暗黙的に優先されると述べています。しかし、それはどのように機能しますか？次の例があると仮定します:(1 + 3 * 2空白はスキップするだけです）最初のトークンを読み取り、それが文法を「バブリング」する時間と同じか、それとも1スタックにプッシュされますか？次のトークンはどの文法規則からチェックされますか？なぜこの文法では、乗算が加算よりも優先されるのですか？NUMBERtermfactor

4

2 に答える 2

2

優先順位は、ADD および SUB のオペランドが因数であり、因数のみが MUL および DIV 演算子を含む結果です。MUL は項にカプセル化されているため、ADD は MUL と競合しません。

パーサーの観点からこれについて考えてみましょう: パーサーが ADD 演算子との関係を考慮する前に式という用語を削減する必要があり、その削減によって MUL 演算子が消去されます。

が与えられA + X * Yた場合、式は、もはや演算子を表現しない単一の文法記号にX * Y縮小されるため、演算子が優先順位の問題を持つものは何もありません。今はちょうどです。term*+A + term

ちなみに、文法は型破りな逆用語を使っています。

これらは用語です: A + B + C

これらは要因です: A*B*C

項が加算され (「級数の項」)、因数が乗算されます (「整数または多項式の因数」)。

それは本当にこの教科書からですか？いずれにしても、Aho、Sethi、Ullman によるCompilers: Principles, Techniques and Toolsを試してください。（1988年だがクラシック）。

于 2012-03-11T00:49:16.447 に答える
2

これが（明示的ではなく）「暗黙的な」優先順位を持つ理由は、因数分解された文法（個別の非終端記号）のために、テキストが言うとおりです。

の例に1 + 3 * 2取り組み、自分自身が解析を行うコンピューターであると想像し、各指示に従って「文字どおり」に進みます。"exp" (式) を見つけるには、まず因数を見つけなければなりません。(他のオプションは、「exp」を見つけることから始めることですが、それは「因子」を見つける必要があります。) したがって、因子を見つける必要があります...しかし、そのためには「項」を見つける必要があります。用語、またはそれ自体が用語で始まる因子。NUMBERそのため、 aまたは keyword のいずれかである用語を見つける必要がありますABS。したがって、(文法用語で) を「受け入れる」ことができます1。これは実際には でNUMBERあり、解析の最初の部分、つまり用語の検索に成功しています。1(トークン ストリームから を削除すると、+

用語ができたので、因子も (定義により) ありますが、いわば「因子を持つアクションを完了する」ためには、より長い一致を試みる必要があります: 因子の後にMULorが続きます。 DIV、その後に何かが続きます。次のトークンは次+のとおりです。これは MUL ではなく、DIV でもありません。したがって、 factor:1が factor であり、次のトークンがまだ+.

因数ができたので、(定義により) exp がありますが、「exp を持つアクションを完了する」ためには、より長い一致を試みる必要があります: exp の後にADDorSUBが続き、その後に何かが続きます。 . 次のトークンはまだ実際には ADD です。したがって、ルール+を続行する必要があります。exp ADD factor { $$ = $1 + $3 };

この時点で、(パーサーとして) これまでのすべてをスタックにプッシュし、適切な非終端記号 (この場合は別の "要素") を探して再び作業を開始します。ここで、因子のルールから始めます。「用語」を探す必要があります。見つかった場合は、MULまたはを含むルールの長いバージョンを実行してみてくださいDIV。この部分を処理すると、トークンが実際に MUL であることがわかり、ルールの一部を*使用する「要素」結果を作成する、より長いルールを使用する必要があります。これは、シーケンスfactor MUL term { $$ = $1 * $3; }を受け入れ、別名、食べたり使い果たしたりして、解析スタックにプッシュしたルールを完成させる「要因」の値を返します。3 * 26

プッシュ状態に戻ったら、1 を追加して式全体を受け入れる (食べる) ことで、「1 +」の解析を完了します。もちろん、1 + 6 は 7 なので、文法は正しい値を返します。

于 2012-03-10T21:15:02.673 に答える