Question

In: Computer Science

Here are two sets of BNF grammars specifying the syntax of a language: <exp> ::= <term>...

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

Solutions

Expert Solution

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.


Related Solutions

Must use AT&T x64/GNU Assembly syntax. Write an assembly language program that reads in two integers,...
Must use AT&T x64/GNU Assembly syntax. Write an assembly language program that reads in two integers, A and B, and uses them to compute the following expressions. You must use the same values for A and B throughout all three expressions. 1) A * 5 2) (A + B) - (A / B) 3) (A - B) + (A * B)
There are two restrictions on the type of grammars that can be used with a recursive...
There are two restrictions on the type of grammars that can be used with a recursive descent parser. The first is that the grammar cannot have any left recursive productions. Give an example of a left recursive production and explain why such productions would be a problem. The second restriction is that the grammar must not require more than one token look ahead. Give an example of a production that does not have this property. Explain why this restriction is...
1. regular expressions as a mechanism to specify tokens, 2. defining context-free grammars for language constructs,...
1. regular expressions as a mechanism to specify tokens, 2. defining context-free grammars for language constructs, and 3. derivation of language terms and expressions based on a context-free grammar. 1 Regex 1. Define the regex for the following description of tokens: (a) Any string that starts with character t (b) Any string of at least length 3 that starts with t and ends with u (c) Any string that specifies the range of numbers between 11 and 23. (d) Any...
Python uses indention in its program structures. How do you define the syntax of a language...
Python uses indention in its program structures. How do you define the syntax of a language construct that uses indention? Give an example to describe.
Plot the functions x, x2, exp(-x), exp(-x2) on four different graphs (two rows and two columns)...
Plot the functions x, x2, exp(-x), exp(-x2) on four different graphs (two rows and two columns) between 0 and 5 in python
Language is an important adaptation that occurred during human evolution. Here, please discuss language origins, the...
Language is an important adaptation that occurred during human evolution. Here, please discuss language origins, the physiological and cognitive requirements for it, when, how, why it evolved, and what evidence scientists use to argue these positions.
Two sets are separated if the intersection of the closure of one of the sets with...
Two sets are separated if the intersection of the closure of one of the sets with the other is empty. a) Prove that two closed and disjoint sets of some metric space are separate. b) Prove that two open and disjoint sets of some metric space are separate.
AT&T x64/GNU Assembly syntax only please Write an assembly language program which either hardcodes or reads...
AT&T x64/GNU Assembly syntax only please Write an assembly language program which either hardcodes or reads in the lengths of the sides of a triangle, and outputs a truthy value (1, “true”, “yes”, and others) indicating whether the triangle is a valid one or not (0, “false”, “no”, etc). A triangle is valid if the sum of each pair of sides is greater than the unpaired side. Meaning if a, b, c are the three sides of a triangle, then...
Listed here are the total costs associated with the production of 1,000 drum sets manufactured by TrueBeat. The drum sets sell for $456 each.
Problem 01-1A Cost computation, classification, and analysis LO C2, C3Listed here are the total costs associated with the production of 1,000 drum sets manufactured by TrueBeat. The drum sets sell for $456 each.  Costs1.Plastic for casing—$19,0002.Wages of assembly workers—$89,0003.Property taxes on factory—$7,0004.Accounting staff salaries—$30,0005.Drum stands (1,000 stands purchased)—$31,0006.Rent cost of equipment for sales staff—$24,0007.Upper management salaries—$155,0008.Annual flat fee for factory maintenance service—$13,0009.Sales commissions—$20 per unit10.Machinery depreciation, straight-line—$38,000Problem 01-1A Part 1Required:1. Classify each cost and its amount as (a) either variable or...
Listed here are the total costs associated with the production of 1,000 drum sets manufactured by...
Listed here are the total costs associated with the production of 1,000 drum sets manufactured by TrueBeat. The drum sets sell for $508 each.    Costs 1. Plastic for casing—$20,000 2. Wages of assembly workers—$88,000 3. Property taxes on factory—$7,000 4. Accounting staff salaries—$37,000 5. Drum stands (1,000 stands purchased)—$41,000 6. Rent cost of equipment for sales staff—$12,000 7. Upper management salaries—$180,000 8. Annual flat fee for factory maintenance service—$18,000 9. Sales commissions—$26 per unit 10. Machinery depreciation, straight-line—$37,000 Required:...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT