当前位置: 首页 > >

编译方法实验

发布时间:

编译方法实验
人民大学信息学院 陈文萍

1

内容
? 实验概述 ? PL0语言简介 ? 词法分析器实验部分

2

实验设置
? 实验内容
? PL/0编译器的实现

? 实验目的
? ? ? ? 理解编译器的工作机制 掌握编译器的构造方法 掌握词法分析器的生成工具LEX的用法 掌握语法分析器的生成工具YACC的用法

3

实验要求
? 独立完成
– 程序源代码 – 文档

? 按时提交
? 迟交影响成绩

? 文档清晰
? ? ? ? 实验内容 程序设计原理与方法 程序设计流程 运行结果 (文件)

? 鼓励扩展
4

实验环境与考评
? 成绩评定
? 程序 ? 文档

? 实验分成三部分:
? 词法分析 ? 语法分析 ? 语义分析和代码生成*

? 实验环境
? Windows ? C或C++
5

PL/0编译程序的实验流程
PL0源程序

词法分析器

PL/0
语法分析器

类汇编

C

语义分析和中间代码生成

类汇编代码

6

PL/0 语言简介
? PL/0语言是Pascal语言的子集
–数据类型只有整型 –标识符的有效长度是10,以字母开始的字母数字串 –数最多为14位 –过程无参,可嵌套(最多三层),可递归调用 –变量的作用域同PASCAL,常量为全局的

7

PL/0 语言简介
? 语句类型:
–赋值语句,if...then..., while...do..., read, write, call, 复合语句begin... end, 说明语句: const..., var..., procedure…

? 13个保留字:
–if, then, while, do, read, write, call, begin, end, const, var, procedure, odd

8

PL0语言的EBNF范式
? EBNF:可说明哪些符号序列是对于某给定语言在语法上 有效的程序。

? EBNF范式的符号说明
– – – – – – < >:语法构造成分,为非终结符 ::= :该符号的左部由右部定义,读作“定义为” | :或 { }:括号内的语法成分可重复 [ ]:括号内成分为任选项 ( ):圆括号内成分优先
9

PL0语言的EBNF范式
? <程序> ::= <分程序>. ? <分程序> ::= [<常量说明部分>][<变量说明部分>][<过 程说明部分>]<语句> ? <常量说明部分> ::= CONST<常量定义>{,<常量定义>}; ? <常量定义> ::= <标识符>=<无符号整数> ? <无符号整数> ::= <数字>{<数字>} ? <变量说明部分> ::= VAR<标识符>{,<标识符>}; ? <标识符> ::= <字母>{<字母>|<数字>}

10

PL0语言的EBNF范式
? <过程说明部分> ::= <过程首部><分程序>{;<过程说明 部分>}; ? <过程首部> ::= PROCEDURE<标识符>; ? <语句> ::= <赋值语句>|<复合语句>|<条件语句>|<当型 循环语句>|<过程调用语句>|<读语句>|<写语句>|<空> ? <赋值语句> ::= <标识符>:=<表达式> ? <复合语句> ::= BEGIN<语句>{;<语句>}END ? <条件> ::= <表达式><关系运算符><表达式>|ODD<表 达式> ? <条件语句> ::= IF<条件>THEN<语句>
11

PL0语言的EBNF范式
? ? ? ? ? ? ? ? <表达式> ::= [+|-]<项>{<加法运算符><项>} <项> ::= <因子>{<乘法运算符><因子>} <因子> ::= <标识符>|<无符号整数>|‘(?<表达式>‘)‘ <加法运算符> ::= +|<乘法运算符> ::= *|/ <关系运算符> ::= =|#|<|<=|>|>= <当型循环语句> ::= WHILE<条件>DO<语句> <过程调用语句> ::= CALL<标识符>

12

PL0语言的EBNF范式
? ? ? ? <读语句> ::= READ‘(?<标识符>{,<标识符>}‘)‘ <写语句> ::= WRITE‘(?<表达式>{,<表达式>}‘)‘ <字母> ::= a|b|...|X|Y|Z <数字> ::= 0|1|...|8|9

13

PL/0语言词法分析器实验
? ? ? 实验内容:用flex工具生成一个PL/0语言的词法分析程序,对PL/0语言的 源程序进行扫描,识别出单词符号的类别,统计输出各种符号的信息 输入:PL0源程序 输出:把单词符号分为下面五类,然后统计PL0源程序中各单词符号出现 的次数。 – K类(关键字)
– – – – I类(标识符) C类(常量) P类(算符及界符) O类(其他)

?

实验环境:
? 词法分析器生成工具:flex ? 编程语言:C ? 调试环境:VC

14

PL/0语言词法分析器实验
? 例如,对如下的程序: var a,b; procedure test; var t; begin t := 1; end; begin call test; end. 词法分析结果输出,类别包括关键字 K(keyword), 标 识 符 I(ident), 常 熟 C(const), 算 符 P (operator) 及 界 符 O (symbol), 其他 (other) K类: var :2 procedure :1 … I类: a :1 b :1 … C类: 1 :1 ……

15

LEX概述
? LEX是一个词法分析器的自动产生系统。
LEX源程序
源语言程序

LEX
yylex()函数

lex.yy.c文件
单词符号串

? LEX源程序的核心是识别规则,它由正规式和 动作组成。

16

LEX源程序的格式
%{ 声明 %}
辅助定义 %% 识别规则 %% 用户子程序 --可选

--可选 --必须有

--可选
17

声明
? 所有嵌在“%{”和“%}”之间的内容将被原样拷 贝到lex.yy.c文件中。 ? 在声明中,可以引入头文件、宏定义以及全局 变量的定义。
例如: %{ #include <stdio.h> int num_ident, num_keyword; %}

18

辅助定义
? 辅助定义可以用一个名字代表一个正规式。 ? 辅助定义的语法是:辅助定义名 正规式
注意:辅助定义必须从第一列写起。 后面的辅助定义可以引用前面的辅助定义。

? 在正规式中,用“{辅助定义名}”可以引用相应的正规 式。
例如: NEW_LINE (\n) INTEGER ([0-9]+) EXPONENT ([Ee][+-] {INTEGER})

19

识别规则
? 识别规则由两部分组成:正规式和相应的动作。 ? 正规式用于描述输入串的词法结构。 ? 动作用于描述识别出某一个词形时要完成的操 作。
例如: %% void {return T_Void;}

(识别的) (动作)

20

识别规则之正规式
? 正规式由正文字符和正规式运算符组成。 ? 正文字符为计算机的字符集。几个特殊的字符 为:“ ”、“\t‖、“\n‖。 ? 正规式运算符包括:.,[,],^,-,*,+,?, {,},―,\,(,),|,/,$,<,>。

21

正规式的写法(1)
x . [xyz] [^A-Z] r* r+ r? r{2,5} r{2,} r{4} {name} “[” \” 匹配字符x 匹配除换行外的所有字符 字符集合,匹配字符‘x’、‘y’或 ‘z’ 字符集合,匹配除大写字母外的所有字符 正规式r出现零次或多次 正规式r出现一次或多次 正规式r出现零次或一次 正规式r重复2至5次 正规式r重复2次以上(含2次) 正规式r重复4次 辅助定义“name”的展开 字符[ 字符”

22

正规式的写法(2)
\0 \123 \x2a (r) rs r|s r/s ^r r$ <s>r <s1,s2,s3>r <*>r <<EOF>> <s><<EOF>> 空字符(ASCII 码为 0) ASCII 码为八进制数123的字符 ASCII码为十六进制数 2a的字符 匹配正规式r 正规式r后面紧跟正规式s,串联 匹配正规式r或s 当正规式r后面紧跟s时,匹配r 当正规式r位于行首时,匹配r 当正规式r位于行尾时,匹配r,相当于"r/\n" 在开始条件s下匹配正规式r 在开始条件s1,s2或s3下匹配正规式r 在任何开始条件下都匹配正规式r 遇到文件结束符时 在开始条件s下遇到文件结束符时

23

书写正规式的注意事项
? 每条规则的正规式必须从第一列写起。 ? 为避免与运算符混淆,建议对所有的非字母数 字字符都使用转义符“或\ 。 ? 在集合中,字符之间不要留空格,否则空白符 “ ”将被包含在集合中。 ? 辅助定义可以使正规式更加简洁清晰。

24

正规式举例
[a-zA-Z0-9] 表示所有的字母和数字组成的集合; [^ \t\n] 表示除空格、tab和换行外的所有字符组成的集合; (\”[^”\n]*) 表示以双引号开头,后跟除双引号和换行外的若干 字符组成的 字符串,例如:“here is a string a{1,5} 表示a重复1至5次形成的串的集合,即{a, aa, aaa, aaaa, aaaaa} [A-Za-z][A-Za-z0-9]* 表示以字母开头,后跟若干字母和数字的串 ([Ee][-+][0-9]+) 表示科学计数法的指数部分

25

识别规则之动作
? 识别规则的动作是一段C语言程序,将被原样 照抄到lex.yy.c文件中。 ? 缺省规则:输入串中不与任何正规式匹配的字 符串将被原样照抄到输出文件中。 ? 在词法分析器实验中,基本的动作就是记录单 词符号的类别

26

书写动作的注意事项
? 动作必须从正规式所在行写起。 ? 当某条规则的动作超过一条语句时,必须用大 括号括起来。 ? 如果希望在输出中滤去某些字符,相应的动作 为空
例如: [ \t\n] {}

? 如果不希望照抄输出,就要为每一个可能出现 的词形提供规则。

27

动作中用到的全局变量

? yytext:char *类型,指向当前正被某规则匹配的字符串。 ? yyleng:整型,存储yytext中字符串的长度。被匹配的 串在yytext[0]~yytext[yyleng-1]中。 (匹配的串)

28

用户子程序
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 子程序用C语言书写,将被原样照抄到lex.yy.c文件中。 例如填加main函数,读入pl0源文件 int main(int argc, char *argv[]) { FILE * fIn; //PL0文件的指针 switch(argc) { case 1: //打开缺省文件 fIn=fopen(―test.frag‖,―r‖); if(fIn==NULL){ printf("default file not found\n"); exit(1); } else yyin = fIn; //yyin 是pl0中的全局变量——指向打开的文件 break; case 2: //打开指定文件 if ((fIn = fopen(argv[1],"r")) == NULL) { printf("File %s not found.\n",argv[1]); exit(1); } else yyin=fIn; break; default: printf("useage:flex [filename]\n"); exit(1); } yylex(); …… fclose(fIn); return 0; }

29

LEX源程序举例
%{ int num_lines = 0, num_chars = 0;

%}
%% \n

//声明

{++num_lines; ++num_chars;}

.
%%

{++num_chars;}
//识别,然后动作

main(){

yylex();

//缺省,默认接受键盘输入

printf( “# of lines = %d, # of chars = %d\n", num_lines, num_chars );

}

//用户子程序

30

识别规则的二义性
有时输入串中的字符可以与多条规则匹配,在这
种情况下,LEX有两个处理原则:

? 能匹配最多字符的规则优先; ? 若各规则匹配的字符数目相同,先给出的规则 优先。
例如,给定规则如下: void {return T_Void;} [A-Za-z]+ {return T_Identifier;} “void”将被识别为T_Void, “voida”将被识别为T_Identifier。

31




友情链接: