c# - 解析泛型时区分 ">>"和 ">"

Question

我的第一个堆栈溢出问题。

我一直对这个很好奇。

假设您正在解析以下代码行:

List<Nullable<int>> list = new List<Nullable<int>>();

解析时，一个简单的标记器会假设两个右尖括号是一个“右移”标记。我还没有用 C 风格语言的任何其他语言构造遇到这个问题。

现代解析器如何处理这个问题？使用这种“贪婪解析”时是否有解决方法？

我曾考虑在解析器中使用堆栈结构，在解析泛型类型时专门处理这些标记。不过，我不确定在编写代码编辑器时效果如何。

万分感谢! :)

Answer 1

解析语言时，通常有两个主要组件:扫描器和解析器。扫描器产生一个 token 流，解析器根据 grammar 解释该流。 ，这是语言中产生式规则的正式定义——你可以找到C# 4.0的语法here .

免责声明:我并不是暗示以下内容一定是 C# 语言的解析方式，我只是使用 C# 片段来说明一般概念。

扫描

所以第一步是为解析器生成标记。 token 通常由某种符号类型(指示它是 token 的类型)、词位( token 的实际文本)和其他信息(例如行号)(用于错误处理)组成。

所以如果我们使用 List<Nullable<int>> list;以您的问题为例，扫描仪将产生以下标记:

available_identifier, List
<
available_identifier, Nullable
<
integral_type, int
>
>
available_identifier, list
;

请注意，标记类型是从上面链接的 C# 语法中推断出来的。

解析

大多数解析器是所谓的 shift-reduce parsers .这意味着 token 逐渐转移到堆栈上，并在它们匹配规则时减少(删除)。为了帮助匹配，解析器将有一定数量的前瞻标记，它可以观察到(我相信一个是最常见的)。通常，当所有标记都减少时，成功的解析将结束。

YACC等编译器构建程序实现的解析器类型和 GPPG被称为 LALR(1)解析器。这些通过基于解析器状态和前瞻符号的每个合法组合构建解析表来工作，并给出当前状态和下一个符号，然后可以告诉我们如何计算下一个状态。

现在我们有了我们的 token ，我们将它们发射到解析器中，其结果通常是 abstract syntax tree ，可用于后续任务，例如代码生成、语义类型检查等。为了解析这些标记，我们需要将它们分组为有意义的句法单元的规则——这就是在遇到 >> 时防止混淆的原因。 .

从 C# 语法:

declaration_statement:
    | local_variable_declaration ";" 
    | local_constant_declaration ";" 

local_variable_declaration:
    | local_variable_type local_variable_declarators 

local_variable_type:
    | type 
    | "var"

local_variable_declarators:
    | local_variable_declarator 
    | local_variable_declarators "," local_variable_declarator 

local_variable_declarator:
    | identifier 
    | identifier "=" local_variable_initializer 

type:
    | value_type 
    | reference_type 
    | type_parameter 
    | type_unsafe 

value_type:
    | struct_type 
    | enum_type 

struct_type:
    | type_name 
    | simple_type 
    | nullable_type 

simple_type:
    | numeric_type 
    | bool 

numeric_type:
    | integral_type 
    | floating_point_type 
    | decimal 

integral_type:
    | "sbyte" 
    | "byte" 
    | "short" 
    | "ushort" 
    | "int"
    | "uint" 
    | "long"
    | "ulong" 
    | "char"

reference_type:
    | class_type 
    | interface_type 
    | array_type 
    | delegate_type 

class_type:
    | type_name 
    | "object"
    | "dynamic" 
    | "string"

type_name:
    | namespace_or_type_name 

namespace_or_type_name:
    | identifier type_argument_list? 
    | namespace_or_type_name "." identifier type_argument_list? 
    | qualified_alias_member 

identifier:
    | available_identifier 
    | "@" identifier_or_keyword 

type_argument_list:
    | "<" type_arguments ">" 

type_arguments:
    | type_argument 
    | type_arguments "," type_argument 

type_argument:
    | type 

看起来很复杂，但留在我身边。每个规则的形式

rule_name:
    | production_1
    | production_2
    | production_2

每个产生式可以是另一个规则(非终结符)或终结符。拿 integral_type规则例如:它的所有产品都是终端。规则也可以引用它们自己，这就是 Tuple<int, int, double> 中的类型参数之类的东西。被处理。

出于本示例的目的，我假设 List<Nullable<int>> list;是局部变量声明。您可以在 Shift-Reduce Parsing 上找到更简单的示例。维基百科页面，另一个位于 LR Parsing页。

首先，我们的 Parse Stack 是空的，我们的单个前瞻标记是第一个，我们的第一个 Action 是移动该标记。也就是说，我们的解析器状态将如下所示:

Step 0
Parse Stack:    empty
Look Ahead:     available_identifier
Unscanned:      List<Nullable<int>> list;
Parser Action:  Shift

在我们的下一步中，我们可以根据生产 identifier <- available_identifier 减少当前代币。 .

Step 1
Parse Stack:    available_identifier
Look Ahead:     "<"
Unscanned:      <Nullable<int>> list;
Parser Action:  Reduce by identifier <- available_identifier

跳过几步，在第 10 步，我们将拥有以下解析器状态:

Step 10
Parse Stack:    identifier "<" identifier "<" type_arguments ">"
Look Ahead:     ">"
Unscanned:      > list;
Parser Action:  Reduce by type_argument_list <- "<" type_arguments ">"

此时我们将能够减少最后三个标记，因为它们的序列组成了 type_argument_list (您可以在上面的规则中检查这一点)。快进到第 13 步，我们有以下内容:

Step 13
Parse Stack:    identifier "<" type_arguments ">"
Look Ahead:     ">"
Unscanned:      list;
Parser Action:  Reduce by type_argument_list <- "<" type_arguments ">"

就像在步骤 10 中一样，我们减少了 type_argument_list <- "<" type_arguments ">" .通过这样做，我们实际上避免了 >> 的任何歧义。 .这些步骤一直持续到我们减少 declaration_statement <- local_variable_declaration ";" - 上面的第一条规则。

摘要

通过创建一个明确的语法，解析器能够轻松地消除看似棘手的情况，如 List<Nullable<int>> .我在这里介绍的内容本质上是一个自底向上的 LALR(1) 解析器。我还没有进入抽象语法树的实际创建过程，但是您可能已经掌握了上述内容。

请记住，规则不包括开始状态 - 这主要是为了简洁起见。如果有帮助，我可以将其余的解析步骤放在那里。

编辑:f(g<a, b>(c))

这在语法中归结为两个 invocation_expression规则，格式为 invocation_expression -> primary_expression ( argument_list? )
第一个匹配 g<a, b>(c) .它首先建立 g<a,b>是 identifier后跟一个 type_argument_list .我们的前瞻现在是 "(" ，并且因为解析器会从前面的上下文中知道这段代码在方法体中，所以它可以减少 identifier type_argument_list经过

primary_expression <- primary_no_array_creation_expression
    <- simple_name <- identifier type_argument_list?

移后"("和 c ，我们可以减少 c经过

argument_list <- argument <- argument_value <- expression
    <- <a really long list of rules> <- simple_name
    <- identifier <- available_identifier

并移动最后一个括号字符给我们

primary_expression ( argument_list? )

然后可以通过 invocation_expression 减少规则，从而匹配 g<a, b>(c) .

此时我们已经匹配了 f作为 identifier并应用减少

primary_expression <- primary_no_array_creation_expression
    <- simple_name <- identifier type_argument_list?

因此，解析堆栈将包含以下内容

primary_expression "(" invocation_expression
        ^           ^            ^
        f           (        g<a, b>(c)

前瞻符号将在最后 ")" ，所以解析器会减少 invocation_expression经过

argument_list <- argument <- argument_value <- expression
    <- <the same really long list of rules> <- primary_expression
    <- primary_no_array_creation_expression <- invocation_expression

移动最后一个 ")"然后会给我们

    primary_expression "(" argument_list ")"
            ^           ^        ^        ^
            f           (    g<a, b>(c)   )

和以前一样，这可以通过 invocation_expression 减少。规则，从而匹配 f(g<a, b>(c)) .