Page 203 - DCAP507_SYSTEM_SOFTWARE

Nisha Sethi, Lovely Professional University Unit 13: Formal Systems

Unit 13: Formal Systems Notes

CONTENTS

Objectives
Introduction
13.1 Hierarchy of Languages
13.1.1 Issues in parsing context-free Grammars
13.2 Backus Naur Form – Backus Normal Form (BNF)

13.2.1 The Purpose and Function of the Notation
13.2.2 The Fundamental Idea
13.2.3 Extensions

13.2.4 Data Type Definitions for Extensions
13.2.5 The Name of the Notation
13.3 Summary
13.4 Keywords
13.5 Review Questions

13.6 Further Readings

Objectives

After studying this unit, you will be able to:

 Understand hierarchy of languages
 Discuss Backus Naur Form or Backus Normal Form
Introduction

We possess a lot of our perceptive of grammars to the work of the American linguist Noam
Chomsky. We will discuss in this unit different types of grammars and their issues. Also you
will understand the concept of Backus Naur Form (BNF) which was originally called as Backus
Normal Form (BNF).

13.1 Hierarchy of Languages

We possess a lot of our perceptive of grammars to the work of the American linguist Noam
Chomsky. We will discuss in this unit different types of grammars and their issues. Also you
will understand the concept of Backus Naur Form (BNF) which was originally called as Backus
Normal Form (BNF).

Type 0 (free or unobstructed grammars)

These are the most familiar. Productions are of the appearance u -> v where both u and v are
random strings of symbols in V, with u non-null.

LOVELY PROFESSIONAL UNIVERSITY 197