<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 22 okt 2009, at 15:56, Robert Atkey wrote:</div><blockquote type="cite"><div><blockquote type="cite"><blockquote type="cite"><font class="Apple-style-span" color="#000000">....</font></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Previously parsed input /can/ determine what the parser will accept in<br></blockquote><blockquote type="cite">the future (as pointed out by Peter Ljunglöf in his licentiate thesis).<br></blockquote><blockquote type="cite">Consider the following grammar for the context-sensitive language<br></blockquote><blockquote type="cite">{aⁿbⁿcⁿ| n ∈ ℕ}:<br></blockquote><br>Yes, sorry, I was sloppy in what I said there. Do you know of a<br>characterisation of what languages having a possibly infinite amount of<br>nonterminals gives you. Is it all context-sensitive languages or a<br>subset?<br></div></blockquote><div><br></div><div>The answer is: all context-sensitive languages. This is a very old insight which has come back in various forms in computer science. The earliest conception in CS terms is the concept of an affix-grammar, in which the infinite number of nonterminals is generated by parameterising non-terminals by trees. They were invented by Kees koster and Lambert Meertens (who applied them to generate music: <a href="http://en.wikipedia.org/wiki/index.html?curid=5314967)">http://en.wikipedia.org/wiki/index.html?curid=5314967)</a> in the beginning of the sixties of the last century. There is a long follow up on this idea, of which the two most well-known versions are the so-called two-level grammars which were used in the Algol68 report and the attribute grammar formalism first described by Knuth. The full Algol68 language is defined in terms of a two-level grammar. Key publications/starting points if you want to learn more about these are:</div><div><br></div><div>&nbsp;- the Algol68 report:&nbsp;<a href="http://burks.brighton.ac.uk/burks/language/other/a68rr/rrtoc.htm">http://burks.brighton.ac.uk/burks/language/other/a68rr/rrtoc.htm</a></div><div>&nbsp;- the wikipedia paper on affix grammars:&nbsp;<a href="http://en.wikipedia.org/wiki/Affix_grammar">http://en.wikipedia.org/wiki/Affix_grammar</a></div><div>&nbsp;- a nice book about the basics od two-level grammars is the Cleaveland &amp; Uzgalis book, "Grammars for programming languages", which may be hard to get,&nbsp;</div><div>&nbsp;&nbsp; &nbsp; but there is hope:&nbsp;<a href="http://www.amazon.com/Grammars-Programming-Languages-languages/dp/0444001875">http://www.amazon.com/Grammars-Programming-Languages-languages/dp/0444001875</a></div><div>&nbsp;-&nbsp;<a href="http://www.agfl.cs.ru.nl/papers/agpl.ps">http://www.agfl.cs.ru.nl/papers/agpl.ps</a></div><div>&nbsp;-&nbsp;<a href="http://comjnl.oxfordjournals.org/cgi/content/abstract/32/1/36">http://comjnl.oxfordjournals.org/cgi/content/abstract/32/1/36</a></div><div><br></div><div>&nbsp;Doaitse Swierstra</div><div><br></div><div><br></div><div><br></div><blockquote type="cite"><div><br><blockquote type="cite"><blockquote type="cite">And a general definition for parsing single-digit numbers. This works<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">for any set of non-terminals, so it is a reusable component that works<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">for any grammar:<br></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Things become more complicated if the reusable component is defined<br></blockquote><blockquote type="cite">using non-terminals which take rules (defined using an arbitrary<br></blockquote><blockquote type="cite">non-terminal type) as arguments. Exercise: Define a reusable variant of<br></blockquote><blockquote type="cite">the Kleene star, without using grammars of infinite depth.<br></blockquote><br>I see that you have an answer in the paper you linked to above. Another<br>possible answer is to consider open sets of rules in a grammar:<br><br><blockquote type="cite">data OpenRuleSet inp exp =<br></blockquote><blockquote type="cite"> &nbsp;&nbsp;forall hidden. OpenRuleSet (forall a. (exp :+: hidden) a -&gt; <br></blockquote><blockquote type="cite"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule (exp :+: hidden :+: inp) a)<br></blockquote><br><blockquote type="cite">data (f :+: g) a = Left2 (f a) | Right2 (g a)<br></blockquote><br>So OpenRuleSet inp exp, exports definitions of the nonterminals in<br>'exp', imports definitions of nonterminals in 'inp' (and has a<br>collection of hidden nonterminals).<br><br>It is then possible to combine them with a function of type:<br><br><blockquote type="cite">combineG :: (inp1 :=&gt; exp1 :+: inp) -&gt;<br></blockquote><blockquote type="cite"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(inp2 :=&gt; exp2 :+: inp) -&gt;<br></blockquote><blockquote type="cite"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;OpenRuleSet inp1 exp1 -&gt;<br></blockquote><blockquote type="cite"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;OpenRuleSet inp2 exp2 -&gt;<br></blockquote><blockquote type="cite"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;OpenRuleSet inp (exp1 :+: exp2)<br></blockquote><br>One can then give a reusable Kleene star by stating it as an open rule<br>set:<br><br><blockquote type="cite">star :: forall a nt. Rule nt a -&gt; OpenRuleSet nt (Equal [a])<br></blockquote><br>where Equal is the usual equality GADT.<br><br>Obviously, this would be a bit clunky to use in practice, but maybe more<br>specialised versions combineG could be given.<br><br>Bob<br><br><br>-- <br>The University of Edinburgh is a charitable body, registered in<br>Scotland, with registration number SC005336.<br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>http://www.haskell.org/mailman/listinfo/haskell-cafe<br></div></blockquote></div><br></body></html>