`
yiminghe
  • 浏览: 1461839 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

LL文法算法-1

阅读更多

为了实现自顶向下的语法分析器,需要将文法的

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 () {}
});
 

 

 

 

分享到:
评论

相关推荐

    编译原理-LL1文法分析--java

    1. **文法定义**:首先,需要将目标语言的文法以形式化的BNF(巴科斯范式)或者EBNF(扩展巴科斯范式)表示出来。 2. **构造First集和FOLLOW集**:利用文法定义,计算出每个非终结符的First集和FOLLOW集。 3. **...

    编译原理实验判断文法是不是LL1文法

    在编译原理中,LL1文法是一种重要的形式文法,它对于...总的来说,通过这个实验,你可以深入理解LL1文法的性质,以及如何通过算法判断一个文法是否满足LL1特性。这将有助于你在编译器设计和实现方面建立坚实的基础。

    编译原理之LL1文法 (C++)

    3. **计算First集和Follow集**:为文法中的每一个非终结符计算First集和Follow集,这通常是通过递归算法实现的。 4. **生成LL1解析表**:根据First集和Follow集构建解析表,每个条目指示了在当前状态下遇到特定符号...

    LL1文法

    1. **LL1文法的特征** - **从左到右扫描**:解析器从输入字符串的左边开始,逐个读取输入符号。 - **左most推导**:解析过程中,总是选择产生式中最左边的非终结符进行替换。 - **First集合**:对于每个非终结符...

    编译原理词法分析和LL1文法判定

    在实验中,我们可以使用LL1文法判定算法来判断一个文法是否为LL1文法,并可以使用这个算法来生成一个LL1文法的解析器。这个算法可以用于提高编译器的性能和效率。 本实验的目的是设计和实现一个词法分析器,并使用...

    LL1文法分析实验报告

    LL(1)文法分析是一种编译原理中的技术,用于...这个实验旨在让学习者熟悉编译原理中的LL(1)文法分析,理解其核心概念并能实现相关算法。通过实验,学生可以更好地理解编译器如何解析程序代码,并提高他们的编程能力。

    编译教程ll1文法-编译

    LL(1)分析是一种特殊的自顶向下预测分析方法,适用于一类特殊的文法——LL(1)文法。这类文法的特点是可以使用固定的向前查看(lookahead)策略来唯一地确定下一步的推导动作。LL(1)分析器能够有效地处理这类文法,...

    编译原理课程设计之LL1文法实现

    在你所给的压缩包文件“LL1”中,可能包含了实现LL1文法算法的代码示例或者相关的指导文档。通过阅读和理解这些材料,你可以更深入地学习和实践LL1文法的实现。这个过程不仅可以帮助你掌握编译原理的基础,还可以...

    ll1文法分析,很强大 mfc

    LL(1)文法分析是编译原理中的一个重要概念,它是自左至右扫描输入串,并且在每个时刻最多查看一个输入符号(1个Lookahead)来决定如何进行语法分析的算法。MFC,全称Microsoft Foundation Classes,是微软提供的一套...

    编译原理实验八:非LL(1)文法到LL(1)文法的转换

    实验中的8.cpp文件可能是实现这些转化算法的源代码,而编译原理实验八:非LL(1)文法到LL(1)文法的转换.doc文件则包含了实验报告,可能详细介绍了实验的目的、方法、步骤以及实验结果。实验报告通常会包括以下部分: ...

    用Java编写的LL(1)文法判别

    根据提供的文件信息,本文将详细解释“用Java编写的LL(1)文法判别”的核心概念、原理以及实现步骤。 ### LL(1) 文法简介 LL(1)是一种自上而下的语法分析方法,其中第一个L表示从左到右扫描输入串,第二个L表示最...

    LL(1)文法自动生成语法分析程序的设计

    在LL(1)文法自动生成语法分析程序的设计中,算法思想是首先输入LL(1)文法,接着计算First集和Follow集,然后构造分析表M,最后使用分析表M对输入串进行语法分析。该设计可以自动构造LL(1)分析表,并生成相应的语法...

    编译原理实验四LL(1)文法【C语言实现】

    编译原理实验四 LL(1)文法 C 语言实现 本实验报告的主要目的是通过实现 LL(1)分析法来加深对预测分析的理解。 LL(1)分析法是一种常用的语法分析方法,它可以对输入的符号串进行自上而下的分析。 实验报告的...

    ll1文法和First集合follow集合

    这种文法的特点是允许使用一个简单的左到右的扫描方式,并且只需要查看当前符号及其前面的一个符号(即“Lookahead”1)就能决定如何进行解析。在LL1分析中,First集合和Follow集合扮演了关键角色。 First集合是...

    java开发的基于LL1文法的语法分析器

    1. **文法定义**:首先,需要定义语言的语法规则,这通常以BNF(巴科斯范式)或EBNF(扩展巴科斯范式)的形式完成。LL1文法要求所有产生式的左部都是非终结符,并且对于每个非终结符和输入符号的组合,只能有一个...

    LL1文法识别 词法分析程序 编译原理程序

    而"语法分析器"文件则可能包含实现LL1解析算法的代码,它会根据预测分析表进行解析操作,逐步构建抽象语法树(Abstract Syntax Tree, AST),AST是对源代码结构的抽象表示。 在实际编程中,实现词法分析和LL1语法...

    LL(1)文法判定器

    根据判断一个文法是LL(1)文法的三个条件,逐一实现其判别条件的算法实现。 满足是LL(1)文法的三个条件: (1)文法不含有左递归 (2)对于文法中每一个非终结符A,若它存在某个候选首符 集两两不相交,即,若A→α1|α2|...

    编译原理C++实现判断LL(1)文法

    analyseTable[i][j] = -1; } } // 生成分析表 // ... } 五、总结 本文档介绍了编译原理中LL(1)文法的判断实现,包括First集、Follow集的计算和句型分析的实现。该实现使用了递归下降分析方法来计算First集和...

    LL1文法判断C++自己的课程设计

    LL1文法是一种自左向右扫描(Left-to-Right)的文法,其中“L”代表左至右扫描,“1”表示只看一个输入符号(First Lookahead)。在LL1解析器中,我们首先构造一个文法的FIRST集和FOLLOW集,它们是文法符号集合的...

    LL.rar_LL1 first_LL1 文法 实验 报告_ll1_ll1 first follow_ll1 文法

    在"LL.cpp"这个文件中,可能包含了实现LL1解析算法的C++代码。这种代码通常会涉及到构造和操作FIRST集、FOLLOW集,以及生成解析表的逻辑。"www.pudn.com.txt"可能是一个文档,提供了实验的详细步骤、文法示例或者...

Global site tag (gtag.js) - Google Analytics