题目
已知文法 G [ E ]: E → T | E + T T → FT * F F →( E )| i (1)给出句型( T * F + i )的最右推导,并画出语法树;(2)给出句型( T * F + i )的短语、素短语和最左素短语;(3)证明 E + T * F 是文法的一个句型,指出这个句型的所有短语、直接短语和句柄。
已知文法 G [ E ]:
E → T | E + T
T → FT * F
F →( E )| i
(1)给出句型( T * F + i )的最右推导,并画出语法树;
(2)给出句型( T * F + i )的短语、素短语和最左素短语;
(3)证明 E + T * F 是文法的一个句型,指出这个句型的所有短语、直接短语和句柄。
题目解答
答案
根据题意已知文法 G [ E ]:
E → T | E + T
T → FT * F
F →( E )| i ,我们需要回答题中所给的三个问题。
(1) 句型 T * F + i 的最右推导如下:
E → E + T → E + T * F → E + T * F + i
对应的语法树如下:
E
/ \
E +
/ \
T E
/ \
T *
/ \
F i
(2) 句型 T * F + i 的短语、素短语和最左素短语如下:
短语:T * F + i
素短语:T、F、i
最左素短语:T
(3) 证明 E + T * F 是文法的一个句型,指出这个句型的所有短语、直接短语和句柄:
首先,我们可以通过产生式的右部逐步推导出 E + T * F:
E → E + T → E + T * F
该句型的所有短语如下:
E
E + T
E + T * F
直接短语是指从句型的最左端开始的连续子串。该句型的所有直接短语如下:
E
E + T
句柄是指在推导过程中,产生式右部被替换的部分。该句型的句柄是 T * F,因为在推导过程中,它被 E + T * F 替换。
解析
步骤 1:最右推导
根据文法 G [ E ],我们从 E 开始,进行最右推导,直到得到句型 T * F + i。
步骤 2:语法树
根据最右推导,画出对应的语法树。
步骤 3:短语、素短语和最左素短语
根据语法树,确定句型 T * F + i 的短语、素短语和最左素短语。
步骤 4:证明 E + T * F 是文法的一个句型
根据文法 G [ E ],证明 E + T * F 是文法的一个句型,并指出这个句型的所有短语、直接短语和句柄。
根据文法 G [ E ],我们从 E 开始,进行最右推导,直到得到句型 T * F + i。
步骤 2:语法树
根据最右推导,画出对应的语法树。
步骤 3:短语、素短语和最左素短语
根据语法树,确定句型 T * F + i 的短语、素短语和最左素短语。
步骤 4:证明 E + T * F 是文法的一个句型
根据文法 G [ E ],证明 E + T * F 是文法的一个句型,并指出这个句型的所有短语、直接短语和句柄。