1

私の脳は、生産ルールからいくつかの左再帰を排除しようとして揚げられています。JavaCCを使用してコンパイラを構築しており、次の2つのプロダクションルールを使用する必要があります。

expression := fragment ( ( + | - | * | / )  fragment )*

fragment := identifier | number | ( + | - ) fragment | expression

しかし、問題は、フラグメントがフラグメントに関連する式に関連していることです。つまり、間接的な左再帰です。

私はインターネットを見回しましたが、誰もがここにあるこのアルゴリズムを使用しているようです。そのサイトでは、ここで見つけることができる直接左再帰の除去については説明していません

私は次のようなルールになります：

void expression(): {}
{
  fragment()
  (
    (< PLUS >|< MINUS >|< DIVIDE >|< ASTERISKS >)
    fragment()
  )*
}

void k(): {}
{
  (
    ((< PLUS >|< MINUS >|< DIVIDE >|< ASTERISKS >)fragment())*k()
  | fragment()
  )
} 

void fragment(): {}
{
  (
    < ID >k()
  | number()k()
  | (< PLUS >|< MINUS >)fragment()k()
)
}

それらはJavaCCで使用されるコードで書かれているので、うまくいけば理解できます。基本的に、再帰を処理するためのルールKを導入しましたが、問題はまだ存在します。ただし、Kの最初の部分は*（0回以上）であるため、K-> k（）が残り、残りが少なくなるため、ゼロに減らすことができます。再帰！！

ここからどこへ行けばいいのかわからず、髪の毛がたくさん抜けてしまいました。任意の洞察をいただければ幸いです！

4

1 に答える 1

1

expressionルールを次のように書き直すことをお勧めします。

expression := ( identifier | number | ( + | - ) fragment ) ( ( + | - | * | / ) fragment )*

事実上、これはfragment元の定義の の置換に過ぎず、Kleene 演算子がいくつかの項を便利に吸収します。

もちろん、元のルールを反映する必要がある場合は、構文解析から作成された構造が何であれ、これに対応する必要があります。

于 2012-12-22T00:42:34.553 に答える