2

ネストされたリストを解析するための LALR 文法を作成したいのですが、常にシフト/リデュースの競合が発生します。

type1 アイテムと list2 のリストである list1 があります。

<list1> ::= <type1> | <type1> <list1> ;
<type1> ::= A | B | <list2> ;

そして、type2 項目のリストである list2 があります。

<list2> ::= <type2> | <type2> <list2> ;
<type2> ::= X | Y ;

この文法はシフト/リデュース エラーを生成します。どうすれば回避できますか？

これは具体的なBiglooソースです。

(lalr-grammar 
  (comment
   new-line 
   text-chunk
   white-space)
  (input
   (()                '())
   ((node-list)       node-list))
  (node-list
   ((node)            (cons node '()))
   ((node node-list)  (cons node node-list)))
  (node
   ((comment)         (cons 'comment comment))
   ((new-line)        (cons 'new-line new-line))
   ((text)            (cons 'text text))
   ((white-space)     (cons 'white-space white-space)))
  (text
   ((text-chunk)      (cons 'text text-chunk))
   ((text-chunk text) (cons 'text (string-append text-chunk text)))))

ターミナルは、コメント、改行、テキストチャンク、および空白です。非ターミナルは、input、node-list、node、および text です。

Bigloo は、テキストからテキストチャンクへの reduce ルールについて不平を言っています。

*** WARNING:bigloo:lalr-grammar
** Shift/Reduce conflict: 
 - shift to state 2
 - reduce rule (text --> text-chunk)
on token `text-chunk'

しかし、これは Bigloo の問題ではないと思います。文法の問題のようです。

4

1 に答える 1

2

インスタンスのシーケンスはレベルでtype2蓄積できるため、文法は実際にはあいまいですが、インスタンスのシーケンスと見なすこともできます。list2type1

たとえば、この入力

 X X

として解析できます

 list1(
   type1(
     list2(
       type2(
         X)
       list2(
         type2(
           X)))))

だけでなく

 list1(
   type1(
     list2(
       type2(
         X)))
   list1(
     type1(
       list2(
         type2(
           X)))))

list1レベルに区切り文字を導入するのはどうですか? これで問題は解決します。

于 2011-09-28T12:12:09.043 に答える