语法分析(1)

.

Word文档资料

《编译原理》上机实验报告

题目：LL(1)语法分析程序

.

Word文档资料 1.设计要求

（1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止；

（2）输入已知文法，由程序自动生成它的LL(1)分析表；

（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。

2.分析

该程序可分为如下几步：

（1）读入文法

（2）判断正误

（3）若无误，判断是否为LL(1)文法

（4）若是，构造分析表；

（5）由总控算法判断输入符号串是否为该文法的句型。

3.流程图

是

是

开始

读入文法

有效？

是LL(1)文法？

判断句型 报错

.

Word文档资料

4.源程序

/*******************************************

LL1语法分析程序

********************************************/

#include

#include

#include

/*******************************************/

int count=0; /*分解的产生式的个数*/

int number; /*所有终结符和非终结符的总数*/

char start; /*开始符号*/

char termin[50]; /*终结符号*/

char non_ter[50]; /*非终结符号*/

char v[50]; /*所有符号*/

char left[50]; /*左部*/

char right[50][50]; /*右部*/

实验2 语法分析（SLR(1)分析）

一、实验任务：

文法为：

E E+T | E-T | T

T T*F | T/F | F

F（E）| i

根据SLR(1)分析法，对表达式进行语法分析，判断一个表达式是否正确。

二、实验时间：上机2次。

三、实验过程和指导：

（一）准备：

1. 判别该文法是否为SLR(1)文法；若是，设计出SLR(1)分析表；

2. 考虑好SLR(1)分析法的设计方案，设计出模块结构和测试数据；

3. 初步编制好程序。

（二）上机实验：上机调试，发现错误，分析错误，逐渐修改完善。

（三）程序要求：

程序输入/输出示例：

如参考C语言的运算符。输入如下表达式（以分号为结束）和输出结果：

（1）10

输出：正确

（2）1+2*(15-6)

输出：正确

（3）(1+2)/3+4- (11+6/7)

输出：正确

（4）((1-2)/3+4

输出：错误，出错位置是

（5）1+2-3+(*4/5)

输出：错误，出错位置是

注意：

1. 为降低难度，表达式中不含变量（只含无符号整数）；

2. 可以直接调用此法分析程序，取得单词；

3. 分析表有两个：ACTION表和GOTO表；

4. 分析过程有两个栈：状态栈和符号栈；

5. 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好，最好有详细的出错位置和出错性质说明）；

6. 测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；

7. 对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果，计算过程用浮点表示，但要注意不要被0除。

（四）练习该实验的目的和思路：

程序比较复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过这个练习可极大提高编程能力。程序规模大概为四百行。通过练习，掌握对表达式进行处理的一种方法。

（四）为了能设计好程序，注意以下事情：

1.设计要求

（1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止；

（2）输入已知文法，由程序自动生成它的LL(1)分析表；

（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。

2.分析

该程序可分为如下几步：

（1）读入文法

（2）判断正误

（3）若无误，判断是否为LL(1)文法

（4）若是，构造分析表；

（5）由总控算法判断输入符号串是否为该文法的句型。

3.流程图

是

是

开始

读入文法

有效？

是LL(1)文法？

判断句型 报错

结束

4.源程序

/*******************************************

语法分析程序

作者：龚勋 刘栋 罗晓波

学号：200131500342 200131500350 200131500351

计科系 13班

********************************************/

#include

#include

#include

/*******************************************/

int count=0; /*分解的产生式的个数*/

int number; /*所有终结符和非终结符的总数*/

char start; /*开始符号*/

char termin[50]; /*终结符号*/

char non_ter[50]; /*非终结符号*/

char v[50]; /*所有符号*/

char left[50]; /*左部*/

char right[50][50]; /*右部*/

char first[50][50],follow[50][50]; /*各产生式右部的FIRST和左部的FOLLOW集合*/

基于LR(1)的语法分析程序

1.设计目的：

设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。

2.设计要求：

（1） 根据LR(1)分析法编写一个语法分析程序，.输入已给定文

法，直接输入根据己知文法构造的LR(1)分析表。

（2） 对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。

3.设计过程：

3.1 LR(1)文法的含义：

LR分析法的规约过程是规范推倒的逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR（0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。

3.2 设计思想：

根据自身实际情况，给定了编译原理书中的一个LR(1)文法，求出其项目集合转换函数，从而得出此LR(1)文法的分析表，在程序中直接输出此分析表，并根据分析表中的内容可对输入的符号串进行分析，判断是接受还是出错，从而得出该输入的符号串是否为文法的一个句子。

3.3 算法描述：

1.CLOSURE(I)的构造

CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到：

(1)I中的所有项目都属于CLOSURE(I)；

(2)若项目[A→a.Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRST中的每一个中介符b,如果[β→.ξ,b]原来不在CLOSURE(I)中，则把它加进去；

(3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。2.GO(I,X)的构造