What are the various syntactic representations for expression?

What are the various syntactic representations for expression?

Ans. If we take expression as characteristically represented by trees, then in order to expression within programs some linearization of trees is required, that is, one must have a notation for writing trees as linear sequences fo symbols. The most commonly used syntactic representation for expression are as follows –

  • Prefix Notation – An expression in prefix notation is written as op E1E2, where op is the operator to sub expression E1 and E2. An advantage of prefix notation is that it is to decode during a left-to-right scan of an expression. If a prefix expression begins with operator + , the next expression after + must be the first operand of + and expression after that must be the second operand of +. The sum of x and y is written in prefix notation as + xy. The product of + xy and z is written as * + xyz. Thus + 20 30 equals 50 and

*+20 30 60 = 50 60 = 3000

Similarly,       *20 + 30 60 = *20 90 = 1800.

The decoding of prefix notation extends to operators with a fixed number k  0 of operands. The number of operands of an operator is called its arity. The application of an operator opk of arity k  0 E1,…..,E2 is written in prefix notation as opk E1, E2,…,Ek. during a leftto-right scan, the ith expression to the right of opk is the ith operand of opk, for 1 <= i<= k.

It is also called Polish notation. A variant of this notation used in LISP is sometimes termed Cambridge Polish. In Cambridge Polish notation, parentheses surround an operator and its arguments. An expression than look like a nested set of list, where each list begins with an operator symbol followed by the lists representing the operands. The prefix/polish and Cambridge Polish notation is represented using  for exponent,  for SQRT and – for unary minus as –

tab2 (Cambridge Polish)


  • Postfix Notation – An expression in postfix notation is written as E1E2op, where op is the operator to sub expressions E1 and E2. That is, postfix notation is similar to prefix notation except that the operation symbol follows the list of operands. This notation is also called suffix or reverse polish. An advantage of postfix expression is that they can be mechanically evaluated with the help of a stack data structure.

The sum of x and y is written in postfix notation as xy +. The product of xy + and z is written as xy +z *. Thus 20 30 + equals 50 and

20 30 + 60 * = 50 60 * = 3000

Similarly,         20 30 60 +* = 20 90 * = 1800

And                  50 40 + 30 20 – * = 90 10 * = 900

  • Infix Notation – In infix notation, operators appear between their operands, + appears between a and b in the sum a + b. an advantage of infix notation is that it is familiar and hence easy to read.

But, how is an expression like a + b * c to be decoded? Is it the sum of a and b * c or it is the product of a + b and C? Such questions are answered by using the concept of precedence and associativity rules of operators. The operator * usually takes its operands before + does. Thus, the operands of * in a+ b * c and b and c the operands of + are a and b * c.

An operator at a higher precedence level takes it operands before an operator at a lower precedence level. Using parentheses to show the structure of infix expression, a + b * c is equivalent to a + (b * c) and d * e + f is equivalent to (d * e) + f. Without rules for specifying the relative precedence of operators, parentheses would be needed in expressions to make explicit the operands of an infix operator. Operators with the same precedence are typically grouped from left to right. The expression 4 – 2 – 1 is grouped as (4 – 2) – 1, which evaluates to 1.

Share this post