Examples Of Context Free Languages (CFL)

So far, we have seen very good examples of Regular expressions and Regular Languages. We will see more difficult problems in future. But at this time, we are going to start examples of context free languages (CFL). There are a lot of problems based on CFL. So we will discuss a lot of problems of CFL.

Example 1
Consider the following input string:
x+2*y

When scanned by a scanner, it produces the following stream of tokens:

id(x)
+
num(2)
*
id(y)

The goal is to parse this expression and construct a data structure (a parse tree) to represent it. One possible syntax for expressions is given by the following grammar G1:

E ::= E + T | E - T | T
T ::= T * F | T / F | F
F ::= num | id

where E, T and F stand for expression, term, and factor respectively. For example, the rule for E indicates that an expression E can take one of the following 3 forms: an expression followed by the token + followed by a term, or an expression followed by the token - followed by a term, or simply a term. The first rule for E is actually a shorthand of 3 productions:

E ::= E + T
E ::= E - T
E ::= T
G1 is an example of a context-free grammar (defined below); the symbols E, T and F are nonterminals and should be defined using production rules, while +, -, *, /, num, and id are terminals (i.e., tokens) produced by the scanner. The nonterminal E is the start symbol of the grammar.

In my next Posts, I will explain types of parsing because knowledge of them is necessary for writing context free grammars.

Automata Step by Step

Today, we will discuss “Regular expressions”.

Regular expressions:

A regular expression (also "RegEx" or "regex”) is a string that is used to describe or match a set of strings, according to certain syntax rules. The specific syntax rules vary depending on the specific implementation, programming language, or library in use. Additionally, the functionality of regex implementations can vary between versions

In another words, a regular expression, often called a pattern, is an expression that describes a set of strings. They are usually used to give a concise description of a set, without having to list all elements. For example, the set containing the three strings Handel, Händel, and Haendel can be described by the pattern "H(ä|ae?)ndel" (or alternatively, it is said that the pattern matches each of the three strings). In most formalism, if there is any regex that matches a particular set then there are an infinite number of such expressions.