Question 1 @ 2025-01-21 18:44
The purpose of a BNF (Backus-Naur Form) is to specify:
- Algorithms
- Languages
- Language grammars
- Language implementations
- Compiler implementations
- Parser implementations
Question 2 @ 2025-01-21 18:48
Does it make sense to talk about a BNF for BNFs?
(Reminder: choose the best answer.)
-
That would not make any sense, since it means that we implement a language in itself, and a BNF is not a programming language.
-
No: a logical system cannot define itself, and a BNF for BNFs is logically impossible in a similar way.
-
Yes: BNFs can specify any language, even natural ones.
-
Yes, since a BNF is a formal language, it can be specified by a BNF.
-
Yes: in fact, we’ve seen that we can implement a simple parser already.
-
Yes, but the result will be highly inefficient.
Question 3 @ 2025-01-21 18:51
Which of the following BNF grammars are ambiguous?
-
<AE> = <num> | <AE> + <AE> | <AE> * <AE>
-
<AE> = <num> | ( <AE> + <AE> ) | ( <AE> * <AE> )
-
<AE> = <MUL> + <MUL>
<MUL> = <num> | <num> * <MUL> -
<AE> = <num> | <ADD> | <MUL>
<ADD> = <AE> + <AE>
<MUL> = <AE> * <AE>
Question 4 @ 2025-01-21 18:54
As you work on a BNF for a simple language, your friend looks over your shoulder and sees the grammar that you wrote:
<PROD> ::= ... <ATOM> ...
<ATOM> ::= <num>
| ( <AE> )
| [ <AE> ]
| { <AE> }
“Why not abstract the parens to make it shorter?” — suggesting this change:
| <OPEN> <AE> <CLOSE>
<OPEN> ::= ( | [ | {
<CLOSE> ::= ) | ] | }
Does this specify the same language?
- Yes.
- Yes, and it even hints at a better parser implementation.
- No.
-
No: parens might not be balanced, e.g.:
(1 + 2))) -
No: paired paren shapes can be different, e.g.:
[1 + 2)
Question 5 @ 2025-01-21 18:57
Generally speaking, what did we mean by the term “compositional”?
-
Making frequent use of function composition, meaning a heavy focus on functional programming.
-
The meaning of something depends only on the meaning of its sub-parts and nothing else.
-
Sticking to a modular implementation of languages, so we can easily change various parts of the code.
-
Same as using “combinatorial”, which cannot be used since it’s often associated with discrete math.
-
Nothing special.