Download presentation
Presentation is loading. Please wait.
1
第3,4次课 一个简单的语法制导翻译器 2.3~2.5
2
中缀表达式转后缀表达式 本次课主要内容都是基于如何将中缀表达式转换为后缀表达式 9 – > 95-2+
3
2.3语法制导翻译的定义
4
第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 例如：将中缀表达式转化成为后缀
– 2 + ？ list digit 9 - 5 + 2
5
第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案
6
第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(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’
7
第二章 一个简单的语法制导翻译器 语法制导翻译 属性 综合属性 继承属性
如果某个属性在语法分析树节点N上的值由N的子节点和N本身的属性值确定，则该属性为综合属性 继承属性 如果某个属性由语法分析树中该节点本身、父节点以及兄弟节点上的属性值决定，则该属性为继承属性
8
后缀表达式（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的后缀表示
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’
10
第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(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’ 简单语法制导定义
11
第二章 一个简单的语法制导翻译器 语法制导翻译 语法制导定义(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上的语义规则求值; 深度优先，自底向上，综合属性
12
第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案
将程序片段附加到一个文法的各个产生式上的表示法 rest + term { print ( ‘ + ‘ ) } rest1
13
第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案
将程序片段附加到一个文法的各个产生式上的表示法 被嵌入到产生式体中的程序片段成为语义动作（semantic action）。语义动作用花括号括起来。 rest + term { print ( ‘ + ‘ ) } rest1 rest + term {print(‘+’)} rest1
14
第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案
将程序片段附加到一个文法的各个产生式上的表示法 如何E是一个变量或常量，则E的后缀是本身 如果E是一个形如E1 op E2的表达式，op是二目运算符，那么E的后缀表示是：E1’ E2’ op，这里E1’ 和E2’分别是E1和E2的后缀表示 如果E是一个形如（E1）的表达式，则E的后缀表示就是E1的后缀表示 ( 9 – 5 ) – 2 + ? *
15
第二章 一个简单的语法制导翻译器 语法制导翻译：对语法树进行语义分析 语法制导定义 语法制导翻译方案 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 {print(‘0’)} term {print(‘1’)} … term {print(‘9’)}
16
总结 语法制导的定义 后缀表达式 语法制导的翻译方案
17
2.4语法分析
18
第二章 一个简单的语法制导翻译器 语法分析 决定如何使用一个文法生成一个终结符号串的过程 给定输入： 输出：？
终结符号串：9 – 5 + 2 文法： list list + digit list list - digit list digit digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 输出：？
19
第二章 一个简单的语法制导翻译器 语法分析 决定如何使用一个文法生成一个终结符号串的过程 给定输入： 输出：？
终结符号串：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
20
第二章 一个简单的语法制导翻译器 语法分析 决定如何使用一个文法生成一个终结符号串的过程 上下文无关文法
通常Parsing的时间复杂度是O(n3) 对于程序设计语言，时间复杂度是O(n) 自顶向下方法 自底向上方法
21
第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 例：给定文法： stmt expr | if ( expr ) stmt
| for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr ε | expr
22
第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 stmt expr | if ( expr ) stmt
| for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr ε | expr 输入是：for ( ; expr ; expr ) other
23
第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 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
24
stmt 语法 分析树 other 输入 for ( ; expr ; expr )
25
stmt 语法 分析树 other 输入 for ( ; expr ; expr ) 语法 分析树 other for ( ; expr ;
optexpr ; optexpr ; optexpr ) stmt other for ( ; expr ; expr ) 输入 stmt
26
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 ) 输入
27
第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程 —— 回溯
预测语法分析法：不需要回溯 要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。 FIRST集合 令α是一个文法符号（终结符号或非终结符号）串， FIRST(α)是由α生成的一个或多个终结符号串的第一个符号的集合。 如果α是ε或者可以生成ε ，那么ε也在FIRST(α)中
28
第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程 —— 回溯
预测语法分析法：不需要回溯 要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。 有两个产生式A α和Aβ，预测分析法要求FIRST(α)和FIRST(β)不相交 如果输入符号在FIRST(α)中，就用A α，如果输入符号在FIRST(β)中，就用A β
29
第二章 一个简单的语法制导翻译器 语法分析 自顶向下分析方法 预测分析法
stmt expr ; | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other optexpr ε | expr FIRST(stmt) = {expr, if, for, other} FIRST(expr ;) = { expr }
30
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
31
第二章 一个简单的语法制导翻译器 void optexpr() { if(lookahead == expr) match(expr); }
void match(terminal t) { if(lookahead == t) lookahead = nextTerminal; else report(“syntax error”); }
32
第二章 一个简单的语法制导翻译器 void optexpr() { if(lookahead == expr) match(expr); }
何时使用ε产生式 输入：for ( ; expr ; expr ) other void match(terminal t) { if(lookahead == t) lookahead = nextTerminal; else report(“syntax error”); }
33
第二章 一个简单的语法制导翻译器 设计一个预测分析器 嵌入翻译方案 对应于非终结符A： 翻译动作作为一个非终结符
检查向前看符号，决定使用A的哪个产生式。如果一个产生式的体为α(α不是空串ε)，且向前看符号在FIRST(α)中，那么就选择这个产生式。 然后，模拟被选中的产生式的体，也就是，从左向右逐个执行此产生式体的符号。“执行”就是调用相应非终结符的过程。 嵌入翻译方案 翻译动作作为一个非终结符
34
第二章 一个简单的语法制导翻译器 语法分析 左递归 可能使递归下降语法分析器进入无限循环
例： expr expr + term | term expr expr term expr term … expr term …
35
第二章 一个简单的语法制导翻译器 语法分析 消除左递归 A A α | β A β R R α R | ε A … A A A
.,. R R β α … Ɛ
36
左递归 消除左递归，并构建语法树 9-5+2 A A α | β A β R R α R | ε
expr expr +term | term expr expr -term | term
37
2.5简单表达式的翻译器
38
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译方案
中缀表达式 翻译成 后缀表达式 翻译方案 expr expr1 + term {print(‘+’)} expr expr1 – term {print(‘-’)} expr term term {print(‘0’)} term {print(‘1’)} … term {print(‘9’)}
39
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： A γR
中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： 消除左递归 A γR R αR | βR | ε A Aα | Aβ | γ
40
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案：
中缀表达式 翻译成 后缀表达式 消除左递归的翻译方案： expr expr + term {print(‘+’)} | expr - term {print(‘-’)} | term term {print(‘0’)} | {print(‘1’)} … | {print(‘9’)} expr term rest rest + term {print(‘+’)} rest | term {print(‘- ’)} rest | ε term 0 {print(‘0’)} | 1 {print(‘1’)} … | 9 {print(‘9’)} 消除左递归
41
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译过程图解： 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’)}
42
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 非终结符的过程
中缀表达式 翻译成 后缀表达式 非终结符的过程 expr term rest void expr() { term(); rest() }
43
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 非终结符的过程
中缀表达式 翻译成 后缀表达式 非终结符的过程 rest + term {print(‘+’)} rest | term {print(‘- ’)} rest | ε void rest () { if( lookahead == ‘+’) { match(‘+’); term(); print(‘+’); rest(); } else if( lookahead == ‘-’) { match(‘-’); term(); print(‘-’); rest(); else { } /*不对输入作任何处理*/
44
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 非终结符的过程
中缀表达式 翻译成 后缀表达式 非终结符的过程 term 0 {print(‘0’)} | 1 {print(‘1’)} … | 9 {print(‘9’)} void term() { if( lookahead是一个数位) { t = lookahead; match(lookahead); print(t); } else {report(“语法错误”);}
45
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () {
中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () { if( lookahead == ‘+’) { match(‘+’); term(); print(‘+’); rest(); } else if( lookahead == ‘-’) { match(‘-’); term(); print(‘-’); rest(); else { } /*不对输入作任何处理*/
46
第二章 一个简单的语法制导翻译器 实现一个简单表达式的翻译器 中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () {
中缀表达式 翻译成 后缀表达式 翻译器的简化 void rest () { while(true) { if( lookahead == ‘+’) { match(‘+’); term(); print(‘+’); continue; } else if( lookahead == ‘-’) { match(‘-’); term(); print(‘-’); continue; break;
47
重点 语法制导定义 语法制导翻译方案 中缀表达式转后缀表达式 深度优先遍历语法树 自顶向下分析的语法分析 FIRST集合 消除左递归 个简单的语法制导翻译器的实现
48
作业 给定以下语句，清除空行，注释，提取变量名，变量和数值 用C++/Python实现，仅限于下文中的情况 int a; int b; a = 2; // comment 1 b = a + 12; /* comment 2 */
Similar presentations
