Rust的词汇语法是常规的,无上下文的还是上下文敏感的？

Question

大多数编程语言的词汇语法都是非常富有表现力的,以便快速掌握它.我不确定Rust的词汇语法属于什么类别.大多数似乎是常规的,可能除了原始字符串文字:

let s = r##"Hi lovely "\" and "#", welcome to Rust"##;
println!("{}", s);

哪个印刷品:

Hi lovely "\" and "#", welcome to Rust

因为我们可以任意添加许多#,看起来它不能正常,对吧？但语法是否至少没有上下文？或者是否有关于Rust的词汇语法的非上下文自由的东西？

---

相关:Rust的语法语法是无上下文还是上下文敏感？

Answer 1

原始字符串文字语法不是无上下文的.

如果你认为它是一个被(被上标作为计数运算符)包围的字符串,那么你可能会认为它是无上下文的:r#k"…"#kk

raw_string_literal
   : 'r' delimited_quoted_string
delimited_quoted_string
   : quoted_string
   | '#' delimited_quoted_string '#'

但这实际上并不是正确的语法,因为虽然它可以包含任何quoted_string内容,但不允许包含它"#k"#jj<k

在不排除任何其他不同长度的类似序列的情况下排除终止序列不能用无上下文语法来完成,因为它涉及在单个生产中三次(或更多次)使用k-repetition,而栈自动机只能处理两个.(语法不是没有上下文的证据非常复杂,所以我不打算在这里尝试缺少MathJax.我能想出的最好的证据是使用Ogden的引理和不常见的引用(但非常有用)在有限状态传感器的应用下关闭无上下文语法的属性.)

C++原始字符串文字也是上下文敏感的[或者如果分隔符长度不受限制,请参见注释1],并且所有对空格敏感的语言(如Python和Haskell)都是上下文敏感的.这些词法分析任务都不是特别复杂,因此上下文敏感性不是一个大问题,尽管大多数标准扫描仪生成器不能提供尽可能多的协助.但它确实如此.

Rust的词法语法为扫描仪生成器提供了许多其他复杂功能.一个问题是双重含义',它既用于创建字符文字,也用于标记生命周期变量和循环标签.显然,可以通过考虑先前识别的令牌来确定其中的哪一个适用.这可以通过词法扫描器解决,该词法扫描器能够从单个模式生成两个连续的令牌,或者可以使用无扫描器解析器来完成; 后一种解决方案是无背景的,但不是常规的.(C++ '作为数字文字的一部分使用不会导致同样的问题; C++标记可以用正则表达式识别,因为'它不能用作数字文字的第一个字符.)

另一个略微依赖于上下文的词汇问题是,范围运算符..优先于浮点值,因此2..3必须在词法上分析为三个标记:2 .. 3而不是两个浮点数2. .3,这是在大多数语言中分析的方式.使用最大蒙克规则.同样,这可能会或可能不会被视为偏离正则表达式标记化,因为它取决于尾随上下文.但由于前瞻最多只有一个字符,因此可以使用DFA实现.

后记

经过反思,我不确定询问"词汇语法"是否有意义.或者,至少,它是模糊的:"词汇语法"可能指的是所有语言"令牌"的组合语法,或者它可能指的是将句子分成标记的行为.后者实际上是一个传感器,而不是一个解析器,并提出了这个语言是否可以用有限状态传感器进行标记的问题.(答案是,不是,因为FSA,甚至是PDA都无法识别原始字符串.)

识别单个令牌并对输入流进行标记不一定是等效的.可以想象一种语言,其中各个令牌都被正则表达式识别,但输入流不能用有限状态换能器处理.如果有两个正则表达式T并且U某些字符串匹配T是最长的令牌,这是一个无限字符串集的严格前缀,那么就会发生这种情况U.作为一个简单(无意义)的示例,请使用带有标记的语言:

a
a*b

这两个令牌都是明确规则的,但输入流不能用有限状态传感器进行标记,因为它必须a在决定是否回退到第一个之前检查任何s(任意长度)的序列,a或者接受由所有的令牌组成的令牌.as和以下b(如果存在).

很少有语言能够显示这种病态(据我所知,Rust不是其中之一),但从技术上来说,它存在于一些关键词是多字短语的语言中.

笔记

1. 实际上,从技术意义上讲,C++原始字符串文字是常规的(因此无上下文),因为它们的分隔符限于从88个字符的字母表中提取的最大长度为16的字符串.这意味着(理论上)可以创建一个由13,082,362,351,752,551,144,309,757,252,761模式组成的正则表达式,每个模式匹配一​​个不同的可能的原始字符串分隔符.