Wie erstelle ich einen Metagrammar?

Question

Ich lerne gerade syntaktische Analyse. Ich versuche, eine metagrammar zu machen, die diese bestimmte Grammatik erzeugen könnten:

A ⇒ A '+' C | C ; 
C ⇒ C * Q ; 
C ⇒ Q ; 
Q ⇒ a | b | 'A' | "B" | "(" A ")" | <num> ; 
<num> ⇒ <Signed Int> | Float ; 
<Signed Int> ⇒ Signe Int ; 
Signe ⇒ '-' | '+' | ~eps~ 
<Int> ⇒ Digit Int | Digit ; 
Digit ⇒ '1' | '2' | '3' | '4' | 5 | 6 | 7 | 8 | "9" | "0" ; 
Float ⇒ Int '.' Int ; 

Wo <> ignoriert werden (das heißt <int> ist die gleiche wie int), Einzel-/doppelte Anführungszeichen sind für eine Zeichenfolge, ~eps~ für Epsilon ist. Alles andere wird als Symbol betrachtet (ob es sich um ein Terminal oder ein Nonterminal handelt).

Zur Zeit habe ich so etwas wie diese:

S ⇒ left "⇒" right ";" | ε 
left ⇒ symb | "<"symb">" 
right ⇒ QP 
Q ⇒ symb | """symb""" | "'"symb"'" | "<"symb">" | ε 
P ⇒ symb | '|' Q | ε 

Aber es fühlt sich für mich so falsch und ich bin nicht so sicher, was zu tun ist. Gibt es eine Methode zur Bestimmung eines Metagrammars? Wie könnte ich über diesen gehen?

Answer 1

Kein schlechter Start. Sie sollten wirklich definieren:

letter = "A" | "B" | ... | "Z" ; 
symb = letter symb | letter ; 

Aber Ihr Metagrammar erlaubt nur eine Grammatikregel. mehrere Regeln zu ermöglichen, ich denke, Sie schreiben wollen:

S = R S | ε ; 
R = left "⇒" right ";" 

Sie könnten in Tools sehr interessiert sein, die metagrammars nutzen, um sich und andere Grammatiken zu verarbeiten. Dieses kleine Papier über MetaII, von (bereit?) bespricht das Problem und zeigt, wie man Compiler baut, die es verwenden. Dies ist ein atemberaubendes Papier, und es wird Ihr Gehirn (auf eine gute Art und Weise!)

Wenn Sie mit diesem Papier fertig sind, werden Sie fühlen sehr komfortabel mit Metagrammen. (Ich habe gelernt, Compiler in den frühen 1970er Jahren damit zu bauen).