Welcome to the World of Computer Grammar!
Have you ever wondered how a computer knows that a line of code like "print('Hello')" is correct, but "print Hello'" is a mistake? Just like English has grammar rules, programming languages have syntax rules. In this chapter, we will learn about two ways to describe these rules: Syntax Diagrams (the visual way) and Backus-Naur Form or BNF (the text way).
Don't worry if this seems tricky at first! Think of these as "recipes" for a language. Once you learn the secret symbols, you'll be able to read and write these rules like a pro.
Prerequisite Concept: Syntax simply means the "rules of the game" for how words and symbols must be arranged in a specific language.
1. Syntax Diagrams
A syntax diagram is a visual way to show the rules of a programming language. It is like a map or a flowchart. You follow the arrows from left to right to see what is allowed.
How to Read the Map
There are two main shapes you need to know:
1. Circles or Ovals: These contain Terminals. These are "the end of the road." They are the actual characters or words that appear in the code (like a semicolon ; or the word IF).
2. Rectangles: These contain Non-Terminals. These are "placeholders" for other rules. If you see a rectangle labeled "Digit," it means you need to go look at the "Digit" rule to see what goes there.
Analogy: Imagine a map for building a sandwich.
- A circle might say "Tomato" (you just put a tomato there).
- A rectangle might say "Bread" (you have to decide which type of bread based on a different rule).
Paths and Choices
- Straight lines: You must follow this order.
- Branches: If the line splits, you can choose which path to take. This represents an OR choice.
- Loops: If a line goes backward above a shape, it means you can repeat that section as many times as you want.
Quick Review:
- Oval/Circle: Actual value (Terminal).
- Rectangle: Another rule (Non-terminal).
- Arrows: The direction you must travel.
2. Backus-Naur Form (BNF)
If syntax diagrams are the "picture," BNF is the "textbook description." It uses specific symbols to define the rules of a language. This is the version you will likely use most in your exam.
The Key Symbols
To understand BNF, you only need to memorize four special symbols:
1. \( ::= \) : This means "is defined as" or "is made of."
2. \( | \) : This means "OR." Use this when there is a choice.
3. \( < > \) : These brackets go around Non-terminals (the names of rules).
4. Plain Text: Anything not in brackets is a Terminal (the actual value).
A Simple Example
Let's define a Digit and a Binary Digit in BNF:
\(
\(
This tells the computer: "A binary digit is defined as either a 0 OR a 1."
Memory Aid: The symbol \( ::= \) looks like a set of eyes and a mouth. It’s "telling" you what the rule is!
Key Takeaway: BNF is a set of text rules where we break down complex items (like a whole program) into smaller items (like statements), and then into the smallest items (like letters and numbers).
3. Terminals vs. Non-Terminals
This is a common area of confusion, so let's clear it up!
Non-Terminals \( (<...>) \):
These are the "labels." They are not the final result. They are like the word "Fruit" in a grocery list. "Fruit" isn't a specific thing you eat; it’s a category that contains apples, bananas, etc.
Terminals:
These are the "final products." They are the actual characters. For example, "A," "5," or "+." Once you reach a terminal, the rule is finished.
Common Mistake to Avoid: Don't forget the \( < > \) brackets around your non-terminals! Without them, the computer thinks you are talking about an actual word in the code instead of a rule name.
4. Recursion: The "Infinite" Rule
How do we define something that can be any length, like an Integer (which could be 5, 50, or 500)? We use Recursion. This is when a rule refers to itself.
The Integer Rule
Look at this BNF rule:
\(
Step-by-step Explanation:
1. An integer can be just a single \(
2. OR it can be a \(
3. Because \(
Did you know? This is how computer scientists define "lists" of any size without having to write a million separate rules.
Quick Review Box:
- Single item: \(
- List of items (Recursion): \(
5. Converting Between Diagrams and BNF
You may be asked to turn a diagram into BNF or vice versa. Follow these simple "translation" tips:
If you see a branch in a diagram... use the \( | \) symbol in BNF.
If you see a rectangle... use \( <...>) \) brackets in BNF.
If you see a loop going backward... use Recursion in your BNF rule.
Key Takeaway Summary:
Syntax diagrams and BNF both do the same job: they define the syntax (grammar) of a language. Diagrams are visual maps using circles (terminals) and rectangles (non-terminals). BNF is a text-based system using \( ::= \) (is defined as), \( | \) (OR), and brackets for rules. Recursion is the secret tool we use to allow things to repeat or have any length.
Final Encouragement: Practice drawing these! Start by trying to write the BNF for your own name or a simple phone number. You've got this!