sum-type inifinite再帰における左回帰文法の解析

Question

から最新のコンパイラ実装であるのTiger言語用のパーサを作成しようとしています。再帰型の1つに固執しています。

私は次の文法では、次のタイプ

data LValue =                              
    Id Atom                               
    | RecordAccess LValue Atom                          
    | ArraySubscript LValue Expression 

あります

lvalue -> id 
     -> lvalue.id 
     -> lvalue[exp] 
id -> atom 
exp -> (the big, overarching, everything-is-an-expression type) 

をそして私はParsecのとそれを解析しようとしているが、私は無限再帰ループで立ち往生しています。ここに私の現在のベースのパーサーです：

lvalueParser :: Parsec String() LValue                        
lvalueParser =                              
    try (Id <$> (atomParser <* (notFollowedBy (char '.'))))                   
    <|> try recordAccessParser                          
    where recordAccessParser = (uncurry RecordAccess) <$> do {                  
     record <- lvalueParser;                           
     char '.';                              
     atom <- atomParser;                           
     return (record, atom)                          
     } 

（注：私はまだArrayAccess部分を処理するために何かを実装しようとしていない）

明らかに、無限loopinessがlvalueParserに戻ったときにrecordAccessParser電話をたまたま。

私はthusly recordAccessParserを変更することができます。

recordAccessParser = (uncurry RecordAccess) <$> do {                  
      record <- atomParser;                           
      char '.';                              
      atom <- atomParser;                           
      return (Id record, atom)                          
      } 

、それが終了します。しかし、それは深い単一レベルよりも多くのレコードアクセス解析を行いません。

Parsec.parse lvalueParser "" "record_1.field_1.field_2" 
#=> RecordAccess (Id record_1) (Id field_1) 

をそして私は、私はchainl1に見えたが、連鎖パーサのタイプはa -> a -> aで、doesnのこと

#=> RecordAccess (RecordAccess (Id record_1) (Id field_1)) (Id field_2) 

を期待します文法を反映するLValueの種類に一致しません。私はまたmanyを見た;しかし、私は各用語の定数プレフィックスを持っていません - 左の再帰用語は、私が結果の型の一部に解析しようとしているものです。

私はParsec/Parsingの具体的な概念が不足していて、正しい方向を指していると思っています。言語の中には、これと同じ構文を持つパーサーを作成する他のタイプもあります。

Answer 1

あなたがここにchainl1、 を使用cannnotけれどもあなたは、このようなchainl1様コンビネータ定義することができます。

leftRec :: (Stream s m t) 
     => ParsecT s u m a -> ParsecT s u m (a -> a) -> ParsecT s u m a 
leftRec p op = rest =<< p 
    where 
    rest x = do f <- op 
       rest (f x) 
      <|> return x 

を私はこれを実装するためにhereを相談しました。 次のように、このコンビネータを使用することにより、lvalueParserを定義することができる。

lvalueParser :: Parser LValue 
lvalueParser = leftRec idParser (recordAccessModifier <|> arraySubscriptModifier) 
    where 
    idParser = Id <$> atomParser 
    recordAccessModifier = do 
     a <- char '.' *> atomParser 
     return (\l -> RecordAccess l a) 
    arraySubscriptModifier = do 
     e <- between (char '[') (char ']') expParser 
     return (\l -> ArraySubscript l e) 

例：

main = parseTest lvalueParser "x.y[2].z" 
-- => RecordAccess (ArraySubscript (RecordAccess (Id 'x') 'y') (ENat 2)) 'z' 

Atom、Expression、以下のようにそれらのパーサが定義されている。実際に

type Atom = Char 
atomParser :: Parser Atom 
atomParser = letter <?> "atom" 

data Expression = ENat Int 
    deriving Show 
expParser :: Parser Expression 
expParser = (ENat . read) <$> many digit 

Answer 2

左再帰文法を左再帰をサポートしないツールで解析する通常の方法は、実際には左再帰を繰り返し（つまりmany）に置き換えることです。

record <- atomParser                          
fields <- many (char '.' >> idParser) 

は今、あなたはのLValueとリストを持っている：意味しているParsecの面では

lvalue ::= primaryLValue ('.' ID)* 

で

lvalue ::= lvalue '.' ID 
     | primaryLValue 

のようなルールを置き換える意味だろうレコード・アクセスのための0個以上のフィールド名はあなたのASTタイプに合っていませんが、RecordAccessコンストラクターをリストの上に折り畳むことでそれを解決できます。