Context Free Grammars: Grammar Components & Derivations and Parse Trees Flashcards
context-free frammars are written in some variation of ____ ____.
backus-Naur Form
What is Backus-Naur Form
a metalanguage to describe the syntax of other languages especially programming languages
The statements of BNF are called ___.
productions
a context-free grammar consists of a collection of ___.
productions
what is the input and output of compiler parsers?
input: grammar of languages defined in some variation of BNF
output: the actual parser
Parsers verify that the … is correct.
syntax of a candidate program
list the 3 kinds of symbols or tokens of BNF production
terminal symbols or tokens
nonterminals
punctuation symbols
what are terminal symbols or tokens?
the actual lexemes, or words of the programming language
what are nonterminal symbols?
intermediate symbols that typically correspond to a sequence of tokens
T/F: Every different kind of statement in a programming language would have a nonterminal that would be used to define its syntax.
True
What technique did BNF originally use to distinguish terminal from nonterminal symbols?
enclose nonterminals in corner brackets
how does the UNIX parser “yacc” differentiate between terminals and non-terminals? What about for single-letter symbols?
terminals: all upper case
nonterminals: all lower case
same rule applies
T/F: The technique used is unimportant as long as it is clear which symbols are terminals and which are nonterminals.
True
what does the symbol “::=” mean? what can it be read ass?
separates the left and right-hand sides of every production.
“defines” or “can be replaced by”
what can variations of BNF use instead of “::=”? (2)
right-pointing arrow
single colon