COMPILER-实验指导书

计算机图形学 实验指导书

课程名称 : 编译原理

英文名称 : Compiler Principle 课程性质 : 必修 / 限选 编写人 :

2010年9月1日 计算机学院

阅读说明

? 未加标注的为必做实验 ? 标有★的为选做实验

实验要求

? 每个小组不超过4人，需要完成以下任务

? 必做实验: 全部完成 (70%)

? 实验1.1 (20%) ? 实验1.2 (10%) ? 实验1.3 (20%) ? 实验1.4 (10%)

? 选做实验: 至少完成3个★ (30%) ? 实验报告 (10%) ? 实验成绩上限 (120%)

第1部分 单元实验

实验1.1 根据状态转换图手工构造词法分析程序

一、实验目的

1. 理解词法分析器的基本功能 2. 理解词法规则的描述方法 3. 理解状态转换图及其实现 4. 能够编写简单的词法分析器

二、实验平台

C/C++

三、实验内容

手工构造一个简单的词法分析程序, 能够识别标识符、整数、关键字、算符、界符。

1. 画出识别所有单词的状态转换图。(若状态转换图过于复杂,可以只画出主要部分) 2. 根据状态转换图手工构造词法分析程序。从以下方法中选一：

? 词法分析器可以作为独立的一遍

? 也可以作为一个子程序被语法分析器调用 3. 实现状态转换图。从以下方法中选一：

? 直接转向法 ? 表驱动法

四、设计文档

1. 画出状态转换图

? 若通过正规式或正规文法手工转换得到，需写明转换步骤

2

? 若通过正规式或正规文法编程转换得到，需附源程序清单 2. 分析直接转向法和表驱动法的优缺点

五、参考资料

1. 《程序设计语言编译原理》国防 陈火旺 3.2 词法分析器的设计

实验1.2 用LEX自动构造词法分析程序

一、实验目的

1. 2. 3. 4.

掌握词法分析程序的自动构造方法

掌握词法分析程序自动构造工具Lex的工作原理和使用方法 熟悉LEX源程序语法

学习使用自动构造软件SLex

二、实验平台

Windows + Slex

三、实验内容

1．实现以下步骤, 掌握SLex的工作过程

a) 构造LEX源程序, 例如命名为Test.Lex

b) 编译lex源程序，生成C语言词法分析程序lexyy.c

在DOS 命令提示符下执行编译 Slex Test.Lex 得到目标文件 lexyy.c

c) 改写生成的C语言代码lexyy.c ，增加主函数(如果没有)

main ( ) { yylex(); }

d) 编译lexyy.c，产生可执行程序lexyy.exe

e) 运行生成的可执行文件 lexyy < Test2.pl0 f) 察看运行结果，并对结果进行分析

2. 编写LEX源程序, 使其自动生成的C程序能够实现以下功能 (至少完成2个)

? 复制一个文件，将文件中每个非空的空白符号序列替换为单个空格

? 将输入文件中的所有小写字母转换成大写字母，将转换后的文件存入另一个文件，

同时在屏幕上输出转换后的文件内容。

? 输入一个C源程序文件, 将其中的所有关键字(即保留字)均转换为大写字母, 将转

换后的文件存入另一个文件，同时在屏幕上输出转换的关键字个数。 ? 将输入文件中的标识符输出到屏幕上。

? 将输入文件中所有能被9整除的整数输出到屏幕上。 ? 为输入文件的每一行打印行行号。

? 统计输入文件中的字符个数、字母个数、各类单词个数、行数。

(字符包括空格、制表符，不包括换行符) ? 把一个文件改变为 “Pig Latin”文.

假设该文件是一个用空白符分隔开的单词(字母串)序列, 每当你遇到一个单词时: (1) 如果第一个字母是辅音字母, 则将它移到单词的结尾, 并加上 ay

3

(2) 如果第一个字母是元音字母, 则只在单词的结尾加上 ay 所有非字母的字符不加处理直接复制到输出

★ 3. 用Lex自动生成词法分析程序

? 词法分析的输出存入文件中, 输出的单词序列格式可以自己定义

★ 4. 修正Slex的bug

Slex本身存在Bug，每次运行后不能正常退出。

注意：因此前已有学生完成了bug修正，所以只有提出不同的修正方案， 或者更好的修正方案，才可以得分。

四、设计文档

1. 分析Test.lex的功能

2. 分析词法分析程序的自动生成原理 3. 分析自动生成的词法分析程序的结构

4. 若对Slex的bug进行了修正, 详细写出修正方案。

五、参考资料

1. lex源程序: Test.lex

2. 参考函数: atoi() – 将字符串转换成整数。例如，调用atoi(“123”)，得到整数123

实验1.3 递归下降分析

一、实验目的

1. 加深对递归下降分析的理解。

二、实验平台

Windows + VC

三、实验内容

1. 选择一个文法或自己设计一个文法(应与范例中的文法不同)，写出文法接受的语言。 2. 对该文法进行LL(1)判别，若不是LL(1)文法，则进行等价变换。 3. 针对文法手工构造递归下降分析程序，实现以下功能：

? 输入一符号串, 输出语法分析的结果 (接受/出错)。

★ 从文件中读入若干个符号串, 依次输出语法分析的结果 ★ 用可视化工具输出语法树

四、设计文档

1. 文法、文法描述的语言、预测分析表

五、参考资料

1. 递归下降分析程序: “ 2-递归下降.c ”

4

此程序对应的文法如下：

G: (1) E→TG

(2) G→+TG|-TG (3) G→ε (4) T→FS

(5) S→*FS|/FS (6) S→ε (7) F→(E) (8) F→i

实验1.4 在Windows平台下使用Flex和Bison

一、实验目的

1. 学习使用词法分析程序自动构造工具Flex和语法分析程序自动构造工具Bison

二、实验平台

Windows + Flex + Bison

三、实验内容

1. 实现以下步骤, 掌握Flex和Bison的工作过程

a) 在DOS 命令提示符下依次执行以下两行命令 flex -olexyy.c calc.lex

bison -ocalc.c calc.y

b) 编译运行 calc.c c) 分析运行结果

2. 用Flex和Bison实现以下功能

(1) 扩充范例程序, 实现以下功能之一

? 乘方、开方运算

? 按位运算 – 与、或、非... ? 三角函数运算 – sin、cos... ? 其他功能

(2) 编写Yacc程序，使其自动生成的C程序能够实现以下功能:

输入中缀表达式,输出后缀表达式

参考属性文法:

G: E ?E＋T {print ‘+’}

E ?T

T ?T*F {print ‘*’} T ?F F ?(E) F ?i {print ‘i’}

★(3) 扩充范例程序, 实现实数运算

★(4) 编写Yacc程序, 使其自动生成的C程序能够实现以下功能:

输入二进制数,输出十进制数

5

11

附录

A. straight-line语言

Straight-line语言的简洁EBNF文法

Stm → Stm; Stm Stm → id := Exp

Stm → print (ExpList) Exp → id Exp → num

Exp → Exp Binop Exp Exp → (Stm, Exp) ExpList → Exp, ExpList ExpList → Exp Binop → + Binop → ? Binop → × Binop → /

B. SimpleBlock语言

SimpleBlock语言的简洁EBNF文法

simpleblock ::= LBRACE { assignment } RBRACE assignment ::= assignment_expression SEMICOLON

assignment_expression ::= IDENTIFIER EQ expression expression ::= expression binary_operator expression | LPAREN expression RPAREN | IDENTIFIER | INTEGER_LITERAL binary_operator ::= PLUS | MINUS | MULT | DIV | MOD

一个SimpleBlock程序有一个内含0条或多条赋值语句的语句块组成，每条赋值语句由一个赋值表达式后跟分号(;)组成。

C. QTiny语言 ★

QTiny语言的文法表示

Program StatementList (

Statement

(

( BEGIN StatementList END

StatementList Statement | Statement Ident = Expr;

| READ(IdList); | WRITE(ExprList);

12

IdList ExprList Expr Factor Op Ident ? | ? | ? | ? | | ? | ? IdList,Ident Ident

ExprList, Expr Expr

Expr Op Factor Factor (Expr) Ident INT + - ID

Qtiny语言范例程序

BEGIN READ(X,AB); Z = (AB+(X+1)); WRITE(X,AB,Z,X-AB,X+AB,X+1); END

D. Tiny语言 ★★

Tiny语言的文法表示 Program ? stmt-sequence stmt-sequence ? stmt-sequence ; statement | statement

statement ? if-stmt

| repeat-stmt | assign-stmt | read-stmt | write-stmt

If-stmt ? if expr then stmt-sequence end | if expr then stmt-sequence else stmt-sequence end repeat-stmt ? repeat stmt-sequence until expr assign-stmt ? identifier := expr read-stmt ? read identifier write-stmt ? write expr expr ? simple-expr comparison-op simple-expr

| simple-expr

comparision-op ? < | = simple-expr ? simple-expr add-op term | term add-op ? + | - term ? term multiple-op factor | factor multiple-op ? * | /

13

factor identifier number letter digit

E. C0语言 ★★★ C0语言的文法表示

<加法运算符> <乘法运算符> <关系运算符> <字符> <数字> <非零数字> <字符串>

? ? ? ? ( (expr) | identifier | number letter | letter number digit | number digit

a | b | … | z | A | B | … | Z 0 | 1 | … | 9

::= +|- ::= * |／

::= <|<＝|>|>＝|!=|== ::= _|a|...|z|A|...|Z ::= ０|<非零数字> ::= １|...|９

::= \｛<合法字符> }\

//字符串中可以出现所有合法的可打印字符集中的字符

<程序> ::= ［<常量说明部分>］［<变量说明部分>］｛<子函数定义部分>｝<主函数> <常量说明部分> ::= const<常量定义>｛,<常量定义>｝; <常量定义> ::= <标识符>＝<整数>

<整数> ::= [+|-] <非零数字>｛<数字>｝|０ <标识符> ::= <字符>｛<字符>|<数字>｝ <声明头部> ::= int <标识符>

<变量说明部分> ::= <声明头部>｛，<标识符>｝；

<子函数定义部分>::= (<声明头部>|void <标识符>)<参数><复合语句> <复合语句> ::= ‘｛’［<常量说明部分>］［<变量说明部分>］<语句序列>‘｝’ <参数> ::= ‘(‘<参数表>‘)’

<参数表> ::= int<标识符>｛，int<标识符>} | <空> <主函数> ::= void main’(‘‘)’<复合语句> <表达式> ::= [＋|－] <项>｛<加法运算符><项>｝ <项> ::= <因子>{<乘法运算符><因子>}

<因子> ::= <标识符>|’(‘<表达式>‘)’|<整数>|<子函数调用语句> <语句> ::= <条件语句> | <循环语句>

| ’{‘<语句序列>‘}’

| <子函数调用语句>;|<赋值语句>;

| <返回语句>; | <读语句>; | <写语句>; | ;

<赋值语句> ::= <标识符>＝<表达式>

<条件语句> ::= if’(‘<条件>‘)’<语句>［else<语句>］ <条件> ::= <表达式><关系运算符><表达式>|<表达式> <循环语句> ::= while’(‘<条件>‘)’<语句> <子函数调用语句>::= <标识符>‘(‘<值参数表>‘)’ <值参数表> ::= <表达式>｛，<表达式>｝|<空> <语句序列> ::= <语句>｛<语句>｝

14

<读语句> <写语句> <返回语句>

::= scanf’(‘<标识符>‘)’

::= printf’(‘<字符串>,<表达式 >|<字符串>|<表达式 >‘)’ ::= return [ ‘(‘<表达式>‘)’]

F. MiniJava语言 ★★★

MiniJava语言文法表示 Program MainClass ClassDecl VarDec MethodDecl FormalList FormalRest Type Statement Exp ExpList → MainClass ClassDecl* → class id { public static void main ( String [] id ) { Statement }} → class id { VarDecl* MethodDecl* }

→ class id extends id { VarDecl* MethodDecl* } → Type id ;

→ public Type id ( FormalList )

{ VarDecl* Statement* return Exp ;} → Type id FormalRest* →

→ , Type id → int [] → boolean → int → id

→ { Statement* }

→ if ( Exp ) Statement else Statement → while ( Exp ) Statement → System.out.println ( Exp ) ; → id = Exp ;

→ id [ Exp ]= Exp ; → Exp op Exp → Exp [ Exp ] → Exp . length

→ Exp . id ( ExpList ) → INTEGER LITERAL → true → false → id → this

→ new int [ Exp ] → new id () → ! Exp → ( Exp )

→ Exp ExpRest* →

15

ExpRest → ,Exp

MiniJava语言范例程序

class Factorial {

public static void main(String[] a) {

System.out.println(new Fac().ComputeFac(10)); } }

class Fac {

public int ComputeFac(int num) { int num_aux; if (num < 1)

num_aux = 1; else

num_aux = num * (this.ComputeFac(num-1)); return num_aux; } }

16

本文来源：https://www.bwwdw.com/article/b0lt.html