Question

Here are two sets of BNF grammars specifying the syntax of a language:

<exp> ::= <term> | <term> + <exp> | <term> - <exp>

<term> ::= <op> | <op> * <term>

<op> ::= <int> | <id> | (<exp>)

*********************************************

<exp> ::= <term> | <term> + <exp> | <term> - <exp> | (<exp>)

<term> ::= <op> | <op> * <term>

<op> ::= <int> | <id>

<int> will lead to non-terminals of a digit or digit sequence '123' etc.

<id> will lead to non-terminals of letters 'ABC' etc.

Do these grammars have the same set of possible outputs?

Are these grammars syntactically different? Are they semantically different? Explain

Answer 1

1. Do these grammars have the same set of possible outputs?

                   No

2. Are these grammars syntactically different?

                 Yes

3. Are they semantically different?

                Yes

Consider an example 3*(4+5)

Leftmost derivation with first set of BNF grammar:

<exp> ::= <term>

            ::= <op>*<term>

::= <int>*<term>

::= 3*<term>

::= 3*<op>

::= 3*(<exp>)

        ::= 3*(<term>+<exp>)

            ::= 3*(<op>+<exp>)

            ::= 3*(<int>+<exp>)

          ::= 3*(4 +<exp>)

            ::= 3*(4+<term>)

            ::= 3*(4+<op>)

            ::= 3*(4+<int>)

            ::= 3*(4+5)

But the expression 3*(4+5) can't be generated with second set of BNF grammar.

Hence, we can say that these grammars do not have the same set of possible outputs

• Syntax: grammatical structure and spelling
• Semantics: meanings

From this example, we know that these grammars have different output set. So, these grammars are syntactically and semantically different.