<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>src/grammar/raw-string-literal-ambiguity.md - fork/rust @ 1.39.0</title>
<meta name="description" content="src/grammar/raw-string-literal-ambiguity.md in fork/rust at 1.39.0.">
<meta property="og:title" content="src/grammar/raw-string-literal-ambiguity.md - fork/rust @ 1.39.0">
<meta property="og:description" content="src/grammar/raw-string-literal-ambiguity.md in fork/rust at 1.39.0.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="1.39.0" data-tip="4560ea788cb760f0a34127156c78e2552949f734">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>fork/rust</h1>
</div>
<pre class="clone">git clone https://git.julia.blue/fork/rust</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">bors</span><span class="commit-message" data-commit="4560ea788cb760f0a34127156c78e2552949f734">Auto merge of #66089 - Mark-Simulacrum:stable-next, r=Mark-Simulacrum</span><span class="snapshot-sha sha" data-commit="4560ea788cb760f0a34127156c78e2552949f734">4560ea788cb</span><time datetime="2019-11-04T15:43:19+00:00" title="2019-11-04 15:43:19 +0000">2019-11-04</time></p>
<header class="topbar"><details class="switcher"><summary>1.39.0</summary><div class="menu"><strong>branches</strong><a href="/fork/rust/ref/master/">master</a><strong>tags</strong><a class="current" href="/fork/rust/ref/1.39.0/">1.39.0</a><a href="/fork/rust/ref/1.40.0/">1.40.0</a><a href="/fork/rust/ref/1.41.0/">1.41.0</a><a href="/fork/rust/ref/1.41.1/">1.41.1</a><a href="/fork/rust/ref/1.42.0/">1.42.0</a><a href="/fork/rust/ref/1.43.0/">1.43.0</a><a href="/fork/rust/ref/1.43.1/">1.43.1</a><a href="/fork/rust/ref/1.44.0/">1.44.0</a><a class="all" href="/fork/rust/refs">all refs →</a></div></details><nav class="crumbs"><a href="/fork/rust/">rust</a> / <a href="/fork/rust/ref/1.39.0/tree/src/">src</a> / <a href="/fork/rust/ref/1.39.0/tree/src/grammar/">grammar</a> / <span class="cur">raw-string-literal-ambiguity.md</span></nav>
<span class="view-stats"><span>2.7 KiB</span><span>64 lines</span></span><span class="actions"><a class="raw" href="/fork/rust/raw/c909f2333148a99d3482373c91e279a2dad2a1ce/src/grammar/raw-string-literal-ambiguity.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><p>Rust's lexical grammar is not context-free. Raw string literals are the source
of the problem. Informally, a raw string literal is an <code>r</code>, followed by <code>N</code>
hashes (where N can be zero), a quote, any characters, then a quote followed
by <code>N</code> hashes. Critically, once inside the first pair of quotes,
another quote cannot be followed by <code>N</code> consecutive hashes. e.g.
<code>r###""###"###</code> is invalid.</p>
<p>This grammar describes this as best possible:</p>
<pre><code>R -&gt; 'r' S
S -&gt; '"' B '"'
S -&gt; '#' S '#'
B -&gt; . B
B -&gt; ε
</code></pre>
<p>Where <code>.</code> represents any character, and <code>ε</code> the empty string. Consider the
string <code>r#""#"#</code>. This string is not a valid raw string literal, but can be
accepted as one by the above grammar, using the derivation:</p>
<pre><code>R : #""#"#
S : ""#"
S : "#
B : #
B : ε
</code></pre>
<p>(Where <code>T : U</code> means the rule <code>T</code> is applied, and <code>U</code> is the remainder of the
string.) The difficulty arises from the fact that it is fundamentally
context-sensitive. In particular, the context needed is the number of hashes.</p>
<p>To prove that Rust's string literals are not context-free, we will use
the fact that context-free languages are closed under intersection with
regular languages, and the
<a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages">pumping lemma for context-free languages</a>.</p>
<p>Consider the regular language <code>R = r#+""#*"#+</code>. If Rust's raw string literals are
context-free, then their intersection with <code>R</code>, <code>R'</code>, should also be context-free.
Therefore, to prove that raw string literals are not context-free,
it is sufficient to prove that <code>R'</code> is not context-free.</p>
<p>The language <code>R'</code> is <code>{r#^n""#^m"#^n | m &lt; n}</code>.</p>
<p>Assume <code>R'</code> <em>is</em> context-free. Then <code>R'</code> has some pumping length <code>p &gt; 0</code> for which
the pumping lemma applies. Consider the following string <code>s</code> in <code>R'</code>:</p>
<p><code>r#^p""#^{p-1}"#^p</code></p>
<p>e.g. for <code>p = 2</code>: <code>s = r##""#"##</code></p>
<p>Then <code>s = uvwxy</code> for some choice of <code>uvwxy</code> such that <code>vx</code> is non-empty,
<code>|vwx| &lt; p+1</code>, and <code>uv^iwx^iy</code> is in <code>R'</code> for all <code>i &gt;= 0</code>.</p>
<p>Neither <code>v</code> nor <code>x</code> can contain a <code>"</code> or <code>r</code>, as the number of these characters
in any string in <code>R'</code> is fixed. So <code>v</code> and <code>x</code> contain only hashes.
Consequently, of the three sequences of hashes, <code>v</code> and <code>x</code> combined
can only pump two of them.
If we ever choose the central sequence of hashes, then one of the outer sequences
will not grow when we pump, leading to an imbalance between the outer sequences.
Therefore, we must pump both outer sequences of hashes. However,
there are <code>p+2</code> characters between these two sequences of hashes, and <code>|vwx|</code> must
be less than <code>p+1</code>. Therefore we have a contradiction, and <code>R'</code> must not be
context-free.</p>
<p>Since <code>R'</code> is not context-free, it follows that the Rust's raw string literals
must not be context-free.</p>
</section><div class="code-panel"><pre class="code src" data-hl="src/grammar/raw-string-literal-ambiguity.md"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text">Rust's lexical grammar is not context-free. Raw string literals are the source</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text">of the problem. Informally, a raw string literal is an `r`, followed by `N`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text">hashes (where N can be zero), a quote, any characters, then a quote followed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text">by `N` hashes. Critically, once inside the first pair of quotes,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text">another quote cannot be followed by `N` consecutive hashes. e.g.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text">`r###&quot;&quot;###&quot;###` is invalid.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text">This grammar describes this as best possible:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text">    R -&gt; 'r' S</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text">    S -&gt; '&quot;' B '&quot;'</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text">    S -&gt; '#' S '#'</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text">    B -&gt; . B</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text">    B -&gt; ε</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text">Where `.` represents any character, and `ε` the empty string. Consider the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text">string `r#&quot;&quot;#&quot;#`. This string is not a valid raw string literal, but can be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text">accepted as one by the above grammar, using the derivation:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text">    R : #&quot;&quot;#&quot;#</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text">    S : &quot;&quot;#&quot;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text">    S : &quot;#</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text">    B : #</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text">    B : ε</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text">(Where `T : U` means the rule `T` is applied, and `U` is the remainder of the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L27" href="#L27">27</a><span class="code-text">string.) The difficulty arises from the fact that it is fundamentally</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L28" href="#L28">28</a><span class="code-text">context-sensitive. In particular, the context needed is the number of hashes.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L30" href="#L30">30</a><span class="code-text">To prove that Rust's string literals are not context-free, we will use</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L31" href="#L31">31</a><span class="code-text">the fact that context-free languages are closed under intersection with</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L32" href="#L32">32</a><span class="code-text">regular languages, and the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L33" href="#L33">33</a><span class="code-text">[pumping lemma for context-free languages](https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L34" href="#L34">34</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L35" href="#L35">35</a><span class="code-text">Consider the regular language `R = r#+&quot;&quot;#*&quot;#+`. If Rust's raw string literals are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L36" href="#L36">36</a><span class="code-text">context-free, then their intersection with `R`, `R'`, should also be context-free.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L37" href="#L37">37</a><span class="code-text">Therefore, to prove that raw string literals are not context-free,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L38" href="#L38">38</a><span class="code-text">it is sufficient to prove that `R'` is not context-free.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L39" href="#L39">39</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L40" href="#L40">40</a><span class="code-text">The language `R'` is `{r#^n&quot;&quot;#^m&quot;#^n | m &lt; n}`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L41" href="#L41">41</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L42" href="#L42">42</a><span class="code-text">Assume `R'` *is* context-free. Then `R'` has some pumping length `p &gt; 0` for which</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L43" href="#L43">43</a><span class="code-text">the pumping lemma applies. Consider the following string `s` in `R'`:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L44" href="#L44">44</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L45" href="#L45">45</a><span class="code-text">`r#^p&quot;&quot;#^{p-1}&quot;#^p`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L46" href="#L46">46</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L47" href="#L47">47</a><span class="code-text">e.g. for `p = 2`: `s = r##&quot;&quot;#&quot;##`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L48" href="#L48">48</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L49" href="#L49">49</a><span class="code-text">Then `s = uvwxy` for some choice of `uvwxy` such that `vx` is non-empty,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L50" href="#L50">50</a><span class="code-text">`|vwx| &lt; p+1`, and `uv^iwx^iy` is in `R'` for all `i &gt;= 0`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L51" href="#L51">51</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L52" href="#L52">52</a><span class="code-text">Neither `v` nor `x` can contain a `&quot;` or `r`, as the number of these characters</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L53" href="#L53">53</a><span class="code-text">in any string in `R'` is fixed. So `v` and `x` contain only hashes.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L54" href="#L54">54</a><span class="code-text">Consequently, of the three sequences of hashes, `v` and `x` combined</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L55" href="#L55">55</a><span class="code-text">can only pump two of them.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L56" href="#L56">56</a><span class="code-text">If we ever choose the central sequence of hashes, then one of the outer sequences</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L57" href="#L57">57</a><span class="code-text">will not grow when we pump, leading to an imbalance between the outer sequences.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L58" href="#L58">58</a><span class="code-text">Therefore, we must pump both outer sequences of hashes. However,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L59" href="#L59">59</a><span class="code-text">there are `p+2` characters between these two sequences of hashes, and `|vwx|` must</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L60" href="#L60">60</a><span class="code-text">be less than `p+1`. Therefore we have a contradiction, and `R'` must not be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L61" href="#L61">61</a><span class="code-text">context-free.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L62" href="#L62">62</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L63" href="#L63">63</a><span class="code-text">Since `R'` is not context-free, it follows that the Rust's raw string literals</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L64" href="#L64">64</a><span class="code-text">must not be context-free.</span></span></pre></div></div>
</main>
</body>
</html>
