Ist das eine mehrdeutige Grammatik? Wie soll ich es lösen?

Question

Um das vorweg zu nehmen, ist mein Wissen über diese Art von Sachen mickrig.

Wie auch immer, ich habe eine kontextfreie Grammatik entwickelt, um die Struktur von algebraischen Ausdrücken zu beschreiben, damit ich mir beibringen kann, wie der CYK Parsing-Algorithmus funktioniert. Ich verstehe, wie eine solche Struktur nur mit infixalgebraischen Ausdrücken arbeiten kann, aber ich kann nicht verstehen, wie man eine Grammatik entwickelt, die sowohl die unären als auch die binären Definitionen des "-" Operators handhaben kann.

als Referenz, hier ist die Grammatik ich geschrieben habe in CNF (wobei S das Startsymbol ist):

S -> x
A -> O
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O ->/
O ->^
K -> -
L -> (
R ->)

Das Problem ist, dass, wie kann die CYK Algorithmus weiß, vor der Zeit, Parsen, ob zwischen S entscheiden -> KS und A -> O wenn es auf den "-" Operator trifft? Ist eine solche Grammatik nicht mehr kontextfrei? Und am wichtigsten, da Programmiersprachen Sprachen mit sowohl dem binären als auch dem unären Minuszeichen behandeln können, wie sollte ich dies vernünftigerweise analysieren?

Answer 1

Dies scheint ein Problem zu endlichen Automaten bezogen und ich weiß nicht alles von meinem Kurs erinnern, aber ich schrieb einen CYK Parser in OCaml ich werde, so gehen Sie vor und einen Schuss nehmen :)

Wenn Sie versuchen, einen Ausdruck wie 3- -4 zum Beispiel zu analysieren, würden Sie Ihre S -> K S Regel die -4 konsumieren und dann A -> O S Regel würde die - -4 absorbieren. Dies würde schließlich bis zur obersten Produktionsregel S funktionieren. Sie sollten jedoch mit der Grammatik, die Sie verwenden, vorsichtig sein, da die A Produktionsregel, die Sie aufgelistet haben, nicht von S erreicht werden kann und Sie wahrscheinlich eine S -> S O S Regel haben sollten.

Die Funktionsweise von CYK-Parsing-Algorithmen beruht auf Backtracking, nicht auf dem "Wissen im Voraus", das Sie in Ihrer Frage erwähnt haben. Was Ihr CYK-Algorithmus tun sollte, ist die -4 als S -> K S Regel zu analysieren und dann würde es versuchen, die zweite - mit der S -> K S Regel wieder zu absorbieren, weil diese Produktionsregel eine beliebig lange Kette von unären - erlaubt. Aber sobald Ihr Algorithmus erkennt, dass er bei der Zwischenanalyse 3 S festsitzt, stellt er fest, dass er keine Produktionssymbole hat, die er zum Parsen verwenden kann. Sobald es erkennt, dass dies nicht mehr analysierbar ist, wird es zurückgehen und stattdessen versuchen, die 10 als Regel S -> O S zu analysieren und weiter auf seine fröhliche Art und Weise.

Das bedeutet, dass Ihre Grammatik kontextfrei bleibt, da eine kontextsensitive Grammatik bedeutet, dass Sie Terminals auf der linken Seite der Produktionsregeln haben, also sind Sie in dieser Hinsicht gut. HTH!

Answer 2

Die Grammatik ist mehrdeutig und der Parser kann nicht entscheiden, welcher Fall zu nehmen ist.

Sie sollen wahrscheinlich eine Grammatik wie die folgenden verwenden:

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

Grammatiken auf algebraischen Ausdrücken basieren, sind ziemlich schwierig, eindeutig zu machen. Hier sind einige Beispiele für Probleme, die angesprochen werden müssen:

a + b + c erstellt natürlich zwei Parsebäume. Um dies zu lösen, müssen Sie die Mehrdeutigkeit der Assoziativität von + auflösen. möchten Sie vielleicht eine von links nach rechts lassen Strategie Pflege für Sie diese nehmen Parsen, aber vorsichtig: Potenzierung wahrscheinlich von rechts nach links verbinden sollte.

a + b * c schafft natürlich zwei Parse-Bäumen. Um dieses Problem zu beheben, müssen Sie sich mit der Vorrangstellung des Operators befassen.

Implizite Multiplikation (a + bc), wenn es erlaubt ist, erzeugt alle Arten von Albträumen, meist bei Tokenisierung.

einstellige Subtraktion ist problematisch, da Sie erwähnen.

Wenn wir diese Probleme lösen wollen, aber immer noch eine schnelle Parsing-Grammatik für Algebra haben, besteht ein Ansatz darin, verschiedene "Ebenen" von EXPR zu haben, einen für jede Ebene der Bindung, die nach Rangstufen erforderlich ist. Zum Beispiel

TERM -> (S) 
EXPO -> TERM^EXPO 
PROD -> PROD * EXPO 
PROD -> PROD/EXPO 
PROD -> -PROD 
SUM -> SUM + PROD 
SUM -> SUM - PROD 
S -> SUM 

Dies erfordert, dass Sie auch "Förderung" von Typen erlauben: SUM -> ART, ART -> EXP, EXP -> TERM, usw., so dass sie die Dinge zu beenden.

Hoffe, das hilft!