编译原理与设计-Lab5-语法分析实验

2020-04-14 2022-07-20

code / report

6 分钟读完 (大约 965 个字) 次访问

选择 C 语言的一个子集，基于 BIT-MiniCC 构建 C 语法子集的语法分析器，该语法分析器能够读入词法分析器输出的存储在文件中的属性字符流，进行语法分析并进行错误处理，如果输入正确时输出 JSON 格式的语法树，输入不正确时报告语法错误。

实现的具体过程和步骤

1 定义C语言子集

参照后续给出的文法，扩充定义自己希望实现的 C 语言语法子集。参考文法只给出了函数定义以及简单的表达式相关的文法。局部变量声明、分支语句以及循环语句等需要自己进行扩充。采用自顶向下的分析方法时，不能有左递归，避免文法产生式的多个候选式存在公共因子。如果出现左递归或者公共因子，则可以通过文法等价变换进行消除。

1 根据C11的语法规则编写C语言子集

statement
    :   labeledStatement
    |   compoundStatement
    |   expressionStatement
    |   selectionStatement
    |   iterationStatement
    |   jumpStatement
    ;
assignmentOperator
    :   '=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<=' | '>>=' | '&=' | '^=' | '|='
    ;
expressionStatement
    :   expression? ';'
    ;
expression
    :   assignmentExpression
    |   expression ',' assignmentExpression
    ;
compoundStatement
    :   '{' blockItemList? '}'
    ;
iterationStatement
    :   'while' '(' expression ')' statement
    |   'do' statement 'while' '(' expression ')' ';'
    |   'for' '(' expression? ';' expression? ';' expression? ')' statement
    |   'for' '(' declaration expression? ';' expression? ')' statement
    ;
selectionStatement
    :   'if' '(' expression ')' statement ('else' statement)?
    |   'switch' '(' expression ')' statement
    ;
jumpStatement
    :   'goto' Identifier ';'
    |   'continue' ';'
    |   'break' ';'
    |   'return' expression? ';'
    |   'goto' unaryExpression ';' // GCC extension
    ;
labeledStatement
    :   Identifier ':' statement
    |   'case' constantExpression ':' statement
    |   'default' ':' statement
    ;

    // 局部变量声明
declarationList
    :   declaration
    |   declarationList declaration
    ;
declarationSpecifier
    :   storageClassSpecifier
    |   typeSpecifier
    |   typeQualifier
    |   functionSpecifier
    |   alignmentSpecifier
    ;
initDeclaratorList
    :   initDeclarator
    |   initDeclaratorList ',' initDeclarator
    ;
initDeclarator
    :   declarator
    |   declarator '=' initializer
    ;
declarator
    :   pointer? directDeclarator gccDeclaratorExtension*
    ;
directDeclarator
    :   Identifier
    |   '(' declarator ')'
    ;
storageClassSpecifier
    :   'typedef'
    |   'extern'
    |   'static'
    |   '_Thread_local'
    |   'auto'
    |   'register'
    ;
typeSpecifier
    :   ('void'
    |   'char'
    |   'short'
    |   'int'
    |   'long'
    |   'float'
    |   'double'
    |   'signed'
    |   'unsigned'
    |   '_Bool'
    ;
typeQualifier
    :   'const'
    ;
pointer
    :   '*' typeQualifierList?
    ;
initializer
    :   assignmentExpression
    |   '{' initializerList '}'
    |   '{' initializerList ',' '}'
    ;
initializerList
    :   designation? initializer
    |   initializerList ',' designation? initializer
    ;
assignmentExpression
    :   conditionalExpression
    |   unaryExpression assignmentOperator assignmentExpression
    ;
// 赋值语句
conditionalExpression
    :   logicalOrExpression ('?' expression ':' conditionalExpression)?
    ;
logicalAndExpression
    :   inclusiveOrExpression
    |   logicalAndExpression '&&' inclusiveOrExpression
    ;
logicalOrExpression
    :   logicalAndExpression
    |   logicalOrExpression '||' logicalAndExpression
    ;
unaryExpression
    :   postfixExpression
    |   '++' unaryExpression
    |   '--' unaryExpression
    |   unaryOperator castExpression
    |   'sizeof' unaryExpression
    |   'sizeof' '(' typeName ')'
    ;
unaryOperator
    :   '&' | '*' | '+' | '-' | '~' | '!'
    ;
constantExpression
    :   conditionalExpression
    ;
expression
    :   assignmentExpression
    |   expression ',' assignmentExpression
    ;
postfixExpression
    :   primaryExpression
    |   postfixExpression '[' expression ']'
    |   postfixExpression '(' argumentExpressionList? ')'
    |   postfixExpression '.' Identifier
    |   postfixExpression '->' Identifier
    |   postfixExpression '++'
    |   postfixExpression '--'
    ;

2 消除左递归

expression
1
2
3
4
expression : assignmentExpression | expression ',' assignmentExpression ;
exp本身不符合LL(0)文法规则，需要消除左递归，消除后expression和expression+分别对应
assignmentExpression
1
2
3
4
assignmentExpression : conditionalExpression | unaryExpression assignmentOperator assignmentExpression ;
conditionalExpression的FIRST几核中包含了unaryExpression的FIRST集合，不符合LL(0)文法规法。BITMiniCC中，对于ASTBinaryExpression节点：
1
2
3
public ASTToken op; public ASTExpression expr1; public ASTExpression expr2;
分别对应assignmentOperator，unaryExpression，assignmentExpression

postfixExpression

postfixExpression
    :   primaryExpression
    |   postfixExpression '[' expression ']'
    |   postfixExpression '(' argumentExpressionList? ')'
    |   postfixExpression '.' Identifier
    |   postfixExpression '->' Identifier
    |   postfixExpression '++'
    |   postfixExpression '--'
    ;

argumentExpressionList

argumentExpressionList
    :   assignmentExpression
    |   argumentExpressionList ',' assignmentExpression
    ;

简化为只有一个参数

2 JAVA实现语法分析器

从递归下降分析方法、LL(1)分析方法、LR 分析方法中选择一种算法，基于 BIT-MiniCC 设计并实现语法分析器。可以使用 ANTLR，也可以手动编码实现。语法分析的输入为词法分析的输出，因此语法分析器首先要读入 xxx.tokens 文件;在分析的过程中构建语法树。

3 将语法树输出为 JSON 文件

未完成

运行效果截图

test0
test1

放大
test2
test3

实验心得体会

这次实验对我来说是前所未有的挑战，看懂框架的文法、参照框架和C语言标准实现语法分析器，在编程能力、数据结构、文法基本理解各方面上都有很大的挑战。
首先是对知识的运用，知识基础之薄弱在应用时原形毕露，
在编码过程我遇到了很多问题，反复调试了很多次都无法正确的运行。树生成失败，空指针，对象初始化等等问题层出不穷，一方面是本身对于框架的研究不够，另一方面也是没有严谨编程习惯
这次实验我投入的时间和精力并不足以达到完成这个实验的要求

title:编译原理与设计-Lab5-语法分析实验

author:Anne416wu

link:https://www.annewqx.top/posts/1742/

publish time:2020-04-14

update time:2022-07-20

编译原理