Grammatik: Unterschied zwischen einem Top Down und Bottom Up? (Beispiel)

Question

Dies ist eine Follow-up-Frage von Grammar: difference between a top down and bottom up?

ich von dieser Frage verstehen, dass:

• die Grammatik selbst ist nicht top-down oder bottom-up, der Parser
• ist es gibt Grammatiken, die von einem analysiert werden kann, nicht aber die anderen
• (dank Jerry Coffin

Also für diese Grammatik (alle pos sible mathematische Formeln):

E -> E T E 
    E -> (E) 
    E -> D 

    T -> + | - | * |/

    D -> 0 
    D -> L G 

    G -> G G  
    G -> 0 | L 

    L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

Würde dies von einem Top-Down- und Bottom-Up-Parser gelesen werden?

Können Sie sagen, dass dies eine Top-Down-Grammatik oder eine Bottom-Up-Grammatik (oder keine) ist?

---

ich frage, weil ich eine Hausaufgaben Frage haben, die fragt:

„schreiben Top-down- und Bottom-up-Grammatiken für die Sprache die alle aus ...“ (andere Frage)

Ich bin nicht sicher, ob dies richtig sein kann, da es scheint, dass es keine Top-down- und Bottom-up-Grammatik gibt. Könnte jemand klären?

Answer 1

Diese Grammatik ist dumm, da sie Lexing und Parsing vereint. Aber ok, es ist ein akademisches Beispiel.

Die Sache mit bottoms-up und top-down ist, dass es spezielle corner cases hat, die schwer zu implementieren sind, wenn Sie normal aussehen. Ich denke wahrscheinlich, dass Sie überprüfen sollten, ob es Probleme gibt und die Grammatik ändern.

Um zu verstehen, Sie Grammatik ich eine richtige EBNF

schrieb

expr: 
    expr op expr | 
    '(' expr ')' | 
    number; 

op: 
    '+' | 
    '-' | 
    '*' | 
    '/'; 

number: 
    '0' | 
    digit digits; 

digits: 
    '0' | 
    digit | 
    digits digits; 

digit: 
    '1' | 
    '2' | 
    '3' | 
    '4' | 
    '5' | 
    '6' | 
    '7' | 
    '8' | 
    '9'; 

ich besonders mag nicht die Regel digits: digits digits. Es ist unklar, wo die ersten Ziffern beginnen und die zweite endet. Ich würde die Regel implementieren als

digits: 
    '0' | 
    digit | 
    digits digit; 

Ein anderes Problem number: '0' | digit digits; Dies steht im Widerspruch mit digits: '0' und digits: digit; ist. In der Tat ist das doppelt vorhanden. Ich würde die Regeln ändern zu (Entfernen von Ziffern):

number: 
    '0' | 
    digit | 
    digit zero_digits; 

zero_digits: 
    zero_digit | 
    zero_digits zero_digit; 

zero_digit: 
    '0' | 
    digit; 

Dies macht die Grammatik LR1 (mit einem Blick linksrekursiv voraus) und kontextfrei. Dies würden Sie normalerweise einem Parser-Generator wie Bison geben. Und da Bison unten ist, ist dies eine gültige Eingabe für einen Bottoms-Up-Parser.

Für einen Top-Down-Ansatz, zumindest für rekursive decent, ist links rekursiv ein bisschen ein Problem. Sie können Rollback verwenden, wenn Sie möchten, aber für diese möchten Sie eine RR1 Grammatik (Recht rekursiv ein Blick nach vorne).Um dies zu tun, tauschen Sie die Rekursionen:

Ich bin nicht sicher, ob das beantwortet Sie Frage. Ich denke, die Frage ist schlecht formuliert und irreführend; und ich schreibe Parser für einen Lebensunterhalt ...