grammar - 如何测试语法是否规则（使用库或框架）？

Question

我如何方便地测试形式语法是否规则？

基本上，我正在寻找提供此类功能的现有库或框架。

一个库应该可以从一些相对通用的语言中调用，例如 C/C++/Python/Haskell。一个为此提供命令行实用程序的框架也可以。

该软件应该是开源的，并支持某种 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，因为不可能在多项式时间内确定正则性。