1

看看下面的语法，就解析器生成器而言，它有一个明显的缺陷：

"Start Symbol" = <Foo>
"Case Sensitive" = True
"Character Mapping" = 'Unicode'

{A} = {Digit}
{B} = [abcdefABCDEF]
{C} = {A} + {B}

Integer = {A}+
HexNumber = {C}+


<ContextA> ::= '[' HexNumber ']'
<ContextB> ::= '{' Integer '}'                      
<Number> ::= <ContextA> | <ContextB>
<Foo> ::= <Number> <Foo>
       | <>

这种语法有缺陷的原因是扫描仪无法区分终端[Integer;HexNumber]。（是1234整数还是十六进制数？！）。

在此示例中编写的产生式中，这与位无关，但可能存在语法，其中产生式的上下文将阐明是否需要整数或十六进制数，并且扫描仪仍会拒绝协作。

因此，扫描器需要知道解析器的状态，以便能够对十六进制或整数令牌做出正确的决定。

现在是术语的问题。这使这...错误...语法是什么？词法分析器？然后？一个上下文敏感的词法分析器？或者有人会说这是一种上下文相关的语法，即使它显然是一个扫描仪问题？是否有其他术语用于描述此类现象？

4

2 回答 2

2

上下文敏感意味着完全不同的东西。

如果您要使用更正式的符号，您会发现您的原始语法是模棱两可的，正如 Ignacio Vazquez-Abrams 所说，您编辑的语法可以由 LR(1)（甚至 LL(1)）很好地处理解析器生成器。这是一个没有问题的野牛语法：

%start number
%%
digit : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
hex   : digit
      | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' 
      | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
decnum: digit | decnum digit
hexnum: hex   | hexnum hex
number: '[' decnum ']'
      | '{' hexnum '}'

当然，通常不使用野牛来创建扫描仪，但这当然是可能的。

我认为您正在考虑的问题是：如果我们使用 flex 构建扫描仪，它将如下所示：

[[:digit:]]+  { yylval.string = strdup(yytext); return DECNUM; }
[[:xdigit:]]+ { yylval.string = strdup(yytext); return HEXNUM; }

Flex 不能返回模棱两可的标记，因此在（下一部分）输入是 的情况下1234，flex 需要返回 DECNUM 或 HEXNUM。第一个最长（“maximal munch”）规则意味着在 flex 定义中最先出现的模式将在可以以任何一种方式解析的令牌的情况下获胜。这意味着 DECNUM 模式需要首先出现，否则它不可能触发（并且 flex 在这种情况下会提供警告）。

但是现在语法有一个小问题，因为当语法期待一个HEXNUM时，它需要准备找到一个DECNUM。这不是问题，只要语法是明确的。我们只需要创建几个非终端：

decnum: DECNUM           { $$ = strtol($1, NULL, 10); free($1); }
hexnum: DECNUM | HEXNUM  { $$ = strtol($1, NULL, 16); free($1); }

这不会产生歧义，甚至不会造成语法中不存在的移位/减少冲突。

如果你想试试这个，你需要在你的野牛序言中声明一些类型：

%union {
   char* string;
   long  integer;
}
%token <string> HEXNUM DECNUM
%type <integer> hexnum decnum
于 2015-05-16T18:04:57.540 回答
0

那语法可谓是模棱两可。

于 2015-05-16T17:34:34.690 回答