编译原理与设计-Lab4-文法设计实验

阅读C11-C规范标准文件并按照规范选择C语言子集，使用BNF文法描述。

下载C11-C规范标准文件

下载Java SE12规范标准文件

实验内容

1. 阅读附件提供的 C 语言和 Java 语言的规范草稿，了解语言规范化定义 应包括的具体内容。
2. 选定 C 语言子集，并使用 BNF 表示方法文法进行描述，要求至少包括 表达式、赋值语句、分支语句和循环语句；或者设计一个新的程序设计语言，并 使用文法对该语言的词法规则和文法规则进行描述。

实验过程与方法

本次实验提供 C 语言和 Java 语言的规范草稿，参考相关内容完成语言的设计和定义工作。此外，可以使用 ANTLRWorks 辅助完成语法的设计工作。

理解语言规范

语言标准规范是每个语言的说明文档，定义了语言的字符集、词法规则、语法规则和语义规则，也包括了对程序结构、编译过程、标准库程序以及语言实现等各方面的内容。一个标准规范描述为不同视角的参与者提供了一个一致的参考标准，例如程序员可以根据规范标准编写程序，系统设计者则可以根据这一标准 规范设计编译器、完成运行时环境和库的构造和实现。由于编译器基于同一标准 规范设计，因此才能对程序员编写完成的各式各样的程序进行不同层面验证，并 将其最终翻译为目标代码。同理，所有的程序设计人员都基于同一个标准设计程 序，按照给定的接口调用库函数，因此大家才能交换共享并理解对方的代码，并协同工作完成大规模软件项目的开发。

C语言提出之后呢，随着技术的不断发展，曾经衍生过不同的版本，也就是C语言的不同标准规范。这里我们使用C11-C标准规范来分析。、语法规则和语义规则，也包括了对程序结构、编译过程、标准库程序以及语言实现

• 语言的字符集。字符集是一个语言中所有可出现字符的集合。C11-C的P40页(chap 5.2)中，给出了可使用的字符集合，源代码字符集(source character set)和运行字符集 (execution character set)两种，分别在C语言源码和执行程序中使用，这两个字符集又各自被分为基本字符集(basic character set)和拓展字符集(estended character set)。字符集是设计分割源代码的有限自动机的基础；
• 语言的词法规则。P76(chap6.4 Lexical element)开始，给出了所有词法元素：
  • 词法分析中的token：关键字 keyword， identifier， constant， string-literal， punctuation；
  • 预处理的token：头文件名，标识符，pp-number，字符常量，字符串字面量、分隔符和任何不能匹配上述规则的非空白字符
• 语言的语义规则：P94(chap6.5~6.10)：给出详细的语义规则。
• 这份规范中甚至还给出了对C语言未来发展方向的指导。

阅读关于一个程序设计语言的标准是一件非常痛苦的事情，C11-C标准规范的正文的长度大约有670页，阅读这样一份标准确实需要很多的时间。但这份规范所包涵的内容极广，无论是语言书写者阅读还是为语言设计提供参考都是一份和好的材料。

在C11-C标准规范的p476开始，给出了C语言的句法规范总结Language syntax summary 。我们使用BNF描述C语言，依据的正是这个规范总结，规范总结中对于C语言的描述大概是下面这样:

这个描述的意思是，对于分支语句，一共有三种格式if，if-else，switch。并且这个描述在语法上对每个格式里各部分组成进行了明确定义。之后按照语法规则得到的结构又被分割为一个个的token和词法分析。这就是一个分支语句。

在C语言的标准规范中不仅仅针对语言本身，更明确了C语言源代码到转译为可执行程序的每一步，以及每一步里的数据结构，转换方法、存储进行了严格说明。C语言规范保证了语言的严谨性，尽力消除歧义。但这份规范中也存在较为宽泛的问题。比如说数据类型，它定义 long型数据长度不短于 int 型，short 型不长于 int 型。这会导致对于 int 型的变量，在 Turbo C 里面它占16位。 然而在VC 里面，一个整型变量却占有32位。在不同的开发平台上关于整型变量的定义不同，导致相同的程序在不同的编译器上运行 可能会有不同的解释 从而造成相同的程序在不同的平台上的运行结果也有可能是不同的。

C语言文法设计报告

字母表

1
2
3
4
5
6

# 非数字 Nondigits
    a..z|A..Z
# 数字 Digits
    0..9
# 29个符号：
    !"#%&'()*+,-./: ;<=>?[\]^_{|}~

语法规则

使用ANTLR文法描述方法

以下将使用ANTLR文法描述C语言的语法规则。ANTLR输入文法是一种扩展的 BNF 表示方法。以下的文法规则并不完整， declaration和 functionDefinition的文法较为庞杂，在此不表。

语法分析的终结符一共有5种：关键字 keyword /标识符 Identifier /字符串字面量 StringLiteral /常量 Constant /分隔符及运算符 punctuator，即词法分析得到的5种token。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 文法分析入口
translationUnit
    :   externalDeclaration
    |   translationUnit externalDeclaration
    ;
externalDeclaration
    :   functionDefinition
    |   declaration
    |   ';' // stray ;
    ;
// 语句类型
statement
    :   labeledStatement
    |   compoundStatement
    |   expressionStatement
    |   selectionStatement
    |   iterationStatement
    |   jumpStatement
    |   ('__asm' | '__asm__') ('volatile' | '__volatile__') '(' (logicalOrExpression (',' logicalOrExpression)*)? (':' (logicalOrExpression (',' logicalOrExpression)*)?)* ')' ';'
    ;

赋值语句

赋值语句，语法成分为 assignmentExpression ，有两种类型

1. 条件表达式 conditionalExpression ，因为用多元运算符也可以对变量进行赋值操作

2. 一元表达式 unaryExpression +赋值运算符 assignmentOperator +赋值语句 assignmentExpression

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// 赋值语句
assignmentExpression
    :   conditionalExpression
    |   unaryExpression assignmentOperator assignmentExpression
    ;
// 赋值运算符
assignmentOperator
    :   '=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<=' | '>>=' | '&=' | '^=' | '|='
    ;
// 判断语句
conditionalExpression
    :   logicalOrExpression ('?' expression ':' conditionalExpression)?
    ;
// 逻辑语句
logicalAndExpression
    :   inclusiveOrExpression
    |   logicalAndExpression '&&' inclusiveOrExpression
    ;
logicalOrExpression
    :   logicalAndExpression
    |   logicalOrExpression '||' logicalAndExpression
    ;
// 一元表达式
unaryExpression
    :   postfixExpression
    |   '++' unaryExpression
    |   '--' unaryExpression
    |   unaryOperator castExpression
    |   'sizeof' unaryExpression
    |   'sizeof' '(' typeName ')'
    |   '_Alignof' '(' typeName ')'
    |   '&&' Identifier // GCC extension address of label
    ;
// 一元运算符
unaryOperator
    :   '&' | '*' | '+' | '-' | '~' | '!'
    ;
postfixExpression
    :   primaryExpression
    |   postfixExpression '[' expression ']'
    |   postfixExpression '(' argumentExpressionList? ')'
    |   postfixExpression '.' Identifier
    |   postfixExpression '->' Identifier
    |   postfixExpression '++'
    |   postfixExpression '--'
    |   '(' typeName ')' '{' initializerList '}'
    |   '(' typeName ')' '{' initializerList ',' '}'
    |   '__extension__' '(' typeName ')' '{' initializerList '}'
    |   '__extension__' '(' typeName ')' '{' initializerList ',' '}'
    ;

表达式

1
2
3
4

expression
    :   assignmentExpression
    |   expression ',' assignmentExpression
    ;

分支语句

分支语句，语法成分为 selectionStatement ，有三种类型(ANTLR简写为两种)

1. 关键字if开头，expression 作为判断条件，然后是执行的结构体 statement ；如果只有有else关键字，则还有一个执行的结构体 statement
2. 关键字switch开头， expression作为判断条件，然后是执行的结构体 statement

1
2
3
4

selectionStatement
    :   'if' '(' expression ')' statement ('else' statement)?
    |   'switch' '(' expression ')' statement
    ;

循环语句

循环语句，语法成分为< Iteration-statement，有四种类型

1. while：while关键字开头，其后 expression 为条件， statement 为执行结构体
2. do-while：do关键字开头，其后 statement 为执行结构体，while关键字，其后 expression 为条件
3. for(;;)
4. for(;)

1
2
3
4
5
6

iterationStatement
    :   'while' '(' expression ')' statement
    |   'do' statement 'while' '(' expression ')' ';'
    |   'for' '(' expression? ';' expression? ';' expression? ')' statement
    |   'for' '(' declaration expression? ';' expression? ')' statement
    ;

具体实验

心得体会

• 这次实验中，我难得有机会阅读了C语言的规范文件。对C语言的产生过程和前端的编译过程有了更深一步的认识，了解程序设计语言的演化过程和相关标准的制定过程，掌握文法的概念， 并能够使用文法对给定的语言进行描述；
• 同时这次实验也进一步了加深我对C语言语法的理解，了解了一些不常使用的库函数或者过程，比如C语言多线程执行的过程。C语言的文法规则体现了C语言及其设计者的严谨性。