Flex 和 Bison - 有时关心空格的语法

Question

目前我正在尝试实现一个与 ruby 非常相似的语法。为简单起见，词法分析器目前忽略 space 个字符。

然而，在某些情况下，space 字母会产生很大的不同：

def some_callback(arg=0)
    arg * 100
end

some_callback (1 + 1) + 1  # 300
some_callback(1 + 1) + 1   # 201
some_callback +1           # 100
some_callback+1            # 1
some_callback + 1          # 1

所以目前所有白色space都被词法分析器忽略了：

{WHITESPACE} { ; }

例如，该语言说的是：

UnaryExpression:
    PostfixExpression
  | T_PLUS UnaryExpression
  | T_MINUS UnaryExpression
  ;

我能想到的解决这个问题的一种方法是在整个语法中显式添加 whitespace，但是这样做整个语法会增加很多复杂度：

// OLD:
AdditiveExpression:
    MultiplicativeExpression
  | AdditiveExpression T_ADD MultiplicativeExpression
  | AdditiveExpression T_SUB MultiplicativeExpression
  ;

// NEW:
_:
    /* empty */
  | WHITESPACE _;

AdditiveExpression:
    MultiplicativeExpression
  | AdditiveExpression _ T_ADD _ MultiplicativeExpression
  | AdditiveExpression _ T_SUB _ MultiplicativeExpression
  ;

//...

UnaryExpression:
    PostfixExpression
  | T_PLUS UnaryExpression
  | T_MINUS UnaryExpression
  ;

所以我想问问有没有关于如何解决这个语法的最佳实践。

提前致谢！

Answer 1

如果没有您要解析的语法的完整规范，就不容易给出准确的答案。在下文中，我假设只有两个地方存在（或不存在）两个标记之间的 whitespace 会影响解析。

f(...) 和 f (...) 之间的区别出现在数量惊人的语言中。一种常见的策略是让词法分析器将紧跟在左括号后的标识符识别为 "FUNCTION_CALL" 标记。

例如，您会发现在大多数 awk 实施中；在 awk 中，函数调用和串联之间的歧义通过要求函数调用中的左括号紧跟在标识符之后来解决。类似地，C 预处理器宏定义指令区分 #define foo(A) A（带参数的宏定义）和 #define foo (A)（展开以 ( 标记开始的普通宏。

如果您使用 (f)lex 执行此操作，则可以使用 / 尾随上下文运算符：

[[:alpha:]_][[:alnum:]_]*/'('   { yylval = strdup(yytext); return FUNC_CALL; }
[[:alpha:]_][[:alnum:]_]*       { yylval = strdup(yytext); return IDENT; }

语法现在非常简单：

call: FUNC_CALL '(' expression_list ')'   /* foo(1, 2) */
    | IDENT expression_list               /* foo (1, 2) */
    | IDENT                               /* foo * 3 */

这种区别并非在所有句法上下文中都有用，因此添加一个与任一标识符形式匹配的非终结符通常会被证明是有用的：

name: IDENT | FUNC_CALL

但是你需要小心这个非终端。特别是，将其用作表达式语法的一部分可能会导致解析器冲突。但在其他情况下，它会很好：

func_defn: "def" name '(' parameters ')' block "end"

（我知道这不是 Ruby 函数定义的精确语法。它仅用于说明目的。）

更麻烦的是另一个歧义，在某些情况下，一元运算符 + 和 - 似乎应该被视为整数文字的一部分。 Ruby 解析器的行为表明词法分析器将符号字符与紧随其后的数字组合在一起，以防它可能是函数的第一个参数。（也就是说，在上下文 <identifier><whitespace><sign><digits> 中，其中 <identifier> 不是已声明的局部变量。）

当然可以使用开始条件将这种上下文规则添加到词法扫描器中，尽管它有点丑陋。一个不完全充实的实现，建立在之前的基础上：

%x SIGNED_NUMBERS
%%

[[:alpha:]_][[:alnum:]_]*/'('          { yylval.id = strdup(yytext);
                                         return FUNC_CALL; }
[[:alpha:]_][[:alnum:]_]*/[[:blank:]]  { yylval.id = strdup(yytext);
                                         if (!is_local(yylval.id))
                                             BEGIN(SIGNED_NUMBERS);
                                         return IDENT;  }
[[:alpha:]_][[:alnum:]_]*/             { yylval.id = strdup(yytext);
                                         return IDENT;  }
<SIGNED_NUMBERS>[[:blank:]]+           ;
 /* Numeric patterns, one version for each context */
<SIGNED_NUMBERS>[+-]?[[:digit:]]+      { yylval.integer = strtol(yytext, NULL, 0);
                                         BEGIN(INITIAL);
                                         return INTEGER; }
[[:digit:]]+                           { yylval.integer = strtol(yytext, NULL, 0);
                                         return INTEGER; }

 /* ... */
 /* If the next character is not a digit or a sign, rescan in INITIAL state */
<SIGNED_NUMBERS>.|\n                   { yyless(0); BEGIN(INITIAL); }

另一种可能的解决方案是让词法分析器区分 space 后面紧跟数字的符号字符，然后让解析器尝试找出是否应该组合符号用下面的数字。但是，这仍然取决于能够区分局部变量和其他标识符，这仍然需要通过符号 table.

进行词法反馈

值得注意的是，所有这些复杂化的最终结果是一种语言，其语义在某些极端情况下不是很明显。 f+3 和 f +3 产生不同结果的事实很容易导致可能很难检测到的细微错误。在许多使用具有此类歧义的语言的项目中，项目风格指南将禁止语义不明确的合法结构。如果您还没有这样做，您可能希望在您的语言设计中考虑到这一点。

Flex 和 Bison - 有时关心空格的语法

Flex and Bison - Grammar that sometimes care about spaces

parsing

grammar

bison

flex-lexer

lex