699 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

664
views
0 answers
1 votes
makhdoom ghaya asked Nov 25, 2016
664 views
The following algorithm (written in pseudo-pascal) work on an undirected graph $G$program Explore (G) procedure Visit (u) begin if Adj (u) is not empty { ... LIST in constant time. Also, show that all edges of the graph are traversed.
1.1k
views
0 answers
1 votes
makhdoom ghaya asked Nov 25, 2016
1,064 views
Consider the following instance of the $0 -1$ Knapsack problem:$\max\; 6X_{1} + 11X_{2} + 16X_{3} + 21X_{4} + 26X_{5}$ ... for each node show the bound on the partial solutions and the decision which leads to that node.
929
views
0 answers
2 votes
makhdoom ghaya asked Nov 24, 2016
929 views
Assume that an instruction test-and-set (TS) has been provided in a machine whose function is as follows: 'the left most bit of the one byte ... checking and setting the condition code, implement a critical region using this instruction.
7.6k
views
1 answers
24 votes
makhdoom ghaya asked Nov 26, 2016
7,627 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$