dnWick
dnWick

Reputation: 393

Converting BNF form to CNF form

I have implemented the cyk algorithm to check a string, whether its in the grammar given in CNF form using java. So if i consider following is the grammar,

S->AB|BC
A->BA|a
B->CC|b
C->AB|a

then i can validate a string like abba. But now i have a grammar as follows, in BNF form

<query> ::= <definestream>|<executionquery>

<definestream>::= define stream <streamname><attributename><type> {<attributename><type>}

<executionquery>::=<input> <output> [<projection>]

<input> ::= from <streams>

<output> ::= ((insert [<outputtype>]into <streamname>)| (return [<outputtype>]))

<streams> ::= <stream>[#<window>]| <stream>#<window> [unidirectional]<join> [unidirectional] <stream>#<window>
on <condition>within <time>| [every] <stream> ><stream> … <stream>within <time>
| <stream>, <stream>, <stream>within <time>

<stream> ::= <streamname><conditionlist>

<projection> ::= (<externalcall><attributelist>)|<attributelist>
[group by <attributename>][having <condition>]

<externalcall>::= call <name> ( <paramlist>)

<conditionlist>::= {‘[’<condition>’]’}

<attributelist>::=(<attributename>[as <referencename>])| ( <function>(<paramlist>)as   <referencename>)

<outputtype>::= expiredevents| currentevents| allevents

<paramlist>::= {<expression>}

<condition> ::= ( <condition> (and|or) <condition> )|(not <condition>)
|( <expression> (==|!=|>=|<=|>|<|contains) <expression> )

<expression> ::= ( <expression> (+||/|*|%)<expression> )|<attributename>|<
int>|<long>|<double>|<float>|<string>

And i need to convert this to CNF form. And i have searched and found out that following should be done to convert any CFG to cnf form. 1.remove null values and then remove unit productions. But the examples they have shown is done for following kind of grammar,

S→ASA|aB        
A→B|S            
B→b|ε

but in BNF form there are lot of other syntax which i have no idea how to convert it. And its hard to identify the terminals of the above BNF grammar as well. Can any one please explain the procedure, so i can get on with this. Thanks in advance

Upvotes: 1

Views: 1633

Answers (0)

Related Questions