2

if-then[-else] ケースを解析するための正しいルールを作成するにはどうすればよいですか? ここにいくつかの文法があります：

{
 module TestGram (tparse) where
}

%tokentype    { String  }
%token one    { "1"     } 
       if     { "if"    }
       then   { "then"  }
       else   { "else"  }

%name tparse  

%%

statement : if one then statement else statement {"if 1 then ("++$4++") else ("++$6++")"}
          | if one then statement                {"if 1 then ("++$4++")"}
          | one                                  {"1"}


{
 happyError = error "parse error"
}

この文法は、次の式を正しく解析します。

> tparse ["if","1","then","if","1","then","1","else","1"]
"if 1 then (if 1 then (1) else (1))"

ただし、コンパイルすると、シフト/削減の競合に関する警告が発生します。幸福へのドキュメントには、そのような競合の例が含まれています: http://www.haskell.org/happy/doc/html/sec-conflict-tips.html

示されている解決策は 2 つあります。1 つ目は、再帰型を変更することです (この場合の方法は明確ではありません)。2 つ目は、何も変えないことです。このオプションは私には問題ありませんが、相談が必要です。

4

1 に答える 1

5

これは、S / Rの競合なしに、LALR（1）の文法で解決できることに注意してください。

stmt: open
    | closed

open: if one then stmt             {"if 1 then ("++$4++")"}
    | if one then closed else open {"if 1 then ("++$4++") else ("++$6++")"}

closed: one                            {"1"}
      | if one then closed else closed {"if 1 then ("++$4++") else ("++$6++")"}

アイデアは、ぶら下がっているelse/if-elseのあいまいさを解決するためのこのページから来ています。

基本的な概念は、ステートメントを「open」または「closed」として分類することです。openステートメントは、次のelseとペアになっていない場合、少なくとも1つあるステートメントです。閉じているのは、まったくない、またはあるが、他のすべてとペアになっているものです。

if one then if one then one else oneしたがって、構文解析は次のように解析します。

  • . if—シフト
  • if . one—シフト
  • if one . then—シフト
  • if one then . if—シフト
  • if one then if . one—シフト
  • if one then if one . then—シフト
  • if one then if one then . one—シフト
  • if one then if one then (one) . else—ルール1で削減closed
  • if one then if one then closed . else—シフト
  • if one then if one then closed else . one—シフト
  • if one then if one then closed else (one) .—ルール1で削減closed
  • if one then (if one then closed else closed) .—ルール2で削減closed
  • if one then (closed) .—ルール2で削減stmt
  • (if one then stmt) .—ルール1で削減open
  • (open) .—ルール1で削減stmt
  • stmt .- 止まる

（リデュースが発生すると、どのリダクションルールが発生するかを示し、リデュースされるトークンを括弧で囲みます。）

LALR（1）にはパーサーにあいまいさがなく（つまり、Happyまたはbison私たちに教えてくれます;-)）、ルールに従うと正しい解釈が生成され、 elseと一緒に縮小された場合は内部が生成されることがわかります。

于 2012-05-26T11:59:18.210 に答える