Ambiguities in Souffle grammar

[quentin]

Hi,
Have you noticed the ambiguities in Souffle grammar between to the dot-keywords (.type, .decl, ...) and qualified names?

Examples

For instance the type declaration is parsed as T being an alias for type foo.type.t:

.comp F {
  .comp Type {
  .type t <: number
  }
  .init type = Type
}
.init foo = F

.type T = foo.type.t

But this is parsed as T being an alias for type foo followed by another type definition .type .t where . is unexpected before t:

...
// added whitespace before `.t`
.type T = foo.type .t
// Error: syntax error, unexpected ., expecting identifier

The issue is not limited to .type, similar ambiguities can be built for other dot-keywords in competition with clause terminal-dot.

This is correctly parsed as fact init(1):

.decl q(v:number)
.decl init(v:number)
q(v) :- q(f), 1 = f.
init (1).

Whereas this is parsed as unexpected initialization .init before the missing terminal-dot of the q(v) clause:

.decl q(v:number)
.decl init(v:number)
q(v) :- q(f), 1 = f.init (1).
// Error: syntax error, unexpected component instantiation, expecting .

Analysis

The grammar is ambiguous because there is no way to distinguish .keyword from . immediately followed by keyword.

For instance these rules requires to distinguish .type from . immediately followed by type:

(1) type_name ::= IDENT ("." IDENT)* | ...
(2) type_decl ::= ".type" IDENT "=" type_name | ...
(3) program ::= (type_decl | ...)*

====
.type T = foo.type.t  ||  program
.type T = foo.type.t  || type_decl (type_decl | ...)*
.type T = foo.type.t  ||  ".type" IDENT "=" type_name (type_decl | ...)*
T = foo.type.t        || IDENT "=" type_name (type_decl | ...)*
= foo.type.t          || "=" type_name (type_decl | ...)*
foo.type.t            || type_name (type_decl | ...)*
foo.type.t            || IDENT ("." IDENT)* (type_decl | ...)*
.type.t               || ("." IDENT)* (".type" IDENT "=" type_name | ...)*  => ambiguity ("." IDENT) or ".type" ?

The ambuiguity is fixed arbitrarily by the lexer rules that match dot-keywords by looking-ahead for a whitespace after the keyword:

WS [ \t\r\v\f]
...
".type"/{WS}

Hence the actual grammar is whitespace sensitive:

(1) type_name ::= IDENT /(?!".type ") ("." IDENT)
(2) type_decl ::= ".type " IDENT "=" type_name

Where /(?! ".type ") is the negative look-ahead of ".type ".

Discussion

How to solve this issue ?

1. Forbid identifier x if .x is a dot-keyword of the language: no more .type input, .decl type, comp: number.
   • optionally support a syntax for raw-identifiers r#x: .type r#input, .decl r#type, r#comp: number.
   • optionally keywords without leading dot may be allowed in the syntax: type r#input, decl r#type.
2. Switch to a new syntax to replace the dot-keywords and the final dot of clauses.

[langston-barrett]

This might be the cause of langston-barrett/tree-sitter-souffle#8