1、为文法G[S] S→(L) | a L→L,S | S (a)写出一个语法制导定义,计算括号的对数(10分) (b)写出一个语法制导定义,计算括号嵌套的最大深度(10分)
时间: 2024-03-19 07:41:33 浏览: 48
(a) 语法制导定义计算括号对数:
首先定义一个计数器变量 $count$,初始值为 $0$。对于每个产生式,我们添加语义规则来更新 $count$ 的值。具体地:
$S \rightarrow (L)$,添加语义规则 $S.val = L.val$,$S.count = L.count+1$,即括号对数为子表达式 $L$ 的括号对数加 $1$。
$S \rightarrow a$,添加语义规则 $S.val = a$,$S.count = 0$,即终结符不计入括号对数。
$L \rightarrow L,S$,添加语义规则 $L.val = L_1.val + ',' + S.val$,$L.count = L_1.count + S.count$,即括号对数为子表达式 $L_1$ 的括号对数加上 $S$ 的括号对数。
$L \rightarrow S(a)$,添加语义规则 $L.val = S.val + '(' + a + ')' $,$L.count = S.count$,即括号对数为子表达式 $S$ 的括号对数。
(b) 语法制导定义计算括号嵌套的最大深度:
首先定义一个计数器变量 $depth$,初始值为 $0$。对于每个产生式,我们添加语义规则来更新 $depth$ 的值。具体地:
$S \rightarrow (L)$,添加语义规则 $S.val = L.val$,$S.depth = L.depth+1$,括号嵌套深度为子表达式 $L$ 的括号嵌套深度加 $1$。
$S \rightarrow a$,添加语义规则 $S.val = a$,$S.depth = 0$,即终结符不参与括号嵌套深度的计算。
$L \rightarrow L,S$,添加语义规则 $L.val = L_1.val + ',' + S.val$,$L.depth = \max(L_1.depth, S.depth)$,即括号嵌套深度为子表达式 $L_1$ 和 $S$ 的括号嵌套深度的最大值。
$L \rightarrow S(a)$,添加语义规则 $L.val = S.val + '(' + a + ')' $,$L.depth = S.depth$,即括号嵌套深度为子表达式 $S$ 的括号嵌套深度。