7

これは Grammar からのフォローアップの質問です: トップダウンとボトムアップの違いは?

私はその質問から次のことを理解しています。

  • 文法自体はトップダウンでもボトムアップでもなく、パーサーは
  • 一方では解析できるが、他方では解析できない文法がある
  • （ジェリー・コフィンに感謝

したがって、この文法 (考えられるすべての数式) の場合:

    E -> E T E
    E -> (E)
    E -> D

    T -> + | - | * | /

    D -> 0
    D -> L G

    G -> G G    
    G -> 0 | L

    L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

これは、トップダウンおよびボトムアップのパーサーで読み取ることができますか?

これはトップダウンの文法かボトムアップの文法か (またはどちらでもない) と言えますか?

宿題の質問があるので質問しています：

「すべてからなる言語のトップダウンとボトムアップの文法を書いてください...」（別の質問）

トップダウンとボトムアップの文法はないように見えるので、これが正しいかどうかはわかりません。誰でも明確にできますか？

4

1 に答える 1

5

その文法は、字句解析と構文解析を 1 つにまとめているため、ばかげています。しかし、わかりました、それは学術的な例です。

ボトムアップとトップダウンの問題は、通常の 1 先読みでは実装が難しい特殊なコーナー ケースがあることです。問題がないか確認して、文法を変更したほうがいいと思います。

あなたの文法を理解するために、私は適切なEBNFを書きました

expr:
    expr op expr |
    '(' expr ')' |
    number;

op:
    '+' |
    '-' |
    '*' |
    '/';

number:
    '0' |
    digit digits;

digits:
    '0' |
    digit |
    digits digits;

digit:
    '1' | 
    '2' | 
    '3' | 
    '4' | 
    '5' | 
    '6' | 
    '7' | 
    '8' | 
    '9';

私は特にルールが好きではありませんdigits: digits digits。最初の数字がどこから始まり、2 番目の数字がどこで終わるかは不明です。私はルールを次のように実装します

digits:
    '0' |
    digit |
    digits digit;

もう 1 つの問題は、これがおよび とnumber: '0' | digit digits;競合することです。さすがに重複です。ルールを（数字を削除する）に変更します。digits: '0'digits: digit;

number:
    '0' |
    digit |
    digit zero_digits;

zero_digits:
    zero_digit |
    zero_digits zero_digit;

zero_digit:
    '0' |
    digit;

これにより、文法 LR1 (1 回先読みで左再帰) とコンテキスト フリーになります。これは通常、bison などのパーサー ジェネレーターに与えるものです。また、bison はボトムアップであるため、これはボトムアップ パーサーの有効な入力です。

トップダウンのアプローチの場合、少なくとも再帰的なまともな場合、左再帰は少し問題です。必要に応じてロールバックを使用できますが、これらには RR1 (右再帰的先読み) 文法が必要です。これを行うには、再帰を交換します。

zero_digits:
    zero_digit |
    zero_digit zero_digits;

それがあなたの質問に答えているかどうかはわかりません。質問の定式化が不十分で誤解を招くと思います。そして私は生計を立てるためにパーサーを書いています...

于 2010-07-21T16:15:04.273 に答える