Move separator elements upwards in xml hierarchy

Question

I have an xml document with separators deep down in the hierarchy.

<A>
  <B>
    <C id='1'/>
    <separator/>
    <C id='2'/>
  </B>
  <B>
    <C id='3'/>
    <separator/>
  </B>
  <B>
    <C id='4'/>
  </B>
</A>

I want to move the separators upwards, keeping elements in order. So the desired output is

<A>
  <B>
    <C id='1'/>
  </B>
</A>
<separator/>
<A>
  <B>
    <C id='2'/>
  </B>
  <B>
    <C id='3'/>
  </B>
</A>
<separator/>
<A>
  <B>
    <C id='4'/>
  </B>
</A>

How can it be done using xslt 1.0 only? Can it be done without for-each, using template match only?

UPDATE: I actually got 4 brilliant answers of different levels of generality, thank you, guys.

Answer 1

This transformation:

<xsl:stylesheet version="1.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:strip-space elements="*"/>

    <xsl:key name="kFollowing" match="C"
         use="generate-id(preceding::separator[1])"/>

 <xsl:template match="/">
  <xsl:apply-templates select="*/*/separator"/>
 </xsl:template>

 <xsl:template match="separator" name="commonSep">
  <separator/>
  <xsl:call-template name="genAncestors">
   <xsl:with-param name="pAncs" select="ancestor::*"/>
   <xsl:with-param name="pLeaves"
        select="key('kFollowing', generate-id())"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template match="separator[not(preceding::separator)]">
  <xsl:call-template name="genAncestors">
   <xsl:with-param name="pAncs" select="ancestor::*"/>
   <xsl:with-param name="pLeaves"
        select="key('kFollowing', '')"/>
  </xsl:call-template>
  <xsl:call-template name="commonSep"/>
 </xsl:template>

 <xsl:template name="genAncestors">
   <xsl:param name="pAncs" select="ancestor::*"/>
   <xsl:param name="pLeaves" select="."/>

   <xsl:choose>
    <xsl:when test="not($pAncs[2])">
     <xsl:apply-templates select="$pLeaves" mode="gen"/>
    </xsl:when>
    <xsl:otherwise>
     <xsl:for-each select="$pAncs[1]">
      <xsl:copy>
        <xsl:copy-of select="@*"/>
        <xsl:call-template name="genAncestors">
               <xsl:with-param name="pAncs" select="$pAncs[position()>1]"/>
               <xsl:with-param name="pLeaves" select="$pLeaves"/>
        </xsl:call-template>
      </xsl:copy>
     </xsl:for-each>
    </xsl:otherwise>
   </xsl:choose>
 </xsl:template>

 <xsl:template match="C" mode="gen">
  <xsl:variable name="vCur" select="."/>
  <xsl:for-each select="..">
   <xsl:copy>
    <xsl:copy-of select="@*|$vCur"/>
   </xsl:copy>
  </xsl:for-each>
 </xsl:template>
</xsl:stylesheet>

when applied on the provided XML document:

<A>
  <B>
    <C id='1'/>
    <separator/>
    <C id='2'/>
  </B>
  <B>
    <C id='3'/>
    <separator/>
  </B>
  <B>
    <C id='4'/>
  </B>
</A>

produces the wanted, correct result:

<A>
   <B>
      <C id="1"/>
   </B>
</A>
<separator/>
<A>
   <B>
      <C id="2"/>
   </B>
   <B>
      <C id="3"/>
   </B>
</A>
<separator/>
<A>
   <B>
      <C id="4"/>
   </B>
</A>