search

ptal / oak

A typed parser generator embedded in Rust code for Parsing Expression Grammars
Apache License 2.0
142 stars 14 forks source link

Improve type inference of the choice combinator #84

Closed ptal closed 3 years ago

ptal commented 8 years ago

We detect type cycle that are not necessarily recursive types. For example:

r = "a" r / "b" .

is invalid because both branch have a different type: (^) and char. This is because we are too conservative on unit cycle. Actually we should not generate a rec type if the cycle does not actually build value with polymorphic types (such as Option<T> or (T1,T2)), if we build a single atom along the path of cycle, this is valid. A more interesting example is for example:

  factor
    = number > number_expr
    / identifier > variable_expr
    / lparen factor rparen

The factor (e) is of the type of e, this is a valid example of unit cycle.