646 views
1 votes
1 votes

Consider the grammar:

$G_{2}$:

  • Para $\rightarrow$ Sentence RP | Sentence
  • RP $\rightarrow$ b Sentence RP | b Sentence
  • Sentence $\rightarrow$ Word b Sentence | Word
  • Word $\rightarrow$ letter * word | letter
  • letter $\rightarrow$ id

where $id,’*’$ and $’b’$ are terminals

  1. Convert the grammar $G_2$ to an operator grammar.
  2. Define precedence relations among the terminals and show how to use a stack algorithm to parse the following string$$id*id\;b\; id * id$$

The parse should generate a rightmost derivation.

1 Answer

0 votes
0 votes

Let's define the precedence relations among the terminals:

  • Precedence of * > Precedence of b

modify the production rules to make it an operator grammar:

\[ \begin{aligned} & \text{Para} \rightarrow \text{Sentence RP | Sentence} \\ & \text{RP} \rightarrow \text{b Sentence RP | b Sentence} \\ & \text{Sentence} \rightarrow \text{Word Sentence'} \\ & \text{Sentence'} \rightarrow \varepsilon \,|\, \text{b Sentence'} \\ & \text{Word} \rightarrow \text{letter Word'} \\ & \text{Word'} \rightarrow \varepsilon \,|\, * \, \text{word Word'} \\ & \text{letter} \rightarrow \text{id} \end{aligned} \]

In the modified grammar, each production has at most one non-terminal on the right side, and the terminals are associated with operators.

Now, let's use a stack algorithm to parse the given string  \[\text{id * id b id * id}\]  based on the defined precedence relations:

  1. Initialize an empty stack and start reading the input from left to right.
  2. For each terminal encountered, push it onto the stack.
  3. When a terminal with lower precedence encounters a terminal with higher precedence on the stack, reduce the stack using the production rules.

Parsing Steps:

  • Stack: [id]
  • Input: * id b id * id
  • Reduce: (Apply Word -> letter)
    • Stack: [Word]
    • Input: * id b id * id
  • Reduce: (Apply Sentence -> Word Sentence')
    • Stack: [Sentence']
    • Input: * id b id * id
  • Shift: (Push b onto the stack)
    • Stack: [Sentence' b]
    • Input: id b id * id
  • Reduce: (Apply Sentence' -> b Sentence')
    • Stack: [Sentence']
    • Input: id * id
  • Reduce: (Apply Sentence -> Word Sentence')
    • Stack: [Word Sentence']
    • Input: id * id
  • Reduce: (Apply Word -> letter Word')
    • Stack: [Word' Sentence']
    • Input: * id
  • Shift: (Push * onto the stack)
    • Stack: [Word' Sentence' *]
    • Input: id
  • Reduce: (Apply Word' -> ε)
    • Stack: [Word Sentence']
    • Input: id
  • Reduce: (Apply Sentence' -> ε)
    • Stack: [Word]
    • Input: id

At this point, the stack contains only one non-terminal, and the input is empty. The parsing is successful

Related questions

24 votes
24 votes
1 answer
4
makhdoom ghaya asked Nov 26, 2016
7,223 views
Show that grammar $G_1$ is ambiguous using parse trees:$G_{1}: S \rightarrow$ if $S$ then $S$ else $S$ $S \rightarrow$ if $S$ then $S$