Ich habe Probleme mit der Übersetzung von EBNF nach BNF

Question

Ich lerne über Compiler und Konzepte von Programmiersprachen. Wie kann ich es übersetzen?

Problem:

<S> → (+ | -)[<C>]{<A>} 

Zuerst habe ich wie folgt übersetzt:

<S> -> epsilon 
    | +<S> 
    | -<S> 
    | <C><S> 
    | <A><S> 

Sie hat jedoch ein Problem, dass es C wiedergeben kann!

Answer 1

Ihre BNF-Version kann nicht nur mehrere <C> s, sondern auch mehrere + s und - s (oder null, die sich auch von der ursprünglichen Grammatik unterscheiden).

Um diese Probleme zu beheben, müssen Sie zusätzliche Nicht-Terminals einführen. Konkret könnte man eine haben, die nur {<A>} entspricht und eine, die [<C>] entspricht. Ihre Definition von <S> könnte dann sein:

<S> -> + <OptionalC> <RepeatedA> 
    | - <OptionalC> <RepeatedA> 

Answer 2

Ihr EBNF Original in <S> nicht rekursiv ist, aber Ihre Studie BNF ist. Wenn Sie möchten, dass das BNF dieselbe Sprache generiert, sollten Sie das nicht tun. Außerdem kann Ihr EBNF epsilon nicht erzeugen, also sollten Sie das auch nicht zu Ihrer <S>-Produktion hinzufügen.

Wie die andere Antwort sagt, müssen Sie zusätzliches nicht-Terminals vorstellen:

<S> -> <plusminus> <optionalC> <repeatedA> 
<plusminus> -> + | - 
<optionalC> -> <C> | epsilon 
<repeatedA> -> <A> <repeatedA> | epsilon 

Dies ist eine einfache Übersetzung der EBNF-Elemente in Ihrer ursprünglichen Grammatik. Selbst wenn Sie zusätzliche Anforderungen haben (z. B. Epsilon-Eliminierung), sollten Sie mit dieser Art von Schritt beginnen.

Beachten Sie, dass die <S> Regel nicht rekursiv ist. Auch wenn epsilon für einige zusätzliche Nicht-Terminals verwendet wird, ist es nicht Teil der <S> oder <plusminus> Regeln, so dass, wie in der EBNF-Original, <S> kann es nicht produzieren.