6 
E -> E+T | E-T | T
T -> T*F | T/F | F
F -> i | (E)

この文法を変更してべき乗演算を許可し、次の^ように記述できるようにするにはどうすればよいi+i^i*iですか? 操作の順序がより高いことがわかっているので、私が知っているの^は、それを正しく関連付ける必要があるということだけです。

4

3 に答える 3

7

EBNF ( Extended Backus-Naur Form ) では、これは次のようになります。

expr -> term [ ('+' | '-') term ]*
term -> factor [ ('*' | '/') factor ]*
factor -> base [ '^' exponent ]*
base -> '(' expr ')' | identifier | number
exponent -> '(' expr ')' | identifier | number

（ここから撮影）

あなたの表記法に変換します（数字と識別子の区別はありません）：

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> F^X | B
B -> i | (E)
X -> i | (E)

わかりやすくするために、「B」と「X」をマージできます。

于 2013-06-18T13:55:10.497 に答える
3

以下のように対称的に。 

E -> E + T | E - T | T
T -> T * F | T / F | X
X -> X ^ Y | Y
Y -> i | (E)

説明:
==========
この文法は明確であることに注意してください。^演算子、*、/、 で構成される式を生成するには、まず、 、 などの優先順位の低い演算子を上位の演算子の前に追加できる手順を書き始める+必要があります。そして、最後にターゲット式に追加できます。したがって、抽象構文ツリー (解析ツリー) 演算子 は下部 (葉に向かって) に表示されます。このように、ツリーに従ってその式を評価すると、最初に実行されます。-+-*/^^^

注: 文法規則によると、センチメンタル形式では, .. のX -> O ^ Y追加に戻ることはできませんが、センチメンタル形式以外に他の演算子を追加することはできます。したがって、この形式の文法では、文法の言語に属する有効な式（文字列）の生成の流れを制御できます（これは、演算子の優先順位を明確に制御する方法です）。+-E+T | E-T | T

たとえば、式 を生成するi + i ^ i * iためE --> T --> X ---> X ^ Yに、(括弧なしで) をX ^ Y追加することはできません。+-(E)

式を生成するために可能な選択肢i + i ^ i * iは次のとおりです。

E --> E - T --> E + T - T --> E + X - T --> E + X ^ Y - T --*--> i+i^i*i

`--*-->` means more than one step

オペレーター^が最後のステップで追加されたことに注意してください (下の図に示すように、ツリーの一番下に表示される可能性があります)。

ツリーは次のようになります。

                     E 
                   / | \ 
                  /  |  \
                 E   -   T    <--  - evaluates 3rd 
               / | \     '
              /  |  \    '
             E   +   T   i    <--  + evaluates 2nd 
             '       |    
             '       |
             i       X 
                   / | \
                  /  |  \ 
                 X   ^   Y     <--  ^ evaluates first 
                 '       '
                 '       '
                 i       i
    NOTE:

    in tree  '  means more than one steps 
             '
    ^ has higher precedence 

    because of Left to right associativity + evaluated before then -

このツリーの評価を開始^すると、最初に評価されます。

優先順位の高い演算子は常に一番下に追加されることを覚えておいてください。したがって、文法は演算子を後で (文の合成で) 追加できるようにする必要があります。

(なぜあなたの文法で+andを-直接生成することができるかを理解する必要があります.木からの評価点重視ET*/E -> E*T | E/T | TT -> T+F | T-F | X）

さらに、YACC ツールを使用してパーサーを作成している場合。この文法のあいまいなバージョンを使用して、生成規則の数を減らし、文法規則の外側で演算子の優先順位を指定できます (これにより、どの演算子を最初に評価するかについて大まかなアイデアが得られるため、ツリーをどのように構築する必要があるかがわかります)。そして、これはこの明確な形式よりも好ましい方法です。プロダクション ルールの数が少ないほど、小さなツリーが上位に構築されるためです (したがって、効率的なコンパイラ - 解析にかかる時間が短縮されます)。

于 2013-06-18T13:55:25.687 に答える