3

競合のある文法の簡素化されたバージョン:

body: variable_list function_list;
variable_list:
  variable_list variable | /* empty */
;
variable:
  TYPE identifiers ';'
;
identifiers:
  identifiers ',' IDENTIFIER | IDENTIFIER
;
function_list:
  function_list function | /* empty */
;
function:
  TYPE IDENTIFIER '(' argument_list ')' function_body
;

問題は、変数と関数の両方が TYPE と IDENTIFIER で始まることです。

int some_var;
int foo() { return 0; }

この言語では、変数は常に関数の前に宣言されますが、解析を試みると、常に

解析エラー: 構文エラー、予期しない '('、',' または ';' が必要 [foo の後]

variable_list をあまり欲張らないようにする方法、または次のトークンが ';' または ',' ではなく '(' である場合、それは明らかに関数であって変数宣言ではないことをパーサーに認識させるにはどうすればよいでしょうか?

競合の bison デバッグ出力は次のとおりです。

state 17

3 body: variable_list . function_list
27 variable_list: variable_list . variable

T_INT    shift, and go to state 27
T_BOOL   shift, and go to state 28
T_STR    shift, and go to state 29
T_VOID   shift, and go to state 30
T_TUPLE  shift, and go to state 31

T_INT     [reduce using rule 39 (function_list)]
T_BOOL    [reduce using rule 39 (function_list)]
T_STR     [reduce using rule 39 (function_list)]
T_VOID    [reduce using rule 39 (function_list)]
T_TUPLE   [reduce using rule 39 (function_list)]
$default  reduce using rule 39 (function_list)

variable       go to state 32
simpletype     go to state 33
type           go to state 34
function_list  go to state 35

reduce を優先するようにあらゆる種類の %prec ステートメントを試しましたが (この場合の違いはわかりませんが)、bison を reduce を使用してこれを解決することに成功しませんでした。また、ルールをシャッフルしてみました。 non_empty_var_list のような新しいルールを作成し、本体を function_list に分割することについて | non_empty_var_list function_list であり、どの試みもこの問題を解決しません。私はこれが初めてで、これを修正する方法のアイデアがなくなったので、完全に困惑しています。

4

1 に答える 1

8

問題は、変数と関数の両方がTYPEとIDENTIFIERで始まることです。

ではない正確に。問題は、function_listが左再帰であり、空である可能性があることです。

先読みでTYPEで終了するセミコロンに到達するvariableと、パーサーは、最初のvariable_listの生成に従って、変数をvariable_listに縮小できます。次はfunction_listかもしれませんが、function_listは空にすることができます。したがって、function_listを空に縮小することができます。これは、関数の解析を開始するために必要なものです。次の3番目のトークンである'（'を確認するまで、これを行わないことはできません。これは遠すぎて関連性がありません。

簡単な解決策は次のとおりです。

function_list: function function_list
             | /* EMPTY */
             ;

別の解決策は、function_listを非オプションにすることです。

body: variable_list function_list
    | variable_list
    ;

function_list: function_list function
             | function
             ;

そうすれば、bisonは、変数または関数の定義の開始であるかどうかを判断しなくても、TYPEトークンをシフトできます。

于 2012-10-29T03:51:45.537 に答える