设有文法G(A): A→BaC|CbB B→Ac|c C→Bb|b 试消除G(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′|ε
