Experimentelle HTML Engine

  • C#

Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von ~blaze~.

    Experimentelle HTML Engine

    Heyho,

    Ich hatte gerade ein wenig Zeit übrig und dachte ich setze mich an die Realisierung von einer sehr sehr einfachen HTML Engine. Habe nach Ideen zum Vorgehen im Internet gesucht und bin auf eine Seite gestoßen, die den Lexer Zeichen für Zeichen realisiert. Das ist doch ein wenig zu aufwändig und da HTML (zumindest XHMTL, dass Tags wie <br> dann unter den Tisch fallen ist mir bewusst) schön gleichmäßig geformt ist, dachte ich das schreit nach RegEx und Rekursion. Soweit so gut:


    C#-Quellcode

    1. class Node
    2. {
    3. public string Tag { get; set; }
    4. public List<Node> SubNodes { get; set; }
    5. public List<string> Class { get; set; }
    6. public string ID { get; set; }
    7. public Dictionary<String, String> Properties = new Dictionary<string, string>();
    8. public string Text { get; set; }
    9. public Node(string _Tag, string _Text ) {
    10. SubNodes = new List<Node>();
    11. this.Tag = _Tag;
    12. this.Text = _Text;
    13. }
    14. public void addProperty(string property, string propertyvalue) {
    15. if (property.ToLower().Equals("class"))
    16. {
    17. this.Class.Add(propertyvalue);
    18. }
    19. else if (property.ToLower().Equals("id"))
    20. {
    21. this.ID = propertyvalue;
    22. }
    23. else
    24. {
    25. Properties.Add(property, propertyvalue);
    26. }
    27. }
    28. public void addChildren(List<Node> nd) {
    29. if(nd!=null)
    30. SubNodes.AddRange(nd);
    31. }
    32. public void addChild(Node nd)
    33. {
    34. if (nd != null)
    35. SubNodes.Add(nd);
    36. }
    37. }


    C#-Quellcode

    1. public List<Node> parseHTML(string html) {
    2. Regex rgx = new Regex("<(.*?)(\\s(.*?)=\"(.*?)\")*>(.*?)</\\1>");
    3. html = html.Trim();
    4. List<Node> nodes = new List<Node>();
    5. Match mt = rgx.Match(html);
    6. while (mt.Success) {
    7. Node parent = new Node(mt.Groups[1].Value, "");
    8. //add the attribute values
    9. var props = mt.Groups[3];
    10. for(int i = 0; i< props.Captures.Count; i++)
    11. {
    12. parent.addProperty(props.Captures[i].Value, mt.Groups[4].Captures[i].Value);
    13. }
    14. string subnodecontent = mt.Groups[5].Value;
    15. if (rgx.IsMatch(subnodecontent))
    16. {
    17. //add all childrens
    18. parent.addChildren(parseHTML(subnodecontent));
    19. }
    20. else
    21. {
    22. Node textnode = new Node("", subnodecontent);
    23. parent.addChild(textnode);
    24. }
    25. //add the node
    26. nodes.Add(parent);
    27. //remove current match and move on
    28. html = html.Remove(mt.Index, mt.Length).Trim();
    29. mt = rgx.Match(html);
    30. }
    31. return nodes;
    32. }


    Zur Erklärung: Die Methode matcht einen umschließenden Tag und ruft sich selbst mit dem Inhalt des Tags wieder auf. Anschließend wird der gefundene Tag aus dem Suchstring gelöscht, sodass als nächstes die Geschwister gefunden werden:

    Quellcode

    1. <div><p></p></div><a>test</a>
    2. <div>(...)</div> wird gefunden, Methode wird rekursiv für (...) aufgerufen, <div>(...)</div> wird entfernt
    3. Nächster Match erwischt <a>test</a>
    4. Methode wird rekursiv für test aufgerufen, <a>test</a> entfernt.


    Das funltioniert auch soweit richtig gut :D . Nur leider ignoriert das Ding Mischungen aus Text und ElementNodes was den Parser recht unbrauchbar macht.
    Beispiel:

    Quellcode

    1. <div>test <a>innerer Text</a></div>
    2. wird zu:
    3. +<div>
    4. ---+<a>
    5. ------+"innerer Text"
    6. anstatt
    7. +<div>
    8. ---+"test "
    9. ---+<a>
    10. ------+"innerer Text"


    Hat jemand ne Idee wie man das intelligent beheben kann?

    8-) faxe1008 8-)
    Hi
    ich würde da eher so ansetzen, dass ich als erstes den Text zu einem "token stream" umforme. D.h. ich würde jedes Zeichen durchgehen und seine Art bestimmen (z.B. Zahlen, Bezeichner, usw.), sodass du bspw.
    <!DOCTYPE html><html>
    usw. zu bspw.
    <, !, DOCTYPE, html, >, <, html, >
    zerlegen kannst. Diese Token würde ich in einer Liste speichern (als Struktur), die jeweils Startposition und Endposition des Zeichens enthält und ggf. noch den Hashwert, Äquivalenzvergleiche und zusätzlich noch eine Funktion besitzt, die das Token selbst als String zurückgibt. Häufig ist es hinreichend, zu wissen, dass ein Token mit einem bestimmten anderen übereinstimmt, d.h. es ist nicht nötig, das vergleichsweise teure Substring auszuführen.
    Der Hashwert wird bereits vorher berechnet, da davon ausgegangen wird, dass ein Vergleich durchgeführt wird. Equals vergleicht erst die Hashwerte, wenn diese identisch sind, wird die String-Sequenz verglichen (ist effizienter, da der String-Vergleich in O(n) ist, der Hashwert-Vergleich in O(1)).
    Die Codierung für die Token erhältst du aus der Html-Spezifikation.

    Anschließend würde ich den token stream in einen Syntaxbaum überführen, d.h. eben hierarchisch strukturieren und ungültige Dokumente verwerfen, bzw. sie entsprechend handhaben - sollte ebenfalls in der Spezifikation stehen. Dort werden auch die Attribute, usw. abgelegt.
    Für das Parsen gibt es ein paar Algorithmen, aber in der Hinsicht habe ich mich noch nicht sonderlich gebildet, außerdem vermute ich, dass du eh erst mal die Grundfunktionalität erstellen willst.

    Danach löst du noch den Syntaxbaum auf, sodass eine rein semantische Darstellung besteht, d.h. du bildest die Token auf bestimmte Funktionalität ab (z.B. das b-Tag auf eine Klasse, die das Bold-Layout auf Text anwendet, außerdem verknüpfst du die Attribute mit bestimmten Eigenschaften - ließe sich btw. sehr gut mit .Net-Attributen realisieren, musst dir aber Gedanken machen, wie du das effizient realisieren kannst. Falls du meine Ansätze wissen willst, sag' bescheid).

    Jeder Tag sollte in eine Instanz überführt werden, die entweder im Hintergrund arbeitet oder am Layout, bzw. Rendering beteiligt ist. Eine Unterscheidung macht insofern schon Sinn. Sobald du mal soweit bist, kannst du eigentlich schon alle HTML-Sachen übersetzen und es ist dennoch übersichtlich und gut erweiterbar. Halte dich da aber möglichst an die Vorgaben aus der Spezifikation.

    Viele Grüße
    ~blaze~
    @~blaze~: so etwas hatte ich schon befürchtet :) . Du meintest es gäbe Algorithmen zum Parsen (xhtml) kannst du mir einen empfehlen, finde da auf anhieb nichts.

    8-) faxe1008 8-)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „faxe1008“ ()

    @~blaze~: Habe den Lexer fertiggestellt:

    C#-Quellcode

    1. using System;
    2. using System.Collections.Generic;
    3. using System.Linq;
    4. using System.Text;
    5. using System.Threading.Tasks;
    6. namespace HTMLEngine
    7. {
    8. public enum TokenType {
    9. LESSTHAN,
    10. GREATERTHAN,
    11. SLASH,
    12. TAG,
    13. TEXT,
    14. EQUALS,
    15. QUOTES,
    16. WHITESPACE
    17. }
    18. class Token
    19. {
    20. public TokenType TokenType { get; set; }
    21. private string _Content = "";
    22. public string Content {
    23. get { return _Content; }
    24. set {
    25. _Content = value;
    26. switch (value) {
    27. case "<":
    28. this.TokenType = TokenType.LESSTHAN;
    29. break;
    30. case ">":
    31. this.TokenType = TokenType.GREATERTHAN;
    32. break;
    33. case "/":
    34. this.TokenType = TokenType.SLASH;
    35. break;
    36. case "\"":
    37. this.TokenType = TokenType.QUOTES;
    38. break;
    39. case "=":
    40. this.TokenType = TokenType.EQUALS;
    41. break;
    42. }
    43. }
    44. }
    45. public Token(string content) {
    46. this.Content = content;
    47. }
    48. public Token(string content, TokenType type)
    49. {
    50. this.Content = content;
    51. this.TokenType = type;
    52. }
    53. public Boolean isDefinedTokenType()
    54. {
    55. return TokenType == TokenType.LESSTHAN || TokenType == TokenType.GREATERTHAN || TokenType == TokenType.SLASH || TokenType == TokenType.EQUALS || TokenType == TokenType.QUOTES;
    56. }
    57. }
    58. }



    C#-Quellcode

    1. using System;
    2. using System.Collections.Generic;
    3. using System.Linq;
    4. using System.Text;
    5. using System.Threading.Tasks;
    6. namespace HTMLEngine.Lexer
    7. {
    8. class Lexer
    9. {
    10. private int CurrentPos;
    11. private string Xhtml;
    12. public Lexer()
    13. {
    14. CurrentPos = 0;
    15. Xhtml = "";
    16. }
    17. public List<Token> Tokenize(string xhtml) {
    18. List<Token> resultList = new List<Token>();
    19. Xhtml = xhtml;
    20. string buffer = "";
    21. while (hasNextSign()) {
    22. string nextSign = consumeChar();
    23. if (isDefinedTokenType(nextSign))
    24. {
    25. if (buffer.Length > 0)
    26. {
    27. if (getLastToken(resultList).TokenType == TokenType.LESSTHAN || getLastToken(resultList).TokenType == TokenType.SLASH) {
    28. resultList.Add(new Token(buffer.Trim(), TokenType.TAG));
    29. }
    30. else
    31. {
    32. resultList.Add(new Token(buffer.Trim(), TokenType.TEXT));
    33. }
    34. }
    35. resultList.Add(new Token(nextSign));
    36. buffer = "";
    37. }else
    38. {
    39. buffer += nextSign;
    40. }
    41. }
    42. return resultList;
    43. }
    44. public Boolean hasNextSign()
    45. {
    46. return CurrentPos < Xhtml.Length;
    47. }
    48. public string consumeChar()
    49. {
    50. return Xhtml.Substring(CurrentPos++, 1);
    51. }
    52. public Token getLastToken(List<Token> tokens)
    53. {
    54. return tokens[tokens.Count - 1];
    55. }
    56. static Boolean isDefinedTokenType(string content)
    57. {
    58. return content.Equals("<") || content.Equals(">") || content.Equals("=") || content.Equals("\"") || content.Equals("/") || content.Equals(" ");
    59. }
    60. }
    61. }


    Das funktioniert auch tadellos. Jetzt muss ich das ja in die Baumstruktur überführen. Dabei ist die Hauptaufgabe ja das "Klammerproblem" (feststellen welche öffnende Klammer zu welcher schließenden gehört). Ich weiß wie das zu lösen ist nur frage ich mich wie der nach dir beschriebene Syntaxbaum auszusehen hat? <,>,/ können ja nach dem Schritt verworfen werden.

    8-) faxe1008 8-)
    Ich würde sogar die Art des Tokens vorher bestimmen und das Enum direkt im Konstruktor mit angeben. Du musstest die Art der Zeichen ja sowieso schon mal bestimmen. Es ist auch eine Überlegung wert, < und > zu unterscheiden. Attribute erhöhen die Komplexität btw. nochmal um einiges. ;) Und es gibt ja noch so Sachen, wie CDATA, wenn ich mich nicht irre.

    consumeChar würde ich außerdem als char definieren. Es ist sonst äußerst ineffizient und schwieriger, Vergleiche, usw. darauf auszuführen.

    Für das Klammerproblem würde ich einen rekursiven Ansatz wählen
    <, !, DOCTYPE, html, >, <, html, >, </, html ,>
    würde zu
    - DOCTYPE (html)
    - html
    --

    führen. Das ist nicht allzu aussagekräftig. Die Tags würde ich ebenfalls entfernen, ebenso das ! bei z.B. DOCTYPE, aber dann eben noch die Tagtypen in Form eines Enums übernehmen, das weiteren Aufschluss gibt und Kommentare würde ich ganz überspringen.

    Ich würde für den Syntaxbaum eine Klasse SyntaxElement einführen, die eine Eigenschaft mit dem entsprechenden Enum-Wert enthält, das für den Typ repräsentativ ist (Node, Text, DOCTYPE, CDATA, usw. nur ggf. mit schöneren Bezeichnungen, alles was keinen Spezialfall darstellt, ist halt Node).
    Für jeden Knotentyp gibt es dann einen Erben, der nur diesen Spezialfall darstellt (d.h. im Falle von Node, DOCTYPE, CDATA gäbe es eben die Klassen NodeSyntaxElement, TextSyntaxElement, DoctypeSyntaxElement, CDataSyntaxElement).

    Neben den Eigenschaften Name ("html", "b" usw.), Attributes (z.B. "html" bei DOCTYPE würde ich als Attribut modellieren, dessen Wert auf Nothing gesetzt ist) könnte man eine Methode Build(BuildContext) einbauen, die alle unterstützten Tags übersetzt. BuildContext liefert dabei das unterstützte "Vokabular", also bspw. die das "html"-Tag in seiner finalen Form konstruierende Klasse.

    Ein anderer Ansatz wäre: XHTML wird auch als XHTML-Schema (ähnlich XML-Schemata) dargestellt, soweit ich weiß. Das müsstest du dann wahrscheinlich erst mal einlesen und Code daraus generieren, damit das halbwegs effizient läuft, aber du hättest wohl sämtliche zulässigen Dinge drin. Würde ich aber ehrlich gesagt eher nicht so gern machen.

    Viele Grüße
    ~blaze~
    Bin mir unsicher, ob ich die DOCTYPE Deklaration überhaupt parse, faktisch weiß ich ja dass es html sein muss.

    Habe das jetzt so gelöst:

    C#-Quellcode

    1. public class Parser
    2. {
    3. List<Token> Tokens = new List<Token>();
    4. public Parser (List<Token> tokens)
    5. {
    6. this.Tokens = tokens;
    7. }
    8. public List<SyntaxElement> buildSyntaxTree(){
    9. return this.buildSyntaxTree (this.Tokens);
    10. }
    11. public List<SyntaxElement> buildSyntaxTree(List<Token> tokens){
    12. List<SyntaxElement> SyntaxTree = new List<SyntaxElement>();
    13. for (int i = 0; i < tokens.Count; i++) {
    14. NodeSyntaxElement parent = new NodeSyntaxElement ("");
    15. if (isOpeningTag (tokens, i)) {
    16. int closingGT = getNextGreaterThan (tokens, i);
    17. int closingTag = getClosingTag (tokens, i);
    18. parent = new NodeSyntaxElement (tokens [i].Content);
    19. SyntaxTree.Add (parent);
    20. parent.addChildren (buildSyntaxTree (tokens.GetRange (closingGT, closingTag - closingGT)));
    21. i = closingTag + 2;
    22. }
    23. if (tokens [i].TokenType == TokenType.TEXT) {
    24. SyntaxTree.Add (new TextSyntaxElement(tokens[i].Content));
    25. }
    26. }
    27. return SyntaxTree;
    28. }
    29. public int getNextGreaterThan(List<Token> tokens, int i){
    30. int closingGT = i+1;
    31. for (int g = i; g < tokens.Count; g++) {
    32. if (tokens [g].TokenType == TokenType.GREATERTHAN) {
    33. closingGT = g+1;
    34. break;
    35. }
    36. }
    37. return closingGT;
    38. }
    39. public int getClosingTag(List<Token> tokens, int i){
    40. Stack<int> Openings = new Stack<int> ();
    41. Openings.Push (i);
    42. for (int g = i+1; g < tokens.Count; g++) {
    43. if (isOpeningTag (tokens, g))
    44. Openings.Push (g);
    45. if (isClosingTag (tokens, g, tokens [Openings.Peek()].Content)) {
    46. if (Openings.Count == 1) {
    47. return g-2;
    48. } else {
    49. Openings.Pop();
    50. }
    51. }
    52. }
    53. return -1;
    54. }
    55. public Boolean isClosingTag(List<Token> tokens, int index, string content){
    56. if (tokens [index].TokenType == TokenType.TAG && content.Equals(tokens[index].Content)) {
    57. if (tokens [index - 1].TokenType == TokenType.SLASH ) {
    58. return true;
    59. }
    60. }
    61. return false;
    62. }
    63. public Boolean isOpeningTag(List<Token> tokens, int index){
    64. if (tokens [index].TokenType == TokenType.TAG) {
    65. if (tokens [index - 1].TokenType == TokenType.LESSTHAN) {
    66. return true;
    67. }
    68. }
    69. return false;
    70. }
    71. }


    Das funktioniert soweit richtig gut :D. Jetzt müssen "nur" noch die Attribute geparst werden und beim Lexer stimmt auch etwas nicht. Wenn z.B. < zwischen zwei " steht dann macht er aus dem < einen eigenständingen Tag.

    8-) faxe1008 8-)
    Ich hätte es etwas anders gemacht: IEnumerator auf das aktuell untersuchte Token und dann einfach jedes nacheinander abarbeiten. Wenn unerwartet, dann überspringen und einen Syntaxfehler ausgeben, sonst entsprechend dem Tokentyp eine parsende Methode aufrufen (z.B. bei Token-Typ LESS würde ReadTag aufgerufen, das alles bis zum Abschluss des Tags verarbeitet. Du kannst ja dann für jeden Fall eigene Methoden definieren, die sich untereinander aufrufen. Das würde ich für Attribute sogar noch stärker empfehlen, da die Methoden sonst sehr groß werden.

    Viele Grüße
    ~blaze~
    @~blaze~
    Habe den Lexer auf RegEx umgestellt, funktioniert bisher alles problemlos. Die Umstellung hat es mir erlaubt auch gleich zu erkennen ob es ein öffnender oder schließender Tag ist, deswegen habe ich als neue TokenTypes CLOSINGTAG und OPENINGTAG eingeführt.

    Habe einer zweite Version des Parser mit IEnumerator erstellt:

    C#-Quellcode

    1. class Parser2
    2. {
    3. public List<SyntaxElement> buildSyntaxTree(List<Token> tokens) {
    4. List<SyntaxElement> syntaxTree = new List<SyntaxElement>();
    5. IEnumerator<Token> tokenNumerator = tokens.GetEnumerator();
    6. while (tokenNumerator.MoveNext()) {
    7. if (tokenNumerator.Current.TokenType == TokenType.OPENINGTAG) {
    8. syntaxTree.Add(readTag(tokenNumerator));
    9. }
    10. }
    11. return syntaxTree;
    12. }
    13. public SyntaxElement readTag(IEnumerator<Token> numerator)
    14. {
    15. NodeSyntaxElement node = new NodeSyntaxElement(numerator.Current.Content);
    16. Stack<Token> oTags = new Stack<Token>();
    17. oTags.Push(numerator.Current);
    18. while (numerator.MoveNext() && oTags.Count>0)
    19. {
    20. if (numerator.Current.TokenType == TokenType.OPENINGTAG) {
    21. node.SubElements.Add(readTag(numerator));
    22. }
    23. if (numerator.Current.TokenType == TokenType.TEXT)
    24. {
    25. node.SubElements.Add(new TextSyntaxElement(numerator.Current.Content));
    26. }
    27. if (numerator.Current.TokenType == TokenType.CLOSINGTAG)
    28. {
    29. if (numerator.Current.Content != oTags.Peek().Content)
    30. throw new ArgumentException("HTML is not well formated.");
    31. oTags.Pop();
    32. }
    33. }
    34. return node;
    35. }
    36. }


    Das funktioniert richtig gut :thumbsup: . Danke für den Tipp.

    8-) faxe1008 8-)
    Hast du mal einen Laufzeit-Vergleich durchgeführt? Regex sollte eher nicht so effizient sein. Wie es mit dem kompilierten Pattern aussieht, weiß ich allerdings nicht, würde aber vermuten, dass es dennoch eher nicht effizient ist. Der Lexer ist an sich aber eh nicht so schwer. Eventuell optimierst du gen Ende noch alles.

    Freut mich auf jeden Fall, dass es so gut läuft ;)

    Viele Grüße
    ~blaze~
    Habe noch ein wenig am Lexer optimiert und gemessen. Mit kompiliertem Regex ist der Geschwindigkeitsunterschied zu vernachlässigen. Es soll ja auch keine HighEnd-Engine werden die tatsächlich kommerziel genutzt wird.

    Der nächste Schritt ist es ja einen CSS Parser zu bauen der zumindest Dinge wie Width, Padding Margin und Font-Größe erkennt.
    Die Frage danach ist nur wie ich den DOM Baum dann zeichne. Man muss ja quasi den äußeren Tag vor den inneren Zeichnen, wobei bei so Sachen wie div die Höhe von den beinhalteten Tags abhängt. Außerdem stellt sich mir die Frage, wie ich generell den style dem Node zuordnen soll, damit Kaskaden möglich sind.

    Jemand ne schöne Idee dazu?

    8-) faxe1008 8-)
    Erklärst du nochmal genauer, wo die Probleme sind? Im Prinzip sollte es ja auch nur das eine Hierarchie sein, wobei du z.B. eine Klasse hast, die die virtuellen Member Measure und Draw anbietet. Measure gibt dann halt die Abmessungen an (relativ zu einem beinhaltenden Rechteck, das du als Parameter bereitstellst) und Draw zeichnet dann in dieses bestimmte Feld den Inhalt. Beachte, dass bspw. bei Zeichenketten verschiedene Fonts nacheinander möglich sind, die alle auf der gleichen Basislinie liegen. FontFamily gibt dir nähere Informationen zu diesem Verhalten.

    Viele Grüße
    ~blaze~