Wie wir aus dem\u00a0Beitrag zu KE5<\/a>\u00a0bereits wissen, sind regul\u00e4re Sprachen (Typ-3, rechte Seite einer Regel besteht nur aus einem Terminal, dem ein Nonterminal folgt oder einem leeren Wort)\u00a0eine echte Teilmenge der kontextfreien Sprachen (Typ-2, linke Seite der Regel besteht nur aus einem Nonterminal). Die Typ-3-Sprachen sind nur noch ein St\u00fcck weiter eingeschr\u00e4nkt . Damit sind regul\u00e4re Sprachen auch kontextfrei, denn alle Nonterminale k\u00f6nnen unabh\u00e4ngig von ihrer Umgebung ersetzt werden (im Gegensatz zu Typ-1-Grammatiken, die auch kontextsensitive Regeln erlauben, dort kann die linke Seite der Regel auch aus einem Terminal und einem Nonterminal bestehen. Der Kontext ist also die Verbindung von Terminal und Nonterminal im Wort).<\/p>\n Wenn man nach Ableitungsb\u00e4umen und kontextfreien Grammatiken sucht, findet man diesen Beitrag<\/a> in der Wikipedia und der Fall ist eig. klar. Leider hat das Skript auch noch 4 Seiten zum Thema der Notation f\u00fcr die kontextfreie Grammatik (die polnische Notation und die vereinfachte Notation). Anschlie\u00dfend geht es um die abstrakte Syntax, das Erzeugungssystem, die abstrakte Semantik und dann drei Arten von Ableitungsb\u00e4umen. Nun stellt sich mir die Frage, ob ich einfach ein paar Beispiele f\u00fcr den Ableitungsbaum aus dem Artikel bringen oder das Skript sezieren soll. Just in diesem Moment entscheide ich mich f\u00fcr Ersteres in Kombination mit dem Beispiel aus dem Skript.<\/p>\n Zun\u00e4chst haben wir drei Arten von Ableitungsb\u00e4umen:<\/p>\n Bitte macht euch noch einmal klar, dass die Front das abgeleitete Wort (oder Zeichen) ist und die Wurzel das Startsymbol (was nicht unbedingt die Startregel sein muss). Die folgende Abbildung zeigt zwei B\u00e4ume (mit gr\u00fcner Front), die auch im Skript Verwendung finden mittels der Regelmenge:<\/p>\n \\(S\\rightarrow a\\mid b\\mid\\emptyset\\mid (S\\cup S)\\mid (SS)\\mid S^{*}\\)<\/p>\n Beispiel<\/strong>: Ableitung von \\(\\emptyset\\) (mittels Baumart Nr. 1)<\/p>\n Sequenz: nicht notwendig, da nur Baumart Nr. 1<\/p>\n Beispiel<\/strong>: Ableitung von \\((\\emptyset^{*}\\cup a)\\) (mittels Baumart Nr. 3)<\/p>\n Sequenz: \\(S\\Rightarrow(S\\cup S)\\Rightarrow(S^{*}\\cup S)\\Rightarrow(\\emptyset^{*}\\cup S)\\Rightarrow(\\emptyset^{*}\\cup a)\\)<\/p>\n Den Baum baut man so sukzessive auf. In der Abbildung sind die einzelnen Ableitungsschritte der Sequenz von \\(1-5\\) nummeriert. Am Ende liest man einfach nur das gesuchte Wort \\(\\omega\\) anhand der Bl\u00e4tter (Knoten ohne Kinder) von links nach rechts ab (auch Tiefensuche genannt).<\/p>\n Baumart Nr. 2 kam f\u00fcr ein Beispiel nicht in Frage, da wir das leere Wort \\(\\epsilon\\) mangels passender Regel nicht ableiten k\u00f6nnen (siehe unsere Regelmenge) und ich zu faul war eine neue Regelmenge zu definieren. Evtl. hole ich das noch nach wenn die Zusammenfassungen zu allen Kurseinheiten online sind.<\/p>\n Noch eine Kleinigkeit zur Notation:<\/p>\n Wenn das Wort \\(\\omega\\) einen Ableitungsbaum mit Wurzel \\(A\\) und Front \\(\\omega\\) hat, so gilt \\(A\\xrightarrow{\\text{*}}\\omega\\)<\/p><\/blockquote>\n Es k\u00f6nnte auch mehrere Ableitungsb\u00e4ume f\u00fcr ein Wort geben. Nehmen wir wieder das Beispiel aus dem Skript:<\/p>\n Beispiel<\/strong>: \\(S\\rightarrow SS\\mid a\\mid b\\) und abgeleitetes Wort \\(aba\\)<\/p>\n Sequenz 1: \\(S\\Rightarrow SS\\Rightarrow SSS\\Rightarrow aSS\\Rightarrow abS\\Rightarrow aba\\)<\/p>\n Sequenz 2: \\(S\\Rightarrow SS\\Rightarrow aS\\Rightarrow aSS\\Rightarrow abS\\Rightarrow aba\\)<\/p>\n Durch die unterschiedlichen Ableitungssequenzen f\u00fcr ein Wort, haben wir auch unterschiedliche Ableitungsb\u00e4ume.\u00a0Damit ist die Grammatik aus diesem Beispiel mehrdeutig<\/em>.<\/p>\n Antwort zum Lernziel<\/strong>: der Ableitungsbaum bezeichnet die baumf\u00f6rmige Darstellung der Ableitung eines Wort \\(\\omega\\) aus einer Grammatik. Sobald der Baum aufgebaut ist, wird das Wort von links nach rechts anhand der Bl\u00e4tter abgelesen (Tiefensuche).<\/p>\n Wann ist eine kontextfreie Grammatik bzw. Sprache eindeutig?<\/em><\/p>\n Wie wir im letzten Beispiel gesehen haben, kann es zu einen Wort mehrere Ableitungsb\u00e4ume geben. Diese Grammatiken sind f\u00fcr die Syntaxdefinition von Programmiersprachen aufgrund dieser Mehrdeutigkeit jedoch unbrauchbar. Der Programmtext w\u00fcrde sich so auf verschiedene Weise ableiten lassen. Wir sind also auf eindeutige Grammatiken f\u00fcr Programiersprachen angewiesen.<\/p>\n Eine eindeutige Grammatik ist also dann eindeutig wenn jedes Wort aus der durch die Grammatik definierten Sprache genau einen Ableitungsbaum hat. Ebenso verh\u00e4lt es sich mit der Sprache: sie ist dann eindeutig wenn es eine eindeutige Grammatik gibt, dass die Sprache beschreibt.<\/p><\/blockquote>\n Man kann die Mehrdeutigkeit auch durch die Verwendung von Pr\u00e4zedenzregeln eliminieren. Da das nicht Teil des Skripts war, lasse ich das zun\u00e4chst einmal aus. Wenn mehr Zeit ist, schreibe ich evtl. noch ein paar Zeilen dazu. Bis dahin sei auf ein PDF der Uni Marburg<\/a> zum Thema verwiesen.<\/p>\n Antwort zum Lernziel<\/strong>: siehe Definition von oben.<\/p>\n Ausgelassen habe ich hier die abstrakten Syntaxb\u00e4ume, da sie nicht in den Lernzielen erw\u00e4hnt werden. Aber vielleicht der Vollst\u00e4ndigkeit halber noch ein paar Worte zum Thema: Was ist also diese abstrakte Syntax?<\/p>\n Sie ist nichts anderes als die wesentlichen<\/em> Teile des Ableitungsbaumes zu einem Ausdruck. Genau dieser Syntaxbaum wird auch vom Compiler verwendet um den Programmcode zu interpretieren, da der Ableitungsbaum (auch „konkreter Syntaxbaum“ statt Ableitungsbaum genannt) zu viele Informationen beinhaltet, die unwichtig sind. Die Informationen k\u00f6nnen auch in in anderer Form gespeichert werden.<\/p>\n Dazu bem\u00fche ich wieder das Beispiel aus dem Skript mit der Regelmenge<\/p>\n \\(S\\rightarrow a\\mid b\\mid\\emptyset\\mid (S\\cup S)\\mid (SS)\\mid S^{*}\\)<\/p>\n aus der verwendeten (eindeutigen) Grammatik.<\/p>\n Beispiel<\/strong>: abgeleiteter Ausdruck \\((((aa)b)^{*}\\cup(b\\cup\\emptyset^{*}))\\)<\/p>\n Sequenz: \\(S\\Rightarrow(S\\cup S)\\Rightarrow(S^{*}\\cup (S\\cup S))\\Rightarrow((SS)^{*}\\cup (b\\cup S^{*}))\\Rightarrow((SS)b^{*}\\cup (b\\cup\\emptyset^{*}))\\Rightarrow((aa)b^{*}\\cup (b\\cup\\emptyset^{*}))\\)<\/p>\n Die folgende Abbildung zeigt den zugeh\u00f6rigen Ableitungsbaum (konkreter Syntaxbaum):<\/p>\n <\/p>\n F\u00fcr uns spannend sind aber nicht die konkreten Ableitungsinformationen, sondern einfach nur die abstrakte Syntax. Entfernen wir nun alle unn\u00f6tigen Knoten aus dem Ableitungsbaum (konkreter Syntaxbaum), so bekommen wir unseren sehr kompakten abstrakten Syntaxbaum.<\/p>\n Wie man sich leicht vorstellen kann, kann dieser Baum deutlich einfacher gespeichert und geparsed werden als sein gro\u00dfer Bruder.<\/p>\n Eine sch\u00f6ne Darstellung findet sich auch in einigen Folien<\/a> aus Magdeburg. Im Kurs 1810<\/a> (Compilerbau) der FernUni wird verst\u00e4rkt darauf Bezug genommen. Wer sich diesen Kurs im Studium als Modul anh\u00f6ren m\u00f6chte (ist im Katalog B), sollte sich diese B\u00e4umchen evtl. genauer ansehen.<\/p>\n Damit haben wir auch KE6 hinter uns. Bei Fehler gilt wie immer: so schnell wie m\u00f6glich in die Kommentare.<\/p>\n","protected":false},"excerpt":{"rendered":" Lernziel 7 Was sind Ableitungsb\u00e4ume kontextfreier Grammatiken? Wie wir aus dem\u00a0Beitrag zu KE5\u00a0bereits wissen, sind regul\u00e4re Sprachen (Typ-3, rechte Seite einer Regel besteht nur aus einem Terminal, dem ein Nonterminal folgt oder einem leeren Wort)\u00a0eine echte Teilmenge der kontextfreien Sprachen (Typ-2, linke Seite der Regel besteht nur aus einem Nonterminal). Die Typ-3-Sprachen sind nur noch … <\/p>\n\n
![\"emptyset\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/emptyset.png\")
<\/a><\/p>\n![\"treeg1\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/treeg1.png\")
<\/a><\/p>\nLernziel 8<\/h2>\n
![\"g2ableitungsbaum\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/g2ableitungsbaum.png\")
<\/a><\/p>\n![\"g2abstraktesyntax\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/g2abstraktesyntax.png\")
<\/a><\/p>\n