0

Haskell のように、通常の中置操作と中置セクションを含む文法の yacc のような実装 (特に ocamlyacc を使用) に問題があります。私はこれらすべてが文法的であることを望みます:

(+1)
(1+)
(+)
(1+1)

ただし、結合性/優先順位の宣言をいじっても、これを機能させることができませんでした。問題が発生している場所は grammar.output で確認できますが (削減したい場所に移動しています)、思い通りに進むように誘導することはできませんでした。これは、問題の単純化されたデモンストレーションです。

lex.mll には次のものがあります。

{
  open Parse
  exception Eof
}
rule token = parse
  | [' ' '\t'] { token lexbuf }
  | ['\n'] { EOL }
  | ['0'-'9']+ as num {INT(int_of_string num)}
  | '+' { PLUS }
  | '*' { TIMES }
  | '(' { LPAREN }
  | ')' { RPAREN }
  | eof { raise Eof }

main.ml には次のものがあります。

let _ =
  try
    let lexbuf = Lexing.from_channel stdin in
    while true do
      let result = Parse.start Lex.token lexbuf in
      print_string result; print_newline(); flush stdout
    done
  with Lex.Eof -> exit 0

そしてparse.mly（問題があるところ）には次のものがあります：

%token <int> INT
%token PLUS TIMES
%token LPAREN RPAREN
%token EOL

%left PLUS
%left TIMES

%start start
%type <string> start
%%

start:
| expr EOL {$1}
;

expr:
| application {$1}
| expr PLUS expr {"[" ^ $1 ^ "+" ^ $3 ^"]"}
| expr TIMES expr {"[" ^ $1 ^ "*" ^ $3 ^"]"}
;

section:
| LPAREN atom PLUS RPAREN { "(" ^ $2 ^ " +)" }
| LPAREN PLUS atom RPAREN { "(+ " ^ $3 ^ ")" }
| LPAREN PLUS RPAREN { "(+)" }
;

application:
| atom {$1}
| application atom {"[" ^ $1 ^ " " ^ $2 ^ "]"}
;

atom:
| INT {string_of_int $1}
| section { $1 }
| LPAREN expr RPAREN { "(" ^ $2 ^ ")" }
;

%%

それを実行ocamlyaccすると、 があることがわかります1 shift/reduce conflict。特に、詳細ログの関連部分は次のとおりです。

Rules:
   6  section : LPAREN atom PLUS RPAREN
   ...
   9  application : atom
...
12: shift/reduce conflict (shift 21, reduce 9) on PLUS
state 12
        section : LPAREN atom . PLUS RPAREN  (6)
        application : atom .  (9)

        PLUS  shift 21
        INT  reduce 9
        MINUS  reduce 9
        TIMES  reduce 9
        LPAREN  reduce 9
        RPAREN  reduce 9
...
state 21
        section : LPAREN atom PLUS . RPAREN  (6)

        RPAREN  shift 26
        .  error

コンパイルされたプログラムを実行すると、次のすべてが正しく解析されます。

(1+)
(+1)
(+)
1+2

しかし、次のように失敗します:

(1+2)

一方、HIGH優先度の高いダミー トークンを作成する場合:

%left PLUS MINUS
%left TIMES
%nonassoc HIGH

次に%prec HIGH、ルール 9 を適用します。

application: atom %prec HIGH {$1}

その場合(1+2)は解析しますが、し(1+)ません。

shift/reduce 競合の一般的な背景を理解しています。この解析の課題を解決するために交渉する方法がわかりません。

4

1 に答える 1

1

多くの文法を除外すると、次のような表現が得られます。これらはすべて同時に実行可能です。

atom:    LPAREN expr RPAREN
expr:           expr PLUS expr
section: LPAREN atom PLUS RPAREN

( 0つまり、 anLPARENと anを読んだところINTで、次のトークンは+です。この時点で、 を に減らす必要がありますINTが、その後に続くものがまたはルールatomに一致するかどうかはわかりません。ルールに一致するには、 を-- 経由で--に減らす必要がありますが、ルールに一致するには、 のままにしておく必要があります。したがって、シフト/リデュースの競合があります。今シフトする必要があるのか​​、それともさらにユニット削減を行った後にシフトする必要があるのか​​ はわかりません。atomsectionatomatomexprapplicationsectionatom+

簡単な解決策は、決定を遅らせることです。sectionルールが次の場合:

section: LPAREN expr PLUS RPAREN

それなら問題ないでしょう。が得られるまでユニットの削減を続けexpr、次に をシフトし+、 を確認する)か、 を開始できる何かを確認しexprます。競合が解決しました。

もちろん、それは言語を変更し、より寛容にします。受け入れたくない場合があります:

( 3 + 4 + )

また

( (+) 3 4 + )

しかし、結果の文法はあいまいではありません。が適切に制限されているsectionかどうかを確認することで、パーサーを続行させ、 を減らすときにエラー メッセージを発行することができます。$2(これはかなり一般的な手法であり、何も問題はありません。)

または、分離することもできます

expr: expr PLUS expr

2 つの相互に排他的な選択肢にルールを適用します。

expr: atom PLUS expr
expr: expr_not_an_atom PLUS expr

atomを に減らすことができなかったため、これによって競合も解決されexpr_not_an_atomます。しかし、どのように を定義するかという問題は未解決のままexpr_not_an_atomです。

たまたま、それが可能であると確信していますが、それはそれほど簡単ではなく、その結果は文法に波及します. 正規表現とは異なり、CFG は否定や集合差の下で閉じられないため、アルゴリズムを提供することもできません。ただし、基本的には、非終端記号をカスケードして分割し、各選択肢がatomorのいずれかに収まるようにする必要がありますexpr_not_an_atom。これも正当なアプローチですが、結果の文法は読みにくい場合があります。

を使用していた場合bisonは、別の方法があります: GLR 文法を生成します。言語があいまいでない限り、GLR 文法は正しい解析を見つけます。おそらく少し遅くなりますが、労力は大幅に軽減されます。

それが役立つ場合に備えて、非ターミナルを分割するための完全に解決されたソリューションを作成した、わずかに関連する回答を次に示します。

于 2015-03-16T05:19:13.677 に答える