Haskell Parser Combinators - identifiers

Question

I am trying to write my own parser combinator library in Haskell, and I am struggling with how to parse identifiers. I have a datatype defined as follows which will be part of my AST.

data Expr = Var String | .... deriving (Show)

The purpose of this expression is to hold the names of variables as I parse them. The parser is defined as follows:

identifiers :: Parser Expr
identifiers = do
  first <-  string "_" <|> alphanum
  rest  <-  many alphanum
  guard $ notElem (first:rest) keywords
  return $ Var (first:rest)

I was wondering where in the parsing do you take into account what value the identifier is bound to. For example, if you had number_of_results = 5, the parser will parse the name of the identifier, but how do you keep reference to what the value of the identifier is?

I was initially considering redefining the data type as follows:

data Expr = Var String Value | .... deriving (Show)

and then, in the parsing stage, continue parsing until I get to a value.

However, I am not too sure whether I should do it like this... Could someone suggest a solution to this problem?

MathematicalOrchid · Accepted Answer · 2016-08-31 11:10:17Z

2

It's not the parser's job to figure out what the value of an expression is — that's the job of the interpreter. The parser's job is merely to turn a wedge of text into something easier for an interpreter to work with.

In this case, you'd probably do something like

data Expr = Assign String Value | Var String | ...

You may or may not want to distinguish between expressions (which just produce a result) and statements (that do flow control and so on). It depends how complicated the language you're trying to parse is.

You may also want to change this to Assign String Expr, since you can (presumably?) assign the result of an arbitrary expression to a variable, not merely a constant like 5.

Once you've built a parser that turns text into this structure, then writing an interpreter that "executes" the program as another, separate, task.

answered Aug 31, 2016 at 11:10

MathematicalOrchid

63.1k21 gold badges131 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Yusuf Over a year ago

ah i see, thank you. Quick qs, i was wondering why in your definition for the Expr data type, you have the Var value constructor, what purpose does it serve? I was under the impression that if you had a statement like x = 5, the parser will convert it in to something like (Assign x (Int 5)). Is your var case for variable declarations that do not have a binding initially, e.g x; ?

MathematicalOrchid Over a year ago

@Zubair What does "5 + x" parse into?

Yusuf Over a year ago

ah i see, assuming we have the relevant data types defined, i would assume something of the sort : BinApp Add (Lit Int 5) ( Var x), thank you for the clarification.

Yusuf Over a year ago

random sidenote, why cant I @ you?

Daniel Wagner Over a year ago

@Zubair The author of the question or answer you are commenting on always gets notified and are assumed to be the target of a comment by default, so adding an @ for them is considered redundant.

Collectives™ on Stack Overflow

Haskell Parser Combinators - identifiers

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related