编译原理:LL(1)文法的判断,递归下降分析程序

时间:2022-02-01 01:42:11

1. 文法 G(S):

(1)S -> AB

(2)A ->Da|ε

(3)B -> cC

(4)C -> aADC |ε

(5)D -> b|ε

验证文法 G(S)是不是 LL(1)文法?

FIRST(Da)={b,a}

  FIRST(ε)={ε}

  FIRST(aADC)={a}

  FIRST(b)={b}

  FOLLOW(A)={c,b,a,#}

  FOLLOW(C)={#,}

  FOLLOW(D)={a,#}

  SELECT(A->Da)=FIRST(Da)={b,a}

  SELECT(A->ε)=FIRST(ε)-{ε}UFOLLOW(A)=FOLLOW(A)={c,b,a,#}

  ∵ SELECT(A->Da) ∩ SELECT(A->ε) ≠ Ø

  ∴ G(S)不是 LL()文法。

2.(上次作业)消除左递归之后的表达式文法是否是LL(1)文法?


解析:

  表达式文法为:

  (1)E->TE'

  (2)E'->+TE' | ε

  (3)T->FT'

  (4)T'->*FT' | ε

  (5)F->(E) | i

 

 FIRST(+TE')={+}

  FIRST(ε)={ε}

  FIRST(*FT')={*}

  FIRST((E))={ ( }

  FIRST(i)={i}

  FOLLOW(E')={ ),# }

  FOLLOW(T')={+,),#}

  FOLLOW(F)={*,+,),#}

  SELECT(E'->+TE')=FIRST(+TE')={+}

  SELECT(E'->ε)=FIRST(ε)-{ε}UFOLLOW(E')=FOLLOW(E')={ ),# }

  SELECT(T'->*FT')=FIRST(*FT')={*}

  SELECT(T'->ε)=FIRST(ε)-{ε}UFOLLOW(T')=FOLLOW(T')={ +,),# }

  SELECT(F->(E))=FIRST((E))={ ( }

  SELECT(F->i)=FIRST(i)={i}

  ∵    SELECT(E'->+TE') ∩ SELECT(E'->ε) = Ø

    SELECT(T'->*FT') ∩ SELECT(T'->ε) = Ø

    SELECT(F->(E)) ∩ SELECT(F->i) = Ø

  所以此表达式文法是LL()文法。

3.接2,如果是LL(1)文法,写出它的递归下降语法分析程序代码。


E()

{T();

E'();

}

E'()

T()

T'()

F()

 解析:

 SELECT集:

  SELECT(E->TE')=FIRST(TE')={ (, i }

  SELECT(E'->+TE')=FIRST(+TE')={+}

  SELECT(E'->ε)=FIRST(ε)-{ε}UFOLLOW(E')=FOLLOW(E')={ ),# }

  SELECT(T->FT')=FIRST(FT')={ (,i }

  SELECT(T'->*FT')=FIRST(*FT')={*}

  SELECT(T'->ε)=FIRST(ε)-{ε}UFOLLOW(T')=FOLLOW(T')={ +,),# }

  SELECT(F->(E))=FIRST((E))={ ( }

  SELECT(F->i)=FIRST(i)={i}

  递归下降语法分析程序:

  void ParseE(){

    switch(lookahead){

      case '(','i':

        ParseT();

        ParseE'();

        break;

      default:

        print("syntax error \n");

        exit();

    }

  }

  void ParseE'(){

    switch(lookahead){

      case '+':

        MatchToken('+');

        ParseT();

        ParseE'();

        break;

      case ')','#':

        break;

      default:

        print("syntax error \n");

        exit();

    }

  }

  void ParseT(){ 

    switch(lookahead){

      case '(','i':

        ParseF();

        ParseT'();

        break;

      default:

        print("syntax error \n");

        exit();

    }

  }

  void ParseT'(){

    switch(lookahead){

      case '*':

        MatchToken('*');

        ParseF();

        ParseT'();

        break;

      case '+',')','#':

        break;

      default:

        print("syntax error \n");

        exit();

    }

  }

  void ParseF(){

    switch(lookahead){

      case '(':

        MatchToken('(');

        ParseE();

        MatchToken(')');

        break;

      case 'i':

        MatchToken('i');

        break;

      default:

        print("syntax error \n");

        exit();

    }

4.加上实验一的词法分析程序,形成可运行的语法分析程序,分析任意输入的符号串是不是合法的表达式。

编译原理:LL(1)文法的判断,递归下降分析程序的更多相关文章

  1. 作业十一——LL(1)文法的判断,递归下降分析程序

    作业十一——LL(1)文法的判断,递归下降分析程序 判断是否为LL(1)文法 选取有多个产生式的求select,只有一条产生式的无需求select 同一个非终结符之间求交集,全部判断为空后则为LL(1 ...

  2. 编译原理 #02# 简易递归下降分析程序(js实现)

    // 实验存档 截图: 代码: <!DOCTYPE html> <html> <head> <meta charset="UTF-8"&g ...

  3. 编译原理之LL&lpar;1&rpar;文法的判断,递归下降分析程序

    1. 文法 G(S): (1)S -> AB (2)A ->Da|ε (3)B -> cC (4)C -> aADC |ε (5)D -> b|ε 验证文法 G(S)是不 ...

  4. 十一次作业——LL&lpar;1&rpar;文法的判断,递归下降分析程序

    1. 文法 G(S): (1)S -> AB (2)A ->Da|ε (3)B -> cC (4)C -> aADC |ε (5)D -> b|ε 验证文法 G(S)是不 ...

  5. LL&lpar;1&rpar;文法的判断,递归下降分析程序

    1. 文法 G(S): (1)S -> AB (2)A ->Da | ε (3)B -> cC (4)C -> aADC | ε (5)D -> b | ε 验证文法 G ...

  6. 第十一次作业 LL&lpar;1&rpar;文法的判断,递归下降分析程序

    1. 文法 G(S): (1)S -> AB (2)A ->Da|ε (3)B -> cC (4)C -> aADC |ε (5)D -> b|ε 验证文法 G(S)是不 ...

  7. 第十一次 LL&lpar;1&rpar;文法的判断,递归下降分析程序

    1. 文法 G(S): (1)S -> AB (2)A ->Da|ε (3)B -> cC (4)C -> aADC |ε (5)D -> b|ε 验证文法 G(S)是不 ...

  8. 编译原理-递归下降分析法 c程序部分的分析

    实验三 语法分析程序实验 专业 商软2班   姓名 黄仲浩  学号 201506110166 一. 实验目的      编制一个部分文法分析程序. 二. 实验内容和要求 输入:源程序字符串 输出:正确 ...

  9. 【编译原理】LL1文法语法分析器

    上篇文章[编译原理]语法分析--自上向下分析 分析了LL1语法,文章最后说给出栗子,现在补上去. 说明: 这个语法分析器是利用LL1分析方法实现的. 预测分析表和终结符以及非终结符都是针对一个特定文法 ...

随机推荐

  1. iOS----------使用 Xcode6或Xcode7配置&period;pch文件

    刚上手 Xcode6/Xcode7 的人,总会发现之前在 6 之前常常会在“利用名-Prefix.pch”这个文件中来配置我们全局要用到的头文件,但是 xcode6 没有了,人家说,这类东西有时候也会 ...

  2. 解析Visual Studio 2015促进生产力的10个新功能

    1 性能提示 Performance Tips 当我们想知道执行一段代码所耗费的时间时,需要借助于.NET 框架的Stopwatch类,像下面这样: class Program { static vo ...

  3. Android 环境配置

    一.开发环境配置 1.使用 eclipse 需要下载安装 Android SDK.Eclipse.ADT 插件. 也可以直接下载整合好的 ADT Bundle 包,下载地址: http://devel ...

  4. 无废话ExtJs 入门教程五&lbrack;文本框:TextField&rsqb;

    无废话ExtJs 入门教程五[文本框:TextField] extjs技术交流,欢迎加群(201926085) 继上一节内容,我们在表单里加了个两个文本框.如下所示代码区的第42行位置,items: ...

  5. bzoj3261&colon; 最大异或和

    可持久化trie.又是%%%Xs酱... #include<cstdio> #include<cstring> #include<iostream> #includ ...

  6. Currency 货币 filter

    angularjs 其实也有一个currency指令,不过好像只是换符号而已. 这里自己写了一个简单的兑换率filter <div ng-controller="ctrl"& ...

  7. curl&plus;个人证书(又叫客户端证书)访问https站点

    摘自http://blog.csdn.net/chary8088/article/details/22990741 curl+个人证书(又叫客户端证书)访问https站点 目前,大公司的OA管理系统( ...

  8. socket(套接字)

    客户端: 创建套接字(socket) 连接服务器(connect) 通信(send,recv或者write,read) 关闭套接字(closesocket) 示例代码: int main(int ar ...

  9. leetcode First Bad Version(二分查找)

    You are a product manager and currently leading a team to develop a new product. Unfortunately, the ...

  10. 安装Nginx到linux服务器(Ubuntu)详解

    先去下载一个nginx放到服务器. 然后解压(可参考前面安装tomcat)编译(./configure --prefix=/usr/local/nginx/server/ && mak ...