编译原理——语法制导的语义计算

---

一、基于属性文法的语义计算

（一）属性文法

属性文法（Attribute Grammar）是编译原理中描述语义的重要工具，由上下文无关文法和属性规则两部分组成。

• 属性：与文法符号（终结符或非终结符）相关联的语义信息，如变量类型、表达式值、代码地址等，分为综合属性（从子节点值计算得出，自底向上传递）和继承属性（由父节点或兄弟节点值决定，自顶向下传递）。
• 属性规则：定义属性之间的依赖关系，用于在语法分析过程中完成语义计算。例如，表达式E→E1+E2可定义综合属性E.val = E1.val + E2.val，将子表达式的值相加。

属性文法通过将语义规则与语法规则绑定，使编译器能够在语法分析的同时完成语义处理，为代码生成或错误检测提供依据。

（二）遍历分析树进行语义计算

语义计算的核心是遍历语法分析树，根据属性规则传递属性值：

1. 自底向上遍历：适用于综合属性，从叶子节点到根节点依次计算。例如，计算算术表达式3+5*2时，先计算5*2的属性值，再计算3+该值的结果。
2. 自顶向下遍历：适用于继承属性，从根节点到叶子节点传递信息。例如，在类型检查中，父节点的类型信息（如数组维度）需传递给子节点以验证表达式合法性。
3. 混合遍历：复杂场景下需结合两种方式，如L-属性文法（见后文）需先自顶向下传递继承属性，再自底向上计算综合属性。

遍历过程中，属性值存储在分析树节点中，或通过栈、符号表等数据结构传递。

（三）S-属性文法和L-属性文法

属性文法可分为两类：

1. S-属性文法（S-Attributed Grammar）

   • 特点：仅使用综合属性，所有属性值通过子节点的综合属性计算得出，不依赖继承属性。
   • 实现：适合自底向上的语法分析（如LR分析），在归约时计算属性值。例如，表达式求值可通过S-属性文法在LR分析栈中完成计算。

2. L-属性文法（L-Attributed Grammar）

   • 特点：允许使用继承属性和综合属性，但要求继承属性仅依赖于父节点或左兄弟节点的属性，确保自顶向下或从左到右的遍历顺序可计算属性值。
   • 实现：适合自顶向下的语法分析（如递归下降分析），在分析过程中通过函数参数传递继承属性。例如，在语法树中，父节点的作用域信息可通过继承属性传递给左兄弟节点的变量声明检查。

关系：S-属性文法是L-属性文法的特例（无继承属性），L-属性文法覆盖更广泛的语义场景。

（四）基于S-属性文法的语义计算

示例：算术表达式求值（S-属性文法）
文法规则与属性规则：

E → E1 + T   { E.val = E1.val + T.val }  
E → T        { E.val = T.val }  
T → T1 * F   { T.val = T1.val * F.val }  
T → F        { T.val = F.val }  
F → ( E )    { F.val = E.val }  
F → num      { F.val = num.value }  // num为终结符，val为词法分析传递的数值

计算过程：

• 输入3+5*2，构建分析树后自底向上归约：
  1. 叶子节点3、5、2的val分别为3、5、2。
  2. 归约T1*F（5*2）得T.val=10。
  3. 归约E1+T（3+10）得E.val=13。
     关键：所有属性均为综合属性，仅需在归约时按规则计算，无需回溯或额外传递信息。

（五）基于L-属性文法的语义计算

示例：数组变量类型检查（L-属性文法）
假设文法包含数组声明D→id[num]，需检查数组索引是否为合法整数：

D → id[E]    { id.type = "array"; E.expected_type = "int"; id.size = E.val }  
E → num      { if E.val > 0 then E.type = "int" else error() }  // 继承属性expected_type来自父节点D

计算过程：

• 自顶向下分析D时，父节点通过继承属性E.expected_type指定子节点E必须为整数类型。
• 分析E→num时，检查num的值是否为正整数，若符合则设置E.type="int"，并将num.value传递给id.size（综合属性）。
  关键：继承属性expected_type从父节点D传递到子节点E，确保类型检查在自顶向下遍历时完成，体现了L-属性文法对上下文依赖的处理能力。

小结

属性文法通过属性规则将语法与语义结合，S-属性文法和L-属性文法分别适用于不同的分析场景。实际编译器中，L-属性文法更常见，因其能处理继承属性带来的复杂语义（如作用域、类型传递），而S-属性文法则在简单求值场景中高效便捷。理解两者的差异与应用，是实现语义分析模块的核心基础。

二、基于翻译模式的语义计算

（一）翻译模式

翻译模式（Translation Scheme）是属性文法的一种实现导向形式，它将属性计算以嵌入语义动作的方式直接关联到语法规则中，更明确地描述了语义计算的顺序。

• 核心特点：
  • 用花括号{ ... }包裹语义动作，指定在语法分析的某个特定点（如推导或归约时）执行计算。
  • 支持继承属性和综合属性的计算，但需确保动作执行时所需属性值已可用（如自底向上归约时，子节点属性已计算完成）。
• 与属性文法的区别：
  属性文法定义属性依赖关系，而翻译模式更关注计算顺序，适合指导编译器编写者实现具体的语义逻辑。

（二）基于S-翻译模式的语义计算

S-翻译模式是基于S-属性文法的翻译模式，仅使用综合属性，语义动作仅在归约时执行（适合自底向上分析）。

示例：中缀表达式转后缀表达式（S-翻译模式）
文法规则与语义动作：

E → E1 + T { print('+'); }  
E → T     { /* 空动作 */ }  
T → T1 * F { print('*'); }  
T → F     { /* 空动作 */ }  
F → ( E ) { /* 空动作 */ }  
F → id    { print(id.name); }  

计算过程：

• 输入a+b*c，自底向上归约时触发语义动作：
  1. 归约F→id（a），输出a。
  2. 归约F→id（c），输出c；归约T1*F（b*c），输出*，此时T.val为后缀式bc*。
  3. 归约E1+T（a+bc*），输出+，最终得到后缀式abc*+。
     关键：语义动作在归约结束时执行，依赖子树的综合属性已计算完毕，符合S-属性文法的自底向上特性。

（三）基于L-翻译模式的自顶向下语义计算

L-翻译模式基于L-属性文法，允许使用继承属性，语义动作可在推导时（自顶向下分析）执行，需确保动作中引用的继承属性已传递到位。

示例：带类型声明的变量初始化（自顶向下翻译模式）
文法规则与语义动作（假设T为类型说明符，D为变量声明）：

D → T id { id.type = T.type; } = E { check(E.type == id.type); }  
T → int { T.type = "int"; }  
T → float { T.type = "float"; }  

计算过程：

• 自顶向下推导D时：
  1. 先推导T，设置T.type（如int），通过继承属性传递给id.type。
  2. 遇到=时，推导E并检查其类型是否与id.type一致（如E为浮点型则报错）。
     关键：语义动作在推导T和E时执行，继承属性id.type通过父节点T传递，体现L-属性文法自顶向下的特性。

（四）基于L-翻译模式的自底向上语义计算

虽然L-属性文法通常与自顶向下分析结合，但在自底向上分析中（如LR分析），可通过延迟计算继承属性的方式实现L-翻译模式，具体通过标记非终结符或栈操作传递继承属性。

示例：计算表达式行号（自底向上翻译模式）
引入标记非终结符M传递行号（继承属性）：

S → M E { E.line = M.line; }  
M → ε { M.line = line_num; }  // 词法分析传递当前行号line_num  
E → E1 + T { E.val = E1.val + T.val; E.line = E1.line; }  

计算过程：

• 自底向上归约时：
  1. 归约M→ε，将line_num存入栈中（作为继承属性）。
  2. 归约S→M E时，从栈中取出M.line并赋给E.line。
     关键：通过标记非终结符在栈中暂存继承属性，模拟自顶向下的传递过程，实现L-属性文法在自底向上分析中的应用。

小结

翻译模式是属性文法的工程化实现手段，通过语义动作的显式嵌入，将语法分析与语义计算紧密结合：

• S-翻译模式适用于自底向上分析，聚焦综合属性的归约时计算；
• L-翻译模式灵活支持继承属性，可通过自顶向下推导或自底向上栈操作实现。
  在实际编译器设计中，翻译模式能有效指导语义动作的编写，例如在递归下降分析器中直接嵌入动作代码，或在LR分析器中通过栈管理属性值传递。理解不同翻译模式的适用场景，是实现复杂语义分析（如类型检查、代码生成）的关键。

三，分析和翻译程序的自动生成工具yacc

（一）yacc描述文件

yacc（Yet Another Compiler-Compiler）是一种基于LALR(1)算法的语法分析器生成工具，可根据用户定义的语法规则和语义动作自动生成语法分析器（通常与词法分析器lex/flex配合使用）。yacc的核心是描述文件，其结构分为三部分，以%%分隔：

1. 声明部分（Declarations）

• 语法声明：定义终结符（%token）和非终结符（隐含定义），如：

  %token INT ID PLUS MULTI LPAREN RPAREN
  

• 语义类型声明：指定属性类型（如表达式值的类型），如：

  %union { int num; char* str; }
  %type <num> expr term factor
  %type <str> id
  

• 优先级与结合性声明：解决运算符优先级和结合性冲突，如：

  %left PLUS MINUS
  %left MULTI DIV
  %right UNARY_MINUS
  

2. 语法规则与语义动作部分（Rules and Actions）

定义文法规则及对应的语义动作（嵌入C代码），格式为：

目标非终结符 : 右部符号序列 { 语义动作 };

• 语义动作使用C语言编写，通过$$访问目标非终结符的属性，$1, $2,...访问右部符号的属性。
• 示例：算术表达式求值

  expr : expr PLUS term { $$ = $1 + $3; }| term          { $$ = $1; }
  term : term MULTI factor { $$ = $1 * $3; }| factor        { $$ = $1; }
  factor : LPAREN expr RPAREN { $$ = $2; }| INT           { $$ = atoi($1); }
  

3. 用户子例程部分（User Subroutines）

包含词法分析函数yylex()、错误处理函数yyerror()等，如：

int yylex() { /* 调用lex/flex生成的词法分析器，返回token */ }
void yyerror(char* msg) { fprintf(stderr, "%s\n", msg); }

（二）使用yacc的一个简单例子

需求：构建一个简单计算器，支持整数加减乘除运算（如3+5*2）。

步骤1：编写yacc描述文件（calc.y）

%{
#include <stdio.h>
#include <stdlib.h>
int yylex();
void yyerror(char *s);
%}// 声明终结符
%token INT
%left '+' '-'
%left '*' '/'
%right '^'// 语义类型声明
%union {int num;
}
%type <num> expr term factor%%// 语法规则与语义动作
expr : expr '+' term { $$ = $1 + $3; }| expr '-' term { $$ = $1 - $3; }| term          { $$ = $1; }term : term '*' factor { $$ = $1 * $3; }| term '/' factor { $$ = $1 / $3; }| factor          { $$ = $1; }factor : INT         { $$ = $1; }| '(' expr ')' { $$ = $2; }%%// 用户子例程：错误处理
void yyerror(char *s) {fprintf(stderr, "Error: %s\n", s);
}// 主函数：调用yacc生成的分析器
int main() {yyparse();printf("Result: %d\n", yylval.num); // yylval存储最终结果return 0;
}

步骤2：编写词法分析器（calc.l，使用flex）

%{
#include "calc.tab.h" // 包含yacc生成的token定义
int yylval; // 传递token的属性值（与yacc的%union对应）
%}%%
[0-9]+      { yylval = atoi(yytext); return INT; } // 匹配整数
[ \t\n]     ; // 忽略空白字符
.           { return yytext[0]; } // 其他字符直接返回
%%int yywrap() { return 1; }

步骤3：编译与运行

1. 生成语法分析器代码：

   yacc -d calc.y   # -d选项生成calc.tab.h和calc.tab.c
   

2. 生成词法分析器代码：

   flex calc.l      # 生成lex.yy.c
   

3. 编译可执行文件：

   gcc calc.tab.c lex.yy.c -o calc
   

4. 测试运行：

   ./calc
   输入：3+5*2   # 输出：Result: 13
   

关键说明

• yylval的作用：词法分析器通过yylval向yacc传递token的属性值（如整数的数值）。
• 优先级声明：yacc根据%left/%right声明处理运算符优先级，避免歧义（如3+5*2先乘后加）。
• 错误处理：当输入不符合文法规则时，yacc调用yyerror()提示错误（如3++5会触发语法错误）。

小结

yacc通过描述文件将语法规则与语义动作分离，大幅简化了编译器的开发流程。其核心优势包括：

• 自动处理冲突：通过LALR(1)算法自动检测语法规则的冲突（如移进-归约冲突）。
• 高效集成语义：支持在语法规则中直接嵌入C代码，实现属性计算、代码生成等复杂语义逻辑。
• 与lex/flex无缝协作：词法分析器负责 token 识别，yacc 专注于语法分析和语义计算，形成完整的编译前端流水线。

实际应用中，yacc 的衍生工具（如Bison）进一步扩展了功能，成为构建编译器的重要工具链组件。通过本例可看出，掌握yacc描述文件的结构与语义动作编写，是实现自动化语法分析与语义计算的关键。