如何测试语法是否正常（使用库或框架）？

Question

如何方便地测试形式语法是否为regular？

基本上，我寻找现有库或框架，其提供这样的功能。

阿库应该从一些相对通用的语言，例如可调用C/C++/Python的/哈斯克尔。为此提供命令行工具的框架也可以。

软件应该是开源的，并支持某种形式的BNF语法输入。

Answer 1

这里是一个Python代码，返回，如果一个语法规则（工作了右和左正规文法）：

#!/usr/local/bin/python2.7 

termials = ['a'] 
nonterminals = ['S'] 
grammar = [('S',['a', 'S']), ('S',['a']) ]; 
regular = True 
leftRG = False 
rightRG = False 
for leftSide, rightSide in grammar: 
    for nonterminal in nonterminals: 
    if not(leftRG or rightRG): 
     if len(rightSide) > 1: 
     if (nonterminal in rightSide[0]): 
      leftRG = True 
     elif (nonterminal in rightSide[-1]): 
      rightRG = True 
     else: 
      regular = regular and not (nonterminal in rightSide) 
    if rightRG: 
     regular = regular and not (nonterminal in rightSide[:-1]) 
    if leftRG: 
     regular = regular and not (nonterminal in rightSide[1:]) 
print regular 

注意：请记住，如果一个非正规文法识别正规语言，这个例程将返回False，因为不可能在多项式时间内决定规则性。