时间戳

首页 > 解决方案 > Flex 和 Bison - 有时关心空格的语法

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

问题描述

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

但是，在某些情况下，空格字母会产生很大的不同：

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

所以目前所有的空格都被词法分析器忽略了：

{WHITESPACE} { ; }

该语言例如说：

UnaryExpression:
    PostfixExpression
  | T_PLUS UnaryExpression
  | T_MINUS UnaryExpression
  ;

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

// 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
  ;

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

先感谢您！

标签： parsinggrammarbisonflex-lexerlex

解决方案

如果没有您尝试解析的语法的完整规范，很难给出准确的答案。在下文中，我假设这是仅有的两个标记之间存在（或不存在）空格会影响解析的两个地方。

区分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); }

另一种可能的解决方案是让词法分析器区分跟随空格并直接跟随数字的符号字符，然后让解析器尝试确定符号是否应该与以下数字组合。然而，这仍然取决于能够区分局部变量和其他标识符，这仍然需要通过符号表进行词法反馈。

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

推荐阅读