Microsoft PowerPoint - SyntaxDirectedTranslation [Compatibility Mode]

Size: px

Start display at page:

Download "Microsoft PowerPoint - SyntaxDirectedTranslation [Compatibility Mode]"

制刁
5 years ago
Views:

1 Outline rror Handling Syntax-Directed Translation xtensions of CFG for parsing Precedence declarations rror handling Semantic actions Constructing a parse tree Originated from Prof. Aiken CS 14 Modified by Yu Zhang 1 2 rror Handling Purpose of the compiler is To detect non-valid programs To translate the valid ones Many kinds of possible errors (e.g. in C) rror kind xample Detected by exical $ exer Syntax x *% Parser Semantic int x; y = x(); Type checker Correctness your favorite program Tester/User Syntax rror Handling rror handler should Report errors accurately and clearly Recover from an error quickly Not slow down compilation of valid code Good error handling is not easy to achieve 4 Approaches to Syntax rror Recovery From simple to complex Panic mode rror productions Automatic local or global correction Not all are supported by all parser generators rror Recovery: Panic Mode Simplest, most popular method When an error is detected: Discard tokens until one with a clear role is found Continue from there Such tokens are called synchronizing tokens Typically the statement or expression terminators 6 1

2 Syntax rror Recovery: Panic Mode (Cont.) Consider the erroneous expression ( ) + Panic-mode recovery: Skip ahead to next integer and then continue ison: use the special terminal error to describe how much input to skip int + ( ) error int ( error ) Syntax rror Recovery: rror Productions Idea: specify in the grammar known common mistakes ssentially promotes common errors to alternative syntax xample: Write x instead of * x Add the production Disadvantage Complicates the grammar 7 8 rror Recovery: ocal and Global Correction Idea: find a correct nearby program Try token insertions and deletions xhaustive search Disadvantages: Hard to implement Slows down parsing of correct programs Nearby is not necessarily the intended program Not all tools support it Syntax rror Recovery: Past and Present Past Slow recompilation cycle (even once a day) Find as many errors in one cycle as possible Researchers could not let go of the topic Present Quick recompilation cycle Users tend to correct one error/cycle Complex error recovery is less compelling Panic-mode seems enough 9 10 Abstract Syntax Trees So far a parser traces the derivation of a sequence of tokens The rest of the compiler needs a structural representation of the program Abstract syntax trees ike parse trees but ignore some details Abbreviated as AST 11 Abstract Syntax Tree. (Cont.) Consider the grammar int ( ) + And the string + (2 + ) After lexical analysis (a list of tokens) int + ( int 2 + int ) During parsing we build a parse tree 12 2

3 xample of Parse Tree xample of Abstract Syntax Tree + Traces the operation of the parser PUS PUS int ( ) Does capture the nesting structure 2 + int 2 int ut too much info Parentheses Single-successor nodes Also captures the nesting structure ut abstracts from the concrete syntax => more compact and easier to use An important data structure in a compiler 1 14 Semantic Actions This is what we ll use to construct ASTs ach grammar symbol may have attributes For terminal symbols (lexical tokens) attributes can be calculated by the lexer ach production may have an action Written as: X Y 1 Y n { action } That can refer to or compute symbol attributes Semantic Actions: An xample Consider the grammar int + ( ) For each symbol X define an attribute X.val For terminals, val is the associated lexeme For non-terminals, val is the expression s value (and is computed from values of subexpressions) We annotate the grammar with actions: int {.val = int.val } {.val = 1.val + 2.val } ( 1 ) {.val = 1.val } 1 16 Semantic Actions: An xample (Cont.) Semantic Actions: Notes String: + (2 + ) Tokens: int + ( int 2 + int ) Productions quations val = 1.val + 2.val 1 int 1.val = int.val = 2 ( ) 2.val =.val 4 +.val = 4.val +.val 4 int 2 4.val = int 2.val = 2 int.val = int.val = 17 Semantic actions specify a system of equations ---- 语法制导的定义 Order of resolution is not specified xample:.val = 4.val +.val Must compute 4.val and.val before.val We say that.val depends on 4.val and.val The parser must find the order of evaluation 18

4 Dependency Graph int + ( + ) ach node labeled has one slot for the val attribute Note the dependencies valuating Attributes An attribute must be computed after all its successors in the dependency graph have been computed In previous example attributes can be computed bottom-up 4 + int 2 2 int Such an order exists when there are no cycles Cyclically defined attributes are not legal Dependency Graph int ( ) Semantic Actions: Notes (Cont.) Synthesized attributes ( 综合属性 ) Calculated from attributes of descendents in the parse tree.valis a synthesized attribute Can always be calculated in a bottom-up order int 2 2 int Grammars with only synthesized attributes are called S-attributed grammars Most common case Inherited Attributes ( 继承属性 ) Another kind of attribute Calculated from attributes of parent and/or siblings in the parse tree xample: a line calculator A ine Calculator ach line contains an expression int + ach line is terminated with the = sign = + = In second form the value of previous line is used as starting value A program is a sequence of lines P P

5 Attributes for the ine Calculator ach has a synthesized attribute val Calculated as before ach has an attribute val = {.val =.val } + = {.val =.val +.prev } We need the value of the previous line We use an inherited attribute.prev Attributes for the ine Calculator (Cont.) ach P has a synthesized attribute val The value of its last line P { P.val = 0 } P 1 { P.val =.val;.prev = P 1.val } ach has an inherited attribute prev.previs inherited from sibling P 1.val xample 2 26 xample of Inherited Attributes xample of Inherited Attributes P val synthesized P val synthesized P = 4 + int 2 2 int prev inherited All can be computed in depth-first order P = int 2 2 int prev inherited All can be computed in depth-first order 语法制导的定义 (Syntax-directed Definition) Semantic Actions: Notes (Cont.) 形式 Semantic actions can be used to build ASTs 基础的上下文无关文法每个文法符号有一组属性每个文法产生式 A 有一组形式为 And many other things as well b = f(c 1, c 2,, c k ) 的语义规则, 其中 : f 是函数 Also used for type checking, code generation, b 和 c 1, c 2,, c k 是该产生式文法符号的属性, 综合属性 (synthesized attribute): 如果 b 是 A 的属性,c 1, c 2,, c k 是产生式右部文法符号的属性或 A 的其它属性 Process is called syntax-directed translation 继承属性 (inherited attribute): 如果 b 是右部某文法符号 X 的 Substantial generalization over CFGs 属性 S 属性定义 : 仅使用综合属性的语法制导定义属性定义 : 使用综合属性 + 属性的语法制导定义属性 : 表示属性信息自左向右流动 0

6 Constructing An AST We first define the AST data type Supplied by us for the project Consider an abstract tree type with two constructors: mkplus( mkleaf(n), ) = = n PUS Constructing a Abstract Syntax Tree We define a synthesized attribute ast Values ofast values are ASTs We assume that int.lexval is the value of the integer lexeme Computed using semantic actions int.ast = mkleaf(int.lexval) ast = mkplus( 1.ast, 2.ast) ( 1 ).ast = 1.ast T 1 T 2 T 1 T AST xample Consider the string int + ( int 2 + int ) A bottom-up evaluation of the ast attribute:.ast = mkplus(mkleaf(), mkplus(mkleaf(2), mkleaf()) PUS PUS Summary We can specify language syntax using CFG A parser will answer whether s (G) and will (implicitly) build a parse tree which we convert to an AST and pass on to the rest of the compiler 2 4 例题 1 下面是产生字母表 = {0, 1, 2} 上数字串的一个文法 : S DSD 2 D 0 1 写一个语法制导定义, 判断它接受的句子是否为回文数对文法拓广, 新增 S 代表整个输入串 S 的匿名属性的定义 S S print(s.val) S D 1 S 1 D 2 S.val =(D 1.val == D 2.val)andS 1.val S 2 S.val = true D 0 D.val =0 D 1 D.val =1 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入时,S.val =.62( 可以修改文法 ) 若按来计算, 该文法对小数点左边部分的计算不利, 因为需要继承属性来确定每个离开小数点的距离 S S

7 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入时,S.val =.62( 可以修改文法 ) 若小数点左边按 (1 2+0) 2+1 计算该办法不能直接用于小数点右边, 需改成 ((1 2+0) 2+1)/2, 这时需要综合属性来统计的个数 S S 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入时,S.val =.62( 可以修改文法 ) 更清楚的办法是将文法改成下面的形式 S.R R R 0 1 S. R R R 例题 2 S.R S.val =.val +R.val S S.val =.val 1.val = 1. val 2+.val.val =.val R R 1 R. val =R 1. val /2+.val /2 R R.val =.val /2 0.val =0 1.val =1 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义例如, 因为和是左结合, ((a (b + c )) (d )) 可以重写成 a (b + c ) d 两种方法 : 先把表达式的括号都去掉, 然后在必要的地方再加括号去掉表达式中的冗余括号, 保留必要的括号第一种方法 S print(. code ) 1 + T if T. op == plus then.code = 1.code + ( T.code ) else. code = 1. code + T. code;. op = plus T. code = T. code;. op = T. op T T 1 F if (F. op == plus)or(f. op == times)then if T 1. op == plus then T. code = ( T 1. code ) ( F. code ) else T. code = T 1. code ( F. code ) else if T 1. op = plus then T. code = ( T 1. code ) F. code else T. code = T 1. code F. code; T. op = times 7

8 T F T. code = F. code; T. op = F. op F id F. code = id. lexeme; F. op = id F ( ) F. code =. code; F. op =. op 第二种方法给,T 和 F 两个继承属性 left_op 和 right_op 分别表示左右两侧算符的优先级给它们一个综合属性 self_op 表示自身主算符的优先级再给一个综合属性 code 表示没有冗余括号的代码分别用 1 和 2 表示加和乘的优先级, 用表示 id 和 () 的优先级, 用 0 表示左侧或右侧没有运算对象的情况 S. left_op =0;. right_op =0;print (. code ) 1 + T 1. left_op =. left_op; 1. right_op =1; T. left_op =1;T. right_op =. right_op;.code = 1.code + T. code ;. self_op =1; T T. left_op =. left_op; T. right_op =. right_op;. code = T. code;. self_op = T. self_op T T 1 F... T F... F id F. code = id. lexeme; F. self_op = F ( ). left_op =0;. right_op =0; F. self_op = if (F. left_op <. self_op)and (. self_op >= F. right_op) then. self_op else F. code = if (F. left_op <. self_op)and (. self_op >= F. right_op) then. code else (. code ) 8

2/80 2

2/80 2 2/80 2 3/80 3 DSP2400 is a high performance Digital Signal Processor (DSP) designed and developed by author s laboratory. It is designed for multimedia and wireless application. To develop application