Create a phrase-structure grammar using the example in Section 12.2 as a guide. Your grammar should specify each of the following separately in your solution (be sure to label the so that theyre easy to read): at least 3 non-terminals, 5 terminals, a start, and a set of rules. You can use any topic domain you wish. From your grammar, create a sentence that satisfies your grammar and a similar sentence that does not. Then, create a syntax tree of your correct grammar following the example from Section 12.3.

section 12.2 and 12.3 are below

12.2 Phrase Structure Grammars

Phrase Structure Grammar

In this section, we'll show how a phrase structure grammar can be used to define a language. This is how programmers create any programming language and compiler. Have you ever thought about how a compiler knows what a keyword like integer is vs a variable name like myAge? Engineers and programmers have to be very detailed when defining what can and can't be done and have to list out all syntax and what constitutes a semantic error. This is where grammar rules come into play. Knowing you need a value assigned if a function has a return type or that you can't put a string into a numeric variable all has to be defined in the grammar.

Before we begin, we need a way to distinguish between when we're talking about a collection of sentences from the words in the sentence. This may not seem like such a big deal, but consider the self-referential sentence,

"This sentence is too short!"

Clearly, the use of "sentence" in this example is not referring to the collection of all sentences. It's also pretty obvious that it also not, itself, the collection of all sentences, but simply a word in the sentence. Thus, how can we distinguish between the term sentence that refers to a collection of sentences and the term sentence, which is just one of our many words?

In the 1960s, the following convention was introduced: when the term sentence refers to the collection of sentences we will use . When the term sentence is just one of our many words we do not use the brackets. For reasons that will become apparent later, we define the set of all terms of the form <...> as nonterminals and an individual member of this set, such as as a single nonterminal. Terms representing the words in our language, such as "sentence", are refered to as terminals. Hence, is a nonterminal and "sentence" (without the quote marks) is a terminal.

Nonterminals may be replaced by other nonterminal or terminals according to a set of rules, refered to as productions, that use the symbol '::=' to mean can be replaced by. Furthermore, the symbol '|' means "or" when used within a rule. For example, here are three rules that use this notation

::= ::= Joe | Sally ::= Runs | Dances

Hence, the first rule states that the nonterminal may be replaced with the two nonterminals and , in precisely this order. Likewise, the nonterminal may be replaced by either the terminal "Joe" or the terminal "Sally". At this point, let's drop the use of "nonterminal" and "terminal" every time we use one since the context should make it clear. Thus, the third rule states that can be replaced by either "Runs" or "Dances". We'll give an example below, but first, we're now in a position to define what we mean by a grammar.

Informally, a phrase-structure grammar consists of:

a set of nonterminal symbols,

a set of terminal symbols,

a special nonterminal start symbol, which is typically or simply , and

a set of replacement rules, refered to as productions, that use the nonterminal and terminal symbols.

For convenience, the Greek letter Gamma '' is often used to represent a grammar, so you might as well get use to it now.

Hence the grammar in our previous example can be specified as,

: nonterminals = {, , } terminals = {Joe, Sally, Runs, Dances} start = rules = { ::= ::= Joe | Sally ::= runs | dances }

A given grammar instance defines a language and the grammar can be used to either produce the syntactically valid sentences in the language or to recognize these sentences. For example, our previous grammar example allows the following sentences:

Joe runs (hey, hey, hey, do not put a period after "runs" since there is no period in this grammar.

Joe dances

Sally runs

Sally dances

And thats all there is to it! The rest is simply "icing" on the cake.

There are a number of different notations in which phrase structure grammars are written. You shouldn't have any difficulty transferring between them. Here's are the productons from our previous grammar using a different notation:

Joe Sally runs dances

Noam Chomsky (1959) introduced phrase structure grammars and John Backus (1959) introduced "::=" notation. You'll study Chomsky and Backus' contributions to Computer Science in more depth in your Computation Theory (CS 375) and Principles of Programming Language (CS 390) courses.

12.3 Syntax Trees

Example

We can also express the results of a grammar using a syntax tree. For example, consider the following grammar,

::= ::=

::= ::= on

::= the | a ::= black | soft ::= cat | chair ::= lay ::= silently

Note, by listing only the production in the grammar, we can easily determine the terminals, nonterminals, and starting symbol.

The previous grammar can produce the sentence,

The black cat lay silently on a soft chair

which can be represented by the following syntax (parse) tree:

This grammar can also be used to produce the syntactically correct sentence,

The black chair lay silently on a soft cat

which is probably not semantically correct.

We should point out that since the 1960s we have made amazing progress on syntax analysis and very slow progress on semantics.

But look at what the human mind can do. Assuming you have some familiarity with childrens fairy tales, here is a syntactically butchered sentence and yet, you will probably get the semantics correct.

When Rindercella arrived at the brancy fall, who did she first run into? ... her two sisty uglers ... you remember them, the sad blisters! But Rindercella was such a bavishing rueaty that the two sisty uglers didnt even CinderizeRecognella.

If you want to jump into the research frenzy associated with Computational Science, find a way to get a computer to do what you just did with the above!

In addition to producing the sentences of a language, a grammar can also be used to recognize the sentences of a language by parsing it into a syntax tree,