当前位置：首页 > news >正文

编译原理—翻译方案、属性栈代码

news 2025/7/5 12:29:16

系列文章戳这里👇

什么是上下文无关文法、最左推导和最右推导
如何判断二义文法及消除文法二义性
何时需要消除左递归
什么是句柄、什么是自上而下、自下而上分析
什么是LL(1)、LR(0)、LR(1)文法、LR分析表
LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系
编译原理第三章习题
词法分析、构建DFA、上下文无关文法、LL(1)分析、提取正规式
证明LL(1)、SLR(1)、LALR(1)文法
翻译方案、属性栈代码

编译原理—翻译方案、属性栈代码

系列文章戳这里👇
属性栈代码：
- 举个栗子
引入标记非终结符模拟继承属性的计算

文法如下：

a\\ L → L, S | S

(a) 写一个翻译方案，它输出每个 a 的嵌套深度。例如，对于句子 (a, (a, a))，输出的结果是 1 2 2。
文法符号S，L继承属性depth表示嵌套深度，则翻译方案如下：

S′→{S.depth=0}SS→({L.depth=S.depth}L)S→a{print(S.depth)}L→{L1.depth=L.depth,S.depth=L.depth}L1,SL→{S.depth=L.depth}S\begin{aligned} S'&→\{S.depth=0\}S\\ S&→(\{L.depth = S.depth\}L)\\ S&→a\{print(S.depth)\}\\ L&→\{L_1.depth=L.depth,S.depth=L.depth\}L_1,S\\ L&→\{S.depth=L.depth\}S \end{aligned}

属性栈代码，由于属性栈上仅能存放综合属性（后文有详细介绍），所以需要引入标记非终结符P、Q、R，及其综合属性s，继承属性i，模拟继承属性的计算，则栈代码如下：

S′→{S.depth=P.s}PSP→ϵ{P.s=0}Stack[ntop]=0S→({Q.i=S.depth,L.depth=Q.s}QL)Q→ϵ{Q.s=Q.i+1}Stack[ntop]=Stack[top−1]+1S→a{print(S.depth)}print(Stack[top−1])L→{L1.depth=L.depth,R.i=L.depth,S.depth=R.s}L1,RSR→ϵ{R.s=R.i}Stack[ntop]=Stack[top−2]L→{S.depth=L.depth}S\begin{aligned} S'&→\{S.depth=P.s\}PS\\ P&→\epsilon\{P.s=0\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop]=0\\ S&→(\{Q.i=S.depth,L.depth = Q.s\}QL)\\ Q&→\epsilon\{Q.s=Q.i+1\}\ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop]= Stack[top-1]+1\\ S&→a\{print(S.depth)\}\ \ \ \ \ \ \ \ \ \ print(Stack[top-1])\\ L&→\{L_1.depth=L.depth,R.i=L.depth,S.depth=R.s\}L_1,RS\\ R&→\epsilon\{R.s=R.i\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop] = Stack[top-2]\\ L&→\{S.depth=L.depth\}S \end{aligned}

(b) 写一个翻译方案，它打印出每个 a 在句子中是第几个字符。例如，当句子是 (a, (a, (a, a),(a)))时，打印的结果是 2 5 8 10 14。
使用综合属性out表示当前文法符号推出的字符总数，基础属性before表示该文法符号前有多少个字符，则翻译方案如下：
$S′→{S.before=0}SS→{L.before=S.before}(L){S.out=L.out+2}S→a{S.out=1;print(S.before+1)}L→{L1.before=L.before,S.before=L.before+L1.out+1}L1,S{L.out=L1.out+S.out+1}L→{S.before=L.before}S{L.out=S.out}\begin{aligned} S'&→\{S.before=0\}S\\ S&→\{L.before = S.before\} \\&\ \ \ \ \ \ \ \ \ \ \ (L) \\&\ \ \ \ \ \ \ \ \ \ \ \{S.out=L.out+2\}\\ S&→a\{S.out=1;print(S.before+1)\}\\ L&→\{L_1.before=L.before, \\&\ \ \ \ \ \ \ \ \ \ \ S.before=L.before+L_1.out+1\} \\&\ \ \ \ \ \ \ \ \ \ \ L_1,S \\&\ \ \ \ \ \ \ \ \ \ \ \{L.out=L_1.out+S.out+1\}\\ L&→\{S.before=L.before\}S\{L.out=S.out\} \end{aligned}$
同理上述翻译方案栈代码如下：
$S′→{S.before=P.s}PSP→ϵ{P.s=0}Stack[ntop]=0S→({Q.i=S.before,L.before=Q.s}QL){S.out=L.out+2}Q→ϵ{Q.s=Q.i+1}Stack[ntop]=Stack[top−1]+1S→a{print(S.before)}print(Stack[top−1])L→{L1.before=L.before,R.i=L.before+L1.out+1,S.before=R.s}L1,RS{L.out=L1.out+S.out+1}Stack[ntop]=Stack[top−3]+Stack[top]+1R→ϵ{R.s=R.i}Stack[ntop]=Stack[top−2]+Stack[top−1]+1L→{S.before=L.before}S{L.out=S.out}Stack[ntop]=Stack[top]\begin{aligned} S'&→\{S.before=P.s\}PS\\ P&→\epsilon\{P.s=0\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop]=0\\ S&→(\{Q.i = S.before,L.before = Q.s\} \\&\ \ \ \ \ \ \ \ \ \ \ QL) \\&\ \ \ \ \ \ \ \ \ \ \ \{S.out=L.out+2\} \\ Q&→\epsilon\{Q.s=Q.i+1\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop]= Stack[top-1]+1\\ S&→a\{print(S.before)\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ print(Stack[top-1])\\ L&→\{L_1.before=L.before, \\&\ \ \ \ \ \ \ \ \ \ \ R.i=L.before+L_1.out+1, \\&\ \ \ \ \ \ \ \ \ \ \ S.before=R.s\} \\&\ \ \ \ \ \ \ \ \ \ \ L_1,RS \\&\ \ \ \ \ \ \ \ \ \ \ \{L.out=L_1.out+S.out+1\} \ \ \ \ \ \ \ \ \ Stack[ntop]=Stack[top-3]+Stack[top]+1 \\ R&→\epsilon\{R.s=R.i\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop] = Stack[top-2]+Stack[top-1]+1\\ L&→\{S.before=L.before\}S \\& \ \ \ \ \ \ \ \{L.out=S.out\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Stack[ntop]=Stack[top] \end{aligned}$

属性栈代码：

如何在自底向上分析中计算继承属性？
- 属性栈上仅能存放综合属性
- 分析栈中符号的继承属性
  - 属性copy规则
    如果， $A \to X Y$ ，有语义规则 $Y . i := X . s$ ，
    翻译方案可写为：
    $A → X \{ Y.i := X.s \} Y$
- 从句柄下面取继承属性!

举个栗子

有如下文法与翻译方案

 D→T { L.in := T.type }  L 			T→int { T.type := integer }T→real	{ T.type := real }L→ { L1.in := L.in }L1 , id {addtype(id.entry, L.in) }L→id { addtype(id.entry, L.in) }