Verschachtelte Parser in Happy/Endlosschleife?

Question

Ich versuche, einen Parser für eine einfache Auszeichnungssprache mit Happy zu schreiben. Momentan habe ich Probleme mit infinit Loops und verschachtelten Elementen.

Meine Markup-Sprache besteht im Wesentlichen aus zwei Elementen, einem für "normalen" Text und einem für fett/hervorgehobenen Text.

data Markup 
    = MarkupText String 
    | MarkupEmph [Markup] 

Zum Beispiel kann ein Text wie Foo *bar* sollte als [MarkupText "Foo ", MarkupEmph [MarkupText "bar"]] analysiert bekommen.

Lexing dieses Beispiels funktioniert gut, aber die Analyse führt zu einer Endlosschleife - und ich kann nicht sehen, warum. Dies ist mein derzeitiger Ansatz:

-- The main parser: Parsing a list of "Markup" 
Markups  :: { [Markup] } 
      : Markups Markup     { $1 ++ [$2] } 
      | Markup       { [$1]  } 

-- One single markup element 
Markup  :: { Markup } 
      : '*' Markups1 '*'     { MarkupEmph $2 } 
      | Markup1       { $1   } 

-- The nested list inside *..* 
Markups1 :: { [Markup] } 
      : Markups1 Markup1     { $1 ++ [$2] } 
      | Markup1       { [$1]  } 

-- Markup which is always available: 
Markup1  :: { Markup } 
      : String       { MarkupText $1 } 

Was ist falsch an diesem Ansatz? Wie könnte das gelöst werden?

Aktualisierung: Entschuldigung. Lexing funktionierte nicht wie erwartet. Die Unendlichkeitsschleife war im Lexer. Es tut uns leid. :)

Update 2: Auf Wunsch Ich verwende dies als Lexer:

lexer :: String -> [Token] 
lexer [] = [] 
lexer str@(c:cs) 

    | c == '*'    = TokenSymbol "*" : lexer cs 
    -- ...more rules... 
    | otherwise    = TokenString val : lexer rest 

    where (val, rest) = span isValidChar str 
     isValidChar = (/= '*') 

Die infinit Rekursion aufgetreten, weil ich lexer str hatte statt lexer cs in dieser ersten Regel für '*'. Habe es nicht gesehen, weil mein tatsächlicher Code etwas komplexer war. :)

Answer 1

Nur eine Warnung, es ist eine Weile her, seit ich Parser-Generatoren behandelt habe.

Es scheint, dass Sie einen LR (1) Parser brauchen, der nicht sicher ist, glücklich ist. Ich bin positiv, sobald ich das schreibe, wird jemand in der Lage sein, mich zu korrigieren.

Wenn Ihr Parser nicht nach vorne schauen kann es auf dieser Aussage stecken für immer

Markups1 :: { [Markup] } 
     : Markups1 Markup1 
     | Markup1 

Es wird für einen Markups1 suchen, was wiederum für eine Markups1 aussieht. Das Beste, was ich erraten kann, ist, dass ich nicht nach Markup1 schaue, um zu sehen, ob es eine Zeichenkette ist.

Probieren Sie es wie diese

Markups1 :: { [Markup] } 
     : Markup1 Markups1 
     | 

Umschreiben Im Wesentlichen Sie es wollen zuerst die Zeichenfolge zu finden, dann versuchen, für eine andere Zeichenfolge zu suchen, wenn es einen nicht findet es braucht, um diese Aussage zu beenden.