1-Give a BNF grammar (do not use EBNF) for the language that generates the set o

Question

1-Give a BNF grammar (do not use EBNF) for the language that generates the set of all strings consisting of the keyword begin, followed by zero or more statements with a semicolon after each one, followed by the keyword end. Use the non-terminal for statements, and do not give productions for it.

2-Give a BNF grammar (do not use EBNF) for the language that generates the set of all strings consisting of the keyword begin, followed by one or more statements with a semicolon after each one, followed by the keyword end. Use the non-terminal for statements, and do not give productions for it.

3-Give a BNF grammar (do not use EBNF) for the set of all strings consisting of zero or more as, with a comma between each a and the next. (There should be no comma before the first or after the last.)

4-Give a BNF grammar (do not use EBNF) for the set of all strings consisting of an open bracket (the symbol [) followed by a list of zero or more digits separated by commas, followed by a closing bracket (the symbol ]).

Explanation / Answer

1)
A sentence is a noun
phrase, a verb, and a
noun phrase.   
<S> ::= <NP> <V> <NP>
A noun phrase is an
article and a noun.   
<NP> ::= <A> <N>    
A verb is            
<V> ::= eats | loves | hates
An article is
<A> ::= a | the
A noun is   
<N> ::= dog | cat | rat
grammar consists of four parts:
-the set of terminals is the atomic
symbols that make up the language
- the set of productions: tree-building rules that define
possible children for each nonterminal
- the start symbol: the nonterminal that forms the root
of any parse tree for the grammar.
-Such grammars are sometimes called
context-free grammars is left-hand
side of each production is one nonterminal
-We can use any production for a given
nonterminal to decide what children to give
it, without looking at the rest of the tree.
-If you take CS you will see one way of
expressing CFG’s
S aSb | X
X cX | .

2)
-Give a BNF grammar for the set of all strings consisting of the keyword begin,
followed by one or more statements with a semicolon after each one, followed by the
keyword end. Use the non-terminal <statement> for statements, and do not give
productions for <statement>.
-Using your grammar in #1, the syntax tree for the string
begin <statement> ; <statement> ; <statement> ; end.
Backus-Naur form (BNF) is a formal notation for encoding grammars intended many programming languages, protocols or formats have a BNF description in their specification.
Every rule in Backus-Naur form has the following structure:
name ::= expansion
The symbol ::= means "may expand into" and "may be replaced with."
In some texts, a name is also called a non-terminal symbol.

Example:
<expr> ::= <term> "+" <expr>
| <term>

<term> ::= <factor> "*" <term>
| <factor>

<factor> ::= "(" <expr> ")"
| <const>

<const> ::= integer.
3)
-The set of all strings consisting of zero or moreas.
-The set of all strings consisting of an uppercase letter followed by zero ormore additional characters, each of which is either an uppercase letter or oneof the digits0through9.
-The set of all strings consisting of one or more.
-The set of all strings consisting of one or more digits.
-The set of all strings consisting of zero or moreas with a semicolon aftereach one.
-The set of all strings consisting of the keywordbegin, followed by zero ormore statements with a semicolon after each one, followed by the keywordend. Use the non-terminal<statement>for statements, and do not giveproductions for it.
4)
-The set of all strings consisting of one or moreas with a semicolon after eachone.
-The set of all strings consisting of the keywordbegin, followed by one ormore statements with a semicolon after each one, followed by the keywordend. Use the non-terminal<statement>for statements, and do not giveproductions for it.
-The set of all strings consisting of one or moreas, with a comma betweeneachaand the next.
-The set of all strings consisting of an open bracket followedby a list of one or more digits separated by commas, followed by a closingbracket.
-The set of all strings consisting of zero or moreas, with a comma betweeneachaand the next.
-The set of all strings consisting of an open bracket followedby a list of zero or more digits separated by commas, followed by a closing bracket.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.