Chapter 20. Parsing
Topics in This Chapter 
20.2 Combining Parser Operations
20.3 Transforming Parser Results
20.10 What Exactly Are Parsers?
In this chapter, you will see how to use the “parser combinators” library to analyze data with fixed structure. Examples of such data are programs in a programming language or data in formats such as HTTP or JSON. Not everyone needs to write parsers for these languages, so you may not find this chapter useful for your work. If you are familiar with the basic concepts of grammars and parsers, glance through the chapter anyway because the Scala parser library is a good example of a sophisticated domain-specific language embedded in the Scala language.
Note
The API documentation for Scala parser combinators is at www.scala-lang.org/api/current/scala-parser-combinators.
The key points of this chapter are:
• Alternatives, concatenation, options, and repetitions in a grammar turn into |, ~, opt, and rep in Scala combinator parsers.
• With RegexParsers, literal strings and regular expressions match tokens.
• Use ^^ to process parse results.
• Use pattern matching in a function supplied to ^^ to take apart ~ results.
• Use ~> and <~ to discard tokens that are no longer needed after matching.
• The repsep combinator handles the common case of repeated items with a separator.
• A token-based parser is useful for parsing languages with reserved words and operators. Be prepared to define your own lexer.
• Parsers are functions that consume a reader and yield a parse result: success, failure, or error.
• For a practical parser, you need to implement robust error reporting.
• Thanks to operator symbols, implicit conversions, and pattern matching, the parser combinator library makes parser writing easy for anyone who understands context-free grammars. Even if you don’t feel the urge to write your own parsers, you may find this an interesting case study for an effective domain-specific language.
20.1 Grammars
To understand the Scala parsing library, you need to know a few concepts from the theory of formal languages. A grammar is a set of rules for producing all strings that follow a particular format. For example, we can say that an arithmetic expression is given by the following rules:
• Each whole number is an arithmetic expression.
• + - * are operators.
• If left and right are arithmetic expressions and op is an operator, then left op right is an arithmetic expression.
• If expr is an arithmetic expression, then ( expr ) is an arithmetic expression.
According to these rules, 3+4 and (3+4)*5 are arithmetic expressions, but 3+) or 3^4 or 3+x are not.
A grammar is usually written in a notation called Backus-Naur Form (BNF). Here is the BNF for our expression language:
op ::= "+" | "-" | "*"
expr ::= number | expr op expr | "(" expr ")"
Here, number is undefined. We could define it as
digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
number ::= digit | digit number
But in practice, it is more efficient to collect numbers before parsing starts, in a separate step called lexical analysis. A lexer discards whitespace and comments, and forms tokens—identifiers, numbers, or symbols. In our expression language, tokens are number and the symbols + - * ( ).
Note that op and expr are not tokens. They are structural elements that were invented by the author of the grammar, in order to produce correct token sequences.
Such symbols are called nonterminal symbols. One of the nonterminal symbols is at the root of the hierarchy; in our case, that is expr. It is called the start symbol. To produce correctly formatted strings, you start with the start symbol and apply the grammar rules until all nonterminals have been replaced and only tokens remain. For example, the derivation
expr -> expr op expr -> number op expr ->
-> number "+" expr -> number "+" number
shows that 3+4 is a valid expression.
The most often used “extended Backus-Naur form,” or EBNF, allows specifying optional elements and repetition. I will use the familiar regex operators ? * + for 0 or 1, 0 or more, 1 or more, correspondingly. For example, a comma-separated list of numbers can be described with the grammar
numberList ::= number ( "," numberList )?
or with
numberList ::= number ( "," number )*
As another example of EBNF, let’s make an improvement to the grammar for arithmetic expressions to support operator precedence. Here is the revised grammar:
expr ::= term ( ( "+" | "-" ) expr )?
term ::= factor ( "*" factor )*
factor ::= number | "(" expr ")"
20.2 Combining Parser Operations
To use the Scala parsing library, provide a class that extends the Parsers trait and defines parsing operations that are combined from primitive operations, such as
• Matching a token
• Choosing between two operations (|)
• Performing two operations in sequence (~)
• Repeating an operation (rep)
• Optionally performing an operation (opt)
The following parser recognizes arithmetic expressions. It extends RegexParsers, a subtrait of Parsers that can match tokens against regular expressions. Here, we specify number with the regular expression "[0-9]+".r:
class ExprParser extends RegexParsers {
val number = "[0-9]+".r
def expr: Parser[Any] = term ~ opt(("+" | "-") ~ expr)
def term: Parser[Any] = factor ~ rep("*" ~ factor)
def factor: Parser[Any] = number | "(" ~ expr ~ ")"
}
Note that the parser is a straightforward translation from the EBNF of the preceding section.
Simply use the ~ operator to join the parts, and use opt and rep instead of ? and *.
In our example, each function has return type Parser[Any]. This type isn’t very useful, and we will improve it in the next section.
To run the parser, invoke the inherited parse method, for example:
val parser = new ExprParser
val result = parser.parseAll(parser.expr, "3-4*5")
if (result.successful) println(result.get)
The parseAll method receives the method to be invoked—that is, the method associated with the grammar’s start symbol—and the string to be parsed.
Note
There is also a parse method that parses a prefix of a string, stopping when it can’t find another match. That method isn’t very useful; for example, parser.parse(parser.expr, "3-4/5") parses 3-4, then quietly stops at the / which it cannot handle.
The output of the program snippet is
((3~List())~Some((-~((4~List((*~5)))~None))))
To interpret this output, you need to know the following:
• Literal strings and regular expressions return String values.
• p ~ q returns an instance of the ~ case class, which is very similar to a pair.
• opt(p) returns an Option, either Some(...) or None.
• rep(p) returns a List.
The call to expr returns the result from term (shown in bold) joined with something optional—the Some(...) part which I won’t analyze.
Since term is defined as
def term = factor ~ rep(("*" | "/" ) ~ factor)
it returns the result from factor joined with a List. That’s an empty list because there is no * in the subexpression to the left of the -.
Of course, this result is quite tedious. In the next section, you will see how to transform it to something more useful.
20.3 Transforming Parser Results
Instead of having a parser build up a complex structure of ~, options, and lists, you should transform intermediate outputs to a useful form. Consider, for example, the arithmetic expression parser. If it is our goal to evaluate the expression, then each of the functions expr, term, and factor should return the value of the parsed subexpression. Let’s start with
def factor: Parser[Any] = number | "(" ~ expr ~ ")"
We want it to return an Int:
def factor: Parser[Int] = ...
When a whole number is received, we want its integer value:
def factor: Parser[Int] = number ^^ { _.toInt } | ...
Here, the ^^ operator applies the function { _.toInt } to the result of number.
Note
There is no particular significance to the ^^ symbol. It conveniently has lower precedence than ~ but higher precedence than |.
Assuming that expr has been changed to return a Parser[Int], we can evaluate "(" ~ expr ~ ")" simply by returning expr, which yields an Int. Here is one way of doing that (you’ll see a simpler one in the next section):
def factor: Parser[Int] = ... | "(" ~ expr ~ ")" ^^ {
case _ ~ e ~ _ => e
}
In this case, the argument of the ^^ operator is the partial function { case _ ~ e ~ _ => e }.
Note
The ~ combinator returns an instance of the ~ case class instead of a pair to make matching easier. If ~ returned a pair, then you would have to write case ((_, e), _) instead of case _ ~ e ~ _.
A similar pattern match yields the sum or difference. Note that opt yields an Option: either None or Some(...).
def expr: Parser[Int] = term ~ opt(("+" | "-") ~ expr) ^^ {
case t ~ None => t
case t ~ Some("+" ~ e) => t + e
case t ~ Some("-" ~ e) => t - e
}
Finally, to multiply the factors, note that rep("*" ~ factor) yields a List of items of the form "*" ~ f, where f is an Int. We extract the second component of each ~ pair and compute their product:
def term: Parser[Int] = factor ~ rep("*" ~ factor) ^^ {
case f ~ r => f * r.map(_._2).product
}
In this example, we simply computed the value of the expression. When building a compiler or interpreter, the usual goal is to build a parse tree—a tree structure that describes the parsed result; see Section 20.5, “Generating Parse Trees,” on page 309.
Caution
If you turn off the warning against postfix operators, you can write p? instead of opt(p) and p* instead of rep(p):
def expr: Parser[Any] = term ~ (("+" | "-") ~ expr)?
def term: Parser[Any] = factor ~ ("*" ~ factor)*
It seems a good idea to use these familiar operators, but they conflict with the ^^ operator. You’ll have to add another set of parentheses, such as
def term: Parser[Any] = factor ~ (("*" ~ factor)*) ^^ { ... }
For that reason, I prefer opt and rep.
20.4 Discarding Tokens
As you saw in the preceding section, it can be tedious to deal with tokens when analyzing a match. The tokens are required for parsing, but they can often be discarded after they have been matched. The ~> and <~ operators are used to match and discard a token. For example, the result of "*" ~> factor is just the result of factor, not a value of the form "*" ~ f. With that notation, we can simplify the term function to
def term = factor ~ rep("*" ~> factor) ^^ {
case f ~ r => f * r.product
}
Similarly, we can discard the parentheses around an expression, like this:
def factor = number ^^ { _.toInt } | "(" ~> expr <~ ")"
A transformation is no longer required in the expression "(" ~> expr <~ ")", since the value is now simply e, which already yields an Int.
Note that the “arrow tip” of the ~> or <~ operator points to the part that is retained.
Caution
You need to be careful when using multiple ~, ~>, and <~ in the same expression. <~ has a lower precedence than ~ and ~>. Consider, for example:
"if" ~> "(" ~> expr <~ ")" ~ expr
Unfortunately, this doesn’t just discard ")", but the subexpression ")" ~ expr. The remedy is to use parentheses: "if" ~> "(" ~> (expr <~ ")") ~ expr.
20.5 Generating Parse Trees
The parsers of the preceding examples simply computed numeric results. When you build an interpreter or compiler, you will want to build up a parse tree instead. This is usually done with case classes. For example, the following classes can represent an arithmetic expression:
class Expr
case class Number(value: Int) extends Expr
case class Operator(op: String, left: Expr, right: Expr) extends Expr
The parser’s job is to turn an input such as 3+4*5 into a value
Operator("+", Number(3), Operator("*", Number(4), Number(5)))
In an interpreter, such an expression can be evaluated. In a compiler, it can be used for generating code.
To generate a parse tree, use ^^ with functions that yield tree nodes. For example,
class ExprParser extends RegexParsers {
...
def term: Parser[Expr] = (factor ~ opt("*" ~> term)) ^^ {
case a ~ None => a
case a ~ Some(b) => Operator("*", a, b)
}
def factor: Parser[Expr] = wholeNumber ^^ (n => Number(n.toInt)) |
"(" ~> expr <~ ")"
}
20.6 Avoiding Left Recursion
If a parser function calls itself without first consuming some input, the recursion will never stop. Consider this function that is supposed to consume any sequence of ones:
def ones: Parser[Any] = ones ~ "1" | "1"
Such a function is called left-recursive. To avoid the recursion, you can reformulate the grammar. Here are two alternatives:
def ones: Parser[Any] = "1" ~ ones | "1"
or
def ones: Parser[Any] = rep1("1")
This problem occurs commonly in practice. For example, consider our arithmetic expression parser:
def expr: Parser[Any] = term ~ opt(("+" | "-") ~ expr)
The rule for expr has an unfortunate effect with subtraction. The expressions are grouped in the wrong order. When the input is 3-4-5, the expression is parsed as
-
/
3 -
/
4 5
That is, 3 is accepted as term, and -4-5 as "-" ~ expr. This yields a wrong answer of 4 instead of -6.
Could we turn the grammar around?
def expr: Parser[Any] = expr ~ opt(("+" | "-") ~ term)
Then we would get the correct parse tree. But that doesn’t work—this expr function is left-recursive.
The original version eliminates the left recursion, but at a cost—it is harder to compute the parse result. You need to collect the intermediate results and then combine them in the correct order.
Collecting intermediate results is easier if you can use a repetition, which yields a List of the collected values. For example, an expr is a sequence of term values, joined by + or -:
def expr: Parser[Any] = term ~ rep(("+" | "-") ~ term)
To evaluate the expression, replace each s ~ t in the repetition with t or -t, depending on whether s is "+" or "-". Then compute the sum of the list.
def expr: Parser[Int] = term ~ rep(
("+" | "-") ~ term ^^ {
case "+" ~ t => t
case "-" ~ t => -t
}) ^^ { case t ~ r => t + r.sum }
If rewriting the grammar is too cumbersome, see Section 20.9, “Packrat Parsers,” on page 314 for another remedy.
20.7 More Combinators
The rep method matches zero or more repetitions. Table 20–1 shows several variations of this combinator. The most commonly used among them is repsep. For example, a list of comma-separated numbers can be defined as
def numberList = number ~ rep("," ~> number)
or more concisely as
def numberList = repsep(number, ",")
Table 20–2 shows additional combinators that are occasionally useful. The into combinator can come in handy to store information from an earlier combinator in a variable so that it can be used later. For example, in the grammar rule
def term: Parser[Any] = factor ~ rep("*" ~> factor)
you can store the first factor in a variable, like this:
def term: Parser[Int] = factor into { first =>
rep("*" ~> factor) ^^ { first * _.product }
}
The log combinator can help debug a grammar. Replace a parser p with log(p)(str), and you get a printout whenever p is called. For example,
def factor: Parser[Int] = log(number)("number") ^^ { _.toInt } | ...
yields outputs such as
trying number at scala.util.parsing.input.CharSequenceReader@76f7c5
number --> [1.2] parsed: 3
20.8 Avoiding Backtracking
Whenever an alternative p | q is parsed and p fails, the parser tries q on the same input. This is called backtracking. Backtracking also happens when there is a failure in an opt or rep. Clearly, backtracking can be inefficient. For example, consider an arithmetic expression parser with the rules
def expr: Parser[Any] = term ~ ("+" | "-") ~ expr | term
def term: Parser[Any] = factor ~ "*" ~ term | factor
def factor: Parser[Any] = "(" ~ expr ~ ")" | number
If the expression (3+4)*5 is parsed, then term matches the entire input. Then the match for + or - fails, and the compiler backtracks to the second alternative, parsing term again.
It is often possible to rearrange the grammar rules to avoid backtracking. For example:
def expr: Parser[Any] = term ~ opt(("+" | "-") ~ expr)
def term: Parser[Any] = factor ~ rep("*" ~ factor)
You can then use the ~! operator instead of ~ to express that there is no need to backtrack.
def expr: Parser[Any] = term ~ opt(("+" | "-") ~! expr)
def term: Parser[Any] = factor ~ rep("*" ~! factor)
def factor: Parser[Any] = "(" ~! expr ~! ")" | number
When p ~! q is evaluated and q fails, no other alternatives are tried in an enclosing |, opt, or rep. For example, if factor finds a "(" and then expr doesn’t match, the parser won’t even try matching number.
20.9 Packrat Parsers
A packrat parser uses an efficient parsing algorithm that caches previous parse results. This has two advantages:
• Parse time is guaranteed to be proportional to the length of the input.
• The parser can accept left-recursive grammars.
In order to use packrat parsing in Scala, follow these steps:
1. Mix the PackratParsers trait into your parser.
2. Use val or lazy val, not def, for each parser function. This is important because the parser caches these values, and it relies on them being identical. (A def would return a different value each time it is called.)
3. Have each parser function return PackratParser[T] instead of Parser[T].
4. Use a PackratReader and supply a parseAll method (which is annoyingly missing from the PackratParsers trait).
For example,
class OnesPackratParser extends RegexParsers with PackratParsers {
lazy val ones: PackratParser[Any] = ones ~ "1" | "1"
def parseAll[T](p: Parser[T], input: String) =
phrase(p)(new PackratReader(new CharSequenceReader(input)))
}
20.10 What Exactly Are Parsers?
Technically, a Parser[T] is a function with one argument, of type Reader[Elem], and a return value of type ParseResult[T]. In this section, we will have a closer look at these types.
The type Elem is an abstract type of the Parsers trait. (See Section 19.12, “Abstract Types,” on page 291 for more information about abstract types.) The RegexParsers trait defines Elem as Char, and the StdTokenParsers trait defines Elem as Token. (We will have a look at token-based parsing in Section 20.12, “Token-Based Parsers,” on page 317.)
A Reader[Elem] reads a sequence of Elem values (that is, characters or tokens) from some source and tracks their positions for error reporting.
When a Parser[T] is invoked on a reader, it returns an object of one of three subclasses of ParseResult[T]: Success[T], Failure, or Error.
An Error terminates the parser and anything that called it. It can arise in one of these circumstances:
• A parser p ~! q fails to match q.
• A commit(p) fails.
• The err(msg) combinator is encountered.
A Failure simply arises from a failure to match; it normally triggers alternatives in an enclosing |.
A Success[T] has, most importantly, a result of type T. It also has a Reader[Elem] called next, containing the input beyond the match that is yet to be consumed.
Consider this part of our arithmetic expression parser:
val number = "[0-9]+".r
def expr = number | "(" ~ expr ~ ")"
Our parser extends RegexParsers, which has an implicit conversion from a Regex to a Parser[String]. The regular expression number is converted into such a parser—a function that consumes a Reader[Char].
If the initial characters in the reader match the regular expression, the function returns a Success[String]. The result property of the returned object is the matched input, and the next property is the reader with the match removed.
If the initial characters in the reader don’t match the regular expression, the parser function returns a Failure object.
The | method combines two parsers. That is, if p and q are functions, then p | q is again a function. The combined function consumes a reader, say r. It calls p(r). If that call returns Success or Error, then that’s the return value of p | q. Otherwise, the return value is the result of q(r).
20.11 Regex Parsers
The RegexParsers trait, which we have used in all examples up to this point, provides two implicit conversions for defining parsers:
• literal makes a Parser[String] from a literal string (such as "+").
• regex makes a Parser[String] from a regular expression (such as "[0-9]".r).
By default, regex parsers skip whitespace. If your notion of whitespace is different from the default of """s+""".r (for example, if you want to skip comments), override whiteSpace with your definition. If you don’t want whitespace skipped, use
override val whiteSpace = "".r
The JavaTokenParsers trait extends RegexParsers and specifies five tokens, shown in Table 20–3. None of them correspond exactly to their Java forms, which makes that trait of limited utility.
20.12 Token-Based Parsers
Token-based parsers use a Reader[Token] instead of a Reader[Char]. The Token type is defined in the trait scala.util.parsing.combinator.token.Tokens. The StdTokens subtrait defines four types of tokens that one commonly finds when parsing a programming language:
• Identifier
• Keyword
• NumericLit
• StringLit
The StandardTokenParsers class provides a parser that produces these tokens. Identifiers consist of letters, digits, or _ but don’t start with a digit.
Caution
The rules for letters and digits are subtly different from those in Java or Scala. Digits in any script are supported, but letters in the “supplementary” range (above U+FFFF) are excluded.
Numeric literals are sequences of digits. String literals are enclosed in "..." or '...', with no escapes. Comments, enclosed in /* ... */ or from // to the end of the line, are considered whitespace.
When you extend this parser, add any reserved words and special tokens to the lexical.reserved and lexical.delimiters sets:
class MyLanguageParser extends StandardTokenParser {
lexical.reserved += ("auto", "break", "case", "char", "const", ...)
lexical.delimiters += ("=", "<", "<=", ">", ">=", "==", "!=", ...)
...
}
When a reserved word is encountered, it becomes a Keyword, not an Identifier.
The parser sorts the delimiters according to the “maximum munch” rule. For example, when the input contains <=, you will get that as a single token, not as a sequence of tokens < and =.
The ident function parses an identifier; numericLit and stringLit parse literals.
For example, here is our arithmetic expression grammar, using StandardTokenParsers:
class ExprParser extends StandardTokenParsers {
lexical.delimiters += ("+", "-", "*", "(", ")")
def expr: Parser[Any] = term ~ rep(("+" | "-") ~ term)
def term: Parser[Any] = factor ~ rep("*" ~> factor)
def factor: Parser[Any] = numericLit | "(" ~> expr <~ ")"
def parseAll[T](p: Parser[T], in: String): ParseResult[T] =
phrase(p)(new lexical.Scanner(in))
}
Note that you need to supply a parseAll method, which is annoyingly missing from the StandardTokenParsers class. In that method, you use a lexical.Scanner, which is the Reader[Token] supplied by the StdLexical trait.
Tip
If you need to process a language with different tokens, it is easy to adapt the token parser. Extend StdLexical and override the token method to recognize the token types you need. Consult the source code of StdLexical for guidance—it is quite short. Then extend StdTokenParsers and override lexical:
class MyParser extends StdTokenParsers {
val lexical = new MyLexical
...
}
Tip
The token method in StdLexical is a bit tedious. It’s nicer to define tokens with regular expressions. Add this definition when you extend StdLexical:
def regex(r: Regex): Parser[String] = new Parser[String] {
def apply(in: Input) = r.findPrefixMatchOf(
in.source.subSequence(in.offset, in.source.length)) match {
case Some(matched) =>
Success(in.source.subSequence(in.offset,
in.offset + matched.end).toString, in.drop(matched.end))
case None =>
Failure("string matching regex '$r' expected but
${in.first} found", in)
}
}
Then you can use regular expressions in your token method, like this:
override def token: Parser[Token] = {
regex("[a-z][a-zA-Z0-9]*".r) ^^ { processIdent(_) } |
regex("0|[1-9][0-9]*".r) ^^ { NumericLit(_) } |
...
}
20.13 Error Handling
When a parser can’t accept an input, you want to get an accurate message indicating where the failure occurred.
The parser generates an error message that describes the position at which the parser was unable to continue. If there were several failure points, the one that was visited last is reported.
You may want to keep error reporting in mind when you order alternatives. For example, if you have a rule
def value: Parser[Any] = numericLit | "true" | "false"
and the parser doesn’t match any of them, then it’s not so useful to know that the input failed to match "false". You can add a failure clause with an explicit error message:
def value: Parser[Any] = numericLit | "true" | "false" |
failure("Not a valid value")
The failure combinator only reports an error when it is visited. It does not change the error messages that another combinator reports. For example, a RegexParser has an error message such as
string matching regex `d+' expected but `x' found
Then use the withFailureMessage method, like this:
def value = opt(sign) ~ digits withFailureMessage "Not a valid number"
When the parser fails, the parseAll method returns a Failure result. Its msg property is an error message that you can display to the user. The next property is the Reader that points to the unconsumed input at the point of failure. You will want to display the line number and column, which are available as next.pos.line and next.pos.column.
Finally, next.first is the lexical element at which the failure occurred. If you use the RegexParsers trait, that element is a Char, which is not very useful for error reporting. But with a token parser, next.first is a token, which is worth reporting.
Tip
If you want to report errors that you detect after a successful parse (such as type errors in a programming language), use the positioned combinator to add a position to a parse result. The result type must extend the Positional trait. For example,
def vardecl = "var" ~ positioned(ident ^^ { Ident(_) }) ~ "=" ~ value
2. Add a ^ operator to the arithmetic expression evaluator. As in mathematics, ^ should have a higher precedence than multiplication, and it should be right-associative. That is, 4^2^3 should be 4^(2^3), or 65536.
3. Write a parser that parses a list of integers (such as (1, 23, -79)) into a List[Int].
4. Write a parser that can parse date and time expressions in ISO 8601. Your parser should return a java.time.LocalDateTime object.
5. Write a parser that parses a subset of XML. Handle tags of the form <ident>... </ident> or <ident/>. Tags can be nested. Handle attributes inside tags. Attribute values can be delimited by single or double quotes. You don’t need to deal with character data (that is, text inside tags or CDATA sections). Your parser should return a Scala XML Elem value. The challenge is to reject mismatched tags. Hint: into, accept.
6. Assume that the parser in Section 20.5, “Generating Parse Trees,” on page 309 is completed with
class ExprParser extends RegexParsers {
def expr: Parser[Expr] = (term ~ opt(("+" | "-") ~ expr)) ^^ {
case a ~ None => a
case a ~ Some(op ~ b) => Operator(op, a, b)
}
...
}
Unfortunately, this parser computes an incorrect expression tree—operators with the same precedence are evaluated right-to-left. Modify the parser so that the expression tree is correct. For example, 3-4-5 should yield an Operator("-", Operator("-", 3, 4), 5).
7. Suppose in Section 20.6, “Avoiding Left Recursion,” on page 310, we first parse an expr into a list of ~ with operations and values:
def expr: Parser[Int] = term ~ rep(("+" | "-") ~ term) ^^ {...}
To evaluate the result, we need to compute ((t0 ± t1) ± t2) ± . . . Implement this computation as a fold (see Chapter 13).
8. Add variables and assignment to the calculator program. Variables are created when they are first used. Uninitialized variables are zero. To print a value, assign it to the special variable out.
9. Extend the preceding exercise into a parser for a programming language that has variable assignments, Boolean expressions, and if/else and while statements.
10. Add function definitions to the programming language of the preceding exercise.