为了实现自顶向下的语法分析器,需要将文法的
1.左递归消除
(完成)
2.提取公因子
(完成)
3.计算first,follow集合(完成)
4.得到LL(1)预测分析表 (100322完成)
如下面的文法:
E = E + T | T
F = ( E ) | id
T = T * F | F
javascript描述的文法规则为:
[
[{tag: "E"},{tag: "E"},{tag: "+",end: "true"/*终结符*/},{tag: "T"}],//E->E+T
[{tag: "E"},{tag: "T"}],//E->T
[{tag: "T"},{tag: "T"},{tag: "*",end: "true"},{tag: "F"}],//T->R*F
[{tag: "T"},{tag: "F"}],//T->F
[{tag: "F"},{tag: "(",end: "true"},{tag: "E"},{tag: ")",end: "true"}],//F->(E)
[{tag: "F"},{tag: "id",end: "true"}]//F->id
]
tag用来表示符号,无论终结或者非终结,end表示符号为终结符号,用数组来表示一条文法规则,表示从数组第一个元素可以推导出数组第二个元素到最后连接的符号串。
需要消除左递归变化为(x表示空):
E = T E'
E' = x | + T E'
F = ( E ) | id
T = F T'
T' = x | * F T'
演示@google code
代码结构:
Ext.ux.compiler.Grammar = function (g, startG) {
//| 拆分
//e->s|t
//拆分为两条
//e->s
//e->t
};
Ext.override(Ext.ux.compiler.Grammar, {
//消除左递归并提取公因子
leftRecurEliminate: function () {
/*
去除公共前缀
*/
},
//得到符号ex的first集合
_first: function (ex) {},
//得到符号ex的follow集合
_follow: function (ex) {},
//得到符号ex后紧跟的符号,可以为文法结尾符号$
getFollowSymbols: function (ex) {},
//得到一组文法的公共前缀
getCommonPrefix: function (gs) {},
//字符串序列化显示
serialize: function () {}
});
分享到:
相关推荐
select集合的算法即为书上所介绍的方法,即求first的集合时,只看本产生式,求follow集合时,要进行递归查找一个非终结符的所有后跟字符,求select其实就是对first与follow集合的运算,最终根据所有的select集合,便...
用C语言实现编译原理中LL1文法分析算法
根据判断一个文法是LL(1)文法的三个条件,逐一实现其判别条件的算法实现。 满足是LL(1)文法的三个条件: (1)文法不含有左递归 (2)对于文法中每一个非终结符A,若它存在某个候选首符 集两两不相交,即,若A→α1|α2|...
编译原理课程设计的LL1文法的算法实现,大家可以参考下!
(1)对输入文法,它能判断是否为LL(1)文法,若是,则转(2);否则报错并终止; (2)输入已知文法,由程序自动生成它的LL(1)分析表; (3)对于给定的输入串,应能判断识别该串是否为给定文法的句型。 2.分析 ...
用C++实现LL(1)文法,程序虽然简单,但是很好的体现了编译原理中算法的精髓
该程序能求出任意给定的文法的所有非终极符和终极符的first集,所有非终极符的follow集,所有语句的select集,能求出能导空的非终极符集合。给定任意字符串该程序能判定出是否能接受
LL(1)文法判定算法,LL(1)文法使用的是确定的自顶向下的分析技术。LL(1)的含义是:第一个L表明自顶向下分析是从左向右扫描输入串,第2个L表明分析过程中将使用最左推导,1表明只需向右看一个符号便可决定如何推导,...
设计内容及要求:对于任意输入的一个LL(1)文法,构造其预测分析表。要求:首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法,再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件...
本程序主要由两大部分组成,分析部分和求值部分。即对表达式进行语法分析,在语法分析成功的情况下,再对表达式求值,语法分析出错时给出相应的错误信息。
1. 给定无左递归和无回溯的文法,计算FIRST集合和FOLLOW集合,并构造出预测分析表。 文法如下:(在这里用e来表示空串ε) E->TA A->+TA A->e T->FB ...2. 根据预测分析表,判断该文法是否为LL(1)文法。
预测分析算法的设计与实现(左递归消除和LL1文法)(是基于字符数组实现,没使用C++容器)
非递归形式的LL(1)文法模拟,用vc2008编写,无错。输入字符串判断文法
语法分析程序可以根据个人的掌握情况选用常见的几种语法分析方法:递归下降分析方法、LL(1)预测分析法、算符优先分析、LR分析等方法中的任何一种来实现,也可以选用不同的方法来分析不同的语法成分,最后再综合起来...
通过课程设计进一步理解高级语言在计算机中的执行过程,加深对编译原理中重点算法和编译技术的理解,提高自己的编程能力,培养好的程序设计风格。...根据给出的LL(1)文法,掌握LL(1)分析表的构造及分析过程的实现。
LL(1)分析法,就是指从左到右扫描输入串(源程序),同时采用最左推导,且对每次直接推导只需向前看一个输入符号,便可确定当前所应当选择的规则。实现LL(1)分析的程序又称为LL(1)分析程序或LL(1)分析器。
编译原理LL1文法的mfc实现,其中包括对LL1文法的First集合的算法,Follow集合的算法 select集合的算法 还包括消除左递归 提取左因子
构造LL(1)语法分析程序,任意输入一个文法符号串,并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表,并按照预测分析算法对输入串进行语法分析,判别程序是否符合已知的语法规则,如果不符合(编译...
需要创建一个名字叫project.txt的文件来存储要识别的文法
LL1算法:程序中根据产生式求得FIRST集合,程序里面已经有详细提示信息,所以不作太多介绍