행복한/무한 루프의 중첩 된 파서?

Question

간단한 마크 업 언어에 대한 파서를 행복하게 작성하려고합니다. 현재, 무한 루프와 중첩 요소에 문제가 있습니다.

내 마크 업 언어는 기본적으로 두 개의 요소, 하나는 "일반"텍스트, 다른 하나는 굵게/강조된 텍스트로 구성됩니다.

data Markup 
    = MarkupText String 
    | MarkupEmph [Markup] 

는 예를 들어, Foo *bar* 같은 텍스트는 [MarkupText "Foo ", MarkupEmph [MarkupText "bar"]]로 분석을하셔야합니다.

예제의 Lexing은 잘 작동하지만 구문 분석을하면 무한 루프가 발생합니다. - 이유를 알 수 없습니다. 이것은 현재 내 접근 방식입니다.

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

그 방법에는 어떤 문제가 있습니까? 어떻게 해결 될 수 있습니까?

업데이트 : 죄송합니다. Lexing은 예상대로 작동하지 않았습니다. 무한 루프는 렉서 내부에있었습니다. 죄송합니다. :)

업데이트 2 : 요청에, 내가 렉서으로 이것을 사용하고 있습니다 : 나는 '*'에 대한 첫 번째 규칙에 lexer str 대신 lexer cs 있었기 때문에

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

infinit 재귀가 발생했습니다. 내 실제 코드가 좀 더 복잡하기 때문에 그것을 보지 못했습니다. :)

Answer 1

파서 생성기를 처리 한 이후로 한동안 경고했습니다.

해피가 확실하지 않은 LR (1) 구문 분석기가 필요합니다. 나는 누군가가 나를 바로 잡을 수있을 것이라고 내가 이것을 쓰면 긍정적이다. 파서는 예견 할 수없는 경우

가이 문에 붙어됩니다 영원히

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

그것은 차례로 Markups1를 찾는 Markups1, 찾습니다. 내가 추측 할 수있는 가장 좋은 것은 Markup1이 문자열인지 알아보기위한 것이 아닙니다.

는 그것이 그 문을 종료해야 하나를 찾을 수없는 경우, 다른 문자열을 찾아하려고하면 먼저 문자열을 찾으려면 기본적으로이

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

처럼 다시 작성하십시오.