Compiler - CS143

此文档主要记录和总结cs143课程相关的lab项目。阅读和理解课程提供的任务指导书和任务指导书中要求阅读的材料非常重要。

The Cool Reference Manual 的部分翻译： https://www.cnblogs.com/pinkman/archive/2013/03/12/2954902.html

A Tour of the Cool Support Code 部分分析

此文档主要介绍lab project中的提供的文件，结合源代码理解它们并正确使用已有架构很重要。

Lists

list.h文件实现了简单的链表数据类型，构造函数List在链表的前部添加新元素，hd返回链表的第一个节点，tl返回链表第一个节点指向的后续链表。提供函数list_map()，list_print(), list_length()。此结构在实现string tables和symbol tables的时候都有用到。

String Tables

所有的编译器都需要维护大量的字符串，例如：程序标识符、数字型常量和字符串常量。通常，这些字符串中有许多是相同的。例如：每一个标识符通常会在程序中出现很多次。为了确保字符串常量的紧凑存储和有效操作，需要使用专门的数据结构——字符串表。

字符串表是维护了每一个字符串的简单copy的查找表，Cool字符串表类在stringtab.h中提供了各种插入和查询字符串表的函数。实际中的编译器使用哈希数据结构来实现字符串表，Cool编译器使用lists链表来实现字符串表。

Cool字符串表由类型Entry组成，每一个Entry存储一个字符串，字符串的长度和该字符串的唯一整数索引下标。Cool编译器结构的重要一点是它有三个不同的字符串表：stringtable（字符串常量表）,inttable（整数常量表）,idtable（标识符表）。code generator 必须区分整数常量和字符串常量，并从标识符中区分它们，因为程序中每一个字符串常量和整数常量都生成不同的代码。拥有三个不同的字符串表容易区分。三个表有不同的数据类型，都是Entry的派生类。指向Entry的指针是Symbol。

由于字符串表存储每个字符串的copy，比较x和y代表的两个IntEntrys，StrEntrys，IdEntrys是否一样只需要比较x==y。比较两个不同符号表中的字符串是没有意义的。

有三个函数向表中添加元素：add string(char *s,int m)；add string(char *s)；
add int(int i)，返回Entry的派生类来描述符号表表项。

相关源代码实现：stringtab.h stringtab_functions.h stringtab.cc

Symbol Tables

除了字符串之外，编译器还必须同时确定和管理作用域。Symbol Table是管理作用域的数据结构，是另一个查找表。关键字是符号/名称，结果是与该符号相关的任何信息。

除了加入和删除符号之外，符号表同时支持进入和退出作用域和检查一个标识符是否在当前作用域下已定义的操作。查询操作必须也遵循语言的作用域规则，如果标识符x有多重定义，作用域规则必须确定x查找返回的定义，在Cool和一般语言中，最内层的定义隐藏外层的定义，因此返回具有x定义的最内层的作用域的定义。

Cool 符号表是作用域链表实现的，每一个作用域都是<identifier,info>的链表。

Utilities

utilities.h和utilities.cc定义了许多函数，供实现和调试Cool 词法和语法分析使用。

Abstract Syntax Tree

Phyla and Constructors

AST数据类型为每一种Cool结构提供一个表示该表达式的类。有一个let表达式的类，+表达式的类等等。这些类的对象是Cool 抽象语法树AST的节点。例如：表达式e1+e2由一个+表达式对象和两个子树：一个用于表示e1表达式的树，一个用于表示e2表达式的树。

Cool 的抽象语法树在一个叫做APS的语言中指定，在APS术语中，抽象语法树的节点（let，＋等）被称为constructors，AST的形式由一组phyla描述，每一种phylum有一个或多个constructors。

Phyla实际上是类型，也就是说，不是一大组没有分化过的constructors，而是constructors根据功能分组在一起。例如：表达式的抽象语法树和类抽象语法树不同。phyla定义在文件cool-tree.aps中:

module COOL begin
  phylum Program;

  phylum Class_;
  phylum Classes = LIST[Class_];

  phylum Feature;
  phylum Features = LIST[Feature];

  phylum Formal;
  phylum Formals = LIST[Formal];

  phylum Expression;
  phylum Expressions = LIST[Expression];

  phylum Case;
  phylum Cases = LIST[Case];

从定义中可以看出，有两种完全不同的phyla：普通型phyla和链表型phyla，每个普通型phyla都有相关的constructors，链表型phyla有一组固定的list操作。

每一个constructor都有含有类型的参数并返回一个有类型的结果。类型要么是phyla要么是任何普通的C++类型。实际上，phyla声明本身会由APS编译器编译成C++类声明。一个constructor定义的样例如下：

constructor class_(name : Symbol ; parent : Symbol ; features : Features ; filename : Symbol): Class_;

定义指出class_ constructor有四个参数：一个类名的Symbol，一个父类名的Symbol，一个Features，一个该类定义出现的文件名的Symbol。Features的phylum被定义为Feature的链表：

phylum Features = LIST[Feature];

定义在AST链表上的操作描述见第二小节。

class_ constructor返回一个Class_类型的抽象语法树。在cool.y文件中，有一个使用class_ constructor的例子：

class : CLASS TYPEID INHERITS TYPEID IS optional_feature_list END ’;’
{ $$ = class_($2,$4,$6,stringtable.add_string(curr_filename)); }

class_ constructor 建立了一个Class_树节点，有四个参数作为子节点。因为参数类型被声明了，C++类型检查器会强制class_ constructor只接受正确类型的参数。见第五小节和cool-tree.aps了解更多其他constructors。

PA2 lexer 词法分析

完成此lab前主要学习哈工大编译原理视频。理解任务说明书非常重要。

参考资料：

flex文档（尤其参考其中pattern部分）： https://eternalsakura13.com/2020/05/27/flex/

The Cool Reference Manual 中 10 Lexical Structure 和 11 Cool Syntax 部分

词法分析器lexer可以将我们输入的程序语言与编写的正则表达式的规则进行匹配来返回一个个token。

在这个lab中我们使用flex语言来编写Cool编译器的词法分析器。利用Flex我们可以通过为每一个匹配的pattern编写一些正则表达式和对应执行的action来实现词法分析器。Flex会把我们的规则文件编译成C源码，实现一个有穷自动机，以识别我们在规则文件中指定的正则表达式。可以检查出因为状态机无法正确转换的错误，例如：引号、注释符号不闭合；字符串过长等。

flex语言的结构如下：

%{
Declarations
%}
Definitions
%%
Rules
%%
User subroutines

其中Declarations和User subroutines是可选项。Definition也是可选的，但是便于我们给正则表达式取名字，例如：\DIGIT [0-9]定义了数字。其中，最重要的部分是rules，它指定了有匹配到的正则表达式时进行的action，action有常规的C语言代码指定。Flex使用最长匹配原则。

编写规则的时候，根据之前遇到的tokens来执行不同的action。可以通过在declaration中声明全局变量来追踪状态，Flex中提供了状态声明的方式，例如：

%Start COMMENT

可以通过BEGIN(COMMENT)把COMMENT状态设置为TRUE，要仅在先前遇到开头注释时执行操作，可以使用以下语法在状态COMMENT中声明规则：

<COMMENT> {
// the rest of your rule ...
}

特殊的默认状态是INITIAL。

生成lexer代码分析

主要分析编写编译器过程中生成的cool-lex.cc文件的代码结构：

首先是定义flex版本号和flex整数类型，以及一些处理缓冲区和状态转换的宏定义，

/* A lexical scanner generated by flex */
#define FLEX_SCANNER
#define YY_FLEX_MAJOR_VERSION 2
#define YY_FLEX_MINOR_VERSION 6
#define YY_FLEX_SUBMINOR_VERSION 0
#if YY_FLEX_SUBMINOR_VERSION > 0
#define FLEX_BETA
#endif

/* First, we deal with  platform-specific or compiler-specific issues. */

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>

/* flex integer type definitions */

#ifndef FLEXINT_H
#define FLEXINT_H

/* C99 systems have <inttypes.h>. Non-C99 systems may or may not. */

typedef signed char flex_int8_t;
typedef short int flex_int16_t;
typedef int flex_int32_t;
typedef unsigned char flex_uint8_t; 
typedef unsigned short int flex_uint16_t;
typedef unsigned int flex_uint32_t;

/* Limits of integral types. */
#ifndef INT8_MIN
#define INT8_MIN               (-128)
#endif
#ifndef INT16_MIN
#define INT16_MIN              (-32767-1)
#endif
#ifndef INT32_MIN
#define INT32_MIN              (-2147483647-1)
#endif
#ifndef INT8_MAX
#define INT8_MAX               (127)
#endif
#ifndef INT16_MAX
#define INT16_MAX              (32767)
#endif
#ifndef INT32_MAX
#define INT32_MAX              (2147483647)
#endif
#ifndef UINT8_MAX
#define UINT8_MAX              (255U)
#endif
#ifndef UINT16_MAX
#define UINT16_MAX             (65535U)
#endif
#ifndef UINT32_MAX
#define UINT32_MAX             (4294967295U)
#endif

#endif /* ! C99 */

#endif /* ! FLEXINT_H */

/*存储类修饰符const有效 */
#define YY_USE_CONST

#ifdef YY_USE_CONST
#define yyconst const
#else
#define yyconst
#endif

/* %not-for-header */

/* 在文件结束时返回YY_NULL */
#define YY_NULL 0

/*将可能为负的，可能为带符号的char转换为一个无符号整数，
 *以用作数组索引。如果带符号的char为负数，我们想将其视为8位无符号的char，
 *因此采用双精度强制转换。
 */
#define YY_SC_TO_UI(c) ((unsigned int) (unsigned char) c)

/* 进入开始状态 */
#define BEGIN (yy_start) = 1 + 2 *

/* 将当前的开始状态转换为一个值，以后可以将该值传递给BEGIN以返回该状态。
   YYSTATE别名用于lex兼容性。
 */
#define YY_START (((yy_start) - 1) / 2)
#define YYSTATE YY_START

/* 给定开始状态的EOF规则的action num。 */
#define YY_STATE_EOF(state) (YY_END_OF_BUFFER + state + 1)

/* 开始处理新文件 */
#define YY_NEW_FILE yyrestart(yyin  )

#define YY_END_OF_BUFFER_CHAR 0

/* 默认输入缓冲区的大小 */
#ifndef YY_BUF_SIZE
#ifdef __ia64__
/* On IA-64, the buffer size is 16k, not 8k.
 * Moreover, YY_BUF_SIZE is 2*YY_READ_BUF_SIZE in the general case.
 * Ditto for the __ia64__ case accordingly.
 */
#define YY_BUF_SIZE 32768
#else
#define YY_BUF_SIZE 16384
#endif /* __ia64__ */
#endif

/* 状态buf必须足够大，才能在主缓冲区中为每个字符保留一个状态。*/
#define YY_STATE_BUF_SIZE   ((YY_BUF_SIZE + 2) * sizeof(yy_state_type))

#ifndef YY_TYPEDEF_YY_BUFFER_STATE
#define YY_TYPEDEF_YY_BUFFER_STATE
typedef struct yy_buffer_state *YY_BUFFER_STATE;
#endif

#ifndef YY_TYPEDEF_YY_SIZE_T
#define YY_TYPEDEF_YY_SIZE_T
typedef size_t yy_size_t;
#endif

extern yy_size_t yyleng;

extern FILE *yyin, *yyout;

#define EOB_ACT_CONTINUE_SCAN 0
#define EOB_ACT_END_OF_FILE 1
#define EOB_ACT_LAST_MATCH 2

    #define YY_LESS_LINENO(n)
    #define YY_LINENO_REWIND_TO(ptr)

/* 将除前 n 个匹配字符外的所有字符返回到输入流。 */
#define yyless(n) \
    do \
        { \
        /*撤消设置yytext的效果。*/ \
        int yyless_macro_arg = (n); \
        YY_LESS_LINENO(yyless_macro_arg);\
        *yy_cp = (yy_hold_char); \
        YY_RESTORE_YY_MORE_OFFSET \
        (yy_c_buf_p) = yy_cp = yy_bp + yyless_macro_arg - YY_MORE_ADJ; \
        YY_DO_BEFORE_ACTION; /* set up yytext again */ \
        } \
    while ( 0 )

#define unput(c) yyunput( c, (yytext_ptr)  )

#ifndef YY_STRUCT_YY_BUFFER_STATE
#define YY_STRUCT_YY_BUFFER_STATE
struct yy_buffer_state
    {
    FILE *yy_input_file;
    char *yy_ch_buf;        /* input buffer */
    char *yy_buf_pos;        /* current position in input buffer */

    /* 输入缓冲区的大小（以字节为单位），不包括EOB字符的空间。*/
    yy_size_t yy_buf_size;

    /* 读入yy_ch_buf的字符数，不包括EOB字符。*/
    int yy_n_chars;

    /*是否创建缓冲区，并且可以对其进行realloc()和free() */
    int yy_is_our_buffer;

    /* 是否是交互式输入; 如果是交互式,并且如果我们使用stdio作为输入,那么我们要使用getc()
     * 而不是fread(), 以确保我们在每个换行符之后都停止获取输入
     */
    int yy_is_interactive;

    /* 是否认为我们处于一行的开头,如果是,则'^'规则将在下一场匹配中生效，否则无效。
     */
    int yy_at_bol;

    int yy_bs_lineno; /**< The line count. */
    int yy_bs_column; /**< The column count. */

    /* 在到达输入缓冲区的末尾时是否尝试填充它 */
    int yy_fill_buffer;

    int yy_buffer_status;

#define YY_BUFFER_NEW 0
#define YY_BUFFER_NORMAL 1
    /* 如果看到了EOF,但仍有一些文本要处理,则我们将缓冲区标记为YY_EOF_PENDING,
    *  以表明我们不应该再尝试从输入源中进行读取了
    *  但是，由于可能存在备份，我们可能仍有许多tokens要匹配
    *  当我们实际看到EOF时，我们将状态更改为 new (通过yyrestart())，
    *  以便用户只需将yyin指向新的输入文件即可继续扫描
    */
#define YY_BUFFER_EOF_PENDING 2
    };
#endif /* !YY_STRUCT_YY_BUFFER_STATE */

/* Stack of input buffers. */
static size_t yy_buffer_stack_top = 0; /**< index of top of stack. */
static size_t yy_buffer_stack_max = 0; /**< capacity of stack. */
static YY_BUFFER_STATE * yy_buffer_stack = 0; /**< Stack as an array. */

/* 我们提供了用于访问缓冲区状态的宏,以防将来我们希望将缓冲区状态置于更通用的"扫描器状态"中
 * 返回栈顶或NULL
 */
#define YY_CURRENT_BUFFER ( (yy_buffer_stack) \
                          ? (yy_buffer_stack)[(yy_buffer_stack_top)] \
                          : NULL)

/* 与以前的宏相同，但是便于缓冲区堆栈不是NULL或需要左值时 仅在内部使用
 */
#define YY_CURRENT_BUFFER_LVALUE (yy_buffer_stack)[(yy_buffer_stack_top)]

/* yy_hold_char holds the character lost when yytext is formed. */
static char yy_hold_char;
static int yy_n_chars;        /* number of characters read into yy_ch_buf */
yy_size_t yyleng;

/* Points to current character in buffer. */
static char *yy_c_buf_p = (char *) 0;
static int yy_init = 0;        /* whether we need to initialize */
static int yy_start = 0;    /* start state number */

/* 用于允许yywrap()进行缓冲区切换而不是设置新的yyin的标志
 */
static int yy_did_buffer_switch_on_eof;

void yyrestart (FILE *input_file  );
void yy_switch_to_buffer (YY_BUFFER_STATE new_buffer  );
YY_BUFFER_STATE yy_create_buffer (FILE *file,int size  );
void yy_delete_buffer (YY_BUFFER_STATE b  );
void yy_flush_buffer (YY_BUFFER_STATE b  );
void yypush_buffer_state (YY_BUFFER_STATE new_buffer  );
void yypop_buffer_state (void );

static void yyensure_buffer_stack (void );
static void yy_load_buffer_state (void );
static void yy_init_buffer (YY_BUFFER_STATE b,FILE *file  );

#define YY_FLUSH_BUFFER yy_flush_buffer(YY_CURRENT_BUFFER )

YY_BUFFER_STATE yy_scan_buffer (char *base,yy_size_t size  );
YY_BUFFER_STATE yy_scan_string (yyconst char *yy_str  );
YY_BUFFER_STATE yy_scan_bytes (yyconst char *bytes,yy_size_t len  );

void *yyalloc (yy_size_t  );
void *yyrealloc (void *,yy_size_t  );
void yyfree (void *  );

#define yy_new_buffer yy_create_buffer

#define yy_set_interactive(is_interactive) \
    { \
    if ( ! YY_CURRENT_BUFFER ){ \
        yyensure_buffer_stack (); \
        YY_CURRENT_BUFFER_LVALUE =    \
            yy_create_buffer(yyin,YY_BUF_SIZE ); \
    } \
    YY_CURRENT_BUFFER_LVALUE->yy_is_interactive = is_interactive; \
    }

#define yy_set_bol(at_bol) \
    { \
    if ( ! YY_CURRENT_BUFFER ){\
        yyensure_buffer_stack (); \
        YY_CURRENT_BUFFER_LVALUE =    \
            yy_create_buffer(yyin,YY_BUF_SIZE ); \
    } \
    YY_CURRENT_BUFFER_LVALUE->yy_at_bol = at_bol; \
    }

#define YY_AT_BOL() (YY_CURRENT_BUFFER_LVALUE->yy_at_bol)

/* %% [1.0] yytext/yyin/yyout/yy_state_type/yylineno etc. def's & init go here */
/* Begin user sect3 */

#define FLEX_DEBUG

typedef unsigned char YY_CHAR;

FILE *yyin = (FILE *) 0, *yyout = (FILE *) 0;

typedef int yy_state_type;

extern int yylineno;

int yylineno = 1;

extern char *yytext;
#ifdef yytext_ptr
#undef yytext_ptr
#endif
#define yytext_ptr yytext

static yy_state_type yy_get_previous_state (void );
static yy_state_type yy_try_NUL_trans (yy_state_type current_state  );
static int yy_get_next_buffer (void );
static void yy_fatal_error (yyconst char msg[]  );

/* 在匹配当前模式之后且在执行相应操作之前完成-设置yytext
 */
#define YY_DO_BEFORE_ACTION \
    (yytext_ptr) = yy_bp; \
/* %% [2.0] code to fiddle yytext and yyleng for yymore() goes here \ */\
    yyleng = (size_t) (yy_cp - yy_bp); \
    (yy_hold_char) = *yy_cp; \
    *yy_cp = '\0'; \
/* %% [3.0] code to copy yytext_ptr to yytext[] goes here, if %array \ */\
    (yy_c_buf_p) = yy_cp;

/* %% [4.0] data tables for the DFA and the user's section 1 definitions go here */
#define YY_NUM_RULES 45
#define YY_END_OF_BUFFER 46

接下来是压缩后的DFA状态转移表：

yyconst flex_int16_t yy_accept[168]
yyconst YY_CHAR yy_ec[256]
yyconst YY_CHAR yy_meta[53]
yyconst flex_uint16_t yy_base[174]
yyconst flex_int16_t yy_def[174]
yyconst flex_uint16_t yy_nxt[349]
yyconst flex_int16_t yy_chk[349]

随后，DFA的工作通过YY_DECL实现，省略了部分条件分支语句的代码如下：

YY_DECL
{
    yy_state_type yy_current_state;
    char *yy_cp, *yy_bp;
    int yy_act;

    if ( !(yy_init) )
        {
        (yy_init) = 1;
        if ( ! (yy_start) )
            (yy_start) = 1;    /* first start state */
        if ( ! yyin )
            yyin = stdin;
        if ( ! yyout )
            yyout = stdout;
        if ( ! YY_CURRENT_BUFFER ) {
            yyensure_buffer_stack ();
            YY_CURRENT_BUFFER_LVALUE =
                yy_create_buffer(yyin,YY_BUF_SIZE );
        }
        yy_load_buffer_state( );
        }

    {
    while ( 1 )        /* loops until end-of-file is reached */
        {
        /* 设置在buf中的指针，通过yytext获取相应的字符串 */
        yy_cp = (yy_c_buf_p);

        /* Support of yytext. */
        *yy_cp = (yy_hold_char);

        /* 初始时 yy_bp 指向 yy_ch_buf */
        yy_bp = yy_cp;
        /* 初始从start状态开始 */
        yy_current_state = (yy_start);
yy_match:
/* 开始进行状态转移, 通过yy_nxt表，结合yy_current_state和当前读入的字符来索引跳转状态, 直到无法转移*/
        do
            {
            YY_CHAR yy_c = yy_ec[YY_SC_TO_UI(*yy_cp)] ;
            if ( yy_accept[yy_current_state] )
                {
                (yy_last_accepting_state) = yy_current_state;
                (yy_last_accepting_cpos) = yy_cp;
                }
            while ( yy_chk[yy_base[yy_current_state] + yy_c] != yy_current_state )
                {
                yy_current_state = (int) yy_def[yy_current_state];
                if ( yy_current_state >= 168 )
                    yy_c = yy_meta[(unsigned int) yy_c];
                }
            yy_current_state = yy_nxt[yy_base[yy_current_state] + (unsigned int) yy_c];
            ++yy_cp;
            }
        while ( yy_base[yy_current_state] != 296 );

yy_find_action:
/* 判断转移后的状态是否是accept ，是否需要后退处理 */
        yy_act = yy_accept[yy_current_state];
        if ( yy_act == 0 )
            { /* have to back up */
            yy_cp = (yy_last_accepting_cpos);
            yy_current_state = (yy_last_accepting_state);
            yy_act = yy_accept[yy_current_state];
            }

        YY_DO_BEFORE_ACTION;

do_action:    
/* 执行成功匹配规则对应的actions */
        if ( yy_flex_debug )
            {
            if ( yy_act == 0 )
                fprintf( stderr, "--scanner backing up\n" );
            else if ( yy_act < 45 )
                fprintf( stderr, "--accepting rule at line %ld (\"%s\")\n",
                         (long)yy_rule_linenum[yy_act], yytext );
            else if ( yy_act == 45 )
                fprintf( stderr, "--accepting default rule (\"%s\")\n",
                         yytext );
            else if ( yy_act == 46 )
                fprintf( stderr, "--(end of buffer or a NUL)\n" );
            else
                fprintf( stderr, "--EOF (start condition %d)\n", YY_START );
            }

        switch ( yy_act )
    { 
            case 0: /* must back up */
            /* undo the effects of YY_DO_BEFORE_ACTION */
            *yy_cp = (yy_hold_char);
            yy_cp = (yy_last_accepting_cpos);
            yy_current_state = (yy_last_accepting_state);
            goto yy_find_action;

case 1:
YY_RULE_SETUP
#line 64 "cool.flex"
{BEGIN COMMENT_IN_LINE;}
    YY_BREAK
...
/* 此处省略case语句 */

        else switch ( yy_get_next_buffer(  ) )
            {
            case EOB_ACT_END_OF_FILE:
                {
                (yy_did_buffer_switch_on_eof) = 0;

                if ( yywrap( ) )
                    {
                    /* 注意：因为我们已经在yy_get_next_buffer()中设置了yytext,
                     * 所以我们现在可以设置yy_c_buf_p
                     */
                    (yy_c_buf_p) = (yytext_ptr) + YY_MORE_ADJ;

                    yy_act = YY_STATE_EOF(YY_START);
                    goto do_action;
                    }

                else
                    {
                    if ( ! (yy_did_buffer_switch_on_eof) )
                        YY_NEW_FILE;
                    }
                break;
                }

            case EOB_ACT_CONTINUE_SCAN:
                (yy_c_buf_p) =
                    (yytext_ptr) + yy_amount_of_matched_text;

                yy_current_state = yy_get_previous_state(  );

                yy_cp = (yy_c_buf_p);
                yy_bp = (yytext_ptr) + YY_MORE_ADJ;
                goto yy_match;

            case EOB_ACT_LAST_MATCH:
                (yy_c_buf_p) =
                &YY_CURRENT_BUFFER_LVALUE->yy_ch_buf[(yy_n_chars)];

                yy_current_state = yy_get_previous_state(  );

                yy_cp = (yy_c_buf_p);
                yy_bp = (yytext_ptr) + YY_MORE_ADJ;
                goto yy_find_action;
            }
        break;
        }

    default:
        YY_FATAL_ERROR(
            "fatal flex scanner internal error--no action found" );
    } /* end of action switch */
        } /* end of scanning one token */
    } /* end of user's declarations */
} /* end of yylex */

以上是DFA的整体工作代码，也是lexer工作的核心。简单来说，有穷状态机DFA通过处理输入缓冲区的字符，从start状态进行状态转换，直到不能再进行转换或字符串处理完成后，判断是否处于accept状态，若符合则执行相应的动作action，至此实现了 pattern -> action 的对应。

参考： https://happyers.top/uncategorized/understanding-c-lexer-generated-by-flex/

PA3 parser 语法分析

完成此lab前主要学习哈工大编译原理视频。理解任务说明书非常重要。

参考资料：

bison语言： https://www.cnblogs.com/pinkman/p/3179056.html

在这个lab中，我们使用bison语言实现一个语法分析器。语法分析器的输出是抽象语法树AST，bison使用自底向上、左递归的方式，因此可以因无法规约检查出一些不符合语法规则的错误。

生成parser代码分析主要学习： https://happyers.top/compiler/bison-parser/

PA4 Semant 语义分析

此lab的完成主要学习Stanford课程的PPT。

目的：完善由parser生成的AST，为其添加函数和数据成员，便于code generator所用。

主要参考资料：

Cool Reference Manual：参考相关类型规则，标识符作用域规则，Cool语言的相关限制

A Tour of Cool Support Code：结合project中的源码理解已有的架构

主要任务：

1. 找到所有的类并建立继承图

2. 检查继承图是否规范

   继承图不能成环，Cool中从基本类继承有限制，如果A类继承了B类但是B类未定义也是一种错误

3. 对于每一个类：

   1. 遍历AST，把所有可视化的声明加入到符号表中

      需要遍历树，管理从AST中收集到的信息，并由此加强语义分析，同时需要利用SymbolTable确定变量的有效作用域

   2. 检查每一个表达式的类型正确性

      包括检查是否在有需要时声明有效类型，以及根据类型规则验证每个表达式是否具有有效类型

   3. 用类型注释符号表

   4. 给出恰当的错误报告

      除了类继承关系的错误之外，语义分析需要为其他错误给出完整且信息丰富的错误

主要实现：

• 安装基本类
  • Basic Class中只有Object 和 IO 类可以被继承，其余类均不可被继承
• 安装用户自定义类
  • 会检查是否与基本类和已install的用户定义类重复
• 简单检查不正确的继承关系
  • 会检查是否继承自未定义或者不可被继承的父类
• 建立继承树，建立父子继承关系
• 从继承树的根部自顶向下标记reachable
• 判断继承图是否成环
  • 为每一个类继承节点设置父子节点关系，由于Cool中的继承是单继承的，每个没有继承父类的节点都设置为继承自父类，因此如果出现成环的情况，该环一定独立于以Object为根的AST。从抽象语法树的根Object出发，递归遍历AST树，为每一个子类标记为Reachable，再次遍历所有的类继承节点，若出现没有被标记过的类，则说明该继承图中存在环，退出。
• 建立feature_table，添加每一个类的attr和method
• 检查main函数
• 从Root自顶向下检查每一个类的features：对类中的每一个attr和method进行类型检查

具体实现：https://github.com/Theffth/skr_university/tree/master/compiler/cool/assignments

项目地址：https://github.com/Theffth/skr_university/tree/master/compiler

思考问题

• 浮点数和无符号整数的文法

  • 无符号整数的文法：

    ​ S->DE

    ​ E->ET| ε

    ​ T->0|D

    ​ D->1|2|3|4|5|6|7|8|9

  • 浮点数的文法

    ​ S -> WpR

    ​ W -> DE

    ​ E -> R | ε

    ​ T -> 0|D

    ​ D -> 1|2|3|4|5|6|7|8|9

• 各类文法的使用条件和比较

  • 自顶向下分析：预测分析法

    ​ LL(1)文法：满足同一非终结符的可产生式的可选集互不相交

    ​ 条件：A-> α | β

    • α 和 β 均不能推导出 ε
    • α 和 β 至多有一个推导出 ε

  • 自底向上分析：移入-归约分析

    • 关键问题：如何识别句柄？
      • LR分析法
        • LR(0)分析 ：存在移进-归约冲突 & 归约-归约冲突 ==>
        • SLR分析 : 通过简单的向前查看一个符号以确定是否是归约或如何归约，但只是必要不充分条件 ==>
        • LR(1)分析 ：在特定位置，A的后继集合是FOLLOW(A)的子集，但比LR(0)分析的状态多很多 ==>
        • LALR分析：把没有冲突的状态集进行合并，但可能会出现归约-归约冲突和推迟错误的发现
        • 综上：SLR < LALR < LR(1)

• for (nd = lookup_class(type1); !type_leq(type2, nd->get_name()); nd = nd->get_parentnd())

  可以改成type_leq(nd->get_name(),type2) 吗？

  不可以，在COOL语言中没有定义>，在类型检查中≤的含义是继承自，需要看继承图中的父子关系。如果求两个类型的最小上界类型的话，应该从一个结点出发一直搜索直到找到另一个节点的父类，如果改成type_leq(nd->get_name(),type2)的话，只要nd不继承自type2就会终止循环并返回nd，可见，两者终止条件不同。

• Post author: Th3ffth
• Post link: http://theffth.github.io/2020/07/29/Compiler-CS143/
• Copyright Notice: All articles in this blog are licensed under unless stating additionally.