regex - 在flex和bison中解析函数作为参数的函数

Question

我一直在网上查看 flex 和 bison 教程，试图通过它们都使用非常简单的示例来解决我的问题，而我的则更复杂。我需要解析一个可能包含如下输入的文件：

f(x,g(x))

这些函数也可以有任意数量的参数。

问题是我需要 f 和 g 都被解析器视为函数，而不是 f 作为函数，g 作为 x 的参数。换句话说，我需要如下所示的输出：

[f,x,[g,x]]

不喜欢：

[f, x, g(x)]

有人可以告诉我如何最好地做到这一点并可能提供正则表达式（因为我对他们不太擅长）？

Answer 1

在词法 (flex) 级别，您将识别四个标记作为标识符：f、x、g 和 x。在语法 (bison) 级别，您会将 g(x) 和 f(x, g(x)) 识别为表达式。非常示意性：

expression -> numeric-literal | 
              identifier |
              identifier left-parenthesis arguments right-parenthesis

arguments -> argument | 
             argument comma arguments

argument -> expression

这个小例子将让您了解识别标记和解析之间的区别。

您还可以将参数解析为：

arguments -> argument | 
             arguments comma argument

两者之间存在一些细微的差异，这可能与您的问题相关，也可能不相关。

在词法级别识别标识符的正则表达式是任何你喜欢的。也许

[a-zA-Z][a-zA-Z0-9]*

换句话说，一个字母后跟可选的数字和字母。

一本好书是 John Levine 的lex & yacc。我没有使用过他的flex & bison，但我会根据早期书籍的优势推荐它。

Answer 2

如果它很简单，可能是递归正则表达式（这是在 Perl 中）。我敢肯定，使用彻底完成它的语言解析器可以更好地处理它。

$str = 'some stuff  F( g(x), tx, , 44, Y(hh()) , 99, b())';

$open      = '\b\w+\s*';

$regex = qr~
  (                                                 # 1
     ($open)                                        # 2
     [(]
        (                                           # 3                       
           (?:  (?> (?: (?!$open[(] | [)] ) . )+ ) 
              | (?1)                                         
           )*                                               
        )                                                   
     [)]
   )                                                 
~xs;

print "Before:  ", $str, "\n";
print "After:   ", parse_func ( $str ), "\n";

###
sub parse_func {
  my ($core) = @_;
  $core =~ s/$regex/ "[$2," . (parse_func( $3 )) . "]" /eg;
  return $core;
}

输出

Before:  some stuff  F( g(x), tx, , 44, Y(hh()) , 99, b())
After:   some stuff  [F, [g,x], tx, , 44, [Y,[hh,]] , 99, [b,]]