ptal / oak

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

Check that prefixes/suffixes (such as '*', '&', ...) doesn't form chain (such as '**', '&!&', '?*'). #17

Closed ptal closed 3 years ago

ptal commented 9 years ago

Most chains will be forbidden by the well-formed analysis (see #66). I think that other chains are not incorrect (&&e or e+* for example) but are just bad style or weird. IMHO, a syntactic analysis is enough if we restrict only one prefix and suffix for a single expression. For prefixes, !e is like not e in logic and &e like e, indeed & is just a syntactic sugar for !!e. Thus we can see & as a hint to the parser generator to avoid consuming input, it is an identity function with regards to the result of e. Since this hint is already provided by !e, chaining & and ! is useless. We have these equivalences:

!!e ~ &e
&&e ~ &e
!&e ~ !e
&!e ~ !e

Let's write down the cases for suffixes:

e** ~ infinite loop
e++ ~ e+
e+* ~ e+
e*+ ~ infinite loop

This time we clearly see that both leads to an infinite loop, and this is already checked by the well-formed grammar analysis. It remains the two others cases that still need an analysis.

ptal commented 3 years ago

Done by Chao Lin & William Sergeant.