LP Quiz Test 4

1. Construct LL(1) parsing table for the following grammar:
                Program → begin d Semi X end
                X → d semi X / s Y
                Y → semi s Y / λ

	begin	d	semi	end	s	$
Program	1
X		2			3
Y			4	5

What will be the entry for 2:

Program → begin d Semi X end

X → s Y

X → d semi X

Y → semi s Y

The entry for 2 in the LL(1) parsing table will be X → d semi X. This is because when the parser sees a non-terminal X followed by the terminal "d", it knows that it should use the production X → d semi X to expand X.

Explanation

The entry for 2 in the LL(1) parsing table will be X → d semi X. This is because when the parser sees a non-terminal X followed by the terminal "d", it knows that it should use the production X → d semi X to expand X.

2. Construct LL(1) parsing table for the following grammar:
                Program → begin d Semi X end
                X → d semi X / s Y
                Y → semi s Y / λ

	begin	d	semi	end	s	$
Program	1
X		2			3
Y			4	5

What will be the entry for 1:

X → d semi X

Program → begin d Semi X end

X → s Y

Y → semi s Y

not-available-via-ai

Explanation

not-available-via-ai

3. Construct LL(1) parsing table for the following grammar:
                Program → begin d Semi X end
                X → d semi X / s Y
                Y → semi s Y / λ

	begin	d	semi	end	s	$
Program	1
X		2			3
Y			4	5

What will be the entry for 4:

Program → begin d Semi X end

X → d semi X

X → s Y

Y → semi s Y

not-available-via-ai

Explanation

not-available-via-ai

4. Construct LL(1) parsing table for the following grammar:
                Program → begin d Semi X end
                X → d semi X / s Y
                Y → semi s Y / λ

	begin	d	semi	end	s	$
Program	1
X		2			3
Y			4	5

What will be the entry for 3:

Program → begin d Semi X end

X → s Y

Y → semi s Y

Y → λ

not-available-via-ai

Explanation

not-available-via-ai

5. Construct LL(1) parsing table for the following grammar:
                Program → begin d Semi X end
                X → d semi X / s Y
                Y → semi s Y / λ

	begin	d	semi	end	s	$
Program	1
X		2			3
Y			4	5

What will be the entry for 5:

Program → begin d Semi X end

X → d semi X

Y → λ

Y → semi s Y

The entry for 5 in the LL(1) parsing table will be Y → λ. This is because when the parser sees a "semi" token in the input, it can choose to expand Y → λ, which represents an empty production. This allows the parser to skip over the "semi" token and continue parsing the rest of the input.

Explanation

The entry for 5 in the LL(1) parsing table will be Y → λ. This is because when the parser sees a "semi" token in the input, it can choose to expand Y → λ, which represents an empty production. This allows the parser to skip over the "semi" token and continue parsing the rest of the input.

6. Consider the following grammar: S → CC C →cC / d The above grammar is

LL(1)

SLR(1) but not LL(1)

SLR(1) but not LR(0)

The given grammar is LL(1) because it is a left-to-right, leftmost derivation with one lookahead symbol. In LL(1) parsing, the parser scans the input from left to right, and at each step, it uses a single lookahead symbol to decide which production rule to apply. In this grammar, the non-terminal S can only derive to CCC or cC, and there is no ambiguity or conflict in the productions. Therefore, the grammar is LL(1).

Explanation

The given grammar is LL(1) because it is a left-to-right, leftmost derivation with one lookahead symbol. In LL(1) parsing, the parser scans the input from left to right, and at each step, it uses a single lookahead symbol to decide which production rule to apply. In this grammar, the non-terminal S can only derive to CCC or cC, and there is no ambiguity or conflict in the productions. Therefore, the grammar is LL(1).

7. Consider the following grammar: E → E + n / E * n / nfor the sentence n+n*n, the handles in the bottom-up parsing will be:

N, E+n and E+n*n

N, E+n and E+E*n

N, n+n and n+n*n

N, E+n and E*n

The given grammar is a right-recursive grammar, which means that the rightmost non-terminal in the production rule is expanded first. In the given sentence "n+n*n", the handles are the substrings that match the right side of a production rule and can be reduced to the left side of that rule.

Starting from the leftmost non-terminal, we can see that the handle "n" matches the right side of the production rule E -> n. This handle can be reduced to E.

Next, the handle "E+n" matches the right side of the production rule E -> E + n. This handle can be reduced to E.

Finally, the handle "E*n" matches the right side of the production rule E -> E * n. This handle can also be reduced to E.

Therefore, the handles in the bottom-up parsing of the given sentence are n, E+n, and E*n.

Explanation

The given grammar is a right-recursive grammar, which means that the rightmost non-terminal in the production rule is expanded first. In the given sentence "n+n*n", the handles are the substrings that match the right side of a production rule and can be reduced to the left side of that rule.

Starting from the leftmost non-terminal, we can see that the handle "n" matches the right side of the production rule E -> n. This handle can be reduced to E.

Next, the handle "E+n" matches the right side of the production rule E -> E + n. This handle can be reduced to E.

Finally, the handle "E*n" matches the right side of the production rule E -> E * n. This handle can also be reduced to E.

Therefore, the handles in the bottom-up parsing of the given sentence are n, E+n, and E*n.

8. Consider SLR(1) and LR(0) table for any given CFG. Which one of the following is false?

Error entries in both the tables may be different

Goto of both the tables may be different

Shift entries are identical in both the tables

Reduce entries in both the tables may be different

The Goto entries in the SLR(1) and LR(0) tables may be different. The Goto entries in the SLR(1) table represent the next state to transition to when a non-terminal symbol is encountered, while the Goto entries in the LR(0) table represent the next state to transition to when a production rule is completed. Since the SLR(1) and LR(0) parsing methods have different lookahead sets, it is possible for the Goto entries to differ between the two tables.

Explanation

The Goto entries in the SLR(1) and LR(0) tables may be different. The Goto entries in the SLR(1) table represent the next state to transition to when a non-terminal symbol is encountered, while the Goto entries in the LR(0) table represent the next state to transition to when a production rule is completed. Since the SLR(1) and LR(0) parsing methods have different lookahead sets, it is possible for the Goto entries to differ between the two tables.

9. Consider the following two statementsa) Every SLR(1) grammar is also LR(0) grammar.b) Every LL(1) grammar is also LL(2) grammar.Which of the following option is correct?

Only a is true

Only b is true

Both are true

Both are false

not-available-via-ai

Explanation

not-available-via-ai

10. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length:

No greater than 2 ^ (i+1)

No greater than 2 ^ i

No greater than 2 ^ (i-1)

No greater than i

If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length no greater than 2 ^ i. This is because the Chomsky normal form grammar restricts the length of the paths in the parse tree. Each rule in the grammar either replaces a non-terminal symbol with two non-terminal symbols or with a terminal symbol. Therefore, at each step, the number of symbols in the word doubles. So, if there is no path of length greater than i, then the word can have at most 2 ^ i symbols.

Explanation

If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length no greater than 2 ^ i. This is because the Chomsky normal form grammar restricts the length of the paths in the parse tree. Each rule in the grammar either replaces a non-terminal symbol with two non-terminal symbols or with a terminal symbol. Therefore, at each step, the number of symbols in the word doubles. So, if there is no path of length greater than i, then the word can have at most 2 ^ i symbols.

Lp Quiz Test 4