Talk:Brace expansion: Difference between revisions
now I understand :-)
m (→Duplicate supression: clarify) |
Walterpachl (talk | contribs) (now I understand :-)) |
||
| (22 intermediate revisions by 5 users not shown) | |||
Line 70:
::::: Regarding "''first identify the nesting, [...] and postpone expansion until all brace expansions have been identified''", you're free to do that if you feel that's the best way to solve the task in your language. In fact the Perl 6 solution does it that way: It uses a grammar to find where all the nested brace group parts are, and then passes the resulting AST tree to a recursive function which does the expansion. It's not a "requirement" though: The Perl and Python solutions both do identification and expansion in one go ''(albeit in rather different ways)''. The only requirement is that the function does the right thing; how it does it is up to you (based on what you think works best in your language).
::::: --[[User:Smls|Smls]] ([[User talk:Smls|talk]]) 22:01, 31 January 2014 (UTC)
:::::: It's scary because it's ambiguously identified. Once again: there are multiple ways of satisfying those test cases. One way requires one recursive pass to identify the relevant braces and commas and then an independent recursive pass to process them. This is certainly doable but many parsing systems are not built that way. Another approach involves suppressing duplicates. Meanwhile, given the wart-for-wart nature of the specification, it seems wrong to leave such a fundamental aspect unspecified. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 22:28, 31 January 2014 (UTC)
::::::: I'm afraid I don't follow. Whether parsing and expansion happens in two separate stages (like #Perl_6 does) or are combined into a single one (like #Perl and #Python do), is an implementation detail. Unless I'm mistaken, all three of those solutions are conceptually '''identical''' implementations of the spec. I don't see any ambiguity, nor any "suppression of duplicates" happening anywhere.
::::::: I think it would help if you could provide a test-case that demonstrates the ambiguity that you see. I.e. and example input for which the "''multiple ways of satisfying [the official] test cases [and spec]''" will disagree with each other. --[[User:Smls|Smls]] ([[User talk:Smls|talk]]) 22:46, 31 January 2014 (UTC)
:::::::: {a,a,b} --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 22:48, 31 January 2014 (UTC)
::::::::: #Perl, #Perl_6, #Python all expand that to the three alternatives <code>a</code> <code>a</code> <code>b</code> (like the spec requires). --[[User:Smls|Smls]] ([[User talk:Smls|talk]]) 22:57, 31 January 2014 (UTC)
:::::::::: My point was that the spec does not explicitly require this. I think that the spec should not neglect this issue. Or let me know if you think I should try to come up with further variations on this theme? --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 23:02, 31 January 2014 (UTC)
::::::::::: Well the second bullet point of the spec includes an example which showcases duplicate alternatives. But I additionally added the phrase "''(which need not be unique)''" now to that paragraph, to make it more explicit. --[[User:Smls|Smls]] ([[User talk:Smls|talk]]) 23:12, 31 January 2014 (UTC)
::::::::::: I tried the perl implementation against this spec. If I use the pattern ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr I see no result line which contains both an 'f' and a 'k'. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 01:10, 1 February 2014 (UTC)
:::::::::::: It would be incorrect if it did so, since f and k come from different alternatives, separated by the comma before the i. Alternatives separated by comma are expanded internally and exclusively from each other—one never takes a cross product over a comma, only over braces. --[[User:TimToady|TimToady]] ([[User talk:TimToady|talk]]) 02:01, 1 February 2014 (UTC)
:::::::::::: The tree of nested alternation groups for that pattern is:
<pre style="margin-left:20em">
⎧c ⎫
⎪ ⎧f ⎫ ⎪
ab⎪d\,e⎩g\h⎭ ⎪qr
⎪ ⎧k ⎫ ⎪
⎪i\,j⎩l\,m⎭n⎪
⎩o\,p ⎭
</pre>
:::::::::::: Thus after recursive flattening ''(which effectively means collecting all the possibilities that you can get by going from left to right through that diagram)'', you get:
<tt style="margin-left:20em; color:#f00; display:block; background:#F9F9F9">
ab<span style="color:#191">c</span>qr<br>
ab<span style="color:#191">d\,e<span style="color:#00f">f</span></span>qr<br>
ab<span style="color:#191">d\,e<span style="color:#00f">g\h</span></span>qr<br>
ab<span style="color:#191">i\,j<span style="color:#00f">k</span>n</span>qr<br>
ab<span style="color:#191">i\,j<span style="color:#00f">l\,m</span>n</span>qr<br>
ab<span style="color:#191">o\,p</span>qr<br>
</tt>
:::::::::::: Which is exactly what the Perl solution prints. --[[User:Smls|Smls]] ([[User talk:Smls|talk]]) 02:07, 1 February 2014 (UTC)
::::::::::: Another datapoint: if you ignore the missing backslashes, bash output is identical to perl's and python's: abcqr abd,efqr abd,eghqr abi,jknqr abi,jl,mnqr abo,pqr. --[[User:TimToady|TimToady]] ([[User talk:TimToady|talk]]) 02:13, 1 February 2014 (UTC)
:::::::::::: Point taken. Thanks for the clarification. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 03:12, 1 February 2014 (UTC)
== Pls clarify edge case example ==
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}
shouln't
{}} some }{ cases, {here} \\\\\}
be a solution? ..[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 19:27, 22 November 2015 (UTC)
: With all those backslashes and the braces without commas, all you're going to see from this algorithm is backslash pairs turning into single backslashes. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 15:40, 23 November 2015 (UTC)
:: Isn't this '{,{\\{ edge, edge} \,}' a choice between nothing and '{\\{ edge, edge} \,'--[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 22:38, 23 November 2015 (UTC)
:::My current program for this case shows:
<pre>
store 3 1 {}} some }{ cases, {here} \\\\\}
store 3 2 {}} some }\\{ edge \,{ cases, {here} \\\\\}
store 3 3 {}} some } edge \,{ cases, {here} \\\\\}
</pre>
:::is thie wrong? Why?? --[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 21:32, 24 November 2015 (UTC)
:::: That comma between ''some'' and ''edge'' is preceded by a brace which still hasn't found its dance partner when the music stops at the end. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 22:10, 24 November 2015 (UTC)
<pre>
:::::{}} some }{,{\\{ edge, edge} \,}{ cases, {here}...
:::::{}} some }{,{\** edge, edge} **}{ cases, {here}... I did this
:::::{}} some }{,{**{ edge, edge} **}{ cases, {here}... and should have done that
::::: | and that's the lonely brace</pre>
:::::Thanks --[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 12:46, 25 November 2015 (UTC)
::::{
Sorry, I am still uncertain.
The results show:
<pre>
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}
</pre>
Why is the rightmost pair of braces not expanded into its 2 elements?
<pre>
111111
2222222222222
i.e. ' cases'
' {here} \\\\\'
</pre>
My result would be
<pre>
{}} some }{,{\\ edge \,} cases
{}} some }{,{\\ edge \,} {here} \\\\\
{}} some }{,{\\ edge \,} cases
{}} some }{,{\\ edge \,} {here} \\\\\
</pre>
..[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 14:52, 25 July 2016 (UTC)
: The right-most brace is escaped by a backslash. (<code>\\\\\}</code> = <code>\\ \\ \}</code>) --[[User:Smls|Smls]] ([[User talk:Smls|talk]]) 18:01, 25 July 2016 (UTC)
:: Thanks. removed my wrong understanding --[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 06:49, 26 July 2016 (UTC)
| |||