Formale Sprachen Informatik EBNF 🙏Bitte um Hilfe?

Die folgende Grammatik einer Programmiersprache ist in EBNF gegeben:

Übertragen Sie diese Grammatik in die klassische Grammatiknotation. Nehmen Sie verständliche Namen für die Nonterminalsymbole.

Hey Leute, könnt ihr mir bei diesem Übungsbeispiel helfen?

Comments

[malte314]

Was genau ist denn das Problem?

[0AXBXCXDX0]

Ja ich verstehe nicht wie das ganze überhaupt geht :(

Answer 1

[ralphdieter]

Ich gehe mal davon aus, dass Du mit formaler Grammatik und der Notation ihrer Produktionsregeln vertraut bist.

EBNF wurde entwickelt, um solche Regeln kompakter und verständlicher zu formulieren, ohne die Exaktheit zu beeinträchtigen. Neue Elemente sind z. B.:

• { X }: beliebige Wiederholung von X
• [ X ]: optionales X
• X | Y: entweder X oder Y

Um eine EBNF in klassische Regeln zu konvertieren, musst Du diese Konstrukte über Hilfsregeln abbilden. Das geht weitgehend nach Schema F:

Aus L = { X } wird:

• L → 𝜀
• L → L X

Aus L = [ X ] wird:

• L → 𝜀
• L → X

Aus L = X | Y wird:

• L → X
• L → Y

Bei Deiner EBNF wird es sinnvoll sein, Nichtterminale für {Stat}, die drei Alternativen von Stat, sowie für {"ELSEIF" ...} einzuführen. Als „verständliche Namen“ würde ich persönlich „block-statement“, „statement-list“, „if-statement“, „for-statement“ und „elif-phrase“ wählen (und „Stat“/“Expr“ durch „statement“/„expression“ ersetzen).

Die Lösung wird dann so anfangen:

• statement → block-statement
• statement → if-statement
• statement → for-statement
• block-statement → "BEGIN" statement-list "END"
• statement-list → 𝜀
• statement-list → statement-list statement
• if-statement → ...
• for-statement → ...

Bei den letzten beiden will ich Dir den Spaß nicht nehmen, es selbst zu lösen.