必威体育Betway必威体育官网
当前位置:首页 > IT技术

编译器----语法分析

时间:2019-06-04 14:44:09来源:IT技术作者:seo实验室小编阅读:83次「手机版」
 

语法分析器

本文通过学习王博俊、张宇的《DIY Compiler and Linker》 ,实现语法分析器,一方面作为自己的学习笔记,一方面也作与大家分享与交流

代码放在github上

一、语法分析的任务

语法分析任务是在词法分析识别出单词符号的基础上,分析源程序的语法结构,即分析由这些单词如何组成各种语法成分,比如“声明”、“函数”、“语句”、“表达式”等,并分析判断程序的语法结构是否复合语法规则。

语法分析分为自上而下和自下而上两个大类,自上而下核心思路是推导,自下而上核心思路是规约,本语法分析采用自上而下的方法。

在《编译原理》课上学到,自上而下方法需要避免左递归、消除回溯。自上而下分析方法分为两种:递归子程序法和预测分析方法,这里采用递归子程序法。

二、语法定义

在实现语法分析之前,先对语言的语法进行定义。

先列出巴科斯范式(EBNF)语法符号表,以防看不懂语法定义:

EBNF元符号 含义
::= 意思是“推导为”
|
{} 含0次在内任意多次重复
[] 含0次和1次重复
() 括号内看作一项
. 一条生成规则的结束
<> 非终结符
“” 终结符

2.1 外部定义

<翻译单元>::={<外部声明>}<文件结束符>

<外部声明>::=<函数定义>|<声明>

2.1.1 函数定义

<函数定义>::=<类型区分符><声明符><函数体>

<函数体>::=<复合语句>

2.1.2 声明

<声明>::=<类型区分符>[<初值声明符表>]<分号>

<初值声明符表>::=<初值声明符>{<逗号><初值声明符>}

<初值声明符>::=<声明符>|<声明符><赋值运算符><初值符>

2.1.3 类型区分符

<类型区分符>::=<void关键字>|<char关键字>|<short关键字>|<int关键字>|<结构区分符>

<结构区分符>::=<struct关键字><标识符><左大括号><结构声明表><右大括号>|<struct关键字><标识符>

<结构声明表>::=<结构声明>{<结构声明>}

<结构声明>::=<类型区分符>{<结构声明符表>}<分号>

<结构声明符表>::=<声明符>{<逗号><声明符>}

2.1.4 声明符

<声明符>::={<指针>}[<调用约定>][<结构体成员对齐>]<直接声明符>

<调用约定>::=<__cdecl关键字>|<__stdcall关键字>

<结构体成员对齐>::=<__align关键字><左小括号><整数常量><右小括号>

<指针>::=<星号>

<直接声明符>::=<标识符><直接声明符后缀>

<直接声明符后缀>::={<左中括号><右中括号>
    |<左中括号><整数常量><右中括号>
    |<左小括号><右小括号>
    |<左小括号><形参表><右小括号>}

<参数声明>::=<类型区分符><声明符>

2.1.5 初值符

<初值符>::=<赋值表达式>

2.2 语句

<语句>::={<复合语句>|
        <if语句>|
        <for语句>|
        <break语句>|
        <continue语句>|
        <return语句>|
        <表达式语句>}

2.2.1 复合语句

<复合语句>::=<左大括号>{<声明>}{<语句>}<右大括号>

2.2.2 表达式语句与空语句

<表达式语句>::=[<expression>]<分号>

2.2.3 选择语句

<if语句>::=<if关键字><左小括号><表达式><右小括号><语句>[<else关键字><语句>]

2.2.4 循环语句

<for语句>::=<for关键字><左小括号><表达式语句><表达式语句><表达式><右小括号><语句>

2.2.5 跳转语句

<continue语句>::=<continue关键字><分号>

<break语句>::=<break关键字><分号>

<return语句>::=<return关键字><expression><分号>

2.3 表达式

<表达式>::=<赋值表达式>{<逗号><赋值表达式>}

2.3.1 赋值表达式

<赋值表达式>::=<相等类表达式>|<一元表达式><赋值等号><赋值表达式>

2.3.2 相等类表达式

<相等类表达式>::=<关系表达式>{<等于号><关系表达式>|<不等于号><关系表达式>}

2.3.3 关系表达式

<关系表达式>::=<加减类表达式>{
            <小于号><加减类表达式>
            |<大于号><加减类表达式>
            |<小于等于号><加减类表达式>
            |<大于等于号><加减类表达式>}

2.3.4 加减类表达式

<加减类表达式>::=<乘除类表达式>{
            <加号><乘除类表达式>
            <减号><乘除类表达式>}

2.3.5 乘除类表达式

<乘除类表达式>::=<一元表达式>{
            <星号><一元表达式>
            |<除号><一元表达式>
            |<取余运算符><一元表达式>}

2.3.6 一元表达式

<一元表达式>::=<后缀表达式>
            |<与号><一元表达式>
            |<星号><一元表达式>
            |<加号><一元表达式>
            |<减号><一元表达式>
            |<sizeof表达式>

<sizeof表达式>::=<sizeof关键字>(<类型区分符>)

2.3.7 后缀表达式

<后缀表达式>::=<初等表达式>{
            <左中括号><expression><右中括号>
            |<左小括号><右小括号>
            |<左小括号><实参表达式表><右小括号>
            |<点号>IDENTIFIER
            |<箭头>IDENTIFIER}

<实参表达式表>::=<赋值表达式>{<逗号><赋值表达式>}

2.3.8 初等表达式

<初等表达式>::=<标识符>|<整数常量>|<字符串常量>|<字符常量>|(<表达式>)

三、语法分析的实现

为了将语法分析表示出来,我们给源代码进行语法缩进,来表示顺利实现语法分析

语法缩进由两个全局变量控制:

int syntax_state;  //语法状态
int syntax_level;  //缩进级别

语法状态取值为:

enum e_SynTaxState
{
    SNTX_NUL,       // 空状态,没有语法缩进动作
    SNTX_SP,        // 空格 int a; int __stdcall messageBoxA(); return 1;
    SNTX_LF_HT,     // 换行并缩进,每一个声明、函数定义、语句结束都要置为此状态
    SNTX_DELAY      // 延迟取出下一单词后确定输出格式,取出下一个单词后,根据单词类型单独调用syntax_indent确定格式进行输出 
};

通过Tab键控制缩进级别:

void print_tab(int n)
{
    int i = 0;
    for (; i < n; i++)
        printf("\t");
}

语法缩进程序为:

void syntax_indent()
{
    switch (syntax_state)
    {
    case SNTX_NUL:
        color_token(LEX_NORMAL);
        break;
    case SNTX_SP:
        printf(" ");
        color_token(LEX_NORMAL);
        break;
    case SNTX_LF_HT:
    {
        if (token == TK_END)        // 遇到'}',缩进减少一级
            syntax_level--;
        printf("\n");
        print_tab(syntax_level);
    }
    color_token(LEX_NORMAL);
    break;
    case SNTX_DELAY:
        break;
    }
    syntax_state = SNTX_NUL;
}

不仅延续之间词法分析的词法着色,并且加上了语法缩进

每次在取单词时执行syntax_indent()函数

void get_token()
{
    ...
    syntax_indent();
}

3.1 外部定义语法分析

语法定义:

<翻译单元>::={<外部声明>}<文件结束符>
<外部声明>::=<函数定义>|<声明>

<函数定义>::=<类型区分符><声明符><函数体>
<函数体>::=<复合语句>

<声明>::=<类型区分符>[<初值声明符表>]<分号>
<初值声明符表>::=<初值声明符>{<逗号><初值声明符>}
<初值声明符>::=<声明符>|<声明符><赋值运算符><初值符>

<类型区分符>::=<void关键字>|<char关键字>|<short关键字>|<int关键字>|<结构区分符>
<结构区分符>::=<struct关键字><标识符><左大括号><结构声明表><右大括号>|<struct关键字><标识符>
<结构声明表>::=<结构声明>{<结构声明>}
<结构声明>::=<类型区分符>{<结构声明符表>}<分号>
<结构声明符表>::=<声明符>{<逗号><声明符>}

<声明符>::={<指针>}[<调用约定>][<结构体成员对齐>]<直接声明符>
<调用约定>::=<__cdecl关键字>|<__stdcall关键字>
<结构体成员对齐>::=<__align关键字><左小括号><整数常量><右小括号>
<指针>::=<星号>
<直接声明符>::=<标识符><直接声明符后缀>
<直接声明符后缀>::={<左中括号><右中括号>
    |<左中括号><整数常量><右中括号>
    |<左小括号><右小括号>
    |<左小括号><形参表><右小括号>}
<参数声明>::=<类型区分符><声明符>

<初值符>::=<赋值表达式>

3.1.1 翻译单元

翻译单元的语法定义:

<translation_unit>::={external_declaration}<TK_EOF>

翻译单元的语法描述图:

这里写图片描述

翻译单元的代码:

void translation_unit()
{
    while (token != TK_EOF)
    {
        external_declaration(SC_GLOBAL);
    }
}

3.1.2 外部声明

外部声明的语法定义:

<external_declaration>::=<function_definition>|<declaration>
<function_definition>::= <type_specifier> <declarator><funcbody>
<declaration>::= <type_specifier><TK_SEMICOLON>|<type_specifier>< init_declarator_list><TK_SEMICOLON>
<init_declarator_list>::=<init_declarator>{<TK_comma> <init_declarator>}
<init_declarator>::=<declarator>|<declarator> <TK_assign><initializer>

等价转换后可以得到外部声明的语法定义:

<external_declaration>::=<type_specifier> (<TK_SEMICOLON>
|<declarator><funcbody>
|<declarator>[<TK_ASSIGN><initializer>]
{<TK_COMMA><declarator>[<TK_ASSIGN><initializer>]}
<TK_SEMICOLON>)

外部声明的语法描述图:

这里写图片描述

外部声明的语法分析函数:

void external_declaration(int l)
{
    if (!type_specifier())
    {
        expect("<类型区分符>");
    }

    if (token == TK_SEMICOLON) //如果取词到分号
    {
        get_token();
        return;
    }
    while (1)// 逐个分析声明或函数定义
    {
        declarator();
        if (token == TK_BEGIN)
        {
            if (l == SC_local)
                ERROR("不支持函数嵌套定义");
            funcbody();
            break;
        }
        else
        {
            if (token == TK_ASSIGN)
            {
                get_token();
                initializer();
            }

            if (token == TK_COMMA)
            {
                get_token();
            }
            else
            {
                syntax_state = SNTX_LF_HT;
                skip(TK_SEMICOLON);
                break;
            }
        }
    }
}

3.1.3 类型区分符

类型区分符的语法定义:

<type_specifier>::= <KW_INT>
        | <KW_CHAR>
        | <KW_SHORT>
        | <KW_VOID >
        | <struct_specifier>

类型区分符的语法描述图:

这里写图片描述

外部声明的语法分析函数:

int type_specifier()
{
    int type_found = 0;
    switch (token)
    {
    case KW_CHAR:
        type_found = 1;
        syntax_state = SNTX_SP;
        get_token();
        break;
    case KW_SHORT:
        type_found = 1;
        syntax_state = SNTX_SP;
        get_token();
        break;
    case KW_VOID:
        type_found = 1;
        syntax_state = SNTX_SP;
        get_token();
        break;
    case KW_INT:
        syntax_state = SNTX_SP;
        type_found = 1;
        get_token();
        break;
    case KW_STRUCT:
        syntax_state = SNTX_SP;
        struct_specifier();
        type_found = 1;
        break;
    default:
        break;
    }
    return type_found;
}

3.1.4 结构区分符

结构区分符的语法定义:

<struct_specifier>::=
    <KW_STRUCT><IDENTIFIER><TK_BEGIN><struct_declaration_list><TK_END>
    | <KW_STRUCT>  <IDENTIFIER>

结构区分符的语法描述图:

这里写图片描述

结构区分符代码:

void struct_specifier()
{
    int v;

    get_token();    
    v = token;

    syntax_state = SNTX_DELAY;      // 新取单词不即时输出,延迟到取出单词后根据单词类型判断输出格式
    get_token();

    if(token == TK_BEGIN)           // 适用于结构体定义
        syntax_state = SNTX_LF_HT;
    else if(token == TK_CLOSEPA)    // 适用于 sizeof(struct struct_name)
        syntax_state = SNTX_NUL;
    else                            // 适用于结构变量声明
        syntax_state = SNTX_SP;
    syntax_indent();    

    if (v < TK_IDENT)               // 关键字不能作为结构名称
        expect("结构体名");

    if (token == TK_BEGIN) 
    {
        struct_declaration_list();
    }
}
3.1.4.1 结构声明符表

结构声明符表的语法定义:

 <struct_declaration_list>::=<struct_declaration>{<struct_declaration>}

结构声明符表的语法描述图:

这里写图片描述

结构声明符表的代码:

void struct_declaration_list()
{
    int maxalign, offset;

    syntax_state = SNTX_LF_HT;  // 第一个结构体成员与'{'不写在一行
    syntax_level++;             // 结构体成员变量声明,缩进增加一级

    get_token();
    while (token != TK_END)
    {
        struct_declaration(&maxalign, &offset);
    }
    skip(TK_END);

    syntax_state = SNTX_LF_HT;
}
3.1.4.2 结构声明

结构声明的语法定义:

<struct_declaration>::=
        <type_specifier><struct_declarator_list><TK_SEMICOLON>

<struct_declarator_list>::=<declarator>{<TK_COMMA><declarator>}

等价转换后语法定义为:

<struct_declaration>::=
        <type_specifier><declarator>{<TK_COMMA><declarator>}
        <TK_SEMICOLON>

结构声明的语法描述图:

这里写图片描述

结构声明的代码:

void struct_declaration()
{
    type_specifier();
    while (1)
    {
        declarator();

        if (token == TK_SEMICOLON || token == TK_EOF)
            break;
        skip(TK_COMMA);
    }
    syntax_state = SNTX_LF_HT;
    skip(TK_SEMICOLON);
}

3.1.5 声明符

声明符语法:

<declarator>::={<pointer>}{<function_calling_convention>}
    {<struct_member_alignment>}<direct_declarator>

<pointer>::=<TK_STAR>

等价转化后为:

<declarator>::={<TK_STAR>}[<function_calling_convention>]
    [<struct_member_alignment>]<direct_declarator>

声明符的语法描述图:

这里写图片描述

声明符的代码为:

void declarator()
{
    while (token == TK_STAR)
    {
        get_token();
    }
    function_calling_convention();
    struct_member_alignment();
    direct_declarator();
}
3.1.5.1 函数调用约定

函数调用约定语法:

<function_calling_convention>::=<KW_CDECL>|<KW_STDCALL>

函数调用约定的描述图:

这里写图片描述

函数调用约定的代码:

void function_calling_convention()
{
    if (token == KW_CDECL || token == KW_STDCALL)
    {
        syntax_state = SNTX_SP;
        get_token();
    }
}
3.1.5.2 结构成员对齐

结构成员对齐语法:

<struct_member_alignment>::=<KW_ALIGN><TK_OPENPA><TK_CINT><TK_CLOSEPA>

结构成员对齐的描述图:

这里写图片描述

结构成员对齐的代码:

void struct_member_alignment()
{
    if (token == KW_ALIGN)
    {
        get_token();
        skip(TK_OPENPA);
        if (token == TK_CINT)
        {
            get_token();
        }
        else
            expect("整数常量");
        skip(TK_CLOSEPA);
    }
}
3.1.5.3 直接声明符

直接声明符语法:

<direct_declarator>::=  <IDENTIFIER><direct_declarator_postfix>

直接声明符的描述图:

这里写图片描述

直接声明符的代码:

void direct_declarator()
{
    if (token >= TK_IDENT)
    {
        get_token();
    }
    else
    {
        expect("标识符");
    }
    direct_declarator_postfix();
}
3.1.5.4 直接声明后缀

直接声明后缀语法:

<direct_declarator_ postfix>::= {<TK_OPENBR><TK_CINT><TK_CLOSEBR>
        |<TK_OPENBR><TK_CLOSEBR>
        |<TK_OPENPA><parameter_type_list><TK_CLOSEPA>
        |<TK_OPENPA><TK_CLOSEPA>}

直接声明后缀描述图:

这里写图片描述

直接声明后缀代码:

void direct_declarator_postfix()
{
    int n;

    if (token == TK_OPENPA)
    {
        parameter_type_list();
    }
    else if (token == TK_OPENBR)
    {
        get_token();
        if (token == TK_CINT)
        {
            get_token();
            n = tkvalue;
        }
        skip(TK_CLOSEBR);
        direct_declarator_postfix();
    }
}
3.1.5.5 形参类型表

形参类型表语法:

<parameter_type_list>::=<parameter_list>
    |<parameter_list><TK_COMMA><TK_ELLIPSIS>

<parameter_list>::=<parameter_declaration>
    {<TK_COMMA ><parameter_declaration>}

<parameter_declaration>::=<type_specifier>{<declarator>}

等价转换后语法:

 <parameter_type_list>::=<type_specifier>{<declarator>}
    {<TK_COMMA><type_specifier>{<declarator>}}<TK_COMMA><TK_ELLIPSIS>

形参类型表语法图:

这里写图片描述

形参类型表代码:

void parameter_type_list()
{

    get_token();
    while (token != TK_CLOSEPA)
    {
        if (!type_specifier())
        {
            error("无效类型标识符");
        }
        declarator();
        if (token == TK_CLOSEPA)
            break;
        skip(TK_COMMA);
        if (token == TK_ELLIPSIS)
        {
            //func_call = KW_CDECL;
            get_token();
            break;
        }
    }
    syntax_state = SNTX_DELAY;
    skip(TK_CLOSEPA);
    if (token == TK_BEGIN)          // 函数定义
        syntax_state = SNTX_LF_HT;
    else                            // 函数声明
        syntax_state = SNTX_NUL;
    syntax_indent();
}
3.1.5.6 函数体

函数体的语法:

<funcbody>::=<compound_statement>

在这里函数体只推导出复合语句

函数体的语法图:

这里写图片描述

函数体的代码:

void funcbody()
{
    compound_statement();
}
3.1.5.6 初值符

初值符的语法:

< initializer>::=<assignment_expression>

这里也是初值符只推导出赋值表达式

初值符的语法图:

这里写图片描述

初值符的代码:

void initializer()
{
    assignment_expression();
}

3.2 语句语法分析

语法定义:

<语句>::={<复合语句>|
        <if语句>|
        <for语句>|
        <break语句>|
        <continue语句>|
        <return语句>|
        <表达式语句>}

<复合语句>::=<左大括号>{<声明>}{<语句>}<右大括号>

<表达式语句>::=[<expression>]<分号>

<if语句>::=<if关键字><左小括号><表达式><右小括号><语句>[<else关键字><语句>]

<for语句>::=<for关键字><左小括号><表达式语句><表达式语句><表达式><右小括号><语句>

<continue语句>::=<continue关键字><分号>
<break语句>::=<break关键字><分号>
<return语句>::=<return关键字><expression><分号>

3.2.1 语句

语句的语法:

<statement >::=<compound_statement>
        | <if_statement>
        | <return_statement>
        | <break_statement>
        | <continue_statement>
        | <for_statement>
        | <expression_statement>

语句的语法图:

这里写图片描述

语句的代码:

void statement()
{
    switch (token)
    {
    case TK_BEGIN:
        compound_statement();
        break;
    case KW_IF:
        if_statement();
        break;
    case KW_RETURN:
        return_statement();
        break;
    case KW_BREAK:
        break_statement();
        break;
    case KW_CONTINUE:
        continue_statement();
        break;
    case KW_FOR:
        for_statement();
        break;
    default:
        expression_statement();
        break;
    }
}

3.2.1 复合语句

复合语句的语法:

<compound_statement>::=<TK_BEGIN>{<declaration>}{<statement>}<TK_END>

复合语句的语法图:

这里写图片描述

语句的代码:

void compound_statement()
{
    syntax_state = SNTX_LF_HT;
    syntax_level++;                     // 复合语句,缩进增加一级

    get_token();
    while (is_type_specifier(token))
    {
        external_declaration(SC_LOCAL);
    }
    while (token != TK_END)
    {
        statement();
    }

    syntax_state = SNTX_LF_HT;
    get_token();
}

复合语句由声明和语句组成,声明在前,语句在后。在应该出现声明的地方用解析声明函数external_declaration(),在应该出现语句的地方用语句解析函数statement()解析语句。

代码中的is_type_specifier()函数就是根据当前单词判断是否是声明:

int is_type_specifier(int v)
{
    switch (v)
    {
    case KW_CHAR:
    case KW_SHORT:
    case KW_INT:
    case KW_VOID:
    case KW_STRUCT:
        return 1;
    default:
        break;
    }
    return 0;
}

3.2.2 表达式语句

表达式语句的语法:

<expression_statement>::= <TK_SEMICOLON>|<expression> <TK_SEMICOLON>

表达式语句的语法图:

这里写图片描述

表达式语句的代码:

void expression_statement()
{
    if (token != TK_SEMICOLON)
    {
        expression();
    }
    syntax_state = SNTX_LF_HT;
    skip(TK_SEMICOLON);
}

3.2.3 选择语句

选择语句的语法:

<if_statement>::=<KW_IF><TK_OPENPA><expression>
    <TK_CLOSEPA><statement>[<KW_ELSE><statement>]

选择语句的语法图:

这里写图片描述

选择语句的代码:

void if_statement()
{
    syntax_state = SNTX_SP;
    get_token();
    skip(TK_OPENPA);
    expression();
    syntax_state = SNTX_LF_HT;
    skip(TK_CLOSEPA);
    statement();
    if (token == KW_ELSE)
    {
        syntax_state = SNTX_LF_HT;
        get_token();
        statement();
    }
}

3.2.4 循环语句

循环语句的语法:

<for_statement>::=<KW_FOR><TK_OPENPA><expression_statement>
    <expression_statement><expression><TK_CLOSEPA><statement>

循环语句的语法图:

这里写图片描述

循环语句的代码:

void for_statement()
{
    get_token();
    skip(TK_OPENPA);
    if (token != TK_SEMICOLON)
    {
        expression();
    }
    skip(TK_SEMICOLON);
    if (token != TK_SEMICOLON)
    {
        expression();
    }
    skip(TK_SEMICOLON);
    if (token != TK_CLOSEPA)
    {
        expression();
    }
    syntax_state = SNTX_LF_HT;
    skip(TK_CLOSEPA);
    statement();//只有此处用到break,及continue,一个循环中可能有多个break,或多个continue,故需要拉链以备反填
}

3.2.5 跳转语句

跳转语句包括continue语句、break语句和return语句

语法图为:

这里写图片描述

3.2.5.1 continue语句

continue语句的语法:

<continue_statement>::=<KW_CONTINUE><TK_SEMICOLON>

continue语句的代码:

void continue_statement()
{
    get_token();
    syntax_state = SNTX_LF_HT;
    skip(TK_SEMICOLON);
}
3.2.5.2 break语句

break语句的语法:

<break_statement>::=<KW_BREAK><TK_SEMICOLON>

break语句的代码:

void break_statement()
{
    get_token();
    syntax_state = SNTX_LF_HT;
    skip(TK_SEMICOLON);
}
3.2.5.3 return语句

return语句的语法:

<return_statement>::=<KW_RETURN><TK_SEMICOLON>
        |<KW_RETURN><expression><TK_SEMICOLON>

return语句的代码:

void return_statement()
{
    syntax_state = SNTX_DELAY;
    get_token();
    if (token == TK_SEMICOLON)  // 适用于 return;
        syntax_state = SNTX_NUL;
    else                        // 适用于 return <expression>;
        syntax_state = SNTX_SP;
    syntax_indent();

    if (token != TK_SEMICOLON)
    {
        expression();
    }
    syntax_state = SNTX_LF_HT;
    skip(TK_SEMICOLON);
}

3.3 表达式语法分析

语法定义:

<表达式>::=<赋值表达式>{<逗号><赋值表达式>}

<相等类表达式>::=<关系表达式>{<等于号><关系表达式>|<不等于号><关系表达式>}

<关系表达式>::=<加减类表达式>{
            <小于号><加减类表达式>
            |<大于号><加减类表达式>
            |<小于等于号><加减类表达式>
            |<大于等于号><加减类表达式>}

<加减类表达式>::=<乘除类表达式>{
            <加号><乘除类表达式>
            <减号><乘除类表达式>}

<乘除类表达式>::=<一元表达式>{
            <星号><一元表达式>
            |<除号><一元表达式>
            |<取余运算符><一元表达式>}

<一元表达式>::=<后缀表达式>
            |<与号><一元表达式>
            |<星号><一元表达式>
            |<加号><一元表达式>
            |<减号><一元表达式>
            |<sizeof表达式>
<sizeof表达式>::=<sizeof关键字>(<类型区分符>)

<后缀表达式>::=<初等表达式>{
            <左中括号><expression><右中括号>
            |<左小括号><右小括号>
            |<左小括号><实参表达式表><右小括号>
            |<点号>IDENTIFIER
            |<箭头>IDENTIFIER}
<实参表达式表>::=<赋值表达式>{<逗号><赋值表达式>}

<初等表达式>::=<标识符>|<整数常量>|<字符串常量>|<字符常量>|(<表达式>)

3.3.1 表达式

表达式的语法图:

这里写图片描述

表达式的代码和语法:

/***********************************************************
* 功能:   解析表达式
*
* <expression>::=<assignment_expression>{<TK_COMMA><assignment_expression>}
**********************************************************/
void expression()
{
    while (1)
    {
        assignment_expression();
        if (token != TK_COMMA)
            break;
        get_token();
    }
}

3.3.2 赋值表达式

赋值表达式的语法图:

这里写图片描述

赋值表达式的代码和语法:

/***********************************************************
* 功能:   解析赋值表达式
*
* <assignment_expression>::= <equality_expression>
*       |<unary_expression><TK_ASSIGN> <equality_expression>
*
*非等价变换后文法:
* <assignment_expression>::= <equality_expression>
*       {<TK_ASSIGN><assignment_expression>}
**********************************************************/
void assignment_expression()
{
    equality_expression();
    if (token == TK_ASSIGN)
    {
        get_token();
        assignment_expression();
    }
}

3.3.3 相等类表达式

相等类表达式的语法图:

这里写图片描述

相等类表达式的代码和语法:

/***********************************************************
* 功能:   解析相等类表达式
*
* < equality_expression >::=<relational_expression>
*       {<TK_EQ> <relational_expression>
*       |<TK_NEQ><relational_expression>}
**********************************************************/
void equality_expression()
{

    int t;
    relational_expression();
    while (token == TK_EQ || token == TK_NEQ)
    {
        t = token;
        get_token();
        relational_expression();
    }
}

3.3.4 关系表达式

关系表达式的语法图:

这里写图片描述

关系表达式的代码和语法:

/***********************************************************
* 功能:   解析关系表达式
*
* <relational_expression>::=<additive_expression>{
*       <TK_LT><additive_expression>
*       |<TK_GT><additive_expression>
*       |<TK_LEQ><additive_expression>
*       |<TK_GEQ><additive_expression>}
**********************************************************/
void relational_expression()
{
    additive_expression();
    while ((token == TK_LT || token == TK_LEQ) ||
        token == TK_GT || token == TK_GEQ)
    {
        get_token();
        additive_expression();
    }
}

3.3.5 加减类表达式

加减类表达式的语法图:

这里写图片描述

加减类表达式的代码和语法:

/***********************************************************
* 功能:   解析加减类表达式
*
* <additive_expression>::=< multiplicative_expression>
*       {<TK_PLUS> <multiplicative_expression>
*       <TK_MINUS>< multiplicative_expression>}
**********************************************************/
void additive_expression()
{
    multiplicative_expression();
    while (token == TK_PLUS || token == TK_MINUS)
    {
        get_token();
        multiplicative_expression();
    }
}

3.3.6 乘除类表达式

乘除表达式的语法图:

这里写图片描述

乘除类表达式的代码和语法:

/***********************************************************
* 功能:   解析乘除类表达式
*
* <multiplicative_expression>::=<unary_expression>
*       {<TK_STAR>  < unary_expression >
*       |<TK_DIVIDE>< unary_expression >
*       |<TK_MOD>  < unary_expression >}
**********************************************************/
void multiplicative_expression()
{
    int t;
    unary_expression();
    while (token == TK_STAR || token == TK_DIVIDE || token == TK_MOD)
    {
        t = token;
        get_token();
        unary_expression();
    }
}

3.3.6 一元表达式

一元表达式的语法图:

这里写图片描述

一元表达式的代码和语法:

/***********************************************************
* 功能:   解析一元表达式
*
* <unary_expression>::= <postfix_expression>
*           |<TK_AND><unary_expression>
*           |<TK_STAR><unary_expression>
*           |<TK_PLUS><unary_expression>
*           |<TK_MINUS><unary_expression>
*           |<KW_SIZEOF><TK_OPENPA><type_specifier><TK_ CLOSEPA>
**********************************************************/
void unary_expression()
{
    switch (token)
    {
    case TK_AND:
        get_token();
        unary_expression();
        break;
    case TK_STAR:
        get_token();
        unary_expression();
        break;
    case TK_PLUS:
        get_token();
        unary_expression();
        break;
    case TK_MINUS:
        get_token();
        unary_expression();
        break;
    case KW_SIZEOF:
        sizeof_expression();
        break;
    default:
        postfix_expression();
        break;
    }
}
3.3.6.1 sizeof表达式

sizeof表达式的语法图:

这里写图片描述

sizeof表达式的代码和语法:

/***********************************************************
* 功能:   解析sizeof表达式
*
* <sizeof_expression>::=
*       <KW_SIZEOF><TK_OPENPA><type_specifier><TK_ CLOSEPA>
**********************************************************/
void sizeof_expression()
{
    get_token();
    skip(TK_OPENPA);
    type_specifier();
    skip(TK_CLOSEPA);
}

3.3.7 后缀表达式

后缀表达式的语法图:

这里写图片描述

后缀表达式的代码和语法:

/***********************************************************
* 功能:   解析后缀表达式
*
* <postfix_expression>::=  <primary_expression>
*       {<TK_OPENBR><expression> <TK_CLOSEBR>
*       |<TK_OPENPA><TK_CLOSEPA>
*       |<TK_OPENPA><argument_expression_list><TK_CLOSEPA>
*       |<TK_DOT><IDENTIFIER>
*       |<TK_POINTSTO><IDENTIFIER>}
**********************************************************/
void postfix_expression()
{
    primary_expression();
    while (1)
    {
        if (token == TK_DOT || token == TK_POINTSTO)
        {
            get_token();
            token |= SC_MEMBER;
            get_token();
        }
        else if (token == TK_OPENBR)
        {
            get_token();
            expression();
            skip(TK_CLOSEBR);
        }
        else if (token == TK_OPENPA)
        {
            argument_expression_list();
        }
        else
            break;
    }
}
3.3.7.1 实参表达式

实参表达式的语法图:

这里写图片描述

实参表达式的代码和语法:

/***********************************************************
* 功能:   解析实参表达式表
*
* <argument_expression_list >::=<assignment_expression>
*       {<TK_COMMA> <assignment_expression>}
**********************************************************/
void argument_expression_list()
{
    get_token();
    if (token != TK_CLOSEPA)
    {
        for (;;)
        {
            assignment_expression();
            if (token == TK_CLOSEPA)
                break;
            skip(TK_COMMA);
        }
    }
    skip(TK_CLOSEPA);
    // return value
}

3.3.8 初等表达式

初等表达式的语法图:

这里写图片描述

初等表达式的代码和语法:

/***********************************************************
* 功能:   解析初等表达式
*
* <primary_expression>::=<IDENTIFIER>
*       |<TK_CINT>
*       |<TK_CSTR>
*       |<TK_CCHAR>
*       |<TK_OPENPA><expression><TK_CLOSEPA>
**********************************************************/
void primary_expression()
{
    int t;
    switch (token)
    {
    case TK_CINT:
    case TK_CCHAR:
        get_token();
        break;
    case TK_CSTR:
        get_token();
        break;
    case TK_OPENPA:
        get_token();
        expression();
        skip(TK_CLOSEPA);
        break;
    default:
        t = token;
        get_token();
        if (t < TK_IDENT)
            expect("标识符或常量");
        break;
    }
}

四、执行结果

主程序入口为main.c:

int main(int argc, char ** argv)
{

    fin = fopen("./test.c", "rb");
    system("pause");
    if (!fin)
    {
        printf("不能打开SC源文件!\n");
        return 0;
    }
    init();
    getch();
    get_token();
    translation_unit();
    cleanup();
    fclose(fin);
    printf("%s 语法分析成功!", argv[1]);
    system("pause");
    return 1;
}

对没有缩进的test.c源文件进行语法分析

test.c:

/*********************************************************** 
 * test.c
 **********************************************************/
struct point{int x;  int y;};
void main()
{int arr[10]; int i;    struct point pt;
pt.x =1024;pt.y=768;
for(i = 0; i < 10; i = i + 1)   {arr[i]=i;          
if(i == 6){continue;        }
else{printf("arr[%d]=%d\n",i,arr[i]);}}
printf("pt.x = %d, pt.y = %d\n",pt.x,pt.y);}

可以得到:

这里写图片描述

相关阅读

【编译原理】语法分析(四)

本文是语法分析的第四篇文章,第一篇文章介绍了基本的文法、推导和归约的概念,第二篇文章介绍了自顶向下的语法分析和LL(1)方法,第三

【编译原理】语法分析(三)

常用的语法分析方法包括自顶向下和自底向上的方法,在上一篇文章中已经介绍了自顶向下的语法分析方法,本文将介绍自底向上的语法分析

编译原理实验(三)词法语法分析综合设计

【编译原理】LL(1)语法分析器

1.项目要求文法要求:(1)从文件读入,每条产生式占用一行(2)文法为LL(1)文法从文件中读入文法,从键盘上输入待分析的符号串,采用 LL(1)分析

第五章 语法分析——自下而上分析

本章的语法分析方法与上一章的方法是相反的。上一章节是自上而下的分析,而这一章是自下而上的分析,即从输入串开始,逐步进行归约,将长

分享到:

栏目导航

推荐阅读

热门阅读