1

我已经实现了 cyk 算法来检查一个字符串，它是否在使用 java 以 CNF 形式给出的语法中。所以如果我考虑以下是语法，

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

然后我可以验证像 abba 这样的字符串。但现在我有一个语法如下，采用 BNF 形式

<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>::= {‘[’&lt;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>

我需要将其转换为 CNF 形式。而且我已经搜索并发现应该执行以下操作以将任何 CFG 转换为 cnf 形式。1.删​​除空值，然后删除单位产品。但是他们展示的示例是针对以下语法的，

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

但是在 BNF 形式中有很多其他的语法，我不知道如何转换它。并且也很难识别上述 BNF 语法的终端。谁能解释一下程序，这样我就可以继续了。提前致谢

4

0 回答 0