Jos*_*ant 13 c# generics parsing
我的第一个Stack Overflow问题.
我一直很好奇这个.
假设您正在解析以下代码行:
List<Nullable<int>> list = new List<Nullable<int>>();
解析时,一个朴素的标记器会假设两个直角括号是一个"右移"标记.我没有用C风格的语言构建任何其他语言构造这个问题.
现代解析器如何处理这个问题？使用这种"贪婪的解析"时是否有解决方法？
我曾考虑在解析器中使用堆栈结构,在解析泛型类型时特别处理这些令牌.我不确定在编写代码编辑器时会有多好.
万分感谢!:)
解析语言时,通常有两个主要组件:扫描程序和解析器.扫描仪生产标记流,解析器解释根据该流的语法,这是在语言的产生式规则的正式定义-你能找到的语法为C#4.0 在这里.
免责声明:我并不是说以下必然是如何解析C#语言,我只是使用C#片段来说明一般概念.
扫描
所以第一步是为解析器生成令牌.令牌通常由某种符号类型(表示令牌的类型),词汇(令牌的实际文本)以及其他信息(如行号(对错误处理有用))组成.
因此,如果我们使用List<Nullable<int>> list;您的问题作为示例,扫描程序将生成以下标记:
available_identifier, List
<
available_identifier, Nullable
<
integral_type, int
>
>
available_identifier, list
;
请注意,令牌类型是从与上面链接的C#语法推断出来的.
解析
大多数解析器都是所谓的shift-reduce解析器.这意味着令牌会逐渐转移到堆栈上,并在符合规则时减少(删除).为了帮助匹配,解析器将具有一定数量的可能观察到的前瞻标记(我相信一个是最常见的).通常,成功的解析将在所有令牌减少时结束.
由编译器构造程序(如YACC和GPPG)实现的解析器类型称为LALR(1)解析器.这些工作通过构建基于解析器状态和先行符号的每个合法组合的解析表,并给定当前状态和下一个符号,然后可以告诉我们如何计算下一个状态.
现在我们有了令牌,我们将它们解压缩到解析器中,其结果通常是一个抽象语法树,可以用于后续任务,如代码生成,语义类型检查等.要解析这些令牌,我们需要将它们分组成有意义的句法单元的规则 - 这是防止遇到混淆的原因>>.
从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 Wikipedia页面上找到一个更简单的示例,在LR Parsing页面上找到另一个示例.
首先,我们的Parse Stack是空的,我们的单个前瞻标记是第一个,我们的第一个动作是移动该标记.也就是说,我们的解析器状态将如下所示:
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)).