PL0编译程序的实现

1【学习目标】

本章目的：以PL/0语言编译程序为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，为后面的原理学习打下基础。

了解并掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对计算机语言的形式描述。

【难重点】

重点：

弄清源语言(PL/0)目标语言(类pcode)实现语言（pascal）这3个语言之间的关系和作用。

掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对一个高级程序设计语言的语法形式描述。

2

本节讲3个内容。

一、对PL/0语言编译程序的功能用“T”型图表示，从而弄清源语言(PL/0)、目标语言(类pcode)和实现语言（pascal）这3个语言之间的关系和作用。。

3

二、程序设计语言的语法规则（词法和语法）的描述方法有3种。

1、是用自然语言描述；

2、是用语法图描述；用语法图描述首先把语法符号分为二种，终结符和非终结符。所谓终结符，是构成语言的语法成分的最小单位，终结符不能由其它文法符号定义。在语法图中用椭圆和圆圈中的英文字表示终结符。所谓非终结符，是可由其它文法符号定义语法成分。在语法图中用长方形内的中文字表示非终结符。箭头表示该语法成分由那些语法符号按怎样的顺序构成。用语法图描述语法规则的优点是直观、易读。4

例如在PL/0语言中程序是由非终结符‘分程序’和终结符“.”组成的串定义的。所以程序的语法图

可以用下图表示：5分程序的语法图如下：63、用扩充的巴科斯-瑙尔范式(EBNF)给出程序设计语言的语法描述。巴科斯-瑙尔范式（BACKUS-NAURFORM）是根据美国的JohnW.Backus与丹麦的PeterNaur命名的。EBNF表示扩充的巴科斯-瑙尔范式。

(EBNF)给出程序设计语言的语法描述用了6个符号，它们是：

〈〉：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，是非终结符。

∷=：该符号的左部由右部定义，可读作'定义为'。

|：表示'或'，为左部可由多个右部定义。

{}：花括号表示其内的语法成分可以重复。在不加上下界时可重复0到任意次数，有上下界时为可重复次数的限制。

7如：{*}表示*重复任意次，{*}38表示*重复3-8次。

[]：方括号表示其内的成分为任选项。

()：表示圆括号内的成分优先。

例：用EBNF描述<整数>文法的定义：

<整数>∷=[+|-]<数字>{<数字>}

<数字>∷=0|1|2|3|4|5|6|7|8|9

或更好的写法

<整数>∷=[+|-]<非零数字>{<数字>}

<非零数字>∷=1|2|3|4|5|6|7|8|9

<数字>∷=0|<非零数字>

8PL/0语言文法的EBNF表示为：

〈程序〉∷=〈分程序〉．

〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉

〈常量说明部分〉∷=CONST〈常量定义〉{，〈常量定义〉}；

〈常量定义〉∷=〈标识符〉=〈无符号整数〉

〈无符号整数〉∷=〈数字〉{〈数字〉}

〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}；

〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉}

〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}；

9

〈过程首部〉∷=PROCEDURE〈标识符〉

〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉

〈赋值语句〉∷=〈标识符〉∶=〈表达式〉

〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END

〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉

〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉}

〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}

〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')'

10〈加法运算符〉∷=+|-

〈乘法运算符〉∷=*|/

〈关系运算符〉∷=#|=|＜|＜=|＞|＞=

〈条件语句〉∷=IF〈条件〉THEN〈语句〉

〈过程调用语句〉∷=CALL〈标识符〉

〈当型循环语句〉∷=WHILE〈条件〉DO〈语句〉

〈读语句〉∷=READ'('〈标识符〉{，〈标识符〉}')'

〈写语句〉∷=WRITE'('〈表达式〉{，〈表达式〉}')'

〈字母〉∷=a|b|…|X|Y|Z

〈数字〉∷=0|1|2|…|8|9

11三、3种方法的比较与总结:1、用语法图描述语言的语法与EBNF描述相比较：

语法图描述：直观，易读，易写。

EBNF表示：形式化强，易机器识别。

2、语法图或EBNF作为描述程序设计语言语法的工具，那么，问题是能不能让机器掌握这些工具，从而让机器自动检查哪些符号序列是所给语言的合理程序。答案是：EBNF方法的最大好处就是容易在机器上实现。3、下面我们用EBNF给出自然语言汉语的构成规则,并且用这些规则检查一句话是不是正确的汉语：12

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示汉语句子的构成规则〈句子〉∷=〈主语〉〈谓语〉

〈主语〉∷=〈代词〉|〈名词〉

〈代词〉∷=我|你|他

〈名词〉∷=王明|大学生|工人|英语

〈谓语〉∷=〈动词〉〈直接宾语〉

〈动词〉∷=是|学习

〈直接宾语〉∷=〈代词〉|〈名词〉

13

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷=左端的带有〈句子〉的规则并把它表示成∷=右端的符号串，重复做下去。例如我们导出句子“我是大学生”是一句正确的汉语的过程是：〈句子〉=》〈主语〉〈谓语〉

=》〈代词〉〈谓语〉

=》我〈谓语〉

=》我〈动词〉〈直接宾语〉

=》我是〈直接宾语〉

=》我是〈名词〉

=》我是大学生

作业：P31第6题的2，3小题。14第二章简单的一遍编译器ASimpleOnePassCompiler15本章主要内容用C语言开发一个把中缀表达式转换为后缀表达式的翻译程序，展示基本的编译技术主要描述编译器的前端词法分析、语法分析和语义分析通过本章对编译的过程有所了解9*5+x95*x+162.1概述程序设计语言由语法(syntax)和语义(semantics)两个方面定义。语义的描述则比语法的描述难得多，采用非形式式化的自然语言描述上下文无关文法还用于语法制导翻译(syntax-directedtranslation)17如何描述语法Bakus-Naur范式(BNF)SyntaxGraph上下文无关文法ContextFreeGrammar(CFG)18Bakus-Naur范式(BNF)19ExamplesofBNF20SyntaxGraph212.2语法定义语法描述程序设计语言的层次结构，如C语言的条件语句为if_stmt

if(expr)stmtelsestmt if_stmt

if(expr)stmt这样的描述规则称为产生式

(production)。我们用上下文无关文法

(Context-freeGrammar,CFG)来形式化这种描述。22上下文无关文法上下文无关文法CFG是一个四元组

(Vt,Vn,S,P)，其中：Vt

是一个非空有穷集合，称作终结符号集合TerminalSymbolsVn

是一个非空有穷集合，称作非终结符号集合Non-terminals

，且Vt

Vn

=。S

Vn

，称作开始符号StartSymbol

。P是一个非空有穷集合，称为产生式集合ProductionRules，每条产生式形为A

，其中A

Vn，

(Vt

Vn)*。23例2.1简单的算术表达式list

list+digitlist

list-digitlist

digitdigit

0|1|2|3|4|5|6|7|8|9(the“|”meansOR)(Sowecouldhavewrittenlist

list+digit|list-digit|digit)24例2.2上述文法定义的是由加号和减号分隔的数字序列构成的列表。wecanderivethestring:9-5+2asfollows:list

list+

digit

list-digit+digit

digit-digit+digit

9-digit+digit

9-5+digit

9-5+2

P1:list

list+digitP2:list

list-digitP3:list

digitP4:digit

9P4:digit

5P4:digit

225listdigitdigitlistdigitlist952-+list

list+

digit

list-digit+digit

digit-digit+digit

9-digit+digit

9-5+digit

9-5+2

ThisderivationcouldalsoberepresentedviaaParseTree

26例2.3pascal语言的begin_end语句块(block)Whatisthisgrammarfor?Whatdoes“

”represent?Whatkindofproductionruleisthis?block

begin

opt_stmts

endopt_stmts

stmt_list|

stmt_list

stmt_list;stmt|stmt272.2.1分析树(ParseTree)分析树描述如何从文法的开始符号推导出它的语言中的一个语句。如果非终结符A有产生式A

XYZ，则A的一棵分析树为：AXYZ28ParseTree分析树具有如下性质：RootislabeledwiththeStartSymbol

Leafnodeisatokenor

Interiornode(Non-leaf)isaNon-TerminalIfA

x1x2…xn,ThenAisaninterior;x1x2…xnarechildrenofAandmaybenon-terminalsortokens一个文法生成的语言是它的某个分析树生成的串的集合。为给定的符号串找到一棵分析树的过程称为串的语法分析(parsing)。292.2.2二义性AmbiguityWhyisthisaProblem?Grammar:string

string+string|string–string|0|1|…|9对某个文法，如一个句子有两棵以上的分析树，称为二义（歧义）文法。stringstringstringstringstring+2-59stringstringstringstringstring-+259302.2.3AssociativityofOperators可以用括号来表明计算顺序，如

9-5+2=(9-5)+2如果对某个运算符op，x1,x2,x3为运算对象，且x1

op

x2

op

x3

表示(x1

op

x2)opx3，则称op是左结合的；如果x1

op

x2

op

x3

表示x1

op(x2

op

x3)，则称op是右结合的。31right

letter=right|letterletter

a|b|c|…|zlistdigitdigitlistdigitlist952-+list

list+digit|list-digit|digitdigit

0|1|…|9rightletterletterrightletterrightcba==Leftvs.Right322.2.4OperatorPrecedenceWhatdoes9+5*2mean?(9+2)*5or9+(5*2)不同的运算符号有不同的优先级，如9-5*2=9-(5*2)，所以*的优先级比+高。Typically()*/+-isprecedenceorder33expr

expr+term|expr–term|termterm

term*factor|term/factor|factorfactor

digit|(expr)通过适当改写文法规则，可以描述不同的结合律和优先级：PrecedenceAchievedby:expr&termforeachprecedencelevelRulesforeachareleftrecursive

or

associatetotheleft34Pascal语句的语法stmt

id

:=expr

|

ifexpr

thenstmt

|

ifexpr

thenstmtelsestmt

|whileexpr

dostmt

|

beginopt_stmts

end352.3语法制导翻译

Syntax-DirectedTranslation语法是掌握语义的钥匙语法制导定义每个文法符号有属性的集合每个产生式有语义计算规则的集合翻译模式：描述翻译过程一个例子：将中缀表达式翻译成后缀表达式362.3.1后缀表示PostfixNotationIfEisavariableorconstant,thenPostfix(E)=EIfEisE1opE2,thenPostfix(E)=Postfix(E1opE2)=Postfix(E1)Postfix(E2)opIfEis(E1)thenPostfix(E)=Postfix(E1)Examples:(9–5)+2

95–2+9–(5+2)

952+-372.3.2语法制导定义

Syntax-DirectedDefinition每个文法符号有属性的集合(aSetofAttributes)每个产生式有语义计算规则的集合(aSetofSemanticRules)382.3.3中缀到后缀翻译的语法制导定义例2.6

为每个非终结符定义属性“t”，表示其对应的表达式的后缀表示，每条产生式带有语义规则ProductionSemanticRuleexpr

expr1+termexpr.t:=expr1.t||term.t||‘+’expr

expr1–termexpr.t:=expr1.t||term.t||’-’expr

termexpr.t:=term.tterm

0

term.t:=‘0’term

1

term.t:=‘1’….….term

9

term.t:=‘9’39注释分析树综合属性：属性值是由子节点的属性确定的通过遍历分析树可以求得结果计算顺序：深度优先遍历是一种常用的方法expr.t=95-expr.t=9expr.t=95-2+term.t=5term.t=2term.t=92+5-9402.3.5翻译模式也可以把上下文无关文法扩展成翻译模式（也叫翻译文法），不生成分析树来进行属性计算。特点是在产生式的右部插入语义动作

rest

+term{print(‘+’)}rest1翻译模式类似于语法制导定义，只是语义规则的计算顺序是显式给出的。41翻译模式expr

expr+term{print(‘+’)}

expr-term{print(‘-’)}

termterm0

{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}42termtermtermexprexprexpr952-+{print(‘-’)}{print(‘9’)}{print(‘5’)}{print(‘2’)}{print(‘+’)}可以把语义动作看作是特殊的终结符，不匹配输入，语法分析的时候直接执行432.4语法分析(Parsing)两类方法（指构造分析树结点的顺序）自顶向下(top-down)自底向上(bottom-up)自顶向下方法从开始符号开始构造分析树对终结符，看是否与输入匹配（否则回溯）对非终结符，选择一个产生式构造子树44type

simple

|

id|

array[simple]of

typesimple

integer|char|numdotdotnum2.4.1自顶向下语法分析的例子Suppose

input

is:array[numdotdotnum]ofintegerTheparsewouldbeginwithstartsymbol

type

array[simple]oftype45type]simpleof[arraytypenumnumdotdot]simpleof[arraytypetypetype46numnumdotdot]simpleof[arraytypetypesimplenumnumdotdot]simpleof[arraytypetypesimpleinteger472.4.2递归下降和预测分析法RecursiveDescentandPredictiveParsing上述分析过程可以用递归下降法来实现：每个非终结符对应一个递归过程如果我们根据输入能确定地选取要扩展的产生式（或要调用的子过程），则称为预测分析法。48procedure

match(t:token);beginiflookahead

=t

then

lookahead:=nexttoken

elseerrorend;49proceduretype;beginiflookaheadisin{integer,char,num}then

simple

elseif

lookahead

=‘’thenbegin

match(‘’);match(id)

endelseiflookahead

=arraythenbegin

match(array);match(‘[‘);simple;

match(‘]’);match(of);typeendelseerrorend;type

simple|id

|array[simple]of

type50proceduresimple;beginiflookahead

=integerthen

match(integer);

elseiflookahead

=charthen

match(char);

elseiflookahead

=numthenbegin

match(num);match(dotdot);match(num)

endelseerrorend;simple

integer|char|numdotdotnum51ProblemwithTopDownParsing如果A|，预测分析法要求

和

的开始符号集合(First集合)能够区分，即不相交First(

)

First(

)=

。如果文法中存在左递归，采用递归下降法会导致无穷循环。为此，需要改写产生式来消除左递归。

expr

expr+term52改写产生式来消除左递归：

A

A

|

可以改成

A

B

B

B|

两者产生的语言都是

*532.5简单表达式的翻译器expr

expr+term{print(‘+’)}

expr-term{print(‘-’)}

termterm0

{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}中缀到后缀的初始翻译模式54初始的文法是左递归的，需要变换。变换时，把语义动作也看成是文法符号

expr

expr1+term{printf(‘+’)}

expr

expr1–term{printf(‘-’)}

expr

term变换成

expr

term

rest

rest

+term{printf(‘+’)}rest |-term{printf(‘-’)}rest|

55修改后的翻译模式expr

term

restrest

+term

{printf(‘+’)}

rest |

-term

{printf(‘-’)}

rest

|

term0

{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}56从9-5+2到95-2+的翻译{print(‘2’)}exprtermterm{print(‘-’)}term{print(‘+’)}rest{print(‘5’)}{print(‘9’)}restrest25-9+

57expr(){ term();rest();}rest(){ if(lookahead==‘+’){ match(‘+’);term();putchar(‘+’);rest();} elseif(lookahead==‘-’){ match(‘-’);term();putchar(‘-’);rest();} else;}term(){ if(isdigit(lookahead)){ putchar(lookahead);match(lookahead); }elseerror();}非终结符expr、rest和term的函数582.6词法分析为上面的翻译器增加一个词法分析器。去除blank（空格、tab、换行）、注释识别整型常数识别标识符和关键字Token用<type,attributes>表示手工编写的简单词法分析器lexan()59在输入和语法分析器之间插入词法分析器词法分析器语法分析器符号表tokennexttoken输入60TheLexicalAnalysisProcess

AGraphicalDepictionusesgetchar()toreadcharacterpushesbackcusingungetc(c,stdin)returnstokentocallertokenvalSetsglobalvariabletoattributevaluelexan()lexicalanalyzer61手工编写的简单词法分析器图2-28intlineno=1,tokenvalue=NONE;intlexan(){ intt; while(1){ t=getchar(); if(t==''||t=='\t') ; elseif(t=='\n') lineno++;

62 elseif(isdigit(t)){ tokenval=t–‘0’; while(isdigit(t)){ tokenval=tokenval*10+