Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Context-free Grammar
2.1.
Production Rules
3.
Frequently Asked Questions
3.1.
Why is context-free Grammar called context-free?
3.2.
What is the difference between context-free Grammar and regular Grammar?
3.3.
What means context-free?
3.4.
What are the advantages of context-free Grammar?
3.5.
What are the limitations of context-free Grammar?
4.
Conclusion
Last Updated: Mar 27, 2024

Context-free Grammars

Author Parth Jain
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Compiler Design

Introduction

Similar to regular expressions, context-free grammars describe a set of strings,
i.e., languages. Furthermore, context-free Grammar also defines the structure of the strings in the language it represents.
This blog will help you understand Context-free grammar.

You can also read about - Symbol Table Operations

Context-free Grammar

Context-free Grammar can be defined using four tuples V, T, P, and S.
G= (V, T, P, S)  
Here 

  • G means the Grammar 
  • T contains a finite set of symbols called Terminals.
    A language is defined over some alphabet, for example, the set of tokens produced by a lexer or the set of alphanumeric characters. These symbols in the alphabet are called terminals.
  • V contains a finite set of symbols that are none-terminals
  • S denotes the start symbol
    The start symbol is used to derive a string. One can derive a string by repeatedly replacing a non-terminal on the right-hand side of the production until all the non-terminals have been replaced by terminal symbols.

Production Rules

T → R
T → aTc
R →T
R → RbR

Now check that the aabbbcc string can be derived from the given CFG.

⇒ aTc
⇒ aaTcc
⇒ aaRcc
⇒ aaRbRcc
⇒ aaRbcc
⇒ aaRbRbcc
⇒ aaRbRbRbcc
⇒ aaRbbRbcc
⇒ aabbRbcc
⇒ aabbbcc
We have successfully derived the string by applying the production from the Production rules.

Also see, Regular Grammar

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Why is context-free Grammar called context-free?

Context-free Grammar does not consider any context for production rules. The context is either terminals or non-terminals. Hence, The Context-free grammars only have a single non-terminal on the left side of the production rules.

What is the difference between context-free Grammar and regular Grammar?

Regular Grammar is either right or left linear, whereas context-free Grammar is a combination of terminals and non-terminals. Hence it can be said that regular Grammar is a subset of context-free Grammar.

What means context-free?

Context-free means relating to or being a grammar or language based on rules that describe a change in a string without reference to elements, not in the string

What are the advantages of context-free Grammar?

Context-Free Grammar(CFG) is useful to describe the nested chain structure or syntactic structure, such as balanced parenthesis, if-else, etc., and these can't be defined by Regular Expression. Furthermore, CFG is more powerful than Regular Grammar as it allows a broader set of rules than Regular Grammar.

What are the limitations of context-free Grammar?

Lexical rules are problematic in the case of Context-free Grammar. Notations in Context-free Grammar are pretty complicated, and by using context-free Grammar, it becomes difficult to construct the recognizer.

Conclusion

In this article, we have extensively discussed Context-free Grammar.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Happy Coding!

Next article
Syntax Trees
Live masterclass