[JS] Nesting Correctie Algoritme

[Verwijderd]

Hallo,

Ik ben momenteel bezig met het maken van een parser die HTML documenten
omzet naar XHTML (in JavaScript). De basis, het analyseren van de HTML input string (elementen filteren, bepalen welk type tag het is, of het een tag is, wat de attributen zijn...) is al gedaan.

Op onderstaande link kan je een demo bekijken want de class die de input analyseert:

www.nextavenue.com/javascript/xhtml/demo/

Het analyseren van de HTML input string is één ding, het corrigeren van de
nesting moet nu nog gebeuren. Ik heb een algoritme bedacht, waarvan ik denk
dat hij efficiënt is.
Als er mensen zijn die samen met mij dit probleem willen oplossen dan zou ik
dat leuk vinden. Als mensen geïnteresseerd zijn, zal ik mijn algoritme posten
en mogen jullie het voorzien van commentaar.

[coubertin119]

Je kan ook al eens beginnen met het moz-compatible maken van je script, voor je verder gaat .

Maar het nut ontgaat me zo'n beetje, de meeste pagina's in HTML4.01 zijn geschreven met methodes die in XHTML zo'n beetje deprecated zijn, zoals <b>/<i>/<s> en lay-outs met tables. En die kan je met zoiets niet omzetten, dus waarom je dit bouwt vat ik niet.

[Verwijderd]

Schaamte, de class zelf is mozilla compatibel, maar ik was te lui om document.getElementById() gebruiken, ik zal het even uploaden en dan kan je het nut zien. Je kan namelijk alle tags die deprecated best omzetten. Ik zal even
uploaden.

[js] Hij is nu aangepast, mozilla werkt ook (de performance tuning is zelfs voor mozilla gedaan )

[ Voor 18% gewijzigd door Verwijderd op 18-01-2004 11:11 ]

[Verwijderd]

Een document dat in correcte HTML 4.01 is geschreven is echt enorm simpel om te zetten naar XHTML 1.0. Het probleem is dat vooral de wat oudere HTML documenten een bij elkaar geraapt zooitje zijn van mensen die eigenlijk niet weten hoe je een document moet opmaken.

offtopic:
Overigens moet coubertin119 eens goed de specificaties kijken, omdat in HTML 4.01 ook het meeste al deprecated is.
Grappig is ook dat er W3C specificaties zijn die vertellen dat je moet vermijden die in een bepaalde context verkeerd geïnterpreteerd kunnen worden. Het is niet erg handig om het woord 'methodes' te gebruiken in een programmeer forum.

Terug ontopic.
Waarin wil jij een i element gaan omzetten en waarom? Ik zie het vaak dat mensen denken dat <i> is vervangen door <em> en dat <b> is vervangen door <strong>. Dat is onzin.
Als je iets schuingedrukt wilt zetten, dan moet je je afvragen waarom je dat wilt. Vaak komt dat omdat het een afkorting of term is, of omdat er nadruk op het woord moet liggen. Moet je dan <abbr>, <acronym>, <em> of <strong> voor gebruiken?
Want je moet als HTML auteur de betekenis vastleggen, niet hoe het exact gepresenteerd moet worden. Dat moet je aan de stylesheets van de gebruiker, het document, en de browser overlaten. Over de middelste heb jij enige controle.

De vraag is: begrijp jij de XHTML standaard? Want volgens mij moet je toch wel kunnen inzien dat dit onmogelijk is te realiseren zonder iets of iemand die de semantiek van het document begrijpt. Als je dat wilt automatiseren heb je een gigantische kennis van taal en grammatica nodig. Ik zie dat voorlopig nog niet gebeuren.

[Verwijderd]

HTML converteren naar XHTML is mogelijk. Mijn oude parser haalde een gemiddelde van 97% (volgens de validator van w3c). Mijn parser controleert
op attributen die verplicht zijn, corrigeert attributen, maakt tags lower case
corrigeert nesting enz.

Die parser van mij kon zelfs de ranzige html van Google corrigeren en terugbrengen van ongeveer 700 fouten naar die van 20.

100% zal niet haalbaar zijn. Maar 99% moet wel te halen zijn. Het parsen van een HTML string is nu gelukt, maar nu wil ik een snel algoritme om de nesting te corrigeren. Die nestig vind ik zelf het belangrijkste. Als de nesting correct is kan
je het document doorlopen als een XML bestand.

Als er mensen zijn die mee willen denken over het nesting probleem, graag...

Ik ben en niet in geïnteresseert om <b> om te zetten naar <strong> zoals je al aangaf is dat onzin. Mijn parser moet:

<B ONCLICK=alert('foo'); class = "test">foo</b><hR noshade>

omzetten naar:

<b onclick="alert('foo');" class="test">foo</b><hr noshade="noshade" />

Snap je nu ongeveer wat mijn parser doet?

[ Voor 19% gewijzigd door Verwijderd op 18-01-2004 12:45 ]

[Verwijderd]

<b> is een deprecated element omdat het alleen over de presentatie gaat en omdat het niets zegt over de inhoud van het element. Om welke reden moet iets vetgedrukt worden? Die reden moet je proberen te beschrijven met HTML tags. Of dat nou in HTML 4.01 of XHTML 1.0 is.

Het noshade attribuut van het <hr> element is eveneens deprecated, omdat dat alleen over de presentatie gaat. Daar hebben we stylesheets voor.

Ik heb dus het vermoeden dus eigenlijk dat jij niet weet wat een (ook semantisch) correct HTML document is. Als jij denkt dat de output die je genereert een geldig XHTML 1.0 document is, dan moet je dat eens door de W3C validator halen. Maar wees gewaarschuwd, de validator kan alleen aangeven of het document syntactisch correct is. Over semantiek kan het je niet veel vertellen.
Om daar meer inzicht in te krijgen raad ik je aan om eens de HTML 4.01, en XHTML 1.0 specificaties en de WCAG 1.0 recommendation door te lezen.

Over het juist nesten van de tags:
Lees alle tags, comments en alles als losse tokens in een array. Dus je krijgt een array met tokens. Een token is een HTML tag, een comment, een CDATA section of doctype declaration, etc.
Laten we deze array eens 'queue' noemen.
Dan moet je elk item in de queue afgaan en je afvragen of iets een open tag, een emtpy tag, een close tag, een doctype declaration of wat dan ook is. Bij een open tag, zet je de tagName aan het eind van een array die we even 'stack' noemen.
Bij een empty tag laat je de stack met rust, en bij een close tag kijk je of de tagName van de tag overeenkomt met de laatste tagName op de stack. Zo ja, dan haal je dat item van de stack en voeg je de close tag toe aan het document, zo nee, dan moet je proberen de tree te herstellen door bijvoorbeeld tussendoor eerst wel de juiste tags toe te voegen. Dit is niet eenvoudig.

Een andere methode is om de queue uit te lezen en met DOM methoden een nieuw document in elkaar zetten aan de hand van de items uit de queue. Ook dit zal niet meevallen als je tags hebt die eventueel leeg mogen zijn, bijvoorbeeld.

Maar ik ben ook ooit eens begonnen met zoiets te maken, maar ik heb besloten dat dit sowieso nog niet geautomatiseerd kan worden, om wat ik eerst noemde.

[curry684]

HTML/Javascript hoort bij Webdesign & Graphics

[crisp]

Zoals Cheatah al aangeeft haal je nesting errors er eigenlijk alleen maar uit door stackbased te werk te gaan; de rest is kinderlijk eenvoudig. Ik heb ooit wel eens een rudimentaire tidier gemaakt met geneste reguliere expressies die voor mij in ieder geval de GoT-html naar leesbare code kon omzetten: http://www.allcrispy.com/exp/tidycode.html

[Verwijderd]

Jou "stack based nesting corrector" heb ik ook. Je moet alleen backtracing gebruiken in het volgende voorbeeld:

<ol>
<li>foo
<li>foo
<ol>
<li>foo
</ol
</ol>

Er zitten wat haken en ogen aan, vooral wanneer bepaalde tags niet genest mogen worden. Maar dat stackbased leek mij ook al de beste oplossing. Je moet
volgens mij ook een tweede stack hebben waarin je de data kopieert en later weer terug zet. Probeer maar eens met deze code:

<b><i>foo</b>foo<u></i></u>

Zolang de validator van W3C aangeeft dat het document (redelijk) correct is en je het document als XML bestand kan doorlopen ben ik tevreden. Reductie van 700 naar 20 fouten, vind ik nog redelijk netjes en acceptabel.

[Verwijderd]

crisp schreef op 18 januari 2004 @ 13:22:
Zoals Cheatah al aangeeft haal je nesting errors er eigenlijk alleen maar uit door stackbased te werk te gaan; de rest is kinderlijk eenvoudig. Ik heb ooit wel eens een rudimentaire tidier gemaakt met geneste reguliere expressies die voor mij in ieder geval de GoT-html naar leesbare code kon omzetten: http://www.allcrispy.com/exp/tidycode.html

Kinderlijk eenvoudig? Daar ben ik het niet mee eens. Niet elk element mag binnen een ander element voorkomen. Dar maakt het algoritme al een stuk ingewikkelder.
Sommige tags hoeften in HTML 4.01 en eerder totaal niet afgesloten te worden. Toch hield de invloed van die tags ergens op. Impliciet werden die elementen dus wél afgesloten. Maar waar moet dat ophouden? Heel eenvoudig is het dus niet. Ik koos er toentertijd zelf voor om eerst de XHTML 1.0 Strict DTD te parsen. Daaruit kun je veel informatie halen, maar helaas niet alles. Maar ik denk dat dit al wat tever gaat.

[ Voor 28% gewijzigd door Verwijderd op 18-01-2004 13:30 ]

[Verwijderd]

Zolang de validator van W3C aangeeft dat het document (redelijk) correct is en je het document als XML bestand kan doorlopen ben ik tevreden. Reductie van 700 naar 20 fouten, vind ik nog redelijk netjes en acceptabel.

Dan ben ik wel benieuwd wat je er verder mee gaat doen, want of iets acceptabel is, is daar natuurlijk van afhankelijk.

[Verwijderd]

Ik heb gewoon een define bestand met tags die geldig zijn, die niet genest mogen worden enz.

Crisp:

<TABLE BORDER=1 WIDTH=200 BGCOLOR=#FF0000>
<TR ONMOUSEOVER="return(4<5);">
<TD><FONT FACE="Verdana,Arial" SIZE=3 COLOR=#0000FF>bla<at<BR>blaat</FONT></TD>
</TR>
</TABLE>

Voer die code maar eens uit. Ik heb bewust voor een teken-voor-teken parser gekozen omdat je anders problemen kan krijgen. In bovenstaand voorbeeld door het onmouseover attribuut van de tr tag. Je kan gewoon < gebruiken. Het is zelfs mogelijk dat iemand:

<b>book <==> boek</b>

gebruikt, hoe ranzig ook.

[Verwijderd]

Cheatah,

100% nauwkeurigheid zal je nooit halen. Zal wil gewoon niet. denk aan mensen die FORM tags direct na een TABLE tag gebruiken...
Misschien moet ik de parser niet HTML2XHTML noemen, maar HTML2XML file, met de leuke bijkomstigheid dat hij 97% van alle XHTML errors eruit filtert.

[Clay]

100% lijkt me eigenlijk best mogelijk maar hoe dichter je bij die 100% komt, hoe groter de kans dat je parser brutere aanpassingen gaat maken in je code en je dus vaker ongewenste effecten gaat krijgen. Grijze gebieden houd je altijd wel, zeker in je voorbeeld met:

code:

<FONT FACE="Verdana,Arial" SIZE=3 COLOR=#0000FF>bla<at<BR>blaat</FONT>

dat <at<BR> deel is gewoon niet eenduiding te parsen omdat het helemaal fout is. in XHTML zou het misschien veranderd moeten worden in &lt;at<br />, maar ik zou b.v. zelf een XHTML parser als laag bovenop een XML parser leggen, en dan begint die tag gewoon bij <at.. Die 2e < daarbinnen is dan gewoon illegaal, die zou je OF kunnen weghalen en de tag veranderen in <atbr /> of <at br=""/> of je zou gewoon de hele tag kunnen lozen.
Dat laatste zou dan mijn voorkeur hebben aangezien je een < in html toch al als &lt; moet schrijven, en "echte" XML parser geeft je ook een vette foutmelding als je dat soort dingen gaat doen; er is een verschil tussen een incompetente parser, en gewoon foute markup.

Daarnaast blijft het ook een kwestie van wat je wel, en wat je niet roekeloos gaat wegknikkeren; b.v. of je inline styles wil omzetten naar classes of niet. Ik heb een tijd geleden een richtext edit ding gemaakt waar je vanuit msword kan copypasten, en daar komt na een dikke regex parse ook xhtml uit. Die gooit dan ook ontzettend veel gewoon zonder pardon weg.

[ Voor 5% gewijzigd door Clay op 18-01-2004 14:31 ]

[Verwijderd]

Dat voorbeeld was een reactie op de parser van Crisp. Voer die code maar eens
uit in mijn parser. Wordt gewoon correct behandeld:

http://www.nextavenue.com/javascript/xhtml/demo/

Stel je hebt deze HTML code:

<B>In alle gevallen is 4<5<BR></B>

Mijn parser heeft een bestand met define variabelen. Een van de variabelen is een Array met alle W3C geldige HTML tags. Mijn parser is een teken-voor-teken parser en maakt onderscheid tussen bepaalde modi; de parser kan in OPEN_TAG, CLOSE_TAG en TEXT mode zijn.
Wanneer de parser in TEXT mode is en een < tekenkomt, dan zou dat een tag kunnen zijn. Er moet dus gecontroleert worden of hetgene na de < tot aan de volgende spatie een geldige HTML tag is. Zo niet, dan moet de < vervangen worden door <

Mijn parser parsed bovenstaande regel in:

<b>In alle gevallen is 4&#60;5<br /></b>

100% nauwkeurigheid is niet mogelijk. Wanneer bijvoorbeeld de HTML invoer het volgende bevat:

<table>
<form>
<tr>
</td>foo</td>
</tr>
</form>
</table>

Dit is XHTML ongeldig. Maar je kan niet zomaar de FORM tag buiten de tabel gooien aangezien je niet weet wat het effect kan zijn, in zulke gevallen kan je dus alleen zorgen dat de nesting correct is.

[ Voor 31% gewijzigd door Verwijderd op 18-01-2004 17:48 ]

[crisp]

de

HTML:

<table><form><tr>...

constructie wordt meestal gebruikt om om de default margins van een form heen te werken; op die manier werd het voorheen op GoT ook gebruikt. Je zou de form-tag er wel buiten kunnen zetten met een style="margin:0px" - dan heb je in 90% van de gevallen toch het juiste effect.

[Verwijderd]

Dan ga je denk ik in dit geval toch probleempjes krijgen:

code:

<table>
  <form>
    <tr>
      <td>foo</td>
    </tr>
  </form>
  <form>
    <tr>
      <td>foo</td>
    </td>
  </form>
</table>

[ Voor 32% gewijzigd door Verwijderd op 18-01-2004 17:50 ]

[crisp]

Verwijderd schreef op 18 januari 2004 @ 17:50:
Dan ga je denk ik in dit geval toch probleempjes krijgen:

code:

<table>
  <form>
    <tr>
      <td>foo</td>
    </tr>
  </form>
  <form>
    <tr>
      <td>foo</td>
    </td>
  </form>
</table>

Tsja, 100% perfect krijg je dat soort dingen nooit, maar dit is ook wel een erg ranzig voorbeeld

[Verwijderd]

Je moet altijd uitgaan van de meeste rampdebielen die er maar zijn.
Alleen een feature implementeren als hij in alle, maar dan ook alle
gevallen goed kan werken.
Ik ga voor de 99%. Ik ben geen XHTML fan, ik ben een XML fan. Ik ben
al lang blij als het document te doorlopen is met een XML parser.
Deze week ga ik het nesting probleem oplossen. Voor vanavond,
lekker performance tunen
Saai, maar noodzakelijk

[Verwijderd]

Crisp,

Bedankt! Ik neem denk ik jou idee over om zoveel mogelijk attributen om te
zetten naar CSS; FACE -> font-family, SIZE -> font-size etc...