Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

对于给定的文法G(B):B:=aBc, B:=Bdc, B:=d, 其中:=为推导符号,请消除这一文法的直接左递归

  1. Assistant

    Sorry, as an AI language model, I cannot predict your thoughts. Can you please provide me with more context or information regarding your question?

  2. User

    对于给定的文法G(B):B:=aBc, B:=Bdc, B:=d, 其中:=为推导符号,请消除这一文法的直接左递归

  3. Assistant

    消除G(B)的直接左递归的步骤如下:

    1. 检查文法中所有的产生式,找出所有的直接左递归的产生式。

    G(B)中有一个直接左递归的产生式:B → Bdc

    1. 为每个直接左递归的产生式生成一个新的非终结符,并在每个非终结符产生式中将原始的产生式拆分为两个产生式。拆分后的产生式的第一部分中不包含新生成的非终结符。

    对于G(B),B → Bdc 可以拆分为以下两个产生式:

    B → dB'

    B' → cB' | ε

    其中,B' 是新生成的非终结符。

    1. 修改原始文法中所有包含直接左递归的产生式的非终结符。这些非终结符应该产生指向新生成非终结符的产生式。

    在G(B)中,B → Bdc已经被拆分并引入新的非终结符B'。现在应将 B → Bdc 修改为 B → dB'。

    因此,消除直接左递归后的G(B)为:

    B → aBcB' | dB'

    B' → cB' | ε

  4. User

    B → dB', B' → aB'c | dc 这样正确吗

  5. Assistant

    不完全正确。如果按照您给出的修改方法,B' → aB'c | dc 中的 aB'c 产生式仍然存在左递归,因为它的形式是 A → Aα,其中 A 为非终结符,α 为一串符号。因此还需要对 B' → aB'c 进行左递归消除,而不仅仅是修改 B → dB', B' → aB'c | dc。

    正确的消除直接左递归后的G(B)如下:

    B → aBcB' | dQ

    B' → cB' | ε

    Q → B'c

    注意,我们引入另一个新的非终结符 Q,用于表示 B → dQ 产生式中的 Qc 部分,以消除 B → dB' 中的左递归。同时,我们也对 B' 的产生式进行了修改,将其表示为 B' → cB' | ε 的形式,以去除 B' → aB'c 中的左递归。