Kontextfreie Grammatik Einführung

Definition - Eine kontextfreie Grammatik (CFG), die aus einem endlichen Satz von Grammatikregeln besteht, ist ein Vierfacher (N, T, P, S) wo

  • N ist eine Reihe von nicht-terminalen Symbolen.

  • T ist eine Reihe von Terminals, wo N ∩ T = NULL.

  • P ist ein Regelwerk, P: N → (N ∪ T)*dh die linke Seite der Produktionsregel P hat einen rechten oder linken Kontext.

  • S ist das Startsymbol.

Example

  • Die Grammatik ({A}, {a, b, c}, P, A), P: A → aA, A → abc.
  • Die Grammatik ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
  • Die Grammatik ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε

Generierung des Ableitungsbaums

Ein Ableitungsbaum oder Analysebaum ist ein geordneter Wurzelbaum, der die semantische Information einer Zeichenfolge grafisch darstellt, die aus einer kontextfreien Grammatik abgeleitet wurde.

Darstellungstechnik

  • Root vertex - Muss mit dem Startsymbol gekennzeichnet sein.

  • Vertex - Mit einem nicht terminalen Symbol gekennzeichnet.

  • Leaves - Beschriftet mit einem Terminalsymbol oder ε.

Wenn S → x 1 x 2 …… x n eine Produktionsregel in einem CFG ist, lautet der Analysebaum / Ableitungsbaum wie folgt:

Es gibt zwei verschiedene Ansätze, um einen Ableitungsbaum zu zeichnen:

Top-down Approach −

  • Beginnt mit dem Startsymbol S

  • Geht mit Produktionen zu Baumblättern hinunter

Bottom-up Approach −

  • Startet von Baumblättern

  • Geht nach oben zur Wurzel, die das Startsymbol ist S

Ableitung oder Ertrag eines Baumes

Die Ableitung oder der Ertrag eines Analysebaums ist die endgültige Zeichenfolge, die durch Verketten der Beschriftungen der Blätter des Baums von links nach rechts unter Ignorieren der Nullen erhalten wird. Wenn jedoch alle Blätter Null sind, ist die Ableitung Null.

Example

Sei ein CFG {N, T, P, S}

N = {S}, T = {a, b}, Startsymbol = S, P = S → SS | aSb | ε

Eine Ableitung von der obigen CFG ist "abaabb"

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

Sentential Form und Partial Derivation Tree

Ein partieller Ableitungsbaum ist ein Unterbaum eines Ableitungsbaums / Analysebaums, sodass sich entweder alle untergeordneten Elemente im Unterbaum oder keines im Unterbaum befinden.

Example

Wenn in irgendeiner CFG die Produktionen sind -

S → AB, A → aaA | ε, B → Bb | ε

Der partielle Ableitungsbaum kann folgender sein:

Wenn ein partieller Ableitungsbaum die Wurzel S enthält, heißt er a sentential form. Der obige Unterbaum ist ebenfalls in sententialer Form.

Ableitung eines Strings ganz links und ganz rechts

  • Leftmost derivation - Eine Ableitung ganz links wird erhalten, indem in jedem Schritt die Produktion auf die Variable ganz links angewendet wird.

  • Rightmost derivation - Eine Ableitung ganz rechts wird erhalten, indem in jedem Schritt die Produktion auf die Variable ganz rechts angewendet wird.

Example

Lassen Sie einen beliebigen Satz von Produktionsregeln in einer CFG sein

X → X + X | X * X | X | ein

über ein Alphabet {a}.

Die Ableitung ganz links für die Zeichenfolge "a+a*a" kann sein -

X → X + X → a + X → a + X * X → a + a * X → a + a * a

Die schrittweise Ableitung der obigen Zeichenfolge ist wie folgt dargestellt:

Die Ableitung ganz rechts für die obige Zeichenfolge "a+a*a" kann sein -

X → X * X → X * a → X + X * a → X + a * a → a + a * a

Die schrittweise Ableitung der obigen Zeichenfolge ist wie folgt dargestellt:

Rekursive Grammatik links und rechts

In einer kontextfreien Grammatik G, wenn es eine Produktion in der Form gibt X → Xa wo X ist ein nicht-terminales und ‘a’ ist eine Folge von Terminals, es heißt a left recursive production. Die Grammatik mit einer linksrekursiven Produktion heißt aleft recursive grammar.

Und wenn in einer kontextfreien Grammatik G, wenn es eine Produktion gibt, ist in der Form X → aX wo X ist ein nicht-terminales und ‘a’ ist eine Folge von Terminals, es heißt a right recursive production. Die Grammatik mit einer richtigen rekursiven Produktion heißt aright recursive grammar.