Parser Combinators

Parser combinators take lists of tokens and produce a parse tree for us.

• Atomic parsers have a concrete task of parsing a number or keyword.
• Sequence and alternative parsers build bigger parsers out of smaller components.
• Semantic action (map-parser) is applying a function to the parsed part.

Examples of parsers

• Atomic parser, for example, for number tokens:

  $$\begin{array}{rl}\text{Num}(123)::\text{rest}& \Rightarrow \{(\text{Num}(123),\text{rest})\}\\ \text{Char}{(}^{\prime }{a}^{\prime })::\text{rest}& \Rightarrow \{\}\end{array}$$

  You consume one or more tokens from the input stream. This also works for characters and strings.

• Alternative parser (code $p||q$) Apply $p$ and also $q$ then combine the outputs

  $$p(\text{input})\cup q(\text{input})$$

• Sequence parser (code $p\sim q$) Apply first $p$ producing a set of pairs Then apply $q$ to the unparsed parts Then combine the results:

  $$(({\text{output}}_1,{\text{output}}_2),\text{unparsed part})$$ $$\begin{array}{rl}\{((o_1,o_2),u_2)& |\\ (o_1,u_1)& \in p(\text{input})\wedge \\ (o_2,u_2)& \in q(u_1)\}\end{array}$$

• Map-parser (code $p.map(f)$) Apply $p$ producing a set of pairs Then apply the function $f$ to each first component

  $$\{(f(o_1),u_1)|(o_1,u_1)\in p(\text{input})\}$$

  $f$ is the semantic action (what to do with the parsed input)

  Semantic Actions Addition

  $$T\sim +\sim E\Rightarrow \underset{\text{semantic action}}{\underbrace{f((x,y),z)\Rightarrow x+z}}$$

  Multiplication

  $$F\sim \ast \sim T\Rightarrow f((x,y),z)\Rightarrow x\ast z$$

  Parenthesis

  $$(\sim E\sim )\Rightarrow f((x,y),z)\Rightarrow y$$