CS Notes

01 EBNF

Oct 11, 20243 min read

Lecture from: 18.09.2024 and 24.09.2024 | Video: Videos ETHZ

BNF (Backus-Naur Form) and EBNF (Extended BNF) is a notation for specifying the syntax of formal languages.

BNF was developed by John Backus and Peter Naur in 1963. EBNF is a extension to BNF that adds more features for defining grammars.

Syntax

EBNF Building Blocks

  1. Terminals: Unbreakable symbols that represent specific values. Examples:

    • Text: some text
    • Digits: 4, 314
    • Strings: 11:00:12 PM

  2. Non-terminals: Aliases that can contain other non-terminals, rules, and terminals.

Defining a EBNF Non-terminal

EBNF rules always have the form of: LHS <- RHS or LHS ::= RHS

The LHS (Left hand side) is always a non terminal which is denoted by <variable-name> ::= ...

The RHS (right hand side) can have other non-terminals, rules or terminals (as explained above).

Examples:

<digit_zero> ::= 0
<number_null> ::= <digit_zero>

Rules

EBNF has several rules for combining and manipulating terminals and non-terminals.

  1. Sequence (a b): Combine two or more elements in the specified order.
  2. Option ([a]): Allow an element to appear zero or one time.
  3. Enum (a | b): Choose between two or more alternatives.
  4. Repetition ({a}): Any number (incl 0) of repetitions.
  5. Recursion ( a <- a ): A non-terminal can reference itself, allowing for recursive definitions.
  6. Grouping ((a)): Group elements together for convenience or to apply rules to the group as a whole.

Convention

It’s important to note that the convention is that the very last non-terminal defined is the one with which you are validating your input string.

Legality and Derivations

A word is legal if there exists a sequence of derivation steps starting from the start rule and ending with the character sequence, where each step applies an EBNF rule to replace non-terminal symbols with their definitions

Here we are looking at two ways of performing derivation steps to validate an input.

Derivation Table

Derivation Tree

Equivalency of EBNF Descriptions

Two different EBNF grammar descriptions are equivalent when the following conditions hold:

B1 and B2 are EBNF grammar descriptions

  1. Legal for B1 if and only if legal for B2
  2. Illegal for B1 if and only if illegal for B2

Syntax vs Semantics

  • Syntax: Refers to the rules that govern the structure of language, including the order and arrangement of words, phrases, and clauses. It’s about the “how” of communication.
  • Semantics: Concerned with the meaning or interpretation of language, including the relationships between words, phrases, and concepts. It’s about the “what” being communicated.

Example

“The fluffy purple elephant quietly juggled several tartan socks while contemplating the aerodynamics of rare jellyfish.”

This sentence has a correct syntax but it’s semantics don’t make any sense.

Continue here: 02 Java (Intro)

Backlinks