2

私は甥の C ラボの宿題を手伝っています。それは文字列操作の課題であり、Wang のアルゴリズムを適用しています。

入力の BNF 表現を次に示します。

<s> ::= <l> # <r>

<l> ::= <list>| ε
<r> ::= <list>| ε
<list> ::= <f>|<f> , <list>
<f> ::= <letter>| - <f>| (<f><op><f>)
<op> ::= & | | | >
<letter> ::= A |... | Z

C でこの種の入力を処理および解析するためのベスト プラクティスは何ですか? を使用せずにこの構造を解析するにはどうすればよいstructですか? 前もって感謝します。

4

2 に答える 2

3

最も簡単なアプローチは、すべてのルール (または「プロダクション」) を関数にすることです。これは「再帰降下」パーサーと呼ばれます。

次の文字も覗いて取得する 2 つのルーチンを作成します。

これにより、次のようなコードが得られます (疑似コード)。

// <sequent> ::= <lhs> # <rhs>
sequent()
    lhs()
    if peekchar() != '#' then error
    else poundsign = nextchar()
    rhs()


// <lhs> ::= <formulalist>| ε
lhs()
    if peekchar() == EOF
        return
    else
       formula()

// <rhs> ::= <formulalist>| ε
rhs()
    if peekchar() == EOF
        return
    else
       formulalist()

// <formulalist> ::= <formula>|<formula> , <formulalist>
formulalist()
   formula()
   if peekchar() is ','
       comma = nextchar()
       return formulalist()

// <formula> ::= <letter>| - <formula>| (<formula><infixop><formula>)
formula()
    next = peekchar()
    if next in A..Z
        letter
    else if next is -
        minus_sign = nextchar()
        return formula()
    else
        formula()
        infixop()
        formula()

// <infixop> ::= & | | | >
infixop()
    c = nextchar()
    if c not in &,|,> then error

// <letter> ::= A | B | ... | Z
letter()
    c = nextchar()
    if c not A..Z then error

など、ルールごとに。

一般的な考え方:

  • 各ルールは関数です
  • 特定の時点で、関数は何をすべきかを確認するために先を見越します。たとえば、formula() は、最初の文字がマイナス記号かどうかを確認します。
于 2010-05-17T09:16:32.817 に答える
0

BNF は既にあるので、この種の入力を解析する最も簡単な方法は、パーサー ジェネレーターを使用することです。しかし、これは宿題であるため、ジェネレーターの使用が許可されているかどうかはわかりません。

それでも、手書きのパーサーを使用することもできます。再帰降下パーサーを検索するだけです...

于 2010-05-17T09:15:55.193 に答える