第3,4次课 一个简单的语法制导翻译器 2.3~2.5

中缀表达式转后缀表达式 本次课主要内容都是基于如何将中缀表达式转换为后缀表达式 9 – 5 + 2 -> 95-2+

2.3语法制导翻译的定义

第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 例如：将中缀表达式转化成为后缀 9 - 5 + 2  9 5 – 2 +  ？ list digit 9 - 5 + 2

第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案

第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(syntax-directed definition) expr.t = 95-2+ 语法制导翻译 语法制导定义(syntax-directed definition) 每个文法符号和一个属性集合相关联 例树中”.t”是属性 每个产生式和一组语义规则相关联 例子：9-5+2 expr.t = 95- + term.t = 2 expr.t = 9 - term.t = 5 2 term.t = 9 5 9 产生式 语义规则 expr  expr1 + term expr.t = expr1.t || term.t || ‘+’ expr  expr1 - term expr.t = expr1.t || term.t || ‘-’ expr  term expr.t = term.t term  0 term.t = ‘0’ term  1 term.t = ‘1’ … term  9 term.t = ‘9’

第二章 一个简单的语法制导翻译器 语法制导翻译 属性 综合属性 继承属性 如果某个属性在语法分析树节点N上的值由N的子节点和N本身的属性值确定，则该属性为综合属性 继承属性 如果某个属性由语法分析树中该节点本身、父节点以及兄弟节点上的属性值决定，则该属性为继承属性

后缀表达式（postfix notation）：E 第二章 一个简单的语法制导翻译器 后缀表达式（postfix notation）：E 如何E是一个变量或常量，则E的后缀是本身 如果E是一个形如E1 op E2的表达式，op是二目运算符，那么E的后缀表示是：E1’ E2’ op，这里E1’ 和E2’分别是E1和E2的后缀表示 如果E是一个形如（E1）的表达式，则E的后缀表示就是E1的后缀表示

第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(syntax-directed definition) expr.t = 95-2+ 语法制导翻译 语法制导定义(syntax-directed definition) 每个文法符号和一个属性集合相关联 例树中”.t”是属性 每个产生式和一组语义规则相关联 expr.t = 95- + term.t = 2 expr.t = 9 - term.t = 5 2 term.t = 9 5 9 后缀表达式 产生式 语义规则 expr  expr1 + term expr.t = expr1.t || term.t || ‘+’ expr  expr1 - term expr.t = expr1.t || term.t || ‘-’ expr  term expr.t = term.t term  0 term.t = ‘0’ term  1 term.t = ‘1’ … term  9 term.t = ‘9’

第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(syntax-directed definition) expr.t = 95-2+ 语法制导翻译 语法制导定义(syntax-directed definition) 每个文法符号和一个属性集合相关联 例树中”.t”是属性 每个产生式和一组语义规则相关联 expr.t = 95- + term.t = 2 expr.t = 9 - term.t = 5 2 term.t = 9 5 9 产生式 语义规则 expr  expr1 + term expr.t = expr1.t || term.t || ‘+’ expr  expr1 - term expr.t = expr1.t || term.t || ‘-’ expr  term expr.t = term.t term  0 term.t = ‘0’ term  1 term.t = ‘1’ … term  9 term.t = ‘9’ 简单语法制导定义

第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(syntax-directed definition) 深度优先遍历 expr.t = 95-2+ 语法制导翻译 语法制导定义(syntax-directed definition) 深度优先遍历 expr.t = 95- + term.t = 2 expr.t = 9 - term.t = 5 2 term.t = 9 5 9 产生式 语义规则 expr  expr1 + term expr.t = expr1.t || term.t || ‘+’ expr  expr1 - term expr.t = expr1.t || term.t || ‘-’ expr  term expr.t = term.t term  0 term.t = ‘0’ term  1 term.t = ‘1’ … term  9 term.t = ‘9’ procedure visit ( node N) { for(从左到右遍历N的每个子节点C) { visit(C); } 按照节点N上的语义规则求值; 深度优先，自底向上，综合属性

第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案 将程序片段附加到一个文法的各个产生式上的表示法 rest  + term { print ( ‘ + ‘ ) } rest1

第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案 将程序片段附加到一个文法的各个产生式上的表示法 被嵌入到产生式体中的程序片段成为语义动作（semantic action）。语义动作用花括号括起来。 rest  + term { print ( ‘ + ‘ ) } rest1 rest + term {print(‘+’)} rest1

第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案 将程序片段附加到一个文法的各个产生式上的表示法 如何E是一个变量或常量，则E的后缀是本身 如果E是一个形如E1 op E2的表达式，op是二目运算符，那么E的后缀表示是：E1’ E2’ op，这里E1’ 和E2’分别是E1和E2的后缀表示 如果E是一个形如（E1）的表达式，则E的后缀表示就是E1的后缀表示 ( 9 – 5 ) + 2  9 5 – 2 + ? 　　 9 5 2 + - 3 *

第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案 expr expr + term {print(‘+’)} expr - term {print(‘-’)} 2 {print(‘2’)} term 5 {print(‘5’)} 9 {print(‘9’)} 翻译方案 expr  expr1 + term {print(‘+’)} expr  expr1 – term {print(‘-’)} expr  term term  0 {print(‘0’)} term  1 {print(‘1’)} … term  9 {print(‘9’)}

总结 语法制导的定义 后缀表达式 语法制导的翻译方案

2.4语法分析

第二章 一个简单的语法制导翻译器 语法分析 决定如何使用一个文法生成一个终结符号串的过程 给定输入： 输出：？ 终结符号串：9 　–　 5　 +　2 文法： list  list + digit list  list - digit list  digit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 输出：？

第二章 一个简单的语法制导翻译器 语法分析 决定如何使用一个文法生成一个终结符号串的过程 给定输入： 输出：？ 终结符号串：9 　–　 5　 +　2 文法： list  list + digit list  list - digit list  digit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 输出：？ list digit 9 - 5 + 2

第二章 一个简单的语法制导翻译器 语法分析 决定如何使用一个文法生成一个终结符号串的过程 上下文无关文法 通常Parsing的时间复杂度是O(n3) 对于程序设计语言，时间复杂度是O(n) 自顶向下方法 自底向上方法

第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 例：给定文法： stmt  expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr  ε | expr

第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 stmt  expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr  ε | expr 输入是：for ( ; expr ; expr ) other

第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 stmt  expr ; | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr  ε | expr 输入是：for ( ; expr ; expr ) other stmt for ( optexpr ; optexpr ; optexpr ) stmt ε expr expr other

stmt 语法 分析树 other 输入 for ( ; expr ; expr )

stmt 语法 分析树 other 输入 for ( ; expr ; expr ) 语法 分析树 other for ( ; expr ; optexpr ; optexpr ; optexpr ) stmt other for ( ; expr ; expr ) 输入 stmt

stmt 语法 分析树 other 输入 for ( ; expr ; expr ) 语法 分析树 other for ( ; expr ; optexpr ; optexpr ; optexpr ) stmt other for ( ; expr ; expr ) 输入 stmt 语法 分析树 for ( optexpr ; optexpr ; optexpr ) stmt other for ( ; expr ; expr ) 输入

第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程 —— 回溯 预测语法分析法：不需要回溯 要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。 FIRST集合 令α是一个文法符号（终结符号或非终结符号）串， FIRST(α)是由α生成的一个或多个终结符号串的第一个符号的集合。 如果α是ε或者可以生成ε ，那么ε也在FIRST(α)中

第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程 —— 回溯 预测语法分析法：不需要回溯 要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。 有两个产生式A  α和Aβ，预测分析法要求FIRST(α)和FIRST(β)不相交 如果输入符号在FIRST(α)中，就用A  α，如果输入符号在FIRST(β)中，就用A  β

第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 预测分析法 stmt  expr ; | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr  ε | expr FIRST(stmt) = {expr, if, for, other} FIRST(expr ;) = { expr }

match(expr); match(‘;’); break; case if: void stmt() { switch(lookahead) { case expr: match(expr); match(‘;’); break; case if: match(if); match(‘(’); match(expr); match(‘)’); stmt(); break; case for: match(for); match(‘(’); optexpr(); match(‘;’); optexpr(); match(‘;’); optexpr(); match(‘)’); stmt(); break; case other: match(other); break; default: report(“syntax error”); } stmt  expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other

第二章 一个简单的语法制导翻译器 void optexpr() { if(lookahead == expr) match(expr); } void match(terminal t) { if(lookahead == t) lookahead = nextTerminal; else report(“syntax error”); }

第二章 一个简单的语法制导翻译器 void optexpr() { if(lookahead == expr) match(expr); } 何时使用ε产生式 输入：for ( ; expr ; expr ) other void match(terminal t) { if(lookahead == t) lookahead = nextTerminal; else report(“syntax error”); }

第二章 一个简单的语法制导翻译器 设计一个预测分析器 嵌入翻译方案 对应于非终结符A： 翻译动作作为一个非终结符 检查向前看符号，决定使用A的哪个产生式。如果一个产生式的体为α(α不是空串ε)，且向前看符号在FIRST(α)中，那么就选择这个产生式。 然后，模拟被选中的产生式的体，也就是，从左向右逐个执行此产生式体的符号。“执行”就是调用相应非终结符的过程。 嵌入翻译方案 翻译动作作为一个非终结符

第二章 一个简单的语法制导翻译器 语法分析 左递归 可能使递归下降语法分析器进入无限循环 例： expr  expr + term | term expr expr term expr term … expr term …

第二章 一个简单的语法制导翻译器 语法分析 消除左递归 A  A α | β A  β R R  α R | ε A … A A A .,. R R β α … Ɛ

左递归 消除左递归，并构建语法树 9-5+2 A  A α | β A  β R R  α R | ε expr expr +term | term expr expr -term | term

2.5简单表达式的翻译器

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译方案 中缀表达式 翻译成 后缀表达式 翻译方案 expr  expr1 + term {print(‘+’)} expr  expr1 – term {print(‘-’)} expr  term term  0 {print(‘0’)} term  1 {print(‘1’)} … term  9 {print(‘9’)}

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： A  γR 中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： 消除左递归 A  γR R  αR | βR | ε A  Aα | Aβ | γ

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： 中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： expr  expr + term {print(‘+’)} | expr - term {print(‘-’)} | term term  0 {print(‘0’)} | 1 {print(‘1’)} … | 9 {print(‘9’)} expr  term rest rest  + term {print(‘+’)} rest | - term {print(‘- ’)} rest | ε term  0 {print(‘0’)} | 1 {print(‘1’)} … | 9 {print(‘9’)} 消除左递归

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译过程图解： 9 {print(‘9’)} 中缀表达式 翻译成 后缀表达式 翻译过程图解： expr  term rest rest  + term {print(‘+’)} rest | - term {print(‘- ’)} rest | ε term  0 {print(‘0’)} | 1 {print(‘1’)} … | 9 {print(‘9’)} expr term rest 9 {print(‘9’)} - term {print(‘-’)} rest 5 {print(‘5’)} + term {print(‘+’)} rest ε 2 {print(‘2’)}

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 非终结符的过程 中缀表达式 翻译成 后缀表达式 非终结符的过程 expr  term rest void expr() { term(); rest() }

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 非终结符的过程 中缀表达式 翻译成 后缀表达式 非终结符的过程 rest  + term {print(‘+’)} rest | - term {print(‘- ’)} rest | ε void rest () { if( lookahead == ‘+’) { match(‘+’); term(); print(‘+’); rest(); } else if( lookahead == ‘-’) { match(‘-’); term(); print(‘-’); rest(); else { } /*不对输入作任何处理*/

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 非终结符的过程 中缀表达式 翻译成 后缀表达式 非终结符的过程 term  0 {print(‘0’)} | 1 {print(‘1’)} … | 9 {print(‘9’)} void term() { if( lookahead是一个数位) { t = lookahead; match(lookahead); print(t); } else {report(“语法错误”);}

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () { 中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () { if( lookahead == ‘+’) { match(‘+’); term(); print(‘+’); rest(); } else if( lookahead == ‘-’) { match(‘-’); term(); print(‘-’); rest(); else { } /*不对输入作任何处理*/

第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () { 中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () { while(true) { if( lookahead == ‘+’) { match(‘+’); term(); print(‘+’); continue; } else if( lookahead == ‘-’) { match(‘-’); term(); print(‘-’); continue; break;

重点 语法制导定义 语法制导翻译方案 中缀表达式转后缀表达式 深度优先遍历语法树 自顶向下分析的语法分析 FIRST集合 消除左递归 个简单的语法制导翻译器的实现

作业 给定以下语句，清除空行，注释，提取变量名，变量和数值 用C++/Python实现，仅限于下文中的情况 int a; int b; a = 2; // comment 1 b = a + 12; /* comment 2 */