ambiguous grammar examples

In the last post, We saw 2 possible parse trees for a+a+a. How many are there for a+a+a+a?

There are 5 possible parses:

(a)+((a+a)+a),

(a)+(a+(a+a)),

(a+a)+(a+a),

((a+a)+a)+(a),

(a+(a+a))+(a)


While in general it may be difficult to prove a grammar is ambiguous, the demonstration of two distinct parse trees for the same terminal string is sufficient proof that a grammar is ambiguous.

equivalent grammer

Consider the following grammar G1 again:
E ::= E + T | E - T | T
T ::= T * F | T / F | F
F ::= num | id

Consider now the following grammar G2

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

Consider now the following grammar G3:
E ::= E + E | E – E | E * E | E / E | num | id

Is this grammar equivalent to our original grammar G1?

Well, it recognizes the same language, but it constructs the wrong parse trees.

parse tree

Consider now the following grammar G2:

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

This is similar to our original grammar G1 (which we considered in our previous posts), but it is right associative when the leftmost derivation rules is used. That is, x-y-z is equivalent to x-(y-z) under G2, as we can see from its parse tree.

Parse tree

Let’s see another example of parse tree. As another example, consider the following grammar:
S ::= ( L )| a

L ::= L , S | S

Under this grammar, the parse tree of the sentence (a,((a, a), a)) is:

S
/ | \
( L )
/ | \
L , S
| / | \
S ( L )
| / | \
a L , S
| |
S a
/ | \
( L )
/ | \
L , S
| |
S a
|
a

Parse Tree

The parse tree of an input sequence according to a CFG is the tree of derivations. For example if we used a production A : : = X1X2...Xn (in either top-down or bottom-up parsing) then we construct a tree with node A and children X1X2...Xn.
For example, the parse tree of id(x) + num(2) * id(y) is:
E
/ | \
E + T
| / | \
T T * F
| | |
F F id
| |
id num

Automata Step by Step

This post is connected to the previous post. So if you have not read that post, please give few minutes in reading that post.

Parsing:

Parsing (more formally syntax analysis) is the process of analyzing a sequence of tokens to determine its grammatical structure with respect to a given formal grammar. A parser is the component of a compiler that carries out this task.

Parsing transforms input text into a data structure, usually a tree, which is suitable for later processing and which captures the implied hierarchy of the input. Lexical analysis creates tokens from a sequence of input characters and it is these tokens that are processed by a parser to build a data structure such as parse tree or abstract syntax trees.

Can you guess what the next question is? Yes, you are right. Next question is what the Formal Grammar is.

Automata Step by Step

I am writing this blog for the people who are strongly interested in Automata and Formal languages or who want to start from basics of Automata.

First of all, we will discuss some very basic definitions of Automata. In Automata theory, all things are related to each other so you will notice that you need definitions of other words for understanding a particular definition. We will also see formal definitions of all terms after understanding their basic definitions. After basic and formal definitions, we will solve a lot of good “Problems of Automata” and see a lot of good examples.

Basic Definitions:

If you are a beginner, you should know what is Automata and Automata theory.

1. Automaton:
In Simple Words, An automaton (plural: automata) is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. Used colloquially, it refers to a mindless follower.

An automaton is a mathematical model for a finite state machine (FSM). An FSM is a machine that, given an input of symbols, 'jumps' through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.

2. Automata theory:

Automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.

Now at this point, it is important to know about Finite state machines.

3. Finite state machine (FSM):

A finite state automaton (plural: automata) is a model of behavior composed of a finite number of states, transitions between those states, and actions.

4. States:

A state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers.

We will see the definition of parser in the next post. Above 4 definitions are enough for today. Please don’t forget to review them otherwise you will not be able to understand the next post. Read carefully. Have a good day.