C语言编译器设计与实现毕业论文设计(6)

算法优先分析法，及其他“移进-规约”分析法。因此，LR分析法是当前最一般的语法分析方法。

对于一般使用的程序设计语言的文法而言，若手工构造分析程序，则工作量太大，而且K越大，构造越复杂，实现越困难。因此，综合考虑，本实验采用LR（1）分析方法进行语法分析。

4.2.2 C语言抽象出来的文法规则

文法是为了深入研究语言的内在性质，而构造语言的方法。换句话说，给定一个文法，就能从结构上唯一的确定语言（形式语言理论可以证明此结论为真）。

一个文法必须由4部分组成：

1. 字母表，表中的字符成为终结符。因为通过文法规则，最终得到的句子只能含有这些字符，这种字母称为终结符集合，记为termanal。

2. 一个中间字母集，称为非终结符，记为nontermanal，一般出现在规则左部的符号都是非终结符。

3. 文法规则集合。规则形如type_specifier -> void。读作“导出”、“产生”、 “生成”或者“定义为”。

4. 文法的开始符号S0。S0为特殊的非终结符。

下面是总结出来的c语言的文法，总共有57条规则：

1 S0 -> translation_unit

2 translation_unit -> external_declaration 3 external_declaration -> function_definition 4 external_declaration -> declaration 5 declaration -> type_specifier id ; 6 type_specifier -> void 7 type_specifier -> int 8 type_specifier -> double

9function_definition->type_specifier function_name parameter compound_statement 10 function_name -> id 11 parameter -> ( )

12 compound_statement -> { decalration_list } 13 compound_statement -> { statement_list }

14 compound_statement -> { decalration_list statement_list } 15 decalration_list -> declaration

16 decalration_list -> decalration_list declaration 17 statement_list -> statement

18 statement_list -> statement_list statement 19 statement -> compound_statement 20 statement -> expression_statement 21 statement -> selection_statement M 22 statement -> iteration_statement M

19

23 statement -> jump_statement 24 expression_statement -> ;

25 expression_statement -> expression ; 26 expression -> assignment_expression

27 assignment_expression -> primary_expression = assignment_expression 28 assignment_expression -> logical_or_expression

29 logical_or_expression -> logical_or_expression || M logical_and_expression 30 logical_or_expression -> logical_and_expression

31 logical_and_expression -> logical_and_expression && M equality_expression 32 logical_and_expression -> equality_expression

33 equality_expression -> equality_expression == relational_expression 34 equality_expression -> relational_expression

35 relational_expression -> relational_expression < additive_expression 36 relational_expression -> relational_expression > additive_expression 37 relational_expression -> relational_expression <= additive_expression 38 relational_expression -> relational_expression >= additive_expression 39 relational_expression -> additive_expression

40 additive_expression -> additive_expression - multiplicative_expression 41 additive_expression -> additive_expression + multiplicative_expression 42 additive_expression -> multiplicative_expression

43 multiplicative_expression -> multiplicative_expression * primary_expression 44 multiplicative_expression -> multiplicative_expression / primary_expression 45 multiplicative_expression -> multiplicative_expression % primary_expression 46 multiplicative_expression -> primary_expression 47 primary_expression -> id

48 primary_expression -> double_num 49 primary_expression -> int_num

50 primary_expression -> ( expression )

51 selection_statement -> if ( expression ) M statement

52 iteration_statement -> while ( M expression ) M statement 53 jump_statement -> continue ; 54 jump_statement -> break ; 55 jump_statement -> return ;

56 jump_statement -> return expression ; 57 M -> e

因为非终结符肯定会在产生是的左边出现，终结符却不会在产生式的左边出现，故首先找出在产生式右边出现但是没在产生式左边出现的即是终结符，所有的符号减去终结符则是非终结符。这些编码都是由程序自动算出，如表4-3所示。

终结符

20

非终结符

符号 \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\编号 1 \2 \符号 编号 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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 表4-3 C的终结符和非终结符

我们可以从表4-2中阅读出本实验C的语法规则：C程序只是一个语句序列，它共有5种语句：if语句、while语句、赋值语句。

另外还可以看出：C的表达式有两类：布尔表达式和算术表达式。布尔表达式使用比较运算符“=”和“<”，通常用在if语句和while语句中作为测试条件；算术表达式使用整型运算符“+”、“-”、“*”、“/”，它们具有左结合和常规的优先关系。与此不同，比较运算是非结合的（每个没有括号的表达式只允许一种比较运算）。比较运算符的优先权都低于算术运算符。

另外，我们也可以把C 的表达式看作三类：算符表达式、常量表达式和标识符表达式。

21

C中的标识符指的是简单整型变量，它没有类似数组或记录等类型的变量。C中也无需显式的变量声明：任何一个变量只是通过出现在赋值语句左边或者read关键字的右边来隐式地声明。另外，变量只有全局作用域。

C的语句序列是指用N个分号分隔开来的N条语句。 4.2.3 C语法分析程序的实现

在实现C的语法分析器时，采用的核心算法是自底而上的LR（1）分析方法。 LR（1）分析方法，最终要的是生产LR（1）分析表，分析表由分析动作表（ACTION）和状态转换表（GOTO）组成。分析表由来Grammer类来表示。

Grammer类继承自ReadCfg类。Grammer类的构造函数用来初始化ReadCfg类的成员变量，成员变量定义为protected型，方便Grammer类直接取到。具体成员如下：

protected:

vector cfg; //文法结点数组 vector table_head; //值符号集 vector string_table_head; //string符号集 set terminal; //存放终结符数值形式的集合 set nonterminal; //存放非终结符数值形式的集合 文法结点结构体：

struct cfg_node {

string left; //文法规则左部 int left_int; //左部多对应的键值

vector right; //文法规则的右部，对于每一个左部， //可能产生多个右部，放入vector中 vector right_int; //文法右部的键值放入对应的vector };

上面数据结构（vector cfg）的表示，能准确完整地表示C语言所有文法规则。

LR（1）语法分析关键的步骤是构造LR（1）分析表。分析表的构造有两种方式：一种是构造先构造识别规范前缀的不确定的有限自动机（NFA），然后转化为确定的有限自动机（DFA），另外一种是机械的由程序用算法构造。由于分析表非常大（171行，57列），故采用机械算法构造。下面是分析表的构造算法： 1) 求非终结符的first集。为方便以后访问，求完所有非终结符的first集后将它放在一

个以非终结符为键的hash表中。

2) 求项目集闭包，需要用到第1步中的结果。闭包利用集合的唯一性，故使用C++标

准STL库中的set模板。利用一个三元式存储标识一个产生式：

//项目结点 struct item_node {

size_t cfg_no; //产生式编号 size_t dot_pos; //加点位置

22

int possible_prefix; //可能出现输入符号的Tag };

其中cfg_no是产生是编号，dot_pos是加点的位置，possible_prefixs是可能出现的输入符号。例如 {S -> aA.d，#}假设是第n个产生式， cfg_no = n， dot_pos=2，possible_prefix=”#”的编号。每一个项目集则是以item_node为元素的集合(set)。 项目集闭包具体实现：

vector& Grammar::get_closure(vector &closure) { for (size_t pos=0; pos

3) 求go函数。即是一个项目集遇到输入代码流中的一个符号后转向的另一个状态时

候的项目集，并将之返回。

//求go函数，即是一个项目集(第i个)遇到输入代码流中的一个符号(Tag为x)后转向的另一个状态时候的项目集，并将之返回

vector Grammar::get_goto(const size_t i, const int x) {

vector j;

static const int dollar = get_int(\ //遍历第i个项目集中的每个项目

for (size_t k=0; kdot_pos && cfg[cfg_no].right_int[dot_pos]==x

23

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库C语言编译器设计与实现毕业论文设计(6)在线全文阅读。