parsing - 左再帰エリミネーターを実装するには?

Question

これにエリミネーターを実装するにはどうすればよいですか?

 A := AB |
      AC |
      D  |
      E  ;

Answer 1

これは、いわゆる即時左再帰の例であり、次のように削除されます。

A := DA' |
     EA' ;

A' := ε   |
      BA' |
      CA' ;

基本的な考え方は、最初に an を解析するときは必ず aまたは anAで始まることに注意することです。or an の後には、終了する (末尾が ε) か、続行する ( or構造の場合) かのいずれかになります。DEDEABAC

実際のアルゴリズムは次のように機能します。

このような左再帰的なプロダクションの場合: A -> A a1 | ... | A ak | b1 | b2 | ... | bmproduction を に置き換えて、 production をA -> b1 A' | b2 A' | ... | bm A'追加しA' -> ε | a1 A' | ... | ak A'ます。

除去アルゴリズム (間接的な左再帰の除去を含む) の詳細については、 Wikipedia: 左再帰を参照してください。

Answer 2

Another form available is:

A := (D | E) (B | C)*

The mechanics of doing it are about the same but some parsers might handle that form better. Also consider what it will take to munge the action rules along with the grammar its self; the other form requires the factoring tool to generate a new type for the A' rule to return where as this form doesn't.