BNF Flashcards
(25 cards)
What is a context-free language?
A set of strings and symbols that follow the rules of a context-free grammar. Context-free grammars describe which strings are and are not possible in a language by laying out production rules.
What is a production rule?
A simple rule that specifies how one character can be replaced by another.
For example: a → ab (the character ‘a’ can be replaced by ‘ab’).
What is Backus-Naur Form (BNF)?
A formal notation used to describe the syntax rules of a language. It’s a meta-language that uses statements in which the left-hand side is defined by the right-hand side.
What is a non-terminal in BNF?
Text placed inside angle brackets (e.g., <FullName>) that represents a syntactic variable which can be broken down further into more non-terminals, terminals, or a combination of both.</FullName>
What is a terminal in BNF?
Text without any brackets that represents a symbol that cannot be broken down any further and must be taken to be the written value.
For example, the letter ‘a’ is a terminal which means the character ‘a’.
What does the pipe symbol (|) represent in BNF?
The OR operator.
For example, <digit> ::= 0|1|2|3|4|5|6|7|8|9 means a digit is defined as either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.</digit>
What does the ::= symbol mean in BNF?
Is defined as. It separates the left-hand side (what is being defined) from the right-hand side (the definition).
What is recursion in BNF?
When a non-terminal is defined in terms of itself. This allows for more complex definitions and enables BNF to represent languages that cannot be represented by regular expressions.
Why is BNF more powerful than regular expressions?
BNF can represent context-free languages that regular expressions cannot support because BNF can handle recursion, which regular expressions cannot.
Give an example of a simple BNF definition for an integer.
<Integer> ::= <Digit>|<Digit><Integer>
<Digit> ::= 0|1|2|3|4|5|6|7|8|9
</Digit></Integer></Digit></Digit></Integer>
Why can’t regular expressions represent the language {a^n b^n | n ≥ 0}?
Regular expressions cannot count and match equal numbers of different symbols, but BNF can represent this through recursion.
This language requires remembering how many ‘a’s appeared to ensure the same number of ‘b’s follow.
What are syntax diagrams?
Visual representations of a regular language, equivalent to BNF. They use rectangles to represent non-terminals, ellipses to represent terminals, and arrows to indicate how strings can be formed.
What is parsing?
The process of checking an input string against a set of BNF rules to see if it is valid. Compilers and interpreters validate input by building a parse tree according to the BNF rules.
What is a parse tree?
A tree structure that shows how an input string can be derived from the grammar rules. Each node represents a grammar rule application, with terminals at the leaf nodes.
Why are context-free languages and BNF important in computing?
They are used to define programming language syntax precisely, allowing compilers to validate code and ensuring that instructions for computers are not ambiguous in any way.
What is the difference between a terminal and a non-terminal symbol?
A terminal symbol cannot be broken down further and represents a specific character or token. A non-terminal symbol can be broken down further and is represented inside angle brackets in BNF.
Give an example of a recursive BNF rule and explain its purpose.
<value> ::= <digit> | <value><digit>
This rule defines a value as either a single digit or a value followed by a digit.
## Footnote
The recursion allows values of any length to be represented concisely.
</digit></value></digit></value>
How would you represent a positive integer in BNF?
<positive_integer> ::= <non_zero_digit> | <non_zero_digit><digits>
<digits> ::= <digit> | <digit><digits>
<digit> ::= 0|1|2|3|4|5|6|7|8|9
<non_zero_digit> ::= 1|2|3|4|5|6|7|8|9
</non_zero_digit></digit></digits></digit></digit></digits></digits></non_zero_digit></non_zero_digit></positive_integer>
What are the advantages of using BNF for language definition?
- It provides a precise, unambiguous representation of language syntax
- It can represent complex languages including recursive structures
- It allows for concise definitions of potentially infinite sets of strings
- It is used by compiler writers to represent programming language syntax
How would you create a BNF definition for a simple variable name that must start with a letter and can contain letters, digits, and underscores?
<variable> ::= <letter> | <letter><rest>
<rest> ::= <char> | <char><rest>
<char> ::= <letter> | <digit> | _
<letter> ::= a|b|c|...|z|A|B|C|...|Z
<digit> ::= 0|1|2|3|4|5|6|7|8|9
</digit></letter></digit></letter></char></rest></char></char></rest></rest></letter></letter></variable>
What is the key feature of context-free languages that makes them more expressive than regular languages?
The ability to use recursion in their definitions, which allows them to represent nested structures and matching patterns that regular expressions cannot handle.
Explain why BNF is considered a meta-language.
BNF is a language used to describe other languages. It provides a formal notation for expressing the grammar rules of a language rather than being a language for direct communication.
What symbols are used in syntax diagrams to represent terminals and non-terminals?
Ellipses or circles represent terminal symbols, and rectangles represent non-terminal symbols.
How would you represent the language of balanced parentheses using BNF?
<balanced> ::= ε | ( <balanced> ) | <balanced><balanced>
Where ε represents an empty string.
</balanced></balanced></balanced></balanced>
