class

TopDown::Parser

Inherits TopDown::CharReader < Reference < Object

TopDown::Parser is the main class to derive for building a parser.

Basis

A minimal parser could be:

class Parser < TopDown::Parser
  root :expression

  syntax :expression do
  end
end

which will parse anything but EOF.

root indicate the starting point of parsing, the rest is to do inside syntax.

Syntax are like functions, in which, any code can be added. Inside it, parse & parse! can be used to define what to parse.

syntax :expression do
  a = parse('a')
  parse(/( )+/)
  foo = parse!("foo")

  {a, foo}
end

"a   foo" # ~> {'a', "foo"}
"a   bar" # ~> Unexpected character 'b', expected 'foo'
"ab"      # ~> Unexpected character 'b', expected expression

NOTE: In this documentation, "foo" # ~> result is used as a shortcut for Parser.new("foo").parse # => result

In the above, if parse!("foo") fail to parse, it raises an error. But parse('a') don't raises, instead it use a break (break Fail.new) to stop the current sequence to be parsed. This failure is caught by the root :expression, that why it next raises an exception.

This difference is important because is on what is based TopDown, using parse let a change to the surrounding context to handle the failure, whereas parse! permit the raise directly, leading to better errors.

For example, using parse! above:

syntax :expression do
  a = parse!('a')
  parse!(/( )+/)
  foo = parse!("foo")

  {a, foo}
end

"ab" # ~> Unexpected character 'b', expected pattern /( )+/

Gives a more precise error.

Repeat, union, maybe

repeat, union, maybe allow interesting things to be parsed. They take both a block, in which parse failure can occur.

syntax :expression do
  repeat do
    parse('a')
    parse!('b')
  end
  maybe { parse('c') }
  parse!('d')

  union do
    parse('e')
    parse('é')
    parse('è')
  end
  "ok"
end

This is equivalent to parse /(ab)*c?d[eéè]/, in a bit more verbose. However, doing so allow to insert code between and retrieve only needed result, storing in array, or to insert some logic.

For example:

syntax :expression do
  array = [] of {Char, Char}
  repeat do
    array << {parse('a'), parse!('b')}
  end
  have_c = maybe { parse('c') }
  parse!('d')

  if have_c
    e = union do
      parse('e')
      parse('é')
      parse('è')
    end
  end
  {array, e}
end

Here, we store each ab in an array and accept the union 'e'|'é'|'è' only if the optional 'c' have been parsed.

"ababd" # ~> {[{'a', 'b'}, {'a', 'b'}], nil}
"cde"   # ~> {[], 'e'}
"dé"    # ~> Unexpected character 'é', expected 'EOF'
"abac"  # # Unexpected character 'c', expected 'b'

NOTE: When using repeat, union, and maybe, we always use parse at first (without exclamation), because they break on failure, which is caught by the repeat/maybe/union. They know so they should continue parsing without a failure.

Infix

infix can be used inside a union. It permits to parse operators with precedence easily.

syntax :expression do
  union do
    parse(/\d+/).to_i
    infix 30 "**" { left() ** parse!(:expression) }
    infix 20 '*' { left() * parse!(:expression) }
    infix 20 '/' { left() / parse!(:expression) }
    infix 10 '+' { left() + parse!(:expression) }
    infix 10 '-' { left() - parse!(:expression) }
  end
end

Infix are treated specially by the union. They are parsed after any other member of the union, the left() result is updated each time. They are parsed in function of their precedence (first argument), higher precedence mean grouped first.

"3*6+6*4" # ~> 42

Precedence:

current_precedence() is initially zero, it changes when entering in infix. This is this value that guide the recursion for parsing operators. Its value can be changed at specific places, so parsing order can be entirely controlled.

For example, assuming we want to parse a ternary if _ ? _ : _ that have a higher precedence that classical operators (e.g. "1+1?2:3+3" gets parsed as (1 + (1?2:3)) + 3.

We can do the following:

syntax(:expression) do
  union do
    parse(/\d+/).to_i
    infix 10, :plus
    infix 90, :ternary_if
  end
end

syntax :plus, '+' do
  left() + parse!(:expression)
end

syntax :ternary_if, '?' do
  cond = left()
  then_arm = parse!(:expression)
  parse!(':')
  else_arm = parse!(:expression)

  cond != 0 ? then_arm : else_arm
end

"1+1?2:3+3" # ~> 6

However the following is not what we except:

"1+1?2+2:3+3" # => Unexpected character '+', expected ':'

This happens because the + inside the then_arm have lower precedence, it wants so let its left with higher precedence finish before parsing itself. So the then_arm finish but we except a : right after, so it fails (got '+', expected ':').

To fix that, we can set the current_precedence() for the then arm to 0:

then_arm = parse!(:expression, with_precedence: 0)

"1+1?2+2:3+3" # ~> 8

Instance methods

each_token

Yields successively parsed tokens.

Basis

Repeat, union, maybe

Infix

Precedence:

Instance methods

Macros

failure:

block:

precedence:

failure:

members:

failure:

infix:

Nested types