求和型无限递归中左递归语法的解析

Question

我正在尝试从ML 中的现代编译器实现为 Tiger 语言编写一个解析器，但陷入了其中一种递归类型。

我有以下类型

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)

我试图用秒差距解析它，但我陷入了无限递归循环。这是我当前的基本解析器：

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部分的方法）

显然，当回调recordAccessParser到lvalueParser.

我可以这样改变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)

我期望

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

我查看了chainl1，但链接解析器的类型是，并且它与反映语法的a -> a -> a类型不匹配。LValue我也看了many；但是我没有每个术语的常量前缀 - 左递归术语是我试图解析为结果类型的一部分。

我想我错过了秒差距/解析的特定概念，并且很乐意指出正确的方向。我正在为其编写解析器的语言中有更多类型，它们将具有类似的结构。

Answer 1

使用不支持左递归的工具解析左递归语法的通常方法实际上是用重复替换左递归（即many）。对于记录访问，这意味着替换类似的规则

lvalue ::= lvalue '.' ID
         | primaryLValue

和

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

就秒差距而言，这意味着：

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

现在您有一个LValue包含 0 个或多个字段名称的列表，这不适合您的 AST 类型，但您可以通过将RecordAccess构造函数折叠到列表上来解决这个问题。