GATE CSE 1993 | Question: 25

Question

A simple Pascal like language has only three statements.

1. assignment statement e.g. x:=expression
2. loop construct e.g. for i:=expression to expression do statement
3. sequencing e.g. begin statement ;…; statement end

• A. Write a context-free grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional parenthesis and * operator in CFG.
• B. Show the parse tree for the following statements:

  for j:=2 to 10 do
  begin 
      x:=expr1;
      y:=expr2;
  end

Comments

what’s the parse tree??

Answer 1

• $P \to A \mid L \mid A \mid S\mid \epsilon$
• $A \to V := E $
• $L \to for \; V := E \;to\; E\; do\; P$
• $S \to begin\; P\;P\; end\mid \epsilon$
• $V \to id$

Comments

$\text{statement} \rightarrow id := \text{expr} $

$\text{statement} \rightarrow for \text{ } id := \text{expr } to\text{ expr } do \text{ statement}$

$\text{statement} \rightarrow begin \text{ chain } end$

$\text{chain} \rightarrow \text{statement ; chain} \mid \epsilon $

Answer 2

context-free grammar (CFG) for the statements in the given Pascal-like language:

\begin{align*}
\text{<statement>} & ::= \text{<assignment\_statement>} \,|\, \text{<loop\_construct>} \,|\, \text{<sequencing>} \\
\text{<assignment\_statement>} & ::= \text{identifier := expression} \\
\text{<loop\_construct>} & ::= \text{for identifier := expression to expression do <statement>} \\
\text{<sequencing>} & ::= \text{begin <statement> ; ... ; <statement> end} \\
\end{align*}

The tree is :