Вложенные парсеры в счастливый / бесконечный цикл?

Question

Я пытаюсь написать парсер для простого языка разметки с happy.В настоящее время у меня есть некоторые проблемы с бесконечными циклами и вложенными элементами.

Мой язык разметки в основном состоит из двух элементов, один для "обычного" текста и один для выделенного / выделенного текста.

data Markup
    = MarkupText   String
    | MarkupEmph   [Markup]

Например, текст, подобный Foo *bar*, должен анализироваться как [MarkupText "Foo ", MarkupEmph [MarkupText "bar"]].

Лексирование этого примера работает нормально, но при его разборе получается бесконечный цикл - иЯ не понимаю почему.Это мой текущий подход:

-- 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 }

Что не так с этим подходом?Как можно решить?

Обновление: Извините.Лексинг работал не так, как ожидалось.Бесконечный цикл был внутри лексера.Сожалею.:)

Обновление 2: По запросу я использую это как лексер:

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 = (/= '*')

Произошла бесконечная рекурсия, потому что вместо * было lexer str1027 * в этом первом правиле для '*'.Не видел, потому что мой настоящий код был немного сложнее.:)

Answer 1

Сразу предупреждаю, что я имел дело с генераторами синтаксических анализаторов.

Может показаться, что вам нужен анализатор LR (1), который я не уверен, что Happy это.Я уверен, что когда я напишу это, кто-то сможет исправить меня.

Если ваш парсер не может смотреть вперед, он застрянет на этом утверждении навсегда

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

Он будет искатьMarkups1, который в свою очередь ищет Markups1.Лучшее, что я могу догадаться, это не заглядывать в Markup1 вперед, чтобы увидеть, является ли она строкой.

Попробуйте переписать это так, затем попытайтесь найти другую строку, если она не найдет ее, она должна завершить этот оператор.