LL(1)文法的判别[00原创]

2007-11-20 /

LL(1)文法的判别[00原创]

编译原理的实验，Java 写的 :-)

package cn.edu.ynu.sei.ll1;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/
* LL1 文法判别 
* 这个方法是严格按照课本《编译原理》清华大学出版社 1998 版 P70 开始处的定义计算的
* 
* 判别算法简述如下：
* <ol>
* <li>Step1. 根据产生式生产所有这个文法的推导式（即句型）</li>
* <li>Step2. 生成过程中判定当前的推导式是否产生了左公因子或者坐递归</li>
* <li>Step3. 凡是含有左公因子或者左递归的都不是 LL(1)文法</li>
* <li>Step4. 不满足以上情况的在根据句型求解出 First，Follow，Select 集</li>
* <li>Step5. 根据 Select 判断是否是 LL(1)文法</li>
* </ol>
* 
*
* @author 88250
* @version 1.0.3, 2007-10-27
*/
public class LL1
{
 /
 * 推导式集合，即 alpha*=>beta 的过程集，其中 alpha、Beta 属于{Vt 并 Vn}*
 */
 static List<DerivedProduct> derivedProducts = new ArrayList<DerivedProduct>();

 /
 * 空串，即 epusilong
 */
 static final String EP = "@";

 /
 * 开始文法符号
 */
 static final String START = "S";

 /
 * 终结符集合，即 Vt
 */
 static final List<String> TERMINATORS = new ArrayList<String>();

 /
 * 非终结符集合，即 Vn
 */
 static final List<String> NTERMINATORS = new ArrayList<String>();

 /
 * First 集列表
 */
 static List<FirstSet> firstSetList = new ArrayList<FirstSet>();

 /
 * 产生式的大小
 */
 static int PRODUCT_SIZE = 0;

 /
 * 预测分析表 M
 */
 static List<ForecastTableItem> M = new ArrayList<ForecastTableItem>();

 /
 * Follow 集列表
 */
 static List<FollowSet> followSetList = new ArrayList<FollowSet>();

 static List<SelectSet> selectSetList = new ArrayList<SelectSet>();

 /
 * 求解 First 集
 */
 public static void calcFirstSet()
 {
 for (final FirstSet fs : firstSetList)
 {
 if (TERMINATORS.contains(fs.leftPart))
 {
 getFirstSet(fs.leftPart).elements.add(fs.leftPart);
 continue;
 }

 final List<String> rightParts = getDerivedProducts(fs.leftPart);
 if (rightParts.isEmpty())
 {// 说明这个 fs.leftPart 串都是由终结符或者空串组成
 boolean isAllEp = true;
 for (int i = 0; i < fs.leftPart.length(); i++)
 {
 final String x = fs.leftPart.substring(i, i + 1);
 if (getFirstSet(fs.leftPart).elements.contains(x))
 {
 isAllEp = false;
 break;
 }
 if (EP.equals(x))
 {
 continue;
 }
 else
 {
 isAllEp = false;
 }

 if (TERMINATORS.contains(x))
 {
 getFirstSet(fs.leftPart).elements.add(x);
 break;
 }
 }
 if (isAllEp)
 {
 getFirstSet(fs.leftPart).elements.add(EP);
 }
 }
 for (final String rightPart : rightParts)
 {
 boolean isAllEp = true;
 for (int i = 0; i < rightPart.length(); i++)
 {
 final String x = rightPart.substring(i, i + 1);
 if (getFirstSet(fs.leftPart).elements.contains(x))
 {// 该元素已经包含在结果集里了
 isAllEp = false;
 break;
 }
 if (EP.equals(x))
 {
 continue;
 }
 else
 {
 isAllEp = false;
 }

 if (TERMINATORS.contains(x))
 {
 getFirstSet(fs.leftPart).elements.add(x);
 break;
 }
 }
 if (isAllEp)
 {
 getFirstSet(fs.leftPart).elements.add(EP);
 }
 }
 }
 }

 /
 * 求解 Follow 集
 */
 public static void calcFollowSet()
 {
 for (final DerivedProduct dp : derivedProducts)
 {
 for (int i = 0; i < dp.rightPart.length(); i++)
 {
 final String x = dp.rightPart.substring(i, i + 1);
 if (NTERMINATORS.contains(x))
 {
 if (i + 1 == dp.rightPart.length())
 {// x 为最后一个文法符号
 getFollowSet(x).elements.add("#");
 }

 if (i + 2 <= dp.rightPart.length())
 {
 final String afterX = dp.rightPart.substring(i + 1,
 i + 2);
 if (TERMINATORS.contains(afterX))
 {
 getFollowSet(x).elements.add(afterX);
 }
 }
 }
 }
 }
 }

 /**
 * 求解预测分析表
 */
 public static void calcForecastTable()
 {
 for (int i = 0; i < PRODUCT_SIZE; i++)
 {
 for (final String terminator : TERMINATORS)
 {
 if (selectSetList.get(i).elements.contains(terminator))
 {
 M.add(new ForecastTableItem(derivedProducts.get(i),
 terminator));
 }
 if (selectSetList.get(i).elements.contains("#"))
 {
 M.add(new ForecastTableItem(derivedProducts.get(i), "#"));
 }
 }
 }
 }

 /**
 * 求解 Select 集
 */
 public static void calcSelectSet()
 {
 for (final SelectSet ss : selectSetList)
 {
 if (!couldDeriveEp(ss.derivedProduct.rightPart))
 {
 getSelectSet(ss.derivedProduct).elements = getFirstSet(ss.derivedProduct.rightPart).elements;
 }
 else
 {
 Set<String> elements = new HashSet<String>();
 elements = getFirstSet(ss.derivedProduct.rightPart).elements;
 elements.remove(EP);
 elements.addAll(getFollowSet(ss.derivedProduct.leftPart).elements);
 getSelectSet(ss.derivedProduct).elements = elements;
 }
 }
 }

 /**
 * 判断给定的产生式右部的文法符号串是否可以与其他右部归纳出相同的部分，并且这些产生式的左部是一样的，即左公因子的情况 
 * 注意：这只是在文法的产生式中进行判断，而不是在推导式（句型）
 *
 * @return 可以由不同的推导式产生返回<code>true</code>，否则返回<code>false</code>
 */
 private static boolean containsLeftCommonFactor()
 {
 for (int i = 0; i < PRODUCT_SIZE; i++)
 {
 final DerivedProduct dp = derivedProducts.get(i);
 for (int j = i; j < PRODUCT_SIZE; j++)
 {
 final DerivedProduct dpj = derivedProducts.get(j);
 if (dp.leftPart.equals(dpj.leftPart))
 {
 final String oX = dp.rightPart.substring(0, 1);
 if (dpj.rightPart.length() < dp.rightPart.length())
 {
 final String x = dpj.rightPart.substring(0, 1);
 if (oX.equals(x))
 {// 看第一个文法符号就可以确定是否含有左公因子
 return true;
 }
 }
 }
 }
 }

 return false;
 }

 /**
 * 判断给定的推导式左部的文法符号串是否包含在这个推导式右部中，即左递归的情况
 * 
 * 左递归的定义如下(参考课本 P81)： 
 * <ul>
 * <li>a) A->AZ A 属于 Vn,Z 属于 V*</li>
 * <li>b) A->BZ B->AX A,B 属于 Vn, Z 与 X 属于 V*</li>
 * </ul>
 * 在 a)中可称为直接左递归，在 b)中为 A+=>A...称文法中含有间接作递归
 * 
 *
 * @param leftPart
 * 推导式左部
 * @param rightPart
 * 推导式右部
 * @return 包含的话返回<code>true</code>，否则返回<code>false</code>
 */
 private static boolean containsLeftRecursion(String leftPart,
 String rightPart)
 {//TODO 左递归判断问题
 String firstRightPart = rightPart.substring(0, 1);

 if (firstRightPart.contains(leftPart))
 {// 直接左递归
 return true;
 }
 if (NTERMINATORS.contains(firstRightPart))
 {
 for (int i = 0; i < derivedProducts.size(); i++)
 {
 DerivedProduct dp = derivedProducts.get(i);
 System.out.println("!" + dp.leftPart + "->" + dp.rightPart);
 if (dp.leftPart.length() == 1 && dp.rightPart.substring(0, 1).equals(dp.leftPart))
 {
 return true;
 }

 }
 }

 return false;
 }

 /**
 * 判断给定的符号串中含有非终结符吗？
 *
 * @param alpha
 * 给定的符号串
 * @return
 */
 private static boolean containsNTerminator(String alpha)
 {
 for (int i = 0; i < alpha.length(); i++)
 {
 if (NTERMINATORS.contains(alpha.substring(i, i + 1)))
 {
 return true;
 }
 }
 return false;
 }

 /**
 * 给定的文法符号串可以*=>空串吗？
 *
 * @param alpha
 * 给定的文法符号串
 * @return 可以的话返回<code>true</code>，否则返回<code>false</code>
 */
 public static boolean couldDeriveEp(String alpha)
 {
 boolean couldDeriveEp = false;
 for (final DerivedProduct dp : derivedProducts)
 {
 if (dp.leftPart.equals(alpha))
 {
 for (int i = 0; i < dp.rightPart.length(); i++)
 {
 final String x = dp.rightPart.substring(i, i + 1);
 if (!EP.equals(x))
 {
 couldDeriveEp = false;
 break;
 }
 else
 {
 couldDeriveEp = true;
 }
 }
 if (couldDeriveEp)
 {
 return true;
 }
 }
 }
 return false;
 }

 /**
 * 推导过程 
 * 在推导的时候将过程推导式加入到推导式集（句型集）中，直到推导式集合不再增大为止
 *
 * @return 如果在推导过程中分析出了这个文法是左递归或者含有左公因子的的，返回<code>false</code>
 * 如果推导过程顺利完成，返回<code>true</code>
 */
 public static boolean derive()
 {
 if (containsLeftCommonFactor())
 {
 System.out.println("文法包含左公因子....");
 return false;
 }

 for (int k = 0; k < derivedProducts.size(); k++)
 {
 if (derivedProducts.size() > 1000)
 {// 如果给定的文法是 LL(1)，那么这个算法可能进入无限穷举
 // 所以，给定一个闸域，控制推导式集合的大小
 return true;
 }
 final DerivedProduct dp = derivedProducts.get(k);
 final List<String> rightPartList = getDerivedProducts(dp.leftPart);

 // 分析一个推导式
 for (int i = 0; i < rightPartList.size(); i++)
 {
 final String rightPart = rightPartList.get(i);
 if (rightPart.equals(dp.rightPart))
 {// 分析推导式右部的每一个文法符号
 for (int j = 0; j < rightPart.length(); j++)
 {
 // 一个文法符号 x
 final String x = rightPart.substring(j, j + 1);
 final List<String> rightPartList2 = getDerivedProducts(x);
 for (int n = 0; n < rightPartList2.size(); n++)
 {
 // 文法符号 x 前的符号串
 final String front = rightPart.substring(0, j);
 // 文法符号 x 后的符号串
 final String back = rightPart.substring(j + 1,
 rightPart.length());
 // 组成新的推导式右部
 final String newRightPart = front + rightPartList2.get(n) + back;
 if (containsLeftRecursion(dp.leftPart, newRightPart))
 {
 System.out.println("文法左递归....");
 return false;
 }

 final List<String> rightPart3 = getDerivedProducts(dp.leftPart);
 if (rightPart3.isEmpty())
 {
 derivedProducts.add(new DerivedProduct(
 dp.leftPart, newRightPart));
 }
 else
 {
 if (!rightPart3.contains(newRightPart))
 {
 derivedProducts.add(new DerivedProduct(
 dp.leftPart, newRightPart));
 }
 }

 final List<String> rightPart4 = getDerivedProducts(dp.rightPart);
 if (rightPart4.isEmpty() && containsNTerminator(dp.rightPart))
 {
 derivedProducts.add(new DerivedProduct(
 dp.rightPart, newRightPart));

 }
 if (!rightPart4.isEmpty())
 {
 if (!rightPart4.contains(newRightPart))
 {
 derivedProducts.add(new DerivedProduct(
 dp.rightPart, newRightPart));
 }
 }

 if (!rightPartList.contains(newRightPart))
 {
 rightPartList.add(newRightPart);
 }
 }
 }
 }
 }
 }
 return true;
 }

 /**
 * 显示推导式集合
 */
 private static void displayDerivedProducts()
 {
 System.out.println("推导式（句型）列表：");
 for (final DerivedProduct dp : derivedProducts)
 {
 System.out.println(dp.leftPart + "->" + dp.rightPart);
 }
 System.out.println("包含了" + derivedProducts.size() + "个推导式");
 }

 /**
 * 显示 First 集
 */
 public static void displayFirstSet()
 {
 System.out.println("First 集如下：");
 for (final FirstSet fs : firstSetList)
 {
 System.out.println("FIRST(" + fs.leftPart + ")=" + fs.elements);
 }
 }

 /**
 * 显示 Follow 集
 */
 public static void displayFollowSet()
 {
 System.out.println("Follow 集：");
 for (final FollowSet fs : followSetList)
 {
 System.out.println("FLLOW(" + fs.A + ")=" + fs.elements);
 }
 }

 /**
 * 显示预测分析表
 */
 public static void displayForecastTable()
 {
 System.out.println("预测分析表如下：");
 for (final ForecastTableItem fti : M)
 {
 System.out.println(fti.derivedProduct.toString() + " " + fti.a);
 }
 }

 /**
 * 显示 Select 集
 */
 public static void displaySelectSet()
 {
 System.out.println("Select 集：");
 for (final SelectSet ss : selectSetList)
 {
 System.out.println("SELECT(" + ss.derivedProduct.toString() + ")=" + ss.elements);
 }
 }

 /**
 * 根据左部的串返回对应它的右部串集合
 *
 * @see cn.edu.ynu.sei.ll1.DerivedProduct
 * @param leftPart
 * 推导式左部符号串
 * @return 对应左部符号串的右部符号串集合
 */
 public static List<String> getDerivedProducts(String leftPart)
 {
 final List<String> rightPartList = new ArrayList<String>();

 for (final DerivedProduct dp : derivedProducts)
 {
 if (dp.leftPart.equals(leftPart))
 {
 rightPartList.add(dp.rightPart);
 }
 }

 return rightPartList;
 }

 /**
 * 返回对应左部的 First 集
 *
 * @param leftPart
 * @return FirstSet
 */
 public static FirstSet getFirstSet(String leftPart)
 {
 for (final FirstSet fs : firstSetList)
 {
 if (leftPart.equals(fs.leftPart))
 {
 return fs;
 }
 }
 return null;
 }

 /**
 * 返回对应非终结符 A 的 Follow 集
 *
 * @param A
 * 非终结符 A
 * @return FollowSet
 */
 public static FollowSet getFollowSet(String A)
 {
 for (final FollowSet fs : followSetList)
 {
 if (fs.A.equals(A))
 {
 return fs;
 }
 }
 return null;
 }

 /**
 * 返回指定产生式的 Select 集
 *
 * @param derivedProduct
 * @return SelectSet
 */
 public static SelectSet getSelectSet(DerivedProduct derivedProduct)
 {
 for (final SelectSet ss : selectSetList)
 {
 if (ss.derivedProduct.leftPart.equals(derivedProduct.leftPart) && ss.derivedProduct.rightPart.equals(derivedProduct.rightPart))
 {
 return ss;
 }
 }
 return null;
 }

 /**
 * 初始化 First 集
 */
 public static void initFirstSet()
 {
 for (final DerivedProduct dp : derivedProducts)
 {
 if (getFirstSet(dp.leftPart) == null)
 {
 firstSetList.add(new FirstSet(dp.leftPart,
 new HashSet<String>()));
 }
 if (getFirstSet(dp.rightPart) == null)
 {
 firstSetList.add(new FirstSet(dp.rightPart,
 new HashSet<String>()));
 }
 }
 }

 /**
 * 初始化 Follow 集
 */
 public static void initFollowSet()
 {
 for (final String nTerminator : NTERMINATORS)
 {
 followSetList.add(new FollowSet(nTerminator, new HashSet<String>()));
 }
 getFollowSet(START).elements.add("#");
 }

 /**
 * 显示文法 G
 */
 public static void displayG()
 {
 System.out.println("S: " + START);
 System.out.print("Vt={");
 for (String t : TERMINATORS)
 {
 System.out.print(t + " ");
 }
 System.out.println("}");
 System.out.print("Vn={");
 for (String nt : NTERMINATORS)
 {
 System.out.print(nt + " ");
 }
 System.out.println("}");
 System.out.println("e(空): " + EP);
 System.out.println("P： ");
 for (int i = 0; i < PRODUCT_SIZE; i++)
 {
 System.out.println(derivedProducts.get(i).toString());
 }
 }

 /**
 * 初始化推导式，即使用文法规定的产生式 P 初始化推导式集合
 */
 public static void initG()
 {
 // 初始化产生式
 /*derivedProducts.add(new DerivedProduct("S", "AB"));
 derivedProducts.add(new DerivedProduct("S", "bC"));
 derivedProducts.add(new DerivedProduct("A", EP));
 derivedProducts.add(new DerivedProduct("A", "b"));
 derivedProducts.add(new DerivedProduct("B", EP));
 derivedProducts.add(new DerivedProduct("B", "aD"));
 derivedProducts.add(new DerivedProduct("C", "AD"));
 derivedProducts.add(new DerivedProduct("C", "b"));
 derivedProducts.add(new DerivedProduct("C", "bC"));
 derivedProducts.add(new DerivedProduct("D", "aS"));
 derivedProducts.add(new DerivedProduct("D", EP));
 derivedProducts.add(new DerivedProduct("D", "c"));*/
 derivedProducts.add(new DerivedProduct("S", "TZ"));
 derivedProducts.add(new DerivedProduct("Z", "+TZ"));
 derivedProducts.add(new DerivedProduct("Z", EP));
 derivedProducts.add(new DerivedProduct("T", "FX"));
 derivedProducts.add(new DerivedProduct("X", "*FX"));
 derivedProducts.add(new DerivedProduct("X", EP));
 derivedProducts.add(new DerivedProduct("F", "i"));
 derivedProducts.add(new DerivedProduct("F", "(S)"));

 PRODUCT_SIZE = derivedProducts.size();

 // 初始化终结符
 /*TERMINATORS.add("a");
 TERMINATORS.add("b");
 TERMINATORS.add("c");
 TERMINATORS.add("d");
 */

 TERMINATORS.add("i");
 TERMINATORS.add("(");
 TERMINATORS.add(")");
 TERMINATORS.add("+");
 TERMINATORS.add("*");

 // 初始化非终结符
 NTERMINATORS.add("S");
 NTERMINATORS.add("Z");
 NTERMINATORS.add("X");
 NTERMINATORS.add("T");
 NTERMINATORS.add("F");
 }

 /**
 * 初始化 Select 集
 */
 public static void initSelectSet()
 {
 for (int i = 0; i < PRODUCT_SIZE; i++)
 {
 final DerivedProduct dp = derivedProducts.get(i);
 selectSetList.add(new SelectSet(dp, new HashSet<String>()));
 }
 }

 /**
 * 主程序入口
 *
 * @param args
 * 为<code>null</code>
 */
 public static void main(String[] args)
 {
 initG();
 displayG();
 if (!derive())
 {
 System.out.println("该文法不是 LL(1)文法！");
 }
 else
 {
 displayDerivedProducts();
 initFirstSet();
 calcFirstSet();
 displayFirstSet();
 initFollowSet();
 calcFollowSet();
 displayFollowSet();
 initSelectSet();
 calcSelectSet();
 displaySelectSet();
 if (!passFinalJudgeLL1())
 {
 System.out.println("该文法不是 LL(1)文法！");
 return;
 }
 calcForecastTable();
 displayForecastTable();
 }
 }

 /**
 * 通过 Select 集来最终判定一个文法是否是 LL1 文法
 *
 * @return 是 LL1 文法返回<code>true</code>，否则返回<code>false</code>
 */
 public static boolean passFinalJudgeLL1()
 {
 for (int i = 0; i < selectSetList.size(); i++)
 {
 final SelectSet ss1 = selectSetList.get(i);
 for (int j = i + 1; j < selectSetList.size(); j++)
 {
 final SelectSet ss2 = selectSetList.get(j);
 if (ss1.derivedProduct.leftPart.equals(ss2.derivedProduct.leftPart))
 {
 for (final String element : ss1.elements)
 {
 if (ss2.elements.contains(element))
 {// 存在交集
 return false;
 }
 }
 }
 }
 }
 return true;
 }
}

package cn.edu.ynu.sei.ll1;

/**
* 推导(dervied)式，即句型。实际上是开始符号 S 经过*步推导而得到的推导式的左部和右部
* 
* 一个推导分为左部{{@link #leftPart}和右部{{@link #rightPart}，其中左部和右部都属于 Vt 并 Vn 的*闭包
* 参考课本 P70~P71 定义 5.1 中的 alpha 与 beta 定义
* 
*
* @author 88250
* @version 1.0.1, 2007-10-23
*/
public class DerivedProduct
{
 /**
 * 左部符号串
 */
 public String leftPart;

 /**
 * 右部符号串
 */
 public String rightPart;

 /**
 * 带参数的构造器
 *
 * @param leftPrduct
 * 推导式左部
 * @param rightProduct
 * 推导式右部
 */
 public DerivedProduct(String leftPrduct, String rightProduct)
 {
 this.leftPart = leftPrduct;
 this.rightPart = rightProduct;
 }

 @Override
 public String toString()
 {
 return leftPart + "->" + rightPart;
 }
}
package cn.edu.ynu.sei.ll1;

import java.util.Set;

/**
* First 集
* 
* 定义： 
* First(leftPart) = {a | leftPart*=>aB, a 属于 Vt, leftPart,B 属于 V*} 
* 若 leftPart*=>空串，则规定空串 e 属于 First(leftPart)
* 
*
* @author 88250
* @version 1.0.0, 2007-10-25
*/
public class FirstSet
{
 /**
 * 要求的 First 集的串
 */
 String leftPart;

 /**
 * 集合元素
 */
 Set<String> elements;

 /**
 * 带参数的构造器
 *
 * @param leftPart
 * @param elements
 */
 public FirstSet(String leftPart, Set<String> elements)
 {
 this.leftPart = leftPart;
 this.elements = elements;
 }
}
package cn.edu.ynu.sei.ll1;

import java.util.Set;

/**
* First 集
* 
* 定义： 
* First(leftPart) = {a | leftPart*=>aB, a 属于 Vt, leftPart,B 属于 V*} 
* 若 leftPart*=>空串，则规定空串 e 属于 First(leftPart)
* 
*
* @author 88250
* @version 1.0.0, 2007-10-25
*/
public class FirstSet
{
 /**
 * 要求的 First 集的串
 */
 String leftPart;

 /**
 * 集合元素
 */
 Set<String> elements;

 /**
 * 带参数的构造器
 *
 * @param leftPart
 * @param elements
 */
 public FirstSet(String leftPart, Set<String> elements)
 {
 this.leftPart = leftPart;
 this.elements = elements;
 }
}
package cn.edu.ynu.sei.ll1;

import java.util.Set;

/**
* Follow 集
* 
* 定义： 
* Follow(A) = {a | S*=>...Aa..., a 属于 Vt} 
* 若有 S*=>...A，则规定#属于 Follow(A)
* 
*
* @author 88250
* @version 1.0.0, 2007-10-25
*/
public class FollowSet
{
 /**
 * 非终结符 A
 */
 String A;

 /**
 * 集合元素
 */
 Set<String> elements;

 /**
 * 带参数的构造器
 *
 * @param A
 * 非终结符 A
 * @param elements
 */
 public FollowSet(String A, Set<String> elements)
 {
 this.A = A;
 this.elements = elements;
 }
}
package cn.edu.ynu.sei.ll1;

/**
* 预测分析表的一个项
* 
* 若 a 属于 Select(A->B)，则把 A->B 放入 M[A,B]中
* 
*
* @author 88250
* @version 1.0.0, 2007-10-26
*/
public class ForecastTableItem
{
 /**
 * 产生式
 */
 DerivedProduct derivedProduct;

 /**
 * 终结符或#
 */
 String a;

 /**
 * 带参数的构造器
 *
 * @param derivedProduct
 * @param a
 */
 public ForecastTableItem(DerivedProduct derivedProduct, String a)
 {
 this.derivedProduct = derivedProduct;
 this.a = a;
 }
}
package cn.edu.ynu.sei.ll1;

import java.util.Set;

/**
* Select 集
* 
* 定义：给定上下文无关文法的产生式 A->a A 属于 Vn, a 属于 V*, 若不能 a*=>空串，则 
* Select(A->a) = First(a) 
* 如果 a*=>空串 e，则 Select(A->a) = (First(a)-{e})并 Follow(A)
* 
*
* @author 88250
* @version 1.0.0, 2007-10-25
*/
public class SelectSet
{
 /**
 * 产生式 A->a
 */
 DerivedProduct derivedProduct;

 /**
 * 集合元素
 */
 Set<String> elements;

 /**
 * 带参数的构造器
 *
 * @param derivedProduct
 * @param elements
 */
 public SelectSet(DerivedProduct derivedProduct, Set<String> elements)
 {
 this.derivedProduct = derivedProduct;
 this.elements = elements;
 }
}

关于实验的一点点心得：

本次实验的过程是曲折的。

一开始实施实验的时候我参考的是《实验指导书》中所给的判定步骤，即课本5.2节中描述的判定步骤。仔细看书，发现在求解FIRST集以及FOLLOW集的时候课本给出了两种方法，一种是根据定义计算；另一种是由关系图法求解。

由于关系图法给了我很直观的感觉，我首先选择的是根据关系图求解这两个集合。但是遇到了很多问题。其中最大的问题就是关系图法只能求解出一个文法符号的FIRST集，而之后的集合求解都是建立在FIRST集的基础上的。类似地，在5.2中给出的“1. 求出能推导出e(空)的非终结符”这个步骤也只能求解出一个文法符号的*=>空，而FIRST集合的求解关键之一就要求的是一个文法符号串alpha能否*=>空。虽然文法符号串alpha是否能*=>空的问题可以解决，并且已经解决（迭代计算，源代码在目录relatedDiagram下，这个目录下的所有代码就是使用关系图法进行实验的所有源代码），但是同样的道理，FIRST(alpha)的求解也需要进行“二次”处理，这样导致了这个实验在整体的实现难度上更麻烦了，所以后来才有了现在实验报告里的这种解决方法。

课本5.3节里的描述其实暗示了判断LL(1)文法的另一种方法。判定一个文法是否是LL(1)文法，可以先判断左公因子和左递归，在判断的过程中就可以逐步产生整个文法的句型（实验里称之为推导式，因为句型只定义了右部，加上左部即推导式，行如 alpha=>beta）。实验中，发现只要一个文法不含有左递归，那么它是一定可以求出这个文法所有的推导式的。有了这个文法所有的句型，不难利用FIRST集，FOLLOW集，SELECT集的定义逐个求解。因为所有文法符号（串）的*推导都已经出来了，所以整个求解过程极为简洁。

其实，在给定文法所有推导式都计算出来的情况下，我们根据FIRST集，FOLLOW集的定义，完全可以利用正则表达式进行直接匹配，对每个推导式都进行匹配，即可计算出这个推导式的FIRST集和FOLLOW集了。不过，本次实验里并没有利用正则式，而是手工编码进行计算求解，因为觉得这样能让我有更深的体会。

呃……所以说这次实验的过程是曲折的……

实验完成后，想了想自顶向下，自底向上这两个语法分析方法其实都可以建立在给定文法所有推导式都产生的前提下进行分析。所以，我觉得只要一个文法可以求解出它的所有推导式，那么整个语法分析的过程其实是很清晰和直观的。不过，我的算法其实用的是穷举的思想，而穷举最大的问题就是效率问题。所以在在算法的核心函数（derive()）中我给了一个闸域来控制穷举（穷举推导式集合）的大小，在给定的闸域内判断出文法是否属于LL(1)。当然，这个是题外话了，可能等到做LR(0)的实验的时候看法会有所改变 :-)

D 的个人博客

但行好事莫问前程

LL(1)文法的判别[00原创]