Syntax for patterns

[JOT85]

We should decide on the syntax for defining patterns.
It should be designed considering:

• Readability
• Ease to parse the rules
• Ease to parse based of the rules
• Efficiency of parsing from the rules

Current syntax

[ optional ]
*<pat>: repeat 0 or more times
+<pat>: repeat 1 or more times
{i,j}<pat>: repeat i to j times (inclusive)
{i,}<pat>: repeat i or more times
{,j}<pat>: repeat 0 to j times (inclusive)
(a | b | c): a or b or c
<|0-9,a-z,A-Z,-,+|>: character in the range 0-9 (inclusive), a-z (inclusive), A-Z (inclusive), character is - or character is +.
.: matches anything
a~<pat>: parse <pat>, but within the rules scope, a is a string literal pattern which matches the syntax that <pat> consumed.
a@rule: parse the given rule and make a and evaluatable which, when used with eval, gives the value from applying the rule to the syntax.
pattern: parse the named pattern pattern
?=<pat>: <pat> must match what follows, but no data is consumed (look ahead)
?!=<pat>``<pat> must not match what follows - no data is consumed (negative look ahead)
#err: if the pattern fails to match after this, the error message referenced by err should be used.

Coming soon...

• intersperse

Possible, but probably not required

!<pat>: not <pat> (note that <pat> must have a pre-determined length)

Note that the amount white-space between syntax elements does not matter - although it cannot contain a newline.

[sharnoff]

A note on greedy vs. lazy matching, and negative look-ahead expressions:

All matching must be greedy, because we otherwise can't separate a repeated pattern into (init, last), e.g:

pattern Decimal: <|0-9|>

pattern Num: Num Decimal

The same goes for rules:

rule DecValue: d~<|0-9|> {
    ...
}

rule Value: x@Value y@DecValue {
    ...
}

[JOT85]

@sharnoff have you had any ideas about intersperse syntax?

[sharnoff]

@sharnoff have you had any ideas about intersperse syntax?

The ABNF that the HTTP RFCs use has an interesting take:

#rule
A construct "#" is defined, similar to "*", for defining lists of elements. The full form is "#element" indicating at least and at most elements, each separated by one or more commas (",") and OPTIONAL linear white space (LWS). This makes the usual form of lists very easy; a rule such as

   ( *LWS element *( *LWS "," *LWS element ))

can be shown as

   1#element

Wherever this construct is used, null elements are allowed, but do not contribute to the count of elements present. That is, "(element), , (element) " is permitted, but counts as only two elements. Therefore, where at least one element is required, at least one non-null element MUST be present. Default values are 0 and infinity so that "#element" allows any number, including zero; "1#element" requires at least one; and "1#2element" allows one or two.

I think that this is just okay because it allows null elements and only allows the delimiter to be a comma. A better syntax should allow you to choose something other than a comma and it should be easier to read. Perhaps something like:

pattern Foo: +( +Alpha &( ", " ) )

would indicate that we'd get words separated by a comma and a space. It would also be cool to be able to write something like:

pattern VarName: +( Alpha | "_" &( | Digit ) )

instead of

pattern VarName: ( Alpha | "_" ) *( Alpha | Digit | "_" )

So &(...) would literally paste the contents of ... into the group once it has repeated at least once.

[JOT85]

. is not the most useful pattern in the world. Especially in a greedy world where *. would just consume the entire file.
We do however need a way to easily define comments.
As a regex, you could match a # starting comment as #.*\n - bit for the reason above, we can't do that with out patterns.
What we need, is the ability to match all but a specific character. This could simply done using !<pat> - which would match something which does not match the given pattern.
This would allow the comment style above to be matched by # *!"\n" "\n".

Are you happy with that syntax @sharnoff?

[JOT85]

Oh but wait... How long is a not pattern?
How long is !"a" - intuitively it should be 1.
!"ab" - 2.
!*"a"?

[sharnoff]

Oh but wait... How long is a not pattern?
How long is !"a" - intuitively it should be 1.
!"ab" - 2.
!*"a"?

We could only allow not patterns for elements with a pre-defined length... However repetition could also work just fine. !*"a" would simply match bytes that aren't 'a' for as long as it can.

[JOT85]

I think that only allowing ! on fixed length patterns is the best solution.
!*"a" would have to be a special rule - changing the behaviour of *. I think it's better to not have special rules.
*!"a" would work as intended if we define !<pat> to consume the amount that would consume if it matched. The only patterns without a fixed length are ones with arbitrary repetition, and the compliment of them would not involve repetition so could be defined using another syntax.

[sharnoff]

Recap of recent discussions

---

Look-ahead, backtracking, and !

We'd like our language to be able to parse context-sensitive grammars, so we have two options; either we allow backtracking or we allow look-ahead assertions. The hypothetical syntax for explicitly allowing was proving to be overly complicated*, so we went with look-ahead assertions. There are two kinds provided: positive and negative look-ahead assertions.

The syntax for each could be represented in BNF as:

positive-lookahead = "?=" pattern-element
negative-lookahead = "?!=" pattern-element

Two simple patterns to match based on whether the next character is a new-line could be:

pattern PeekWS:    ?= <| ,\t|>
pattern PeekNotWS: ?!=<| ,\t|>

or

pattern PeekNotWS: ?!=PEEK_WS

* Due to efficiency concerns, we wouldn't want backtracking to be on by default.

---

Revised repetition syntax

We also discussed the syntax for allowing arbitrary numbers of repetitions. To start, the ABNF definition for repetitions would now look something like:

pat-rep = "*" pat-rep-tail
        | "+" pat-rep-tail
        | "{" [+DIGIT] "," [+DIGIT] "}" pat-rep-tail

where

pat-rep-tail = "(" pattern-element *( *WS pattern-element ) ")
             | pattern-element
WS = <any whitespace character that does not imply a new line>

Each of the options can be thought of simply as below:

• *Foo => zero or more repetitions of Foo
• +Foo => one or more repetitions of Foo
• {a,b}*Foo => any number of repetitions of Foo in the range a to b, inclusive

In the third (new) case, if either of the numbers are not given, they will default to zero and infinity, respectively - in a similar fashion to regex's <foo>{a,b}. Therefore, [ Foo ] can be replicated with {0,1}*Foo (or {,1}*Foo) and +Foo with {1,}*Foo. We are choosing to provide the additional syntax because it means that patterns can be written more elegantly.

---

Breaking patterns (and rules!) across lines

We briefly mentioned the idea of allowing both patterns and rule match definitions to span multiple lines. The syntax for this takes inspiration from LaTeX, and simply uses \\ at the end of the line to indicate that we continue after. The ABNF could look something like

pat-line-break = "\\" <newline>

and you could use it to write

pattern Foo: "This pattern has many options." \\
    | "So many that we may want it to..." \\
    | "Span multiple lines!"

Unresolved question

If we allow splitting across lines like this, we might also want to allow comments at the end of those lines. In a similar vein, we may actually want to allow comments at the end of every line. We could then define a line-ending ABNF rule to be:

line-end = *WS [ "#" *<anything not newline> ] <newline>

which allows us to re-define the line-break pattern element as:

pat-line-break = "\\" line-end

---

Making patterns cause errors - Discuss more

More discussion needs to be had to work out the details of this, but a sketch of the idea is as follows:

There are times in which a pattern or rule may have advanced far enough in its matching that we know that it must complete or there is invalid syntax. For example - if we have a language that simply evaluates addition expressions, defined by rules like:

rule AddExpr: n@Num "+" e@{ AddExpr | Num } { ... }

and we are parsing "1 + 2 + + 4", we can immediately see that it is invalid syntax and exactly why. Getting the compiler to give a clear error may be not too bad in this case, but it could prove to be difficult in others - How could we know what the actual cause error was, not just the literal failure to match?

To remedy this, we'd add the following syntax to the ABNF definition:

pat-error = "#" var-name

with the precise definition of var-name to be decided later.

We could now rewrite AddExpr to be:

rule AddExpr: n@Num "+" #err e@{ AddExpr | Num } { ... }

where we have defined err elsewhere to say something like "failed to parse the addition expression!"
The semantics of defining these errors must also be determined later.

An important note is that these errors don't interfere with how the text is parsed - they simply determine the messages to give when text cannot be parsed with the given rules.

[JOT85]

Look-ahead, backtracking, and !

positive-lookahead = "?=" pattern-element
negative-lookahead = "?!=" pattern-element

I'm happy with the syntax :). Tiny bit weird though. I blame regex.

Quick question about this code:

pattern PeekWS:    ?= <| ,\t|>

There's a space after ?= above, are we allowing that? I have nothing against it, but it's not required.

Look-aheads can be used to do the equivalent of ! - but not as readable or concise. We won't implement ! unless we feel that the convenience it brings is worth it. ! is sort of like [] but I don't think it would be used as much.

Revised repetition syntax

Perfect :)

Breaking patterns (and rules!) across lines

pattern Foo: "This pattern has many options." \\
    | "So many that we may want it to..." \\
    | "Span multiple lines!"

We also talked about using it in cerror for error messages. If we didn't do this (so it was only allowed in patterns), then \\<newline> would only have to be part of pattern syntax. If we were to allow it in cerror, we would either have to:

• have the \\ syntax as a part of the directive syntax, just acting as white-space;
• make cerror special so that it has \\ syntax (which I'm not keen on because I don't want special things);
• or, just like a colon marks the start of a pattern, we have something to mark the start of a string, which has \ syntax.

The last option could also give us other features, such as the amount of whitespace making a difference. Currently,

directive a b c`

is the same as:

directive     a    b                 c

which is good. But if the number of spaces in a string made a difference, you'd be able to write a compiler error with 4 space indentation for example. Also, it would probably make sense for \<newline> to actually be a newline in a string - otherwise we have no way of doing this.

Unresolved question

I was thinking about this and what the printed line/column numbers should be.
The obvious solution is to print the position where the pattern failed to match, however if you have options for the syntax which can be used, this may not make sense. I think that the position printed in the error message should be the position the parser was at when the #err was used. This gives you pretty much full control over labeling where the error occurred. For example, you could put the error reference before or inside a repeat - which would print the position of the start of the repeats or the start of the individual repeat respectively.
I also can't find a syntax for defining the errors that I like!
They should be scoped, so we could have a directive before the rule which defines them all.
Or, they could be on a rule by rule basis, but there's not a nice place to put them without distracting from the intent of the code.

[sharnoff]

There's a space after ?= above, are we allowing that?

I think that generally we should be pretty forgiving about whitespace - the only reason I actually put the space there was so that it could line up and "look nice", which hopefully is something that people will be able to replicate if they have similar desires.

We also talked about using it in cerror for error messages.

Right! I forgot to mention that. Because we haven't figured out what sort of syntax we want for cerror (or whether to call it cerror), I'll offer my two cents on the whole matter.

Personally, the best option to me seems to be allowing "\" to part of the normal whitespace, meaning that it could (theoretically) be included anywhere whitespace is allowed - e.g. builtins, rule/pattern definitions, yield statements, etc. I had previously thought of compiler errors as taking a series of string literals ("foobar") and string variables (n, where we matched n ~ Name, for example) - these would be separated by spaces. This solves the newline problem, because string literals can contain escaped characters. Here would be an example:

rule FooBar: n ~ Name "++" {
    cerror "Couldn't find variable " n \\
           "\n\tFor a guide on scoping, see *this link*"
}

Unresolved question

Currently, I think the best way might be something like this:

rule AddExpr: n@Num "+" #err e@{ AddExpr | Num } {
    #err1 "Expected a number after '+'"
    ...
}

Where we require the error definitions to take up the first n lines of the rule definition, followed by the rest of the body of the definition. I'm not entirely sure about this way of doing it, but it might be the way we want to go about it. The alternative that I see (which may be the way we head) would be take a page from Rust and add attributes before rule definitions, which normalizes a bunch of different syntax elements as well. In Rust, you could write something like:

#[inline(always)]
fn foo_bar(x: i32) -> String { ... }

We could mirror this with some other type of attribute syntax (because "#" is already used for comments)

-- err: "Expected a number after '+'"
rule AddExpr: n@Num "+" #err e@{ AddExpr | Num } { ... }

Because this syntax is pretty general, we could also add

-- upper
-- manual-scoping
rule AddExpr: n@Num "+" #err e@{ AddExpr | Num } { ... }

I'm also not sold on "--".... Perhaps "*" could work better, if we were to go this path?

* manual-scoping
rule AddExpr: n@Num "+" #err e@{ AddExpr | Num } { ... }

The only thing that I don't like about defining errors outside of the rule body is that it doesn't seem to match with the "spirit" of what the error definition is - errors (to me) seem like they should be something that isn't necessary for reading, almost a parenthetical for the rule, but putting them in the same scope as the "rule" keyword itself seems like it amplifies their presence - perhaps more than we'd need.