Left Factoring using Parsec

2
votes

Helllo, I have the following syntax:

<attribute_value> ::= <spec_constant> | <symbol> | ( <s_expr>*)
<attribute>       ::= <keyword> | <keyword> <attribute_value>

by reading a tutorial, it says it's possible to use buildExpressionParser and it will perform Left-factoring, but there isn't an example.

Can someone give me an example on how i should parse the above syntax using Parsec or just point me in the right direction ?

Thank you for any help you can give.

1
haskellparsec
What little of your grammar you have shown is not left-recursive, so it doesn't need left-factoring. – pat
I don't know a lot about parsers, but isn't left factoring used to solve a First /First conflict? My question in <attribute> how does the parser knows which path to take between <keyword> and <keyword> <attribute_value>? – Rogerp062
Left-factoring is required when the first match in a rule is the rule itself, which leads to an infinite loop in a recursive descent parser. Here, you just need to use try to allow the parser to backtrack over the <keyword> if it doesn't find the <attribute_value>, or make the <attribute_value> optional, and remove the <keyword>-only branch. – pat
Hum, i will try it, thank you very much for your answers. – Rogerp062
@Rogerp062 Backtracking isn't even necessary, here. Your attribute parser could be composed of a keyword parser, followed by an alternative: a parser for one attribute value, or a parser that returns a default value if the previous one (i.e. the parser for one attribute value) fails. In applicative style, it could be something like: attribute = keyword *> (attributeValue <|> pure defaultValue). See the section entitled Backtracking and its discontents in chapter 16 of Real World Haskell for an example of this. – jub0bs

1 Answers

1
votes

Suppose you already have

data Keyword
data AttributeValue

data Attribute = KeywordOnly Keyword
               | KeywordWithAttribute Keyword AttributeValue

keyword :: Parser Keyword
attributeValue :: Parser AttributeValue

then you can implement attribute :: Parser Attribute by first parsing the Keyword, then optionally parsing the attribute, then combining them:

attribute :: Parser Attribute
attribute = pack <$> keyword <*> optionMaybe attributeValue
  where
    pack :: Keyword -> Maybe AttributeValue -> Attribute
    pack kw = maybe (KeywordOnly kw) (KeywordWithAttribute kw)

without having to change the structure of your grammar.