设有文法G(A): A→BaC|CbB B→Ac|c C→Bb|b 试消除G(A)的左递归。

大学 递归,文法, 已帮助 人

设有文法G(A): A→BaC|CbB B→Ac|c C→Bb|b 试消除G(A)的左递归。

请帮忙给出正确答案和分析,谢谢!

热搜:a是b的充分条件,b是a的必要条件吗

答案解析

难度★★☆ 搜索
  • 正确答案:令文法G(A)的非终结符排序为ABC。 对于A不存在直接左递归将A带入B代换后的B的规则变为: B→BaCc|C6Bc|c B存在直接左递归消除B的直接左递归有 B→CbBcB′ |cB′ B′→aCcB′|ε 将B代入C代换后的C的规则变为: C→CbBcB′b|cB′b|b C存在直接左递归消除C的直接左递归有 C→cB′bC′|bC′ C′→bBcB′b C′|ε 消除G[A]的左递归后的文法为: A→BaC|CbB B-CbBcB′|cB′ B′→aCcB′|ε C→cB′bC′|bC′ C′→bBcB′bC′|ε
    令文法G(A)的非终结符排序为A,B,C。对于A,不存在直接左递归,将A带入B,代换后的B的规则变为:B→BaCc|C6Bc|cB存在直接左递归,消除B的直接左递归有B→CbBcB′|cB′B′→aCcB′|ε将B代入C,代换后的C的规则变为:C→CbBcB′b|cB′b|bC存在直接左递归,消除C的直接左递归有C→cB′bC′|bC′C′→bBcB′bC′|ε消除G[A]的左递归后的文法为:A→BaC|CbBB-CbBcB′|cB′B′→aCcB′|εC→cB′bC′|bC′C′→bBcB′bC′|ε