ubuntu linux NJU 编译原理Project1 实验过程记录

本文参考南京大学编译原理实验指导书！！NJU Complier

写在前面——熟悉一下你要编译的语言：c--！

如果你对指导书中c--文法列表式定义一头雾水，来看看陈老师的精简语法树！

实验环境的搭建

实验在linux（ubuntu）环境下进行，需要的工具有gcc、flex、bason。ubuntu的安装这里不做展开，后面三个工具的安装按照指导书操作即可。

词法分析器部分

根据实验指导书，理了一下各个文件or程序之间的依赖关系。粉色部分是你需要编写的。

关于yyin：flex定义的变量，指向标准输入流（键盘）或文件流。类型是FILE*。

关于yylex（）：从yyin指向的位置读取一个词法单元。

关于yytext：返回当前词法单元对应的词素。类型是char*，就是一个字符串。

关于yylen（）：就是strlen（yytext）。

如何编写Lexical.l?

根据指导书，这个文件有三个部分：

｛defination｝ // 给正则表达式起别名，简化｛rules｝的表达

%%

｛rules｝ // 当前词法单元匹配时，要执行的动作（c风格）

%%

｛user subroutines} // 自定义部分

重点正则表达式的书写，即给你的测试文件所有可能出现的单词用正则表达式概括出来。在词法分析阶段，执行的动作就是打印种别码。测试文件可能出现的单词指导书中有总结，大部分都很简单。下面列举其中一些复杂的正则表达。

INT [0-9]|[1-9][0-9]*|0[0-7]*|0x[0-9a-fA-F]*

FLOAT ([0-9]+\.[0-9]+)|((([0-9]*\.[0-9]+)|([0-9]+\.))(E|e)(\+|\-)?[0-9]+)

rules部分样例：

{INT} { printf("INT\n");}

{FLOAT} { printf("FLOAT\n");}

大家自己写的时候多留意指导书中的 词法分析提示 标题下的内容，能避免踩很多坑！

如何编写main.c?

指导书上有，直接cv。

最终效果：

noname:Code>./scanner ../Test/test.cmm

TYPE

ID

LP

RP

LC

TYPE

ID

ASSIGNOP

INT

SEMP

TYPE

ID

ASSIGNOP

Error type A at Line 4: Mysterious characters '~'

ID

SEMP

RC

语法分析部分

关于函数yylex()在bison中的调用：yylex(在Bison yyparse 函数中调用)返回值可以理解分为两部分，一个是token本身（SEMI、TYPE、INT等）, 另一个是与之一一对应的属性值yylval。因为我们要建立语法分析树，所以每个token都应该看作树的叶节点，所以yylval的属性值是树结点。我们需要自行设计（多叉）树结点的数据结构，以及后序建树（采用自底向上的方式）用到的插入算法、打印树用到的遍历算法。

关于yylval：类型是bison自定义的宏YYSTYPE。YYSTYPE是一个联合体，我们的程序中通过自定义这个宏，来声明所有语法、词法单元的属性。

// syntax.y //

%union{

struct MFT* node;

}

在设计树节点的数据结构时，有下两种参考：

struct node｛

    char* name；

    ...

    int num_of_children;

    struct node* children[MAX];

}

struct node{

    char* name;

    ...

struct node* child; // node's first child

    struct node* brother; // node's next brother

}

考虑到程序健壮性，第一种方式子节点最大数目是常量，故采用第二种方式。

结点的数据结构除了指向它孩子和弟弟的指针外，还应该包括（line：当前节点所在行号、type：对不同类型的结点输出格式不同、name：当前节点的名称、val：当前节点的值）注意区分这里val的值和yylval的值，前者其实是yytext对应的字符串的实际意义，后者是一个token作为语法分析树的一个结点而拥有的值。比如0x34作为一个token，它的val是52， yylval是struct node。以下给出多叉树的头文件供参考。

#ifndef MFT_H

#define MFT_H

#include

#include

#include

#include

enum TYPE{

TOKEN_TYPE,

TOKEN_ID,

TOKEN_INT,

TOKEN_FLOAT,

TOKEN_OTHERS,

NOT_A_TOKEN,

NODE_NULL

};

struct MFT{

int line; //number of line where the node is located

char* name; // name of node

enum TYPE type; // type of node(terminator or non-terminator)(for printer)

union{ // value of node(if they have)

int i;

float f;

char* id;

};

struct MFT* child; // the first child of the node

struct MFT* brother; // the next brother of the node

};

int convert2binary(char* text);

// insert node(has children)

struct MFT* addNode(int line, char* name, enum TYPE type, int argc, ...);

// insert leaf(has not children)

struct MFT* addLeaf(int line, char* name, enum TYPE type, char* val);

// release memory

void release(struct MFT* root);

void preorder(struct MFT* root, int layer);

#endif

syntax.y文件的编写：

分三个部分：

抄写指导书的产生式，并指明相应动作（建树）。

对于有二义性的部分，bison给出的默认动作是：移入规约冲突先规约，规约规约冲突先选择排在前面的产生式。为使语法正确分析，通过指定算符优先级和结合性，改变bison的默认动作。对本实验而言，主要有两部分需要你来指定（详见指导书）

if else 的匹配

算术表达式的运算符号的匹配

错误恢复处理

TODO这部分还没学明白TAT，等过几天不忙了再补。

最后是一个令人头疼的问题是，这几个文件相互调用，头文件引用不当会使声明重复。善用ifndef。

给出各文件程序的依赖关系：

最终效果：就像指导书一样啦；）

推荐文章