Анализ грамматики выражения с применением функции с комбинаторами-парсерами (левая рекурсия)

Question

Как упрощенная подзадача анализатора для реального языка, я пытаюсь реализовать парсер для выражений вымышленного языка, который похож на стандартные императивные языки (например, Python, JavaScript и т. д.). Его синтаксис имеет следующие особенности конструкции:

• целые числа
• идентификаторы ([a-zA-Z]+)
• арифметических выражений с + и * и скобкой
• структура доступа с . (например foo.bar.buz)
• кортежей (например, (1, foo, bar.buz)) (для устранения двусмысленности в одном кортеже записаны как (x,))
• функции приложения (например foo(1, bar, buz()))
• функции первого класса, так что они также могут быть возвращены из других функций и непосредственно применяться (например foo()() является законным, поскольку foo() может возвращать функцию)

Так довольно сложная программа в этом языке

(1+2*3, f(4,5,6)(bar) + qux.quux()().quuux) 

ассоциативность должен быть

((1+(2*3)), (((f(4,5,6))(bar)) + ((((qux.quux)())()).quuux))) 

В настоящее время я использую очень красивую uu-parsinglib аппликативную библиотеку комбинаторов парсеров.

Первая проблема была, очевидно, что грамматика интуитивного выражения (expr -> identifier | number | expr * expr | expr + expr | (expr) лево-рекурсивная. Но я мог бы решить эту проблему, используя в pChainl комбинатор (см parseExpr в примере ниже).

Остающейся проблему (отсюда этот вопрос) является функциональным приложением с функциями, возвращаемыми из других функций (f()()). Опять же, грамматика оставлена ​​рекурсивной expr -> fun-call | ...; fun-call -> expr (parameter-list). Любые идеи, как я могу решить эту проблему элегантно, используя uu-parsinglib? (проблема должна быть непосредственно применима к parsec, attoparsec и другому парсеру Комбинаторы, как я полагаю).

См. Ниже мою текущую версию программы. Он хорошо работает, но функция приложение работает только с идентификаторами, чтобы удалить левую рекурсию:

{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE RankNTypes #-} 

module TestExprGrammar 
    (
    ) where 

import Data.Foldable (asum) 
import Data.List (intercalate) 
import Text.ParserCombinators.UU 
import Text.ParserCombinators.UU.Utils 
import Text.ParserCombinators.UU.BasicInstances 

data Node = 
    NumberLiteral Integer 
    | Identifier String 
    | Tuple [Node] 
    | MemberAccess Node Node 
    | FunctionCall Node [Node] 
    | BinaryOperation String Node Node 

parseFunctionCall :: Parser Node 
parseFunctionCall = 
    FunctionCall <$> 
     parseIdentifier {- `parseExpr' would be correct but left-recursive -} 
     <*> parseParenthesisedNodeList 0 

operators :: [[(Char, Node -> Node -> Node)]] 
operators = [ [('+', BinaryOperation "+")] 
      , [('*' , BinaryOperation "*")] 
      , [('.', MemberAccess)] 
      ] 

samePrio :: [(Char, Node -> Node -> Node)] -> Parser (Node -> Node -> Node) 
samePrio ops = asum [op <$ pSym c <* pSpaces | (c, op) <- ops] 

parseExpr :: Parser Node 
parseExpr = 
    foldr pChainl 
      (parseIdentifier 
      <|> parseNumber 
      <|> parseTuple 
      <|> parseFunctionCall 
      <|> pParens parseExpr 
      ) 
      (map samePrio operators) 

parseNodeList :: Int -> Parser [Node] 
parseNodeList n = 
    case n of 
     _ | n < 0 -> parseNodeList 0 
     0 -> pListSep (pSymbol ",") parseExpr 
     n -> (:) <$> 
      parseExpr 
      <* pSymbol "," 
      <*> parseNodeList (n-1) 

parseParenthesisedNodeList :: Int -> Parser [Node] 
parseParenthesisedNodeList n = pParens (parseNodeList n) 

parseIdentifier :: Parser Node 
parseIdentifier = Identifier <$> pSome pLetter <* pSpaces 

parseNumber :: Parser Node 
parseNumber = NumberLiteral <$> pNatural 

parseTuple :: Parser Node 
parseTuple = 
    Tuple <$> parseParenthesisedNodeList 1 
    <|> Tuple [] <$ pSymbol "()" 

instance Show Node where 
    show n = 
     let showNodeList ns = intercalate ", " (map show ns) 
      showParenthesisedNodeList ns = "(" ++ showNodeList ns ++ ")" 
     in case n of 
       Identifier i -> i 
       Tuple ns -> showParenthesisedNodeList ns 
       NumberLiteral n -> show n 
       FunctionCall f args -> show f ++ showParenthesisedNodeList args 
       MemberAccess f g -> show f ++ "." ++ show g 
       BinaryOperation op l r -> "(" ++ show l ++ op ++ show r ++ ")" 

Answer 1

кратко Глядя на the list-like combinators для uu-parsinglib (я больше знаком с parsec), я думаю, вы можете решить эту проблему путем складывания над результатом pSome комбинатора:

parseFunctionCall :: Parser Node 
parseFunctionCall = 
    foldl' FunctionCall <$> 
     parseIdentifier {- `parseExpr' would be correct but left-recursive -} 
     <*> pSome (parseParenthesisedNodeList 0) 

Это также эквивалентно Alternativesome, который должен действительно применяться к другим синтаксическим анализам, которые вы упомянули.

Answer 2

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

E -> T E' 
E' -> + TE' | eps 
T -> F T' 
T' -> * FT' | eps 
F -> NUMBER | ID | (E) 

Чтобы добавить приложение функции, вы должны решить, какой уровень его приоритета. На большинстве языков я видел, что он самый высокий. Таким образом, вы добавили бы еще один уровень производств для применения функций.

E -> T E' 
E' -> + TE' | eps 
T -> AT' 
T' -> * A T' | eps 
A -> F A' 
A' -> (E) A' | eps 
F -> NUMBER | ID | (E) 

Да, это волосатая грамматика и больше, чем левая рекурсивная. Это цена прогнозирующего синтаксического анализа сверху вниз. Если вы хотите, чтобы более простые грамматики использовали генератор парсера снизу вверх, я пытаюсь.