Slide 2.5: Context-free grammars

Slide 2.4: Context-free grammars vs regular grammars
Slide 2.6: Syntax diagrams
Home

Context-Free Grammars

Considering the syntactic specification of simple arithmetic expressions, its context-free grammar in BNF could be

   G = ( Σ, N, P, S )
     = ( {+, -, *, (, ), number}, {<exp>, <op>}, P, <exp> )

where P consists of

   <exp> ::= <exp> <op> <exp> | ( <exp> ) | number
   <op>  ::= + | – | *

The grammar is context-free because only single nonterminals occur on the left sides of the rules. The hyperlink gives the BNF of Pascal.

Extended BNF: EBNF
EBNF, such as the EBNF of Pascal, includes the following two constructs:

Repetition using { } such as

 <stmt-sequence> ::= <stmt> ; <stmt-sequence> | <stmt>
 <stmt>          ::= s
                          ⇓
 <stmt-sequence> ::= { <stmt> ; } <stmt> 
 <stmt>          ::= s

Option using [ ] such as

 <statement> ::= <if-stmt> | other
 <if-stmt>   ::= if ( <exp> ) <statement>
               | if ( <exp> ) <statement> else <statement> 
 <exp>       ::= 0 | 1 
                          ⇓ 
 <statement> ::= <if-stmt> | other 
 <if-stmt>   ::= if ( <exp> ) <statement>
                      [ else <statement> ]
 <exp>       ::= 0 | 1