6

実際の言語のパーサーの単純化された部分問題として、標準の命令型言語 (Python、JavaScript など) に似た架空の言語の式のパーサーを実装しようとしています。その構文には、次の構造があります。

  • 整数
  • 識別子 ( [a-zA-Z]+)
  • +and*と括弧を使用した算術式
  • を使用した構造アクセス.(例: foo.bar.buz)
  • タプル (例: (1, foo, bar.buz)) (あいまいさをなくすため、1 タプルは のように記述します(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)を使用してその問題を解決できました (以下の例を参照)。pChainlparseExpr

残りの問題 (したがって、この質問) は、他の関数 ( f()()) から返された関数を使用した関数の適用です。繰り返しますが、文法は recursive のまま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 ++ ")"
4

2 に答える 2

4

私はこのライブラリを知りませんが、左再帰を削除する方法を示すことができます。標準的な右再帰式の文法は次のとおりです。

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 )

はい、これは毛むくじゃらの文法で、左の再帰的な文法よりも大きくなります。これが、トップダウンの予測解析の代償です。より単純な文法が必要な場合は、yacc のボトムアップ パーサー ジェネレーターを使用します。

于 2014-10-05T00:05:44.083 に答える