Ambiguità grammaticale: perché? (Problema è: "(a)" vs "(az)")

Question

Così sto cercando di implementare un piuttosto semplice grammatica per le dichiarazioni di una sola riga:

# Grammar 

    c   : Character c  [a-z0-9-] 
    (v)  : Vowel    (= [a,e,u,i,o]) 
    (c)  : Consonant 
    (?)  : Any character (incl. number) 
    (l)  : Any alpha char  (= [a-z]) 
    (n)  : Any integer  (= [0-9]) 
    (c1-c2) : Range from char c1 to char c2 
    (c1,c2,c3) : List including chars c1, c2 and c3 

    Examples: 
    h(v)(c)no(l)(l)jj-k(n) 
    h(v)(c)no(l)(l)(a)(a)(n) 
    h(e-g)allo 
    h(e,f,g)allo 
    h(x,y,z)uul 
    h(x,y,z)(x,y,z)(x,y,z)(x,y,z)uul 

Sto usando il generatore Felice parser (http : //www.haskell.org/happy/) ma per qualche ragione sembra esserci un problema di ambiguità.

Il messaggio di errore è: "shift/ridurre i conflitti: 1"

Credo che l'ambiguità è con queste due righe:

| lBracket char rBracket    { (\c -> case c of 
               'v' -> TVowel 
               'c' -> TConsonant 
               'l' -> TLetter 
               'n' -> TNumber) $2 } 
    | lBracket char hyphen char rBracket { TRange $2 $4    } 

Un caso ad esempio è: "(a)" vs "(az)"

il lexer darebbe la seguente per i due casi:

(a) : [CLBracket, CChar 'a', CRBracket] 
(a-z) : [CLBracket, CChar 'a', CHyphen, CChar 'z', CRBracket] 

Quello che non capisco è come questo possa essere ambiguo con un parser LL [2].

In caso aiuta Ecco l'intera definizione della grammatica Felice:

{ 

module XHappyParser where 

import Data.Char 
import Prelude hiding (lex) 
import XLexer 
import XString 

} 

%name parse 
%tokentype { Character } 
%error  { parseError } 

%token 
    lBracket     { CLBracket } 
    rBracket     { CRBracket } 
    hyphen     { CHyphen  } 
    question     { CQuestion } 
    comma      { CComma  } 
    char      { CChar $$ } 

%% 

xstring : tokens       { XString (reverse $1)  } 

tokens : token        { [$1]      } 
     | tokens token      { $2 : $1     } 

token : char        { TLiteral $1    } 
     | hyphen        { TLiteral '-'    } 
     | lBracket char rBracket    { (\c -> case c of 
                'v' -> TVowel 
                'c' -> TConsonant 
                'l' -> TLetter 
                'n' -> TNumber) $2 } 
     | lBracket question rBracket   { TAny      } 
     | lBracket char hyphen char rBracket { TRange $2 $4    } 
     | lBracket listitems rBracket   { TList $2     } 

listitems : char       { [$1]      } 
      | listitems comma char   { $1 ++ [$3]    } 

{ 

parseError :: [Character] -> a 
parseError _ = error "parse error" 

} 

Grazie!

Answer 1

Ecco l'ambiguità:

token : [...] 
     | lBracket char rBracket 
     | [...] 
     | lBracket listitems rBracket 

listitems : char 
      | [...] 

il parser potrebbe accettare (v) sia come TString [TVowel] e TString [TList ['v']], per non parlare dei caratteri mancanti in quel case espressione.

Un modo per risolverlo sarebbe quella di modificare la grammatica in modo liste sono almeno due prodotti, o hanno qualche notazione diversa per le vocali, le consonanti, ecc

Answer 2

Il problema sembra essere:

| lBracket char rBracket 
... 
| lBracket listitems rBracket 

o nella sintassi più pulito:

(c) 

può essere un TVowel, TConsonant, Tletter, tNumero (come sapete) o un Singleton TList.

Come dice il manuale felice, lo spostamento ridotto di solito non è un problema. Puoi avere la precedenza per forzare il comportamento/rimuovere l'avviso, se lo desideri.