Menu
    1. 用上下文无关文法描述下列语言
      1. 定义在字母表 ∑={a,b}\sum=\lbrace a, b\rbrace 上，所有首字符和尾字符相同的非空字符串
      2. L={0i1j∣0≤i≤j≤2i}L=\lbrace 0^i1^j\vert 0\le i\le j \le 2i\rbrace
      3. 定义在字母表 ∑={0,1}\sum =\lbrace 0, 1\rbrace 上，所有含有相同个数的 0 和 1 的字符串（包括空串）
    2. 考虑以下文法
      1. 用最左推导（leftmost derivation）推导出句子 abbcde
      2. 用最右推导（rightmost derivation）推导出句子 abbcde
      3. 画出句子 abbcde 对应的分析树（parse tree）
    3. 考虑下述文法
    4. 这一文法产生什么语言（用自然语言描述）
    5. 证明这一文法是二义的
    6. 写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言

    编译原理（四）

    post on 14 May 2020 about 1709words require 6min
    CC BY 4.0 （除特别声明或转载文章外）
    如果这篇文章帮助到你，可以请我喝一杯咖啡~

    用上下文无关文法描述下列语言

    定义在字母表 ∑={a,b}\sum=\lbrace a, b\rbrace 上，所有首字符和尾字符相同的非空字符串

    S→aRa∣bRb∣a∣bR→Ra∣Rb∣εS\to aRa\vert bRb\vert a\vert b \\ R\to Ra\vert Rb\vert \varepsilon
    1. RR 表示字典表是 ∑\sum 上的所有字符串
    2. SS 在 RR 的基础上定义题目要求的串，注意到单个 aa 和 bb 也是符合要求的。

    L={0i1j∣0≤i≤j≤2i}L=\lbrace 0^i1^j\vert 0\le i\le j \le 2i\rbrace

    S→0S1∣0S11∣εS\to 0S1\vert 0S11\vert\varepsilon
    1. 若 SS 符合要求，则 0S10S1 符合要求，可得 S→0S1S\to 0S1
    2. 若 SS 符合要求，则 0S110S11 符合要求，可得 S→0S11S\to 0S11
    3. 空串符合要求，可得 S→εS\to\varepsilon

    定义在字母表 ∑={0,1}\sum =\lbrace 0, 1\rbrace 上，所有含有相同个数的 0 和 1 的字符串（包括空串）

    S→SS∣0S1∣1S0∣εS\to SS\vert 0S1\vert 1S0 \vert\varepsilon
    1. 若首尾字母相同，那么原字符串一定能划分成两个符合要求的子串，于是得到 S→SSS\to SS
    2. 若首尾字母不同，则去掉首尾字母仍然符合要求，于是得到 S→0S1∣1S0S\to 0S1\vert 1S0
    3. 空串符合要求，得到 S→εS\to\varepsilon

    考虑以下文法

    S→aABeA→Abc∣bB→bS\to aABe \\ A\to Abc\vert b \\ B\to b

    用最左推导（leftmost derivation）推导出句子 abbcde

    S⇒aABe⇒aAbcBe⇒abbcBe⇒abbcdeS\Rightarrow aABe\Rightarrow aAbcBe \Rightarrow abbcBe \Rightarrow abbcde

    用最右推导（rightmost derivation）推导出句子 abbcde

    S⇒aABe⇒aAde⇒aAbcde⇒abbcdeS\Rightarrow aABe \Rightarrow aAde \Rightarrow aAbcde \Rightarrow abbcde

    画出句子 abbcde 对应的分析树（parse tree）

    S

    a

    A

    B

    e

    A

    b

    c

    d

    b

    flowchart TB
S0---S1
S0---S2
S0---S3
S0---S4
S2---S5
S2---S6
S2---S7
S3---S8
S5---S9
S0[S]
S1[a]
S2[A]
S3[B]
S4[e]
S5[A]
S6[b]
S7[c]
S8[d]
S9[b]

    考虑下述文法

    S→aSbS→aSS→εS \to aSb\\ S \to aS\\ S \to \varepsilon

    这一文法产生什么语言（用自然语言描述）

    若干个 aa 紧接若干个 bb 的字符串，且 aa 的数量不少于 bb 。

    证明这一文法是二义的

    例如，对于串 aabaab 可以产生下述两种分析树:

    分析树A

    S

    a

    S

    a

    S

    b

    ε

    分析树B

    S

    a

    S

    b

    a

    S

    ε

    flowchart LR
subgraph 分析树B
S0---S1
S0---S2
S0---S3
S2---S4
S2---S5
S5---S6
S0[S]
S1[a]
S2[S]
S3[b]
S4[a]
S5[S]
S6["#epsilon;"]
end
subgraph 分析树A
S7---S8
S7---S9
S9---Sa
S9---Sb
S9---Sc
Sb---Sd
S7[S]
S8[a]
S9[S]
Sa[a]
Sb[S]
Sc[b]
Sd["#epsilon;"]
end

    写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言

    S→aSb∣RR→aR∣εS\to aSb\vert R\\ R\to aR\vert \varepsilon

    由前一问可以知道，产生二义性的原因是，对于某些位置的 aa ，既可以从第一条规则得到，也可以由第二条规则得到。因此考虑定义一个新的只含有字母 aa 的串 RR，这样就可以规定每一个 aa 是由哪一条规则得到的（不妨设串中有 α\alpha 个 aa，β\beta 个 bb ，则由第一问有 α≥β\alpha \ge \beta）：

    1. 如果对于特定位置的 aa，它到最近的 bb 的距离小于等于 β\beta，则它是由第一条规则得到的。
    2. 如果对于特定位置的 aa，它到最近的 bb 的距离大于 β\beta，则它是由第二条规则得到的。
    3. 对于所有的 bb，它一定是由第一条规则得到的。

    由此可以证明文法无二义，同时证明过程也推导了任意一个前述文法相同语言的过程，于是这个新的文法是符合要求的。

    Related posts