haskell / haskell/happy

Parameterised Productions - Termination

Open
#118 2 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.