仲恺农业技术学院
编译原理课程设计
课程设计题目 ：LL（1）文法判定算法
姓 名 ：
院（系） ：
专业班级 ：
学 号 ：
指导教师 ：
设计日期 ：
目 录
目 录 ..........................................................................................................................
一．需求分析 ................................................................................................................1
1.1 原理简单概述....................................................................................................1
二．概要设计 ................................................................................................................1
三．详细设计 ................................................................................................................2
3.1 数据结构............................................................................................................2
3.2 模块划分............................................................................................................3
3.3 能推出$的非终结符 ...........................................................................................5
3.4 FIRST 集的确定 ..................................................................................................5
3.5 FOLLOW 集的确定 ............................................................................................6
3.6 SELLECT 集的确定............................................................................................7
3.7 LL(1)文法的判定 ................................................................................................7
四．测试分析 ................................................................................................................8
4.1 测试一 ...............................................................................................................8
4.2 测试二 ...............................................................................................................9
五．课程结论 ..............................................................................................................10
参考文献 ......................................................................................................................12
附 录 ....................................................................................................................12
主要算法...................................................................................................................12
- 1 -
一．需求分析
1.1 原理简单概述
LL(1)文法使用的是确定的自顶向下的分析技术。LL(1)的含义是：第一个 L 表明自顶向
下分析是从左向右扫描输入串，第 2 个 L 表明分析过程中将使用最左推导，1 表明只需向右
看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。
LL(1)文法的判别需要依次计算 FIRST 集、FOLLOW 集和 SELLECT 集,然后判断是否为
LL(1)文法,最后再进行句子分析。
根据判断一个文法是 LL(1)文法的三个条件，逐一实现其判别条件的算法实现。
满足是 LL(1)文法的三个条件：
(1)文法不含有左递归
(2)对于文法中每一个非终结符 A，若它存在某个候选首符
集两两不相交，即，若 A→α1|α2|…|αn，则 first(α
i
)∩first(α
j
)=Φ (i≠j)
(3)对 文 法 中 的 每 个 非 终 结 符 A， 若 它 存 在 某 个 候 选 首 符 集 包 含 ε ， 则 first(A) ∩
follow(A)=Φ。
此课程设计主要介绍 FIRST 集、FOLLOW 集和 SELLECT 集的计算以及句子分析的算法。
二．概要设计
1、判断文法是否含有左递归：将所有的产生式扫描到一个 ArrayList 的集合中，构造一
个栈 Stack。然后倒序遍历这个 ArrayList，将所有的产生式压栈到栈 Stack 里面。然后开始
Stack.pop()，做一下操作：
(1)若被弹出的产生式的右部第一个字符属于终结符，继续弹栈。
(2)若被弹出的产生式的右部第一个字符属于非终结符，做一下操作：
判断右部第一字符是不是和左部一样，即判断直接左递归，若一样返回程序，含
有左递归。
若右部第一个字符和左部不一样，则获取以右部第一个字符为左部的所有产生式，
然后用这些产生式的右部分别替换被弹出的产生式的右部中的第一个字符，然后压入
栈。
(3)循环直到整个栈弹空，若都未返回，就返回 false，表示整个文法不含左递归。
2、SELLECT 集的确定：FIRST 集＆FOLLOW 集都已经求出来后 SELLECT 集就很好求
了，扫描每一个产生式，使用以下三个步骤确定：
A→α A∈ VN，α∈ V*，
(1)若α是终结符，那么 SELLECT(A→α)={α}
(2)若α是$，则 SELECT(A→α)=FOLLOW(A)
(3)若α是非终结符那么
- 2 -
若 α*=>$，则 SELECT(A→α)=(FIRST(α)-$)∪ FOLLOW(A)
若 α┐*=>$ 则 SELECT(A→α)=FIRST(α)
3、LL(1)文法的判定：当 SELLECT 集求出来后就可以判断是不是一个文法是不是 LL(1)
文法了，扫描产生式左部相同的 SELLCET 集是否含有相同元素，一旦发现相同元素立刻返
回 FALSE，扫描结束没有发现相同元素则返回 TRUE。
三．详细设计
3.1 数据结构
1、用于判断是否含有左递归时候的用的 Stack 结构。
public class Stack {
public Stack();
public virtual int Count { get; }//获取Stack 中包含的元素数。
public virtual void Clear();//从Stack 中移除所有对象。
//如果在 System.Collections.Stack 中找到 obj
public virtual bool Contains(object obj);
public virtual object Peek();//返回位于Stack 顶部的对象但不移除。
public virtual object Pop();//移除并返回位于Stack 顶部的对象.
public virtual void Push(object obj); //将对象插入Stack 的顶部。
}
2、产生式 Product，分为左部和右部
public class Product{
public string LeftItem; //产生式的左部
public ArrayList RightItems; //产生式的右部
//构造方法,构造一个产生式
public Product(string m_LeftItem,ArrayList m_RightItem)
public Product()
// 以字符串式的形式返回右部产生式
public string StringRightItem()
// 以字符串式的形式返回右部第index个产生式
public string StringRightItemAt(int index)
// 检测第index个产生式右部是否都是非终结符
public bool CheckRightItemAt(int index)
//判断一个产生式的第一个右部的第一个字母是否为非终结符
public string GetFirstRightItemNonTerminal()
// 返回所有产生式右部第一个非终结符字母
public string [] FirstRight()
- 3 -
//覆盖ToString方法,按照制定格式输出
public override string ToString()
}
3、queue结构
public class Queue{
public Queue();
// System.Collections.Queue 中包含的元素数。
public virtual int Count { get; }
//可用于同步对 System.Collections.Queue 的访问的对象。
public virtual object SyncRoot { get; }
// 从 System.Collections.Queue 中移除所有对象。
public virtual void Clear();
//如果在 System.Collections.Queue 中找到 obj，则为 true；否则为 false。
public virtual bool Contains(object obj);
//从System.Collections.Queue 的开头移除的对象。
public virtual object Dequeue();
//要添加到 System.Collections.Queue 的对象。该值可以为null。
public virtual void Enqueue(object obj);
// 位于 System.Collections.Queue 的开头的对象。
public virtual object Peek();
}
3.2 模块划分
(1)
模块名：IsHaveLeftRecursion
输 入：所有产生式的集合
输 出：相应的判断结果
功 能：判断输入的文法是否含有左递归。此处利用了栈进行递归判断。
(2)
模块名：SelectSet
输 入：First 集和 Follow 集
输 出：Select 集
功 能：利用输入的 First 集和 Follow 集求出各个产生式的候选首字符集，即为 Select 集。
(3)
模块名：IsLL1
输 入：Select 集
输 出：相应的判断结果
功 能：利用输入的 Select 集进行比较，看看有没有两两相交的，若有不是所判断文法，没
有则是。
