Backus Naur Form Flashcards
what does the following symbol mean
<>
encloses a synctatic item
what does the following symbol mean
::=
consists of
what does the following symbol mean
|
or choice between two items
what does the following symbol mean
{}
zero or more repetitions of the content
write a BNF definition for a digit assignment
?digit? :: = 0|1|2|3|4|5|6|7|8|9
* question marks supposed to be < and >
Write a BNF definition for a simple variable assignment like this:
x = 5
<assignment> ::= <identifier> "=" <value>
<identifier> ::= "x" | "y" | "z"
<value> ::= <digit> | <digit> <value>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
</digit></value></digit></digit></value></identifier></value></identifier></assignment>
Why can BNF represent some languages that regular expressions cannot?
BNF can define context-free grammars, which can handle nested or recursive structures (like parentheses or nested conditionals). Regular expressions can’t handle recursion.
What does the following BNF define?
<letter> ::= "a" | "b" | "c" | "d"
<identifier> ::= <letter> | <letter> <identifier>
</identifier></letter></letter></identifier></letter>
<letter> is a terminal: either a, b, c, or d.
<identifier> is a recursive rule — it allows a single letter or a letter followed by another identifier.
➡ So <identifier> defines a sequence of one or more letters, using only a–d.
</identifier></identifier></letter>
Given the BNF:
<digit> ::= "0" | "1"
<number> ::= <digit> | <digit> <number>
Which of the following are valid <number>s?
A) 10
B) 01
C) 12
D) 110
</number></number></digit></digit></number></digit>
✅A) 10 → valid
✅ B) 01 → valid
❌ C) 12 → invalid (2 not allowed)
✅ D) 110 → valid
What does this syntax diagram represent?
–>──(a)──>──(b)──>──(c)──>──>
This syntax diagram represents the string “abc” — it must be made up of:
the character “a”
followed by “b”
followed by “c”
