BNF & EBNF

This presentation includes all the details regarding the Backus Naur Form and the Extended Backus Naur Form.For more information visit : https://www.youtube.com/watch?v=hl2NLbIaU7U&t=255s

1. BNF EBNF

2. What is BNF ? Why need BNF ? What does BNF look like ? Examples of BNF Parse trees Examples of parse trees Origin of EBNF Examples

3. What is BNF? BNF = Backus-Naur Form It is a formal, mathematical way to specify context-free grammars BNF is Meta language (Meta language - a language that describes a language, which can describe a programming language). It is precise and unambiguous

4. Why need BNF? Before BNF, people specified programming languages ambiguously, i.e., with English “He fed her cat food .” Can have different meanings, He fed a woman’s cat some food. He fed a woman some food that was intended for cats. He somehow encouraged some cat food to eat something.

5. Peter Naur John Backus

6. What does BNF look like? BNF grammar consists of 4 parts , The set of tokens The set of non terminal symbols The start symbol The set of productions LHS = RHS Non-terminals = Terminals/non-terminals

7. “or” “ is defined as” Assign -> id := expr id -> A|B|C expr -> id+ expr | id * expr |(expr)|id Terminal Nonterminal What does BNF look like?

8. Example 1 A := B*(A+C ) Solution --> Assign -> id := expr A := expr A := id*expr A := B*(expr) A := B*(id + expr) A := B*(A + expr) A := B*(A + id) A := B*(A + C)

9. Example 2 A := (B * A) + C Solution --> Assign -> id := expr A := ( expr) A := ( id*expr) A := ( B*expr) A := ( B*(expr)) This cannot be derived.

10. Example 3 A:=A+B*C Solution --> Assign -> id := expr A :=id+expr A :=A+expr A :=A+id*expr A :=A+B*expr A :=A+B*id A :=A+B*C

11. Parse Trees A Parse tree is a hierarchical representation of a derivation.

12. A grammar is ambiguous if it generates a sentential form that has two or more distinct parse trees .

13. Example 1 A := B*(A+C) <assign> id := <expr> A id * <expr> B ( expr ) id + expr A id C

14. Example 3 A:= A+B*C <assign> Id := <expr> A id + <expr> A id * <expr> B id C

15. <assign> Id := < expr > A <expr> + <expr> id < expr > * < expr > A id id B C

16. Origin of EBNF Stands for “Extended Backus-Naur Form”. Increase readability and write ability.

17. Optional [ ] < if_cond > if <logic> then <stmt> Repetition { } < stmts > <stmt> { ; <stmt> } * 0 or more + 1 or more eg :- digit { digit } digit can be 1 or more Group ( ) value + integer | - integer value ( + | - )integer +

18. Syntax Graphs <stmt> < var > = <expr> var = expr < var > A | B | C A B C < var > <stmt>

19. < stmt> <stmt> | ; <stmt > < var > a | ab <stmt> ; a b

20. Example 1 < expr > <term> + <term> | <term> - <term> Example 2 <program> begin < stmt_list > end <term> <term> - + < expr > begin end < stmt_list >

21. Example 3 <stmt> < var > = <expression> < var > = <expression> <stmt>