3. forth als LL(1) sprache?

forth als LL(1) sprache?

  • ?

    Hi Leuts. Ich schreibe gerade einen fourth parser. Wollte mit einer möglichst einfachen sprache beginnen. Als Grundlage gilt mir das das Buch von Wirth. Compiler Construction, welches es kostenlos zum herrunterladen gibt. Leider nur die englische Ausgabe. Kennt einer vielleicht ne Quelle für die deutsche Ausgabe? Legal natürlich. Aber zurück zum eigentlichen Problem.

    Das Buch beschreibt den Bau eines rekursiv absteigenden LL(1) Parsers. Also Top-Down-Parser mit der vorrausschau eines Tokens.

    Und beim letzten Punkt liegt das Problem. Die Zahlen können ein vorzeichen haben. Mit nur einem Zeichen ist da keine Unterscheidung möglich. -36 - sehen somit identisch aus. Hier meine EBNF ohne vorzeichen.

    // EBNF:
// non_zero_digit  = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
// zero_digit      = "0" .
// digit           = non_zero_digit | zero_digit .
// non_zero_number = non_zero_digit {digit}
// number          = non_zero_number | zero_digit .
// operator        = "+" | "*" .
// whitespace      = space | tabulator | newline .
// word            = number | operator  .
// expression      = {whitespace} word whitespace .
// program         = {expression} .

    Währe non_zero_number = [+|-] non_zero_digit {digit}, dann währe das erste Zeichen möglicherweise ein +. Somit auch das Erste von number möglicherweise ein +. Und bei word tritt dann das Problem auf. sowohl das erste zeichen von operator als auch von number könnte ein + sein. 😞

    Sieht einer vielleicht ne Lösung, wie ich das Problem umgehen kann, ohne zwei Zeichen vorraus zu schauen?

    Danke, Martin

    0
  • V

    Ich denke, bei
    1 2 -3 + + 3 * (kommt 0 raus)
    wäre der Job des Tokenizers, die -3 bzw die 3 als EIN Token zu erkennen und auszuwerten.
    Und
    1 2 - 3 + +3 * (kommt 6 raus)
    würde zu einem ganz anderen Token-Stream führen.

    Ohne Tokenizer ist für '-' der Unterschied zwischen einem Vorzeichen und einem Operator genau das folgende Zeichen (ist es ein Whitespace, war's ein Operator) (ist es eine Ziffer, war's ein Vorzeichen). Ist das dann schon LL(2)?

    0
  • ?

    Ich glaube das ist schon LL(2). Der Tokenizer ist ja nix anderes als ein parser. Dann ist halt der Tokenizer LL(2). Bin aber noch nicht sehr vertraut mit der Materie. Somit ist diese Feststellung mit Vorsichtg zu genießen.

    Aber wie wär's hier mit?

    word_prefix = "+" | "-" | digit
    word_suffix = {digit}
    word = word_prefix word_suffix
    program = {word}

    Ich hab mit den Rat mit dem Tokenizer mal zu herzen genommen und lass vorher den ganzen unnützen Leerraum überspringen. Macht das Ganze wesentlich übersichtlicher.

    0
  • O

    Hi,

    bei nur einem Zeichen vorausschau, kannst du natürlich mit

    word = number | operator

    nichts unterscheiden. Aber du must ja keinen Parser in polnischer Notation schreiben. das wäre der erste Weg, da szu fixen. Der zweite weg ist zuerst einmal herauszufinden, ob deine Sprache überhaupt LL(1) ist. Zettel und Stift nehmen und den Beweis führen sind angesagt 😛

    ich würde aber mal behaupten, dass der Parser das hier können sollte:

    // non_zero_digit  = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
// zero_digit      = "0" .
// digit           = non_zero_digit | zero_digit .
// non_zero_number = non_zero_digit {digit}
// number          = non_zero_number | zero_digit .
// whitespace      = space | tabulator | newline .
// operator        = "+" | "*" .
// minus           = number | whitespace (operator | number | "-" minus)
// word            = number | operator | "-" minus  .
// expression      = {whitespace} word whitespace .
// program         = {expression} .

    Dann hat der Whitespace eben ne Bedeutung:
    "-3" ist eine negative Zahl und "- 3" ist ein Operator - mit nachfolgender Zahl. irgendwie so halt.

    0
  • ?

    Hi Otze,

    Hier ist mein neuer Ansatz.

    negative_number = number . <-- eine negative zahl auf den Stapel
    substraction_indicator = whitespace . <-- subtrahieren der ersten beiden Zahlen auf dem Stapel
    minus = negative_number whitespace | substraction_indicator.
    word = number whitespace | operator whitespace | "-" minus .
    expression = {whitespace} word .
    program = {expression} .

    Dad scheint mir aber für die implementierung unpraktisch für weitere arbeiten.

    Danke. der Whitespace ist in der Tat teil der Syntax. Jetzt kann ich ihn natürlich mit dem Tokenizer vorher nicht mehr rausfiltern.

    Wie beweist man denn, dass ein Sprache LL(1) ist? Gibt es dafür eine Schematische Vorgehensweise?

    Ein anderer Ansatz, den ich mir überlegt habe ist folgender:

    zero = "0" .
    non_zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
    digit = zero | non_zero .
    integer = ["+" | "-"] non_zero {digit} | zero .
    DIV = "d" "i" "v"
    operator = "+" | "-" | "*" | DIV
    first_expression = number number operator .
    expression = number operator .
    program = [first_expression {expression}] .

    Hier ist es dann zwingend erforderlich die richtige Anzahl an parametern für den operator anzugeben.
    Ich glaube das es sich dann um eine pure funktionale syntax handelt, da es nicht mehr möglich ist
    Zahlen auf vorrat im Stapel zu speichern. Ein weiterer Vorteil ist, dass ich Whitespace bereits durch dcen Tokenizer herrausfiltern kann.

    0
  • ?

    Ups. Da ist ein Fehler in meiner zweiten EBNF. Es muss natürlich integer heißen und nicht number.

    Hier nochmal leicht überarbietet:

    zero              = "0" .
non_zero          = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
digit             = zero | non_zero .
integer           = ["+" | "-"] non_zero {digit} | zero .
addition_op       = "+" .
substraction_op   = "-" .
multiplication_op = "*" .
division_op       = "d" "i" "v" .
operator          = addition_op | substraction_op | multiplication_op | division_op .
first_expression  = integer integer operator .
expression        = integer operator .
program           = [first_expression {expression}] .
    0
  • ?

    Martin Kalbfuß schrieb:

    Wie beweist man denn, dass ein Sprache LL(1) ist? Gibt es dafür eine Schematische Vorgehensweise?

    Ich habe gestern zufällig zwei Algorithmen implementiert, die die FIRST- und FOLLOW-Mengen einer Grammatik berechnen können. Damit könnte man es beweisen oder widerlegen. Habe mir deine Grammatik jetzt nicht angesehen, vielleicht sieht man es auch so. Bin jetzt zu müde 😉

    Folgendes ist aus dem Drachenbuch. Kursiv sind Anmerkungen von mir:

    Eine Grammatik G gehört genau dann zur Klasse LL(1), wenn für zwei unterschiedliche Produktionen A -> alpha und B -> beta von G folgende Bedingungen gelten:

    • Für kein Terminal a werden sowohl alpha als auch beta zu Strings abgeleitet, die mit a beginnen.
      Also darf kein Terminal a in der Schnittmenge von FIRST(alpha) mit FIRST(beta) liegen.
    • alpha und beta können nicht beide zum leeren String epsilon abgeleitet werden.
      Also darf auch der leere String epsilon nicht in der Schnittmenge von FIRST(alpha) mit FIRST(beta) liegen
    • Wenn beta => epsilon, dann wird alpha zu keinem String abgeleitet, der mit einem Terminal in FOLLOW(A) beginnt. Desgleichen, wenn alpha => epsilon, dann wird beta zu keinem String abgeleitet, der mit einem Terminal in FOLLOW(B) beginnt.
      Harter Brocken. Der erste Teil heißt: Wenn epsilon in FIRST(beta) liegt, dann darf kein Element aus FIRST(alpha) auch in FOLLOW(A) liegen. Ebenso für die andere Produktion.

    <<<<<
    (Anmerkung: In der dritten Bedingung war wohl ein Fehler im Drachenbuch. Da wurde zweimal von Follow(A) gesprochen)

    Hab's gerade etwas schnell niedergetippt, sollte aber stimmen.

    Also: Wenn Du deine EBNF Syntax in stinknormale Grammatiksyntax umbaust, jage ich sie durch meine Programm und sage Dir, ob die Grammatik LL(1) ist.

    0
Anmelden zum Antworten