Gramatyka bezkontekstowa to gramatyka formalna. Składnię lub strukturę języka formalnego można opisać za pomocą gramatyki bezkontekstowej (CFG), rodzaju gramatyki formalnej. Gramatyka ma cztery krotki: (V, T, P, S).

V - It is the collection of variables or nonterminal symbols. T - It is a set of terminals.  P - It is the production rules that consist of both terminals and nonterminals. S - It is the Starting symbol.>

Gramatykę nazywamy gramatyką bezkontekstową, jeśli każde przedstawienie ma postać:

G ->(V∪T)*, gdzie G ∊ V>

• A lewa strona G, w tym przykładzie, może być tylko zmienną, nie może to być terminal.
• Ale po prawej stronie może to być zmienna lub terminal, albo obie kombinacje zmiennej i terminala.

Powyższe równanie stwierdza, że ​​każda produkcja zawierająca dowolną kombinację zmiennej „V” lub terminala „T” nazywana jest gramatyką bezkontekstową.

Na przykład gramatyka A ​​= { S, a, b, P, S} mająca produkcję :

• Tutaj S jest symbolem początkowym.
• {a, b} to terminale zazwyczaj reprezentowane przez małe znaki.
• P jest zmienne wraz z S.

S->as S-> bSa>

Ale

a->bSa lub a->ba nie jest CFG, gdyż po lewej stronie znajduje się zmienna, która nie spełnia reguły CFG.>

W informatyce często stosuje się gramatykę bezkontekstową, zwłaszcza w obszarach teorii języka formalnego, tworzenia kompilatorów i przetwarzania języka naturalnego. Służy również do wyjaśniania składni języków programowania i innych języków formalnych.

Ograniczenia gramatyki bezkontekstowej

Oprócz wszystkich zastosowań i znaczenia gramatyki bezkontekstowej w projektowaniu kompilatorów i w dziedzinie informatyki, istnieją pewne ograniczenia, które należy uwzględnić, to znaczy CFG są mniej wyraziste i ani angielski, ani język programowania nie mogą być wyrażone za pomocą bezkontekstowej Gramatyka. Gramatyka bezkontekstowa może być niejednoznaczna, co oznacza, że ​​możemy wygenerować wiele drzew analizy tych samych danych wejściowych. W przypadku niektórych gramatyk gramatyka bezkontekstowa może być mniej wydajna ze względu na wykładniczą złożoność czasową. Mniej precyzyjne raportowanie błędów, jakie ma system raportowania błędów CFG, nie jest tak precyzyjne, aby zapewnić bardziej szczegółowe komunikaty o błędach i informacje.