7

大多数编程语言的词法语法是相当不具表现力的,以便快速对其进行词法分析。我不确定 Rust 的词法语法属于哪个类别。其中大部分似乎是常规的,可能除了原始字符串文字

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

哪个打印:

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

由于我们可以任意添加许多#,所以它似乎不能是规则的,对吧?但是语法至少是上下文无关的吗?或者关于 Rust 的词汇语法是否有一些与上下文无关的东西?


有关的Rust 的句法语法是上下文无关的还是上下文敏感的?

4

1 回答 1

10

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

如果您将其视为由(使用上标作为计数运算符)包围的字符串,那么您可能会认为它是上下文无关的:r#k"…"#kk

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

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

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

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

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

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

后记

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

识别单个标记和标记输入流不一定是等效的。可以想象一种语言,其中各个标记都被正则表达式识别,但输入流不能用有限状态转换器处理。如果有两个正则表达式T并且U某个字符串匹配T是最长的标记,它是U. 作为一个简单(且无意义)的示例,以带有标记的语言为例:

a
a*b

这两个标记显然都是规则的,但输入流不能用有限状态转换器标记,因为它必须检查任何as 序列(任何长度),然后再决定是回退到第一个a还是接受由所有as 和以下b(如果存在)。

很少有语言表现出这种病态(据我所知,Rust 不是其中之一),但它在技术上存在于一些关键字是多词短语的语言中。

笔记

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