语法制导的翻译 个翻译是符号串对的一个集合。在一个编译程 序定义的翻译中,符号串对是源程序和目标程序 各个编译阶段定乂一个翻译,词法分析:(字符 串,单词串)语法分析:(单词串,语法树)代 码生成(语法树,汇编语言) 设Σ是输入字母表且Δ是输出字母表。定义由语言 Llc∑*到语言L2cΔ*的一个翻译是由∑*到△*的 个关系T使得T的定义域为L1且T的值域为L2 使(xy)∈T的句子y叫做x的一个输出
语法制导的翻译 • 一个翻译是符号串对的一个集合。在一个编译程 序定义的翻译中，符号串对是源程序和目标程序。 各个编译阶段定义一个翻译，词法分析：（字符 串，单词串）语法分析：（单词串，语法树）代 码生成（语法树，汇编语言） • 设是输入字母表且是输出字母表。定义由语言 L1 *到语言L2 *的一个翻译是由*到 *的 一个关系T,使得T的定义域为L1且T的值域为L2 。 使(x,y) ∈T的句子y叫做x的一个输出
语法制导的翻译 直观地说,一个语法制导翻译的基础是一个文法, 其中翻译成分依附在每一产生式上。 ·例84:下列翻译模式,它定义翻译,即对每个输入ⅹ, 其输出y是x的逆转。定义此翻译的规则是 产生式 翻译规则 (1)s→>0s (1)s=s0 (2)s→>1s (2)s=s1 (3)s→>ε (3)s=ε
语法制导的翻译 • 直观地说，一个语法制导翻译的基础是一个文法， 其中翻译成分依附在每一产生式上。 • 例8.4： 下列翻译模式，它定义翻译，即对每个输入x， 其输出y是x的逆转。定义此翻译的规则是 产生式 翻译规则 (1)s→0s (2)s→1s (3)s→ ε (1)s=s0 (2)s=s1 (3)s=ε
输入输出对可由(αx,β)表示,其中α是输入句子形式 而β是输出句子形式。 (S,S)开始用产生式S→>0s来扩展得到(0SS0) 再用一次规则(1),得到(0S,S00 再用规则(2),就得到(001S,S100) 然后应用规则(3)并得到(001,100)
输入输出对可由(,)表示，其中是输入句子形式 而是输出句子形式。 (S,S)开始用产生式s→0s来扩展得到(0S,S0). 再用一次规则(1)，得到(00S,S00)。 再用规则(2)，就得到(001S,S100). 然后应用规则(3)并得到(001,100)
例85: 把下述产生式定义的算术表达式映射到后缀波兰表 产生式 翻译规则 E-E+T E=ET+ E→)T E=T T→T*F TTFa T→F T=F F→>(E) F=E F→>a F=a
• 例8.5： 把下述产生式定义的算术表达式映射到后缀波兰表 示： E→E+T E →T T →TF T →F F →(E) F →a E=ET+ E=T T=TF T=F F=E F=a 产生式 翻译规则
确定输入a+a*a的输出: (E,E)→(E+T,ET+) →(T+T,TT+) →(F+T,FT+) →(a+T,aT+) →(a+T*FaFF*+) →(a+F*F,aFF*+) →(a+a*F2aF* →(a+a*a,a*+)
• 确定输入a+aa的输出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+TF,aFF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+)