leon_a
- 浏览: 77500 次
- 性别:
- 来自: 拜月神教
-
最新评论
-
huangfenghit：
你绝对的大牛~
答复: 阿里巴巴面试感言 -
liuxuejin：
好！慢慢下载来看看
区间树 -
xiaobian：
看不懂，怎么知道是讲的好呢 ？
数据挖掘 决策树ID3算法原理 -
longay00：
不错，很牛，不过没有原理与实验很难相信它的正确性。从代码上看， ...
决策树C4.5算法 -
yangguo：
用我的study方法就可以了。
答复: java最优算法讨论
package com.leon;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
* @author : Leon
* @since : 2013-8-11
* @see :
*/
public class LL1 {
public String[] grammar_str;
private int token_i;
private String lambda = "lambda";
public boolean[] mark_lambda(Grammar g) {
boolean[] derives_lambda = new boolean[g.vocabulary.length];
boolean changes;
do {
changes = false;
for (int i = 0; i < g.productions.length; i++) {
Production p = g.productions[i];
if (!derives_lambda[index(p.lhs, g.vocabulary)]) {
if (p.rhs.length == 0) {
derives_lambda[index(p.lhs, g.vocabulary)] = true;
changes = true;
continue;
}
boolean rhs_derives_lambda = derives_lambda[index(p.rhs[0], g.vocabulary)];
for (int j = 1; j < p.rhs.length; j++) {
rhs_derives_lambda = rhs_derives_lambda && derives_lambda[index(p.rhs[j], g.vocabulary)];
}
if (rhs_derives_lambda) {
derives_lambda[index(p.lhs, g.vocabulary)] = true;
changes = true;
}
}
}
}
while (changes);
return derives_lambda;
}
public Set<String> compute_first(String[] alpha, Set<String>[] first_set, Grammar g) {
Set<String> result = new HashSet<String>();
int k = alpha.length;
if (k == 0) {
result.add(lambda);
}
else {
result.addAll(first_set[index(alpha[0], g.vocabulary)]);
int i;
for (i = 1; i < alpha.length && first_set[index(alpha[i - 1], g.vocabulary)].contains(lambda); i++) {
result.addAll(first_set[index(alpha[i], g.vocabulary)]);
if (result.contains(lambda)) {
result.remove(lambda);
}
}
if (i == alpha.length && first_set[index(alpha[alpha.length - 1], g.vocabulary)].contains(lambda)) {
result.add(lambda);
}
}
return result;
}
@SuppressWarnings("unchecked")
public Set<String>[] fill_first_set(Grammar g) {
Set<String>[] first_set = new Set[g.vocabulary.length];
for (int i = 0; i < first_set.length; i++) {
if (first_set[i] == null) {
first_set[i] = new HashSet<String>();
}
}
boolean[] derives_lambda = mark_lambda(g);
for (int i = 0; i < g.nonterminals.length; i++) {
String nonterminal = g.nonterminals[i];
if (derives_lambda[index(nonterminal, g.vocabulary)]) {
first_set[index(nonterminal, g.vocabulary)].add(lambda);
}
}
for (int i = 0; i < g.terminals.length; i++) {
String terminal = g.terminals[i];
first_set[index(terminal, g.vocabulary)].add(terminal);
for (int j = 0; j < g.nonterminals.length; j++) {
String nonterminal = g.nonterminals[j];
if (have_derives(nonterminal, terminal, g)) {
first_set[index(nonterminal, g.vocabulary)].add(terminal);
}
}
}
boolean changes;
do {
changes = false;
for (int i = 0; i < g.productions.length; i++) {
Production p = g.productions[i];
int before_size = first_set[index(p.lhs, g.vocabulary)].size();
first_set[index(p.lhs, g.vocabulary)].addAll(compute_first(p.rhs, first_set, g));
int after_size = first_set[index(p.lhs, g.vocabulary)].size();
if (before_size != after_size) {
changes = true;
}
}
}
while (changes);
return first_set;
}
@SuppressWarnings("unchecked")
public Set<String>[] fill_follow_set(Grammar g, Set<String>[] first_set) {
Set<String>[] follow_set = new Set[g.nonterminals.length];
for (int i = 0; i < follow_set.length; i++) {
if (follow_set[i] == null) {
follow_set[i] = new HashSet<String>();
}
}
follow_set[index(g.start_symbol, g.nonterminals)].add(lambda);
boolean changes;
do {
changes = false;
for (int i = 0; i < g.productions.length; i++) {
Production p = g.productions[i];
for (int j = 0; j < p.rhs.length; j++) {
String symbol = p.rhs[j];
if (index(symbol, g.nonterminals) != -1) {
String[] beta = build_beta(j, p.rhs);
Set<String> compute_first = compute_first(beta, first_set, g);
Set<String> set = new HashSet<String>(compute_first);
set.remove(lambda);
int before_size = follow_set[index(symbol, g.nonterminals)].size();
follow_set[index(symbol, g.nonterminals)].addAll(set);
if (compute_first.contains(lambda)) {
follow_set[index(symbol, g.nonterminals)].addAll(follow_set[index(p.lhs, g.nonterminals)]);
}
int after_size = follow_set[index(symbol, g.nonterminals)].size();
if (before_size != after_size) {
changes = true;
}
}
}
}
}
while (changes);
return follow_set;
}
public void predict(Production p, Set<String>[] first_set, Set<String>[] follow_set, Grammar g, int p_index,
int[][] m) {
Set<String> set = new HashSet<String>();
for (int i = 0; i < p.rhs.length; i++) {
if (first_set[index(p.rhs[i], g.vocabulary)].contains(lambda)) {
continue;
}
else {
set.addAll(first_set[index(p.rhs[i], g.vocabulary)]);
break;
}
}
if (set.size() == 0) {
set.addAll(follow_set[index(p.lhs, g.nonterminals)]);
}
for (Iterator<String> iterator = set.iterator(); iterator.hasNext();) {
String symbol = iterator.next();
m[index(symbol, g.terminals)][index(p.lhs, g.nonterminals)] = p_index;
}
}
public void gen_action(String[] symbol, Grammar g) {
if (symbol.length == 0) {
System.out.println("\t\t\t/* null */");
}
else {
for (int i = 0; i < symbol.length; i++) {
if (is_terminal(symbol[i], g)) {
System.out.println("\t\t\tmatch(\"" + symbol[i] + "\");");
}
else {
System.out.println("\t\t\t" + symbol[i] + "();");
}
}
}
}
public void make_parsing_proc(String nonterminal, int[][] m, Grammar g) {
System.out.println("public void " + nonterminal + "(){");
System.out.println("\tString tok = current_token();");
System.out.println("\tswitch(tok){");
for (int j = 0; j < g.terminals.length; j++) {
for (int i = 0; i < g.nonterminals.length; i++) {
if (g.nonterminals[i].equals(nonterminal)) {
if (m[j][i] > 0) {
System.out.println("\t\tcase \"" + g.terminals[j]+"\":");
Production selected_p = g.productions[m[j][i] - 1];
gen_action(selected_p.rhs, g);
System.out.println("\t\t\tbreak;");
}
break;
}
}
}
System.out.println("\t\tdefault:");
System.out.println("\t\t\tsyntax_error(tok);");
System.out.println("\t\t\tbreak;");
System.out.println("\t}");
System.out.println("}");
}
public void ll1_driver(Grammar g, int[][] m) {
Stack<String> stack = new Stack<String>();
stack.push(g.start_symbol);
String a = next_token();
while (!stack.is_empty()) {
System.out.println(stack);
String symbol = stack.pop();
if (is_nonterminal(symbol, g) && m[index(a, g.terminals)][index(symbol, g.nonterminals)] > 0) {
Production p = g.productions[m[index(a, g.terminals)][index(symbol, g.nonterminals)] - 1];
String[] rhs = p.rhs;
for (int i = rhs.length-1; i >= 0; i--) {
stack.push(rhs[i]);
}
}
else if (symbol.equals(a)) {
a = next_token();
}
else {
System.out.println("syntax error");
}
}
}
public String next_token() {
if(token_i<grammar_str.length){
return grammar_str[token_i++];
}
return null;
}
private boolean is_nonterminal(String symbol, Grammar g) {
for (int i = 0; i < g.nonterminals.length; i++) {
if (g.nonterminals[i].equals(symbol)) {
return true;
}
}
return false;
}
private boolean is_terminal(String symbol, Grammar g) {
for (int i = 0; i < g.terminals.length; i++) {
if (g.terminals[i].equals(symbol)) {
return true;
}
}
return false;
}
private boolean have_derives(String nonterminal, String terminal, Grammar g) {
for (int i = 0; i < g.productions.length; i++) {
Production production = g.productions[i];
if (production.lhs.equals(nonterminal) && production.rhs.length > 0 && production.rhs[0].equals(terminal)) {
return true;
}
}
return false;
}
private int index(String symbol, String[] vocabulary) {
for (int i = 0; i < vocabulary.length; i++) {
if (symbol.equals(vocabulary[i])) {
return i;
}
}
return -1;
}
private String[] build_beta(int j, String[] rhs) {
String[] result = new String[rhs.length - (j + 1)];
int k = 0;
for (int i = j + 1; i < rhs.length; i++) {
result[k++] = rhs[i];
}
return result;
}
}
package com.leon;
import java.util.Set;
/** @author : Leon
* @since : 2013-8-11
* @see :
*/
public class Main {
public static void main(String[] args) {
new Main().do_third_gammar();
}
public void do_first_gammar(){
LL1 c= new LL1();
Grammar g = new Grammar();
g.nonterminals = new String[]{"S","B","C"};
g.terminals = new String[]{"a","b","c","d","e"};
g.start_symbol = "S";
g.vocabulary = new String[]{"S","B","C","a","b","c","d","e"};
Production p1 = new Production("S",new String[]{"a","S","e"});
Production p2 = new Production("S",new String[]{"B"});
Production p3 = new Production("B",new String[]{"b","B","e"});
Production p4 = new Production("B",new String[]{"C"});
Production p5 = new Production("C",new String[]{"c","C","e"});
Production p6 = new Production("C",new String[]{"d"});
g.productions = new Production[]{p1,p2,p3,p4,p5,p6};
Set<String>[] first_set = c.fill_first_set(g);
for (int i = 0; i < first_set.length; i++) {
Set<String> set = first_set[i];
System.out.println(set);
}
Set<String>[] follow_set = c.fill_follow_set(g, first_set);
for (int i = 0; i < follow_set.length; i++) {
Set<String> set = follow_set[i];
System.out.println(set);
}
}
public void do_second_gammar(){
LL1 c= new LL1();
Grammar g = new Grammar();
g.nonterminals = new String[]{"S","A","B"};
g.terminals = new String[]{"a","b","c"};
g.start_symbol = "S";
g.vocabulary = new String[]{"S","A","B","a","b","c"};
Production p1 = new Production("S",new String[]{"A","B","c"});
Production p2 = new Production("A",new String[]{"a"});
Production p3 = new Production("A",new String[]{});
Production p4 = new Production("B",new String[]{"b"});
Production p5 = new Production("B",new String[]{});
g.productions = new Production[]{p1,p2,p3,p4,p5};
Set<String>[] first_set = c.fill_first_set(g);
for (int i = 0; i < first_set.length; i++) {
Set<String> set = first_set[i];
System.out.println(set);
}
Set<String>[] follow_set = c.fill_follow_set(g, first_set);
for (int i = 0; i < follow_set.length; i++) {
Set<String> set = follow_set[i];
System.out.println(set);
}
}
public void do_third_gammar(){
LL1 c= new LL1();
Grammar g = new Grammar();
g.nonterminals = new String[]{"program","statement_list","statement","statement_tail","expression","id_list","expr_list","id_tail","expr_tail","primary","primary_tail","add_op","system_goal"};
g.terminals = new String[]{"ID","INTLIT",":=",",",";","+","*","(",")","begin","end","read","write","$"};
g.start_symbol = "system_goal";
g.vocabulary = new String[]{"program","statement_list","statement","statement_tail","expression","id_list","expr_list","id_tail","expr_tail","primary","primary_tail","add_op","system_goal","ID","INTLIT",":=",",",";","+","*","(",")","begin","end","read","write","$"};
Production p1 = new Production("program",new String[]{"begin","statement_list","end"});
Production p2 = new Production("statement_list",new String[]{"statement","statement_tail"});
Production p3 = new Production("statement_tail",new String[]{"statement","statement_tail"});
Production p4 = new Production("statement_tail",new String[]{});
Production p5 = new Production("statement",new String[]{"ID",":=","expression",";"});
Production p6 = new Production("statement",new String[]{"read","(","id_list",")",";"});
Production p7 = new Production("statement",new String[]{"write","(","expr_list",")",";"});
Production p8 = new Production("id_list",new String[]{"ID","id_tail"});
Production p9 = new Production("id_tail",new String[]{",","ID","id_tail"});
Production p10 = new Production("id_tail",new String[]{});
Production p11 = new Production("expr_list",new String[]{"expression","expr_tail"});
Production p12 = new Production("expr_tail",new String[]{",","expression","expr_tail"});
Production p13 = new Production("expr_tail",new String[]{});
Production p14 = new Production("expression",new String[]{"primary","primary_tail"});
Production p15 = new Production("primary_tail",new String[]{"add_op","primary","primary_tail"});
Production p16 = new Production("primary_tail",new String[]{});
Production p17 = new Production("primary",new String[]{"(","expression",")"});
Production p18 = new Production("primary",new String[]{"ID"});
Production p19 = new Production("primary",new String[]{"INTLIT"});
Production p20 = new Production("add_op",new String[]{"+"});
Production p21 = new Production("add_op",new String[]{"*"});
Production p22 = new Production("system_goal",new String[]{"program","$"});
g.productions = new Production[]{p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22};
Set<String>[] first_set = c.fill_first_set(g);
for (int i = 0; i < first_set.length; i++) {
Set<String> set = first_set[i];
System.out.println(set);
}
System.out.println("===============================");
Set<String>[] follow_set = c.fill_follow_set(g, first_set);
for (int i = 0; i < follow_set.length; i++) {
Set<String> set = follow_set[i];
System.out.println(set);
}
System.out.println("===============================");
System.out.println(g.terminals.length);
System.out.println(g.nonterminals.length);
System.out.println("===============================");
int[][] m = new int[g.terminals.length][g.nonterminals.length];
for (int i = 0; i < g.productions.length; i++) {
c.predict(g.productions[i], first_set, follow_set, g, i+1, m);
}
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[i].length; j++) {
System.out.print(m[i][j]+",");
}
System.out.println();
}
for (int i = 0; i < g.nonterminals.length; i++) {
c.make_parsing_proc(g.nonterminals[i], m, g);
}
c.grammar_str = "begin ID := ID * INTLIT + ID ; end $".split(" ");
for (int i = 0; i < c.grammar_str.length; i++) {
System.out.println(c.grammar_str[i]);
}
c.ll1_driver(g, m);
}
}
- src.7z (4 KB)
- 下载次数: 11
分享到：
发表评论
-
庞果英雄会 覆盖数字
2013-11-14 15:13 811庞果覆盖数字原题如下 给定整数区间[a,b]和整数区间[x, ... -
2-3 tree
2013-10-09 17:10 696package com.leon.cc; imp ... -
应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串问题
2011-11-30 16:35 1464/** * @see IOI2009国家集训队论文《后 ... -
谷哥的KOF连招问题
2010-10-09 14:38 1457传说问题是这样的 玩过KOF（拳皇）的人都知道，玩的时候会连招 ... -
KOF
2010-10-09 00:13 0package org.struct.trietree; ... -
ACM/ICPC HDU 1195
2010-09-06 10:37 1849本年度还有8篇博客需要完成 开篇前附加一个看完《盗梦空间》的我 ... -
答复: 阿里巴巴面试感言
2009-10-09 22:27 2136好吧，我承认我闲的蛋疼 问题：3000万条的记录取最大的前50 ... -
正向最大匹配改进算法
2009-05-26 22:11 5799AD.： 2年J2EE经验，熟悉常用数据结构算法，熟悉常 ... -
决策树C4.5算法
2009-05-19 02:05 5205数据挖掘中决策树C4.5预测算法实现(半成品，还要写规则后 ... -
区间树
2008-07-18 15:47 2132package acmcode; /** * ... -
红黑树初版
2008-07-16 17:20 1517package acmcode; /** * R ... -
四则运算的中缀转后缀，逆波兰表达式求值
2008-04-23 23:10 8993首先描述问题 给定一 ... -
最大0，1子矩阵
2008-04-20 21:16 5971首先描述一下问题 /** * * 时间限制(普 ... -
数据挖掘 决策树ID3算法原理
2008-04-11 22:24 11338上一篇博客写了ID3算法的简单实现 这一篇讲讲ID3的原理 写 ... -
决策树ID3算法
2008-04-01 22:18 7540算了,还是自己修正一个BUG.... package gr ... -
ext2.0 的XMLWriter
2008-02-20 21:04 1239做ext相关的一个example项目,把我们的客户端移植成ex ... -
树与哈夫曼树
2008-02-20 20:50 1537package tree; public ... -
LCS与图算法
2008-02-20 20:46 1188求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个 ... -
《程序员》算法擂台：骑士聚会
2008-02-20 20:40 1168在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士 ...
相关推荐
自己实现的编译原理的LL1语法分析器，是自己的实验作业，用Vs2017实现，可以直接运行，代码注释丰富，希望与大家交流学习！欢迎大家下载！
可适用任何文法 可输出匹配过程 有错误处理不会影响执行 文法有使用者输入 很好啊 莫要错过 经vc6.0编译执行通过100%可用
编译原理 从词法分析器到语法分析器的实现，词法分析器以有穷状态机实现，而语法分析器主要使用LL1算法实现，中间使用了大量的图论算法。
编译原理课程实验-LL(1) 语法分析实验： 实验目的：1.了解 LL(1)语法分析是如何根据语法规则逐一分析词法分析所得到的单词，检查语法错误，即掌握语法分析过程；2.掌握LL(1)文法判别调剂和 LL(1)语法分析器的设计与...
编译原理 LL1语法分析 湖南大学
编译原理课设 LL1语法分析器，注释掉的一部分代码是可以扩展的部分
语言为C++，使用了set，map容器，输入格式：S -> Aa | g | e，支持多‘|’ 符号，采用文件输入
编译原理-LL1文法分析-java
自己实现的编译原理的LL1语法分析器，是自己的实验作业，用Vs2017实现，可以直接运行
编译原理 LL1算法LL1算法编译原理 LL1算法LL1算法编译原理 LL1算法LL1算法编译原理 LL1算法LL1算法
安徽大学 LL1 语法分析 first follow select 规约 预测分析表 清华大学 编译原理
编译原理-LL1文法分析-java
使用MFC实现编译原理LL1语法分析器（含消除左递归）使用MFC实现编译原理LL1语法分析器（含消除左递归）
编译原理LL1分析法编译原理LL1分析法编译原理LL1分析法编译原理LL1分析法
编译原理C语言LL1语法分析器的简单实现.zip
大学编译原理实验用，LL1文法（C++编写）。不错的资源
编译 语法分析 LL(1) 编译 语法分析 LL(1) 编译 语法分析 LL(1) 编译 语法分析 LL(1)
LL1文法识别 词法分析程序 编译原理程序 花了几天时间用C++编写的程序。 简单的词法设计——DFA模拟程序 语法设计——基于LL(1)文法的预测分析表法
自定义一个文法集，输入文法产生式，计算文法的FIRST，FOLLOW和SELECT集合， 利用SELECT集合构造预测分析表，接着用预测分析程序，栈 和预测分析表对输入串进行分析，给出分析过程。