Grammer in computer science is a set of rules that defines the structure of a language. It defines a language in a structured way and parsers are built based on it.

BNF

Backus-Naur Form, or BNF, is a notation technique used to express context-free grammars. It is used to define syntax of programming languages, datastructures, etc.

EBNF

Extended Backus-Naur Form, or EBNF, is a notation technique used to express context-free grammars. It is an extension of BNF.

  • It is more readable and compact than BNF.
  • It has some additional features like repetition, optional, etc.
  • It is used to define syntax of programming languages, datastructures, etc.
  • It is used in many places like scripting languages, command line tools, etc.

Syntax

  • {} : Zero or more
  • [] : Optional
  • | : Or
  • () : Grouping
  • ... : Range
  • ; : End of statement
  • , : Concatenation
  • = : Definition

Example

Let’s take a simple language that has only 2 types of statements: let and return.

program = { statement } ;
statement = letStatement | returnStatement ;
letStatement = "let" , identifier , "=" , expression , ";" ;
returnStatement = "return" , expression , ";" ;
expression = identifier | integerLiteral ;
identifier = letter , { letter | digit } ;
integerLiteral = digit , { digit } ;
letter = "a" ... "z" | "A" ... "Z" ;
digit = "0" ... "9" ;

The above grammar defines a simple language that has only 2 types of statements: let and return. It also defines the structure of an expression.

Explanation

  • program is a list of statement.
  • statement can be a letStatement or a returnStatement.
  • letStatement is a let followed by an identifier followed by = followed by an expression followed by ;.
  • returnStatement is a return followed by an expression followed by ;.
  • expression can be an identifier or an integerLiteral.
  • identifier is a letter followed by a sequence of letter or digit.
  • integerLiteral is a sequence of digit.
  • letter is a character from a to z or A to Z.
  • digit is a character from 0 to 9.

A programming language follows a grammar. It’s an implementation of an evaluater that parses the input into a syntax tree ( which follows the grammar ) and evaluates it. It is a great way to understand the language and write a parser for it.

So, A grammar is blueprint for parsing the language.