Question

For an example BNF grammar, be able to identify the tokens which a lexical analyzer would be able to produce.

For an example BNF grammar, and a list of tokens, construct a state diagram of the language’s lexical analyzer.

Answer 1

solution:

given data:

For an example BNF grammar:

Context free grammar(CFG) is a set of rules G(N,T,P,S) . It can be used to generate patterns of strings.

G(N,T,P,S)

Where N is set of non terminal symbol

T is set of terminal symbol

P is set of production rules

S is non terminal start symbo

BNF(Backus Naur Form)grammar is a variation of context free grammer.

Syntax

Left hand side ::= Riht hand side

where

::= ->  is defined as

Left hand side -> Non terminal symbol

Riht hand side is a sequence of terminal and nonterminal symbols.

Non terminal symbols are enclosed in angular brackets <>

Example

Consider a BNF grammar for binary numbers with a leading1

<Start> :: 1<BinNum> //First rule nonterminal BinNum with a leading1

<BinNum>= <BinValue>|<BinValue><BinNum> //With 2 alternative and second alternative //is recursive

<BinValue>=0|1 //Terminal symbols 0,1

Valid inputs are

10

11001

1000011

Invalid inputs are

1

0011

011

Consider the above grammar which accepts a string of 0 and 1 starting with 1. A state diagrom is a directed graph with each state is represented by a node with a start state and incoming arrow with no source. Final state is represented by double lined node.

please give me thumb up