Context Free Grammars: Grammar Components & Derivations and Parse Trees

Question 1

context-free frammars are written in some variation of ____ ____.

Answer 1

backus-Naur Form

Question 2

What is Backus-Naur Form

Answer 2

a metalanguage to describe the syntax of other languages especially programming languages

Question 3

The statements of BNF are called ___.

Answer 3

productions

Question 4

a context-free grammar consists of a collection of ___.

Answer 4

productions

Question 5

what is the input and output of compiler parsers?

Answer 5

input: grammar of languages defined in some variation of BNF
output: the actual parser

Question 6

Parsers verify that the … is correct.

Answer 6

syntax of a candidate program

Question 7

list the 3 kinds of symbols or tokens of BNF production

Answer 7

terminal symbols or tokens
nonterminals
punctuation symbols

Question 8

what are terminal symbols or tokens?

Answer 8

the actual lexemes, or words of the programming language

Question 9

what are nonterminal symbols?

Answer 9

intermediate symbols that typically correspond to a sequence of tokens

Question 10

T/F: Every different kind of statement in a programming language would have a nonterminal that would be used to define its syntax.

Answer 10

True

Question 11

What technique did BNF originally use to distinguish terminal from nonterminal symbols?

Answer 11

enclose nonterminals in corner brackets

Question 12

how does the UNIX parser “yacc” differentiate between terminals and non-terminals? What about for single-letter symbols?

Answer 12

terminals: all upper case
nonterminals: all lower case
same rule applies

Question 13

T/F: The technique used is unimportant as long as it is clear which symbols are terminals and which are nonterminals.

Answer 13

True

Question 14

what does the symbol “::=” mean? what can it be read ass?

Answer 14

separates the left and right-hand sides of every production.
“defines” or “can be replaced by”

Question 15

what can variations of BNF use instead of “::=”? (2)

Answer 15

right-pointing arrow

single colon

Question 16

T/F: The left side of every production must always be a single terminal symbol.

Answer 16

False, nonterminal

Question 17

T/F: The right-hand sides consists of a sequence of nonterminal symbols only

Answer 17

False, terminal and nonterminal

Question 18

T/F: productions can have multiple right-hand sides.

Answer 18

True

Question 19

What separates the various right-hand sides in a production?

Answer 19

vertical bar “|”

Question 20

How do we know when symbols are optional?

Answer 20

when they are enclosed in square brackets “[]”

Question 21

how do we know when symbols can be repeated 0 or more times?

Answer 21

when they are enclosed in curly braces “{}”

Question 22

In every grammar, one of the nonterminal symbols must be the ____ ____

Answer 22

start symbol

Question 23

T/F: It is customary to make the production defining the start symbol, the first production of the grammar.

Answer 23

True

Question 24

In order for the grammar to be well-defined, every ____ used on the right-hand side of a production must appear on the ____ ____ of some other production that defines it.

Answer 24

nonterminal

left-hand side

Question 25

example of a well-defined grammar

Answer 25

S –> {a} b T [c]

T –> d | e

Question 26

what is the rule for sentences of this language grammar?

S –> {a} b T [c]
T –> d | e

Answer 26

The sentences or strings of this language start with zero or more a’s followed by one b, then either a d or e followed by an optional c

Question 27

why does the below language allow for an infinite number of possibilities?

Answer 27

there is no limit to the number of a’s

Question 28

what makes a production recursive? give an example

Answer 28

nonterminal symbol on the left-hand side is also one of the symbols on the right-hand side

Ex: T –> T b

Question 29

what does a grammar need for a recursive production to be well-defined?

Answer 29

there must be another right-hand side that does not have the nonterminal

Question 30

List the two kinds of recursive productions that are especially important.

Answer 30

left or head recursive

right or tail recursive

Question 31

describe the “left or head recursive”

Answer 31

the nonterminal on the left is the leftmost symbol on the right-hand side

Question 32

describe the “right or tail recursive”

Answer 32

the nonterminal defined on the left is the rightmost symbol on the right-hand side.

Question 33

give an example of a regular recursive production. explain what makes it well-defined.

Answer 33

S –> a S a | b

“| b” which gives you an alternative to “a S a”

Question 34

What language does the grammar below define? (2)

S –> a S a | b

Answer 34

strings that begin with n a’s follow by one b and then n a’s again.
n represents any nonnegative integer. So there are the same number of a’s before the b as after the b.

Question 35

What makes the grammar below left recursive?

S –> S a | b

Answer 35

the nonterminal S is the left-most symbol on the right-hand side.