语法制导翻译

编译器在做语法分析的过程中，除了回答程序语法是否合法外，还必须完成后续工作
- 可能的工作包括（但不限于）
  - 类型检查
  - 目标代码生成
  - 中间代码生成
  - (dots)
这些后续的工作一般可通过语法制导的翻译完成

基本思想

给每条产生式规则附加一个语义动作
- 一个代码片段
语义动作在产生式“归约”时执行
- 即当右部分析完毕时刻
- 由右部的值计算左部的值
- 自顶向下分析和自底向上分析采用的技术类似
  - 接下来重点讨论在自底向上的技术中的语法制导翻译

LR 分析中的语法制导翻译

示例

首先创建一个 .y 文件：

%{

#include <stdio.h>

#include <stdlib.h>

int yylex();

void yyerror();

%}


%left '+'


%%


lines: line

     | line lines

;


line: exp'
';


exp: n

   | exp '+' exp

;


n: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0';


%%


int yylex()

{

        return getchar();

}


void yyerror(char *s)

{

        fprintf(stderr, "%s
", s);

        return;

}


int main(int argc, char ** argv)

{

        yyparse();

        return 0;

}

在上面的代码中附加几个语义动作，该语义动作将在产生时进行规约的时候执行。

语义动作使用 {} 括起来，其中 $$ 表示产生式左部， $n 表示产生式有部的第 n 个元素。

然后使用 bison 和 gcc 编译运行程序，就可以发现每次完成规约之后遇到换行符之后就会直接在屏幕打印输出表达式的值。

实现原理

if (action[s, t] == "ri") {
    ai  // 执行附加语义动作
    pop(βi);
    state s' = stack[top];
    push(X);
    push(goto[s', X]);
}

在分析栈上维护三元组： <symbol, value, state> 其中 symbol 是终结符或非终结符， value 是 symbol 所拥有的值， state 是当前的分析状态。