代码之家 › 专栏 › 技术社区 › Davidbrcz

Parsec解析不同类型语句的列表

parsec haskell parsing

Davidbrcz · 技术社区 · 4 年前

我(目前)正在尝试解析Dot语言的一个子集。语法是 here 我的代码如下

import System.Environment
import System.IO
import qualified Text.Parsec.Token as P
import Text.ParserCombinators.Parsec.Char -- for letter
import Text.Parsec
import qualified Control.Applicative as App

import Lib
type Id = String
data Dot = Undirected Id  Stmts
         | Directed Id  Stmts
         deriving (Show)

data Stmt = NodeStmt Node | EdgeStmt Edges
          deriving (Show)
type Stmts = [Stmt]

data Node = Node Id Attributes deriving (Show)
data Edge =  Edge Id Id deriving (Show)
type Edges = [Edge]

data Attribute = Attribute Id Id deriving (Show)
type Attributes = [Attribute]

dotDef :: P.LanguageDef st
dotDef = P.LanguageDef
  { P.commentStart    = "/*"
  , P.commentEnd      = "*/"
  , P.commentLine     = "//"
  , P.nestedComments  = True
  , P.identStart      = letter
  , P.identLetter     = alphaNum
  , P.reservedNames   = ["node", "edge", "graph", "digraph", "subgraph", "strict" ]
  , P.caseSensitive   = True
  , P.opStart         = oneOf "-="
  , P.opLetter        = oneOf "->"
  , P.reservedOpNames = []
  }



lexer = P.makeTokenParser dotDef

brackets    = P.brackets lexer
braces      = P.braces lexer

identifier  = P.identifier lexer
reserved    = P.reserved lexer

semi = P.semi lexer
comma = P.comma lexer

reservedOp = P.reservedOp lexer

eq_op = reservedOp "="
undir_edge_op = reservedOp "--"
dir_edge_op = reservedOp "->"

edge_op = undir_edge_op <|> dir_edge_op

-- -> Attribute
attribute = do
  id1 <- identifier
  eq_op
  id2 <- identifier
  optional (semi <|> comma)
  return $ Attribute id1 id2

a_list = many attribute

bracked_alist =
  brackets $ option [] a_list

attributes =
  do
    nestedAttributes <- many1 bracked_alist
    return $ concat nestedAttributes


nodeStmt = do
  nodeName <- identifier
  attr <- option [] attributes
  return $ NodeStmt $ Node nodeName attr

dropLast = reverse . tail . reverse

edgeStmt = do
  nodes <- identifier `sepBy1` edge_op
  return $ EdgeStmt $ fmap (\x -> Edge (fst x) (snd x)) (zip (dropLast nodes) (tail nodes))


stmt = do
  x <- nodeStmt <|> edgeStmt
  optional semi
  return x

stmt_list = many stmt
graphDecl = do
  reserved "graph"
  varName <- option "" identifier
  stms <- braces stmt_list
  return $ Undirected varName stms

digraphDecl = do
  reserved "digraph"
  varName <- option "" identifier
  stms <- braces stmt_list
  return $ Directed varName stms

topLevel3 = do
  spaces
  graphDecl <|> digraphDecl

main :: IO ()
main = do
  (file:_) <- getArgs
  content <- readFile file
  case parse topLevel3 "" content of
    Right g -> print g
    Left err -> print err

鉴于此输入

digraph PZIFOZBO{
        a[toto = bar] b ;   c  ; w  // 1
        a->b // 2
        }

如果对第1行或第2行进行注释,则可以正常工作,但如果同时启用这两行,则会失败

(第3行,第10列):意外的“-”预期标识符或“}”

据我所知,解析器会选择第一个匹配规则(带回溯)。这里的边和节点语句都以and identifier开头,所以它总是选择这个。

我试着颠倒顺序 stmt ,没有任何运气。我还试着撒了一些 try 在stmt、nodeStmt和edgeStmt中,也没有运气。

任何帮助感谢。

0 回复 | 直到 4 年前

K. A. Buhr 4 年前

请注意,无论第1行是否被注释掉,我都会得到相同的错误,因此:

digraph PZIFOZBO{
        a->b
        }

还说 unexpected "-" .

我认为你的诊断是正确的,这里的问题是 stmt 解析器尝试 nodeStmt 第一。成功并解析 "a" ,离开 "->b" 尚未被消耗,但 ->b 不是有效的声明。请注意,Parsec确实如此不在没有 try 因此,当它“发现”以下情况时,它不会回去重新审视这些决定 ->b 无法解析。

您可以通过交换订单来“修复”此问题 stmt :

x <- edgeStmt <|> nodeStmt

但现在解析将在表达式上中断,如下所示 a[toto = bar] 那是因为 edgeStmt 是马车。它解析 一 作为有效声明 EdgeStmt [] 因为 sepBy1 允许单边 一 ,这不是你想要的。

如果你重写 edgeStmt 需要至少一个边缘:

import Control.Monad (guard)
edgeStmt = do
  nodes <- identifier `sepBy1` edge_op
  guard $ length nodes > 1
  return $ EdgeStmt $ fmap (\x -> Edge (fst x) (snd x)) (zip (dropLast nodes) (tail nodes))

和调整 stmt 到“ 尝试 “先执行边语句,然后回溯到节点语句:

stmt = do
  x <- try edgeStmt <|> nodeStmt
  optional semi
  return x

那么你的例子编译得很好。