Rational Numbers

Arithmetic expressions are sequences of integer numbers interleaved with operators +-/*, possibly in parentheses. Evaluating an arithmetic expression results in a rational number. Expressions in parentheses are evaluated first, the operators * and / take precedence over + and -.

Parsing is reading and processing a sequence of characters, e.g. an arithmetic expression.


provides constructors to combine parsers and transform (sub-)parsings arbitrarily with julia syntax. This example demonstrates reading of arithmetical terms for rational numbers.

Reflecting operator precedence, term are subterms, interleaved by */, and subterms are Either integer numbers

@syntax subterm = Either{Rational{Int}}([NumericParser(Int)]; convert=true)

or a subterm can also be an additive term in parentheses:

@syntax for parentheses in subterm
    mult = evaluate |> join(subterm, CharIn("*/"), infix=:prefix )
    @syntax term = evaluate |> join(mult,    CharIn("+-"), infix=:prefix )

This CombinedParser definition in 5,5 lines registers a @term_string macro for parsing and evaluating rational arithmetics:

julia> term"4*10+2"

No need to roll our own integer parser, we can use NumericParser composing TextParse.Numeric(Int), automatically converted to Rational{Int}. If convert=false an error would be raised on construction, the default.


CombinedParsers provides constructors and operators:

  • Base.join(x,infix; infix=:prefix): shorthand for x(*)Repeat( infix * x ),
  • a*b: shorthand to Sequence(a,b),
  • f |> parser: shorthand for map(f,parser), and
  • evaluate::Function is detailed at the end of the page.

You can investigate the matching process with logging. The defined CombinedParser term can be used as a function with a log keyword option.

julia> term("(1+2)/5", log=true)
   match subterm@2-3: (1+2)/5
   match subterm@4-5: (1+2)/5
   match term@2-5: (1+2)/5
   match parentheses@1-6: (1+2)/5
   match subterm@1-6: (1+2)/5
   match subterm@7-8: 1+2)/5
   match term@1-8: (1+2)/5

Logging technically rewrites a parser with annotation side-effects (see deepmap_parser).

You can flexibly fine-tune logging by name, type or any labeling function.

julia> term("1/((1+2)*4+3*(5*2))",log = [:parentheses])
   match parentheses@4-9: 1/((1+2)*4+3*(
   match parentheses@14-19: *4+3*(5*2))
   match parentheses@3-20: 1/((1+2)*4+3*(5*2))
julia> term("4*10+2", log = NumericParser)
   match <Int64>@1-2: 4*10+2
   match <Int64>@3-5: 4*10+2
   match <Int64>@6-7: 4*10+2

Is every rational answer ultimately the inverse of a universal question in life?

Parser printing

The parser representation can be printed as a tree. Each tree node starts with a brief oriented at PCRE regular expression syntax (blue in REPL). The node then lists parser constructors, delimited by |>. This is especially useful for understanding PCRE regular expressions and BNF grammars: the tree parser representation is really clear about how you would construct the parser with CombinedParsers.

julia> term
๐Ÿ—„ Sequence |> map(evaluate) |> with_name(:term)
โ”œโ”€ ๐Ÿ—„ Sequence |> map(evaluate)
โ”‚  โ”œโ”€ |๐Ÿ—„ Either |> with_name(:subterm)
โ”‚  โ”‚  โ”œโ”€ ๐Ÿ—„ Sequence |> map(#54) |> with_name(:parentheses)
โ”‚  โ”‚  โ”‚  โ”œโ”€ \( 
โ”‚  โ”‚  โ”‚  โ”œโ”€ ๐Ÿ—„ Sequence |> map(evaluate) |> with_name(:term) # branches hidden
โ”‚  โ”‚  โ”‚  โ””โ”€ \) 
โ”‚  โ”‚  โ””โ”€  <Int64> |> map(Rational{Int64})
โ”‚  โ””โ”€ ๐Ÿ—„* Sequence |> Repeat
โ”‚     โ”œโ”€ [\*/] ValueIn
โ”‚     โ””โ”€ |๐Ÿ—„ Either |> with_name(:subterm) # branches hidden
โ””โ”€ ๐Ÿ—„* Sequence |> Repeat
   โ”œโ”€ [\+\-] ValueIn
   โ””โ”€ ๐Ÿ—„ Sequence |> map(evaluate) # branches hidden


Parsing times for Int, operators, brackets are

@benchmark match(term,"(1+2)/5") 

in unfair benchmark-comparison with the more expressive Julia syntax parser

julia> @benchmark Meta.parse("(1+2)/5")

Parsing and transforming (here eval)

julia> @benchmark term("(1+2)/5") 

compared to Julia

julia> @benchmark eval(Meta.parse("(1+2)/5"))

Transformation by evaluate

Subterms can use algebraic operators +-*/ that will be evaluated with

function evaluate( (start, operation_values) )
    aggregated_value::Rational{Int} = start
    for (op,val) in operation_values
        aggregated_value = eval( Expr(:call, Symbol(op), 
			              aggregated_value, val
    return aggregated_value
julia> evaluate( (0, [ ('+',1), ('+',1) ]) )

julia> evaluate( (1, [ ('*',2), ('*',3) ]) )