Syntax überprüfen

[babuschka]

Hallo! Meine Frage hat mit der händischen Syntaxüberprüfung zu tun.

Und zwar geht es um die polnische Notation:
Beispiel: 4+8-2 = +(4,-(8,2))

D.h. man schreibt die Verknüpfungsoperatoren vorne und erst danach die Ausdrücke.
Die Ausdrücke sollen aus ganzen Zahlen, den mathematischen Grundoperationen +,-,*,/, runden Klammern () und Kommata zusammengesetzt sein.

Für die Einfachheit sind auch Zahlen mit führenden Nullen zugelassen.

Hieraus folgt die folgende lexikalische Grammatik:

binop = '+' | '/' | '*'
minop = '-'
lb = '('
rb = ')'
komma = ','
nums = num {nums}
num = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Hierauf aufbauend besteht die Grammatik aus diesen Regeln:

TERM = BINTERM
         | MINTERM
         | nums

BINTERM = binop ARGS

MINTERM = minop MINREST

MINREST = ARGS
             | nums

ARGS = lb TERM komma TERM rb

Die Aufgabe besteht nun darin, für die folgenden Ausdrücke einen Ableitungsbaum zu entwickeln:

1.) *(+(4,12),/(10,3))

2.) -(-(4,*(3,4)))

3.) /(+(-3,04),-01)


Für 1.) habe ich das schon mittels graphviz erstellt (s. Anhang). Das Prinzip ist mir also - denke ich - klar.

Doch bei 2.) und 3.) komme ich nicht so einfach zurecht.

Wieso braucht man hier Zahlen mit führender Null, was bedeutet zum Beispiel:

+(-3,04) in "normaler" Schreibweise?

 

[Firephoenix]

Wenn die 1 so geht schaffst du auch die 2 und die 3.
Einfach den Term anschauen, überlegen aus welchen Regeln er sich zusammensetzt und das Ding zerlegen.

-(-(4,*(3,4)))

ganz vorne steht ein- , die einzige Möglichkeit wie es entstanden sein kann ist ein minterm
(-(4,*(3,4))) sind also ARGS oder num (num offensichtlich nicht). das nächste zeichen ist die (, wo kommt sie her?
ARGS = lb TERM komma TERM rb
ist der einzige Term der passt.

du hast also -(4,*(3,4)) was du noch als Term komma Term schreiben musst.
jetzt ist wieder die Frage: welcher Term fängt mit einem - an?
usw...

Gruß

 

[babuschka]

Das habe ich soweit auch gemacht, aber ich kriege den Ausdruck 2.) nicht in so einen Baum.

Ich komme nur bis zur vorletzten Klammer und danach müsste ein Komma und dann die letzte Klammer kommen, da steht ja aber mehr kein Komma zwischen der vorletzten und der letzten Klammer.


Edit: Achso, das bedeutet dann wohl: Der Ausdruck ist nicht gültig im Sinne der festgelegten Grammatik?

 

[Firephoenix]

sieht zumindest so aus, denn wenn du den minterm innen mal durch term ersetzt bekommst du

-(TERM)
und dafür gibt es keine ableitung, sinn würde höchstens -(0,Term) machen um eine negation auszudrücken

 

[babuschka]

Also ich habe das jetzt mal so dargestellt (s. Dateianhang).

Das Rote soll das sein, das man meines Erachtens ergänzen könnte, um einen erlaubten Ausdruck (der im Ergebnis unverändert ist) im Sinne der gegebenen Grammatik zu erhalten.

So (ohne das Rote) handelt es sich jedenfalls um einen Ausdruck, der im Sinne der Grammatik nicht darzustellen ist.


Korrekt?

 

[babuschka]

Und dann noch die Frage: Ist der dritte Baum okay?
(Anhang)