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

Find non-reachable expression in prioritized choice #26

Open ptal opened 10 years ago

ptal commented 10 years ago

For this simple example, the neq rule will never match because lt will always match first and so the rule comparison will succeed and > will not be matched. We could find a way to statically analyse such situation and report the error to the user.

comparison = le / lt / ge / gt / eq / neq
lt = "<" spacing
le = "<=" spacing
gt = ">" spacing
ge = ">=" spacing
eq = "==" spacing
neq = "<>" spacing
ptal commented 10 years ago

A solution might be to check if sub-rules of a choice are overlapping. We need to define what overlapping means for all PEG operators.

ptal commented 6 years ago

Such an analysis can draw some inspiration in the FIRST/FOLLOW analysis of LL(1) grammar. An optimization could be to detect such LL(1) cases and to optimize the code accordingly (using match instead of nested if, and avoiding backtracking in this case: it would also improve the error reporting since we do not the try the other (not relevant) alternatives).

ptal commented 3 years ago

A first draft has been wrote by Chao Lin & William Sergeant. See unreachable_rule.rs.