Parameterised Productions - Termination
- Dominant language
- Haskell
- Stars
- 322
- Forks
- 86
- PR merge metrics
- No merged PRs in 30d
Description
There is a caveat to using parameterised productions which is not mentioned in the online documentation, which is that it is possible to effectively define infinite grammars, causing non-termination. A simply example is some recursive production in which the argument always "grows". In this case, the Happy pre-processor would have to generate infinitely many nonterminals.
For example:
%tokentype { Char }
%token '1' { '1' }
%error { error }
%%
start : list('1') { $1 }
list(p) : p { 1 }
| p list(parens(p)) { $2 + 1 }
parens(p) : '(' p ')' { $2 }
This describes the language `{"1" |-> 1, "1(1)" |-> 2, "1(1)((1)) |-> 3", ...}`.
When I run the happy tool on this grammar description (version 1.19.5), it fails to terminate.
I am reporting this because I thought it would be helpful to add this caveat to the online documentation.
Note that parser combinators may be able to handle such descriptions. This is the case when parsers terminate when all of the input is consumed. For example, the parser written with Parsec below:
```
import Text.ParserCombinators.Parsec hiding (Parser)
type Parser a = GenParser Char () a
pStart :: Parser Int
pStart = pList (char '1')
pList :: Parser Char -> Parser Int
pList p = try (1 <$ p <* eof)
<|> (1+) <$ p <*> pList (parens p)
where parens :: Parser a -> Parser a
parens x = char '(' *> x <* char ')'
```
Contributor guide
Assessment
This issue has not been assessed yet.